Page Replacement Policies: FIFO, LRU, Clock and Optimal

Why memory needs an eviction policy

Virtual memory lets a process address more memory than physically exists by keeping only the working set of frequently used pages in RAM and the rest on disk. When a process references a page that isn't resident, a page fault occurs, and if every frame is already full, the operating system must evict one to make room. Which page it evicts is the entire question — evict the wrong one and the program immediately faults again to bring it back, wasting a disk access that can be five orders of magnitude slower than a memory access.

FIFO and Bélády's anomaly

The simplest policy, FIFO, evicts whichever page has been resident the longest, regardless of whether it was just used a moment ago. It is cheap — just a queue — but ignores locality of reference entirely, and it has a famous pathology: Bélády's anomaly, discovered by László Bélády in 1969, where adding more physical frames can increase the number of page faults for the same reference string under FIFO. Optimal, LRU and several other policies belong to a class called stack algorithms that provably cannot exhibit this anomaly — the set of pages resident with k frames is always a subset of the set resident with k+1 frames — but FIFO is not a stack algorithm, so more memory can, counterintuitively, make it slower.

reference string: 1 2 3 4 1 2 5 1 2 3 4 5
FIFO, 3 frames  -> 9 faults
FIFO, 4 frames  -> 10 faults   (Bélády's anomaly: more RAM, more faults)

LRU: the practical standard

Least Recently Used (LRU) evicts the page that hasn't been touched for the longest time, on the assumption that recent access predicts near-future access — the principle of locality that almost all real workloads exhibit. LRU is a stack algorithm, so it never suffers Bélády's anomaly, and empirically it tracks the optimal policy closely for typical programs. Its problem is cost: exact LRU needs a timestamp or ordered list updated on every memory reference, which is far too expensive to do in hardware or software at full memory-access speed.

The Clock algorithm approximates LRU cheaply

Nearly every production kernel instead uses the Clock algorithm (also called second-chance): each page frame carries one hardware-maintained reference bit, set to 1 whenever the page is accessed. A hand sweeps circularly over the frames; on a fault it inspects the frame under the hand — if the reference bit is 1, it clears the bit and gives the page a second chance, advancing to the next frame; if the bit is already 0, that page is evicted. This costs one bit per frame and O(1) amortised work per fault, and its behaviour approximates LRU well enough that the difference in fault rate is usually small.

// Clock / second-chance
while (true) {
  const p = frames[hand];
  if (p.referenceBit === 0) { evict(p); frames[hand] = newPage; break; }
  p.referenceBit = 0;              // give it a second chance
  hand = (hand + 1) % frames.length;
}

Belady's Optimal (MIN) as the unreachable benchmark

Bélády's optimal algorithm (MIN) evicts whichever resident page will be referenced furthest in the future — or never again. It provably minimises the number of page faults for any reference string, which makes it the yardstick every real policy is measured against. It is not implementable online because it requires knowledge of future references, but it is easy to compute offline for a known trace, and its fault count is the number every practical algorithm tries to approach.

Thrashing

When the sum of processes' working sets exceeds physical memory, the system enters thrashing: pages are evicted and immediately refaulted in a cycle, CPU utilisation collapses because processes spend nearly all their time waiting on disk, and adding more processes makes it dramatically worse rather than better. The fix is not a smarter replacement policy but admission control — the working-set model or page-fault-frequency monitoring that suspends processes until enough memory is free for the remaining set to run without constant faulting.

Frequently asked questions

Try it live

Everything above runs in your browser — open Page Replacement and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.