Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 7 / a / i / Solution

FIFO page replacement orders resident pages by when they were loaded and evicts the oldest arrival. An access to a resident page does not change this order, so an old but heavily used page can be the next victim.

LRU replacement records the recency of every page access and evicts the page whose most recent access is oldest. It makes use of temporal locality, but exact reference tracking can require expensive per-access hardware or software bookkeeping.

CLOCK page replacement arranges frames in a circle with a scanning hand and one reference flag per frame. A use sets the flag. During replacement, the hand clears a set flag and moves on, giving that page another chance; it selects an eligible frame with a clear flag. Recent pages tend to survive a scan. CLOCK page replacement approximates recency rather than preserving the exact LRU replacement ordering. A dirty victim must be written back before its frame is reused, and pinned frames must be skipped.