Eviction Under Memory Pressure
Demand paging allows the aggregate virtual memory of running processes to exceed physical RAM. As long as the active working set of pages fits in physical memory, execution proceeds at native RAM speed.
When a page fault occurs and every physical frame is already occupied, the kernel must evict an existing page to make room (writing it to swap first if its PTE dirty bit is set). Evicting the wrong page is catastrophic: if the chosen victim belongs to an active loop, the CPU will fault on it again microseconds later—triggering thrashing, where the system spends nearly $100%$ of its time waiting on disk I/O.
The theoretical lower bound on page faults is Bélády’s Optimal Policy (OPT / MIN): evict the page whose next reference lies furthest in the future. Because an operating system kernel cannot see future instructions, real systems approximate OPT using historical access patterns. Let’s analyze the three classic eviction policies—FIFO, LRU, and Clock (Second Chance)—and benchmark them in C on a famous pathological workload.
1. First-In-First-Out (FIFO) and Bélády’s Anomaly
The simplest policy tracks resident pages in a circular queue ordered strictly by arrival time, evicting whichever page has been in RAM the longest.
While FIFO requires zero hardware support from the MMU ($O(1)$ enqueue/dequeue only on page faults), it suffers from two fatal flaws:
- Blindness to Hot Pages: A page containing frequently executed code or core global state loaded at startup is the oldest page in memory; FIFO evicts it repeatedly regardless of how heavily it is used.
- Bélády’s Anomaly: Intuitively, giving a computer more physical RAM should never increase the number of page faults. Yet in 1969, László Bélády proved that for FIFO, certain reference strings (such as
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5) suffer more page faults with 4 physical frames (10 faults) than with 3 frames (9 faults).
2. Least Recently Used (LRU)
To exploit temporal locality—the observation that pages accessed in the recent past are likely to be accessed again in the near future—Least Recently Used (LRU) evicts the resident page whose most recent access timestamp is oldest.
Crucially, LRU satisfies the stack inclusion property: at any point in a reference trace, the set of pages resident in a $k$-frame LRU cache is always a strict subset of the pages resident in a $(k+1)$-frame LRU cache. Consequently, LRU is mathematically immune to Bélády’s Anomaly.
Why Operating System Kernels Cannot Use Exact LRU
If exact LRU is so well-behaved, why don’t Linux, macOS, or Windows use it directly on hardware page tables?
Because the kernel is not invoked on TLB hits! A CPU executes billions of load and store instructions per second entirely in hardware. Maintaining an exact LRU ordering would require the hardware MMU to update a 64-bit timestamp or manipulate a doubly-linked list in RAM on every single memory instruction.
Instead, hardware MMUs provide only a single 1-bit flag in each Page Table Entry: the accessed (or reference) bit, which the CPU hardware sets to 1 whenever a page is read or written.
3. The Clock (Second-Chance) Algorithm
The Clock algorithm (attributed to Fernando Corbató) bridges the gap between FIFO and LRU using only that 1-bit hardware referenced flag.
Physical frames are arranged logically around a circular dial with a sweeping pointer called the hand. Whenever a page is accessed, the MMU sets referenced = 1. When a page fault requires an eviction, the kernel sweeps hand clockwise:
- If
referenced == 1: The page was used recently. The kernel grants it a second chance by clearingreferenced = 0, advancinghandto the next frame, and continuing the sweep. - If
referenced == 0: The page has not been accessed since the last time the clock hand swept past it. The kernel selects this frame as the victim, replaces its resident page, setsreferenced = 1, and advanceshand.
(In the worst case where every frame has referenced == 1, the hand sweeps full circle, clearing all bits to 0, and evicts the starting frame—degrading gracefully to FIFO).
Implementing and Benchmarking All Three Policies in C
Let’s write a clean, unified C benchmark that implements FIFO, Exact LRU, and Clock, and runs all three against Bélády’s classic 12-access reference string for both 3 and 4 physical frames:
| |
Benchmark Output and Architectural Summary
Compiling and running the simulation produces:
| |
Notice how adding a 4th frame reduces Exact LRU faults from 10 down to 8, whereas FIFO and single-hand Clock exhibit Bélády’s anomaly (9 $\to$ 10 on this specific adversarial sequence).
In production kernels such as Linux, the page reclaimer refines the Clock concept into a Two-Handed / Two-List LRU (active and inactive lists, or Multi-Generational LRU MGLRU), combining the hardware accessed and dirty bits to protect frequently used working-set pages from one-off sequential scans while keeping memory-access overhead near zero.