Page Replacement
Which resident page to evict on a fault. The policy is the whole game.
Level: intermediate
What is it?
Page replacement chooses which resident virtual-memory page to evict when a process needs a frame and no suitable free frame is available. The policy aims to retain pages likely to be reused, but the future reference sequence is unknown in general.
Why does it matter?
Poor victim choices increase page faults and storage I/O, potentially causing thrashing. Replacement algorithms approximate locality so a limited amount of RAM can serve a larger virtual-memory working set.
Mental model
Memory is a limited cache of pages. On a miss, the OS needs space for the requested page and must decide which resident page is least valuable to keep.
How it works
- The optimal policy evicts the page whose next use is farthest in the future, but it requires future knowledge and is mainly a comparison benchmark.
- FIFO evicts the oldest resident page and can exhibit Belady's anomaly.
- LRU evicts the page least recently used and has the stack property, but exact tracking can be expensive.
- Clock/second-chance algorithms approximate recency using reference bits.
- The fault cost depends on whether the victim is clean or dirty and on storage and memory pressure.
Steps
- A process references a page that is not resident.
- The OS chooses a free frame or applies a replacement policy to select a victim.
- If the victim is dirty, its contents may need to be written back; the requested page is loaded.
- The page table and TLB state are updated before the process resumes.
Real-world usage
- Solving page-fault-count questions with reference strings.
- Explaining locality, working sets, and thrashing.
- Comparing exact LRU with lower-overhead approximations.
Common mistakes
- Counting a TLB miss as a page fault without checking residency.
- Assuming replacement always means disk I/O; a clean victim may be discarded, while shared and file-backed pages have special behavior.
- Comparing algorithms on different reference strings or frame counts.
Interview questions
Why is optimal page replacement not directly implementable?
It requires knowing the next future reference to every page, which a real operating system cannot generally know.
What factors matter beyond choosing a victim?
Whether the page is dirty or shared, writeback cost, memory pressure, locality, and the implementation overhead of tracking usage.