Page Replacement

When every frame is full and a new page faults in, a replacement policy picks the victim — fewer page faults wins. FIFO can even worsen with more frames (Belady's anomaly).

9 min read Watch it move Build it

When a program references a page that isn't in memory and every frame is already full, the OS must evict something to make room. The page-replacement policy chooses the victim. The whole goal is to minimize page faults — every fault means a slow trip to disk.

The three classic policies

1FIFO — evict the page that was loaded earliest, no matter how heavily it's still used.
2LRU (Least Recently Used) — evict the page unused for the longest, betting the recent past predicts the near future.
3Optimal — evict the page that won't be needed for the longest time. It must see the future, so it's an unbeatable *benchmark*, not a runnable policy.

Clock approximates LRU cheaply

True LRU needs to track recency on every access. Clock (second chance) approximates it with one reference bit per frame: a hand sweeps the frames, and any page whose bit is set gets cleared and spared once before it can be evicted.

Worked example — Belady's anomaly

Intuitively, more frames should mean fewer faults. For FIFO that isn't always true. Take the reference string 1 2 3 4 1 2 5 1 2 3 4 5 and run FIFO:

Reference: 1 2 3 4 1 2 5 1 2 3 4 5

FIFO with 3 frames -> 9 page faults
FIFO with 4 frames -> 10 page faults   (more frames, MORE faults)

Belady's anomaly

Giving FIFO more memory produced more faults — 9 with three frames, 10 with four. This is Belady's anomaly. It can happen because FIFO ignores usage. LRU and Optimal are *stack algorithms* and provably never suffer it: their resident pages with N frames are always a superset of those with fewer.

OperationTimeSpace

FIFO / Clock · cheap; FIFO can hit Belady's anomalyO(1) per faultO(frames)

LRU · no anomaly; needs recency trackingO(1) with a list+mapO(frames)

Optimal · benchmark onlyneeds the futureO(frames)

Check yourself

Which page-replacement policy can suffer Belady's anomaly — more frames causing more page faults?