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

Use LRU replacement, or a modest recency-based approximation, for eligible buffer-cache entries. Unlike individual memory accesses, buffer cache lookups already pass through operating system code. Updating an LRU replacement list on each lookup is therefore practical: remove the accessed entry from its old position and put it at the most-recent end; choose the oldest unpinned entry as victim. A hash lookup plus a doubly linked recency list makes this bookkeeping constant time.

Good temporal locality favors retaining recently used blocks. FIFO page replacement's arrival-only criterion can evict a block used moments ago. CLOCK page replacement can save bookkeeping, but the difficulty of observing arbitrary memory references that motivates it is absent for software-mediated block accesses. Dirty victims require write-back, so a policy can favor an old clean buffer or arrange background cleaning without discarding recent hot data. A long one-pass scan can pollute pure LRU replacement; scan-resistant variants are useful refinements rather than a reason to ignore recency altogether.