NOTE
3.7 Page Replacement
Page-replacement goals and classic OPT, FIFO, LRU, LFU, Clock, and working-set ideas, with the distinction between textbook algorithms and real kernels.
This is a historical learning note and may contain outdated or incomplete understanding.
1. Why Page Replacement Is Needed
When physical memory is under pressure, the OS must decide which resident pages can be reclaimed or evicted.
The goal is not merely to “move unused pages back to disk.” Clean file-backed pages may simply be discarded and loaded again later; anonymous pages may require swap if they must be preserved.
A good policy tries to keep the active working set resident and minimize expensive future page faults.
2. Classic Algorithms
2.1 OPT
Evict the page whose next use is farthest in the future. This produces an optimal result for a known reference string but requires future knowledge, so it is a benchmark rather than an implementable general policy.
2.2 FIFO
Evict the page that has been resident longest. It is simple but can perform poorly and can exhibit Belady’s anomaly.
2.3 LRU
Evict the page that has not been used for the longest time. Exact LRU can be expensive to maintain at page granularity, so systems use approximations.
2.4 LFU
Evict pages with the lowest access frequency. Pure LFU can keep stale historically-hot pages too long unless aging is applied.
2.5 Clock / Second Chance
Clock-style algorithms approximate recency using reference bits and are a common bridge between textbook LRU and practical implementation.
3. Real Systems
Modern kernels use more sophisticated reclaim logic involving active/inactive lists, generations, page type, dirty state, cgroups, NUMA locality, and workload behavior.
The durable lesson is: replacement policy estimates future usefulness from imperfect history while balancing implementation cost.