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

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.

Emulate reference observations using page table protection and page faults. When resetting a page's reference state, temporarily revoke access to its resident mapping and invalidate any corresponding translation lookaside buffer entry. The first subsequent access traps. The handler recognizes an intentionally protected resident page, sets a software reference flag and restores the mapping without performing a disk read. A later CLOCK page replacement scan can use and clear this software flag.

One protection fault records the first access after each reset, rather than trapping on every access. All mappings that can access the frame must be considered. The method requires ordinary memory-protection traps, even though hardware reference bits are absent, and adds a fault cost that native reference flags avoid.

Choose CLOCK for page replacement in a conventional operating system. Good temporal locality makes recency valuable, and CLOCK page replacement captures it reasonably well using cheap reference flags. FIFO page replacement ignores accesses after a page arrives, so it can evict a hot page. Exact LRU replacement has a stronger recency rule but recording and maintaining the order on every ordinary memory access is usually too costly. This is a practical cost-versus-hit-rate choice, not a theorem that CLOCK page replacement minimizes faults on every reference sequence.