LRU
Replace the page unused for the longest time. Stack algorithms and clock approximations.
Level: intermediate
What is it?
Least Recently Used (LRU) replaces the resident page whose most recent access is farthest in the past. It relies on temporal locality: a page used recently is often more likely to be needed again soon.
Why does it matter?
LRU can outperform FIFO on workloads with reuse patterns, but exact implementations require tracking recency on each access and can be expensive. Practical systems often approximate LRU with reference bits, generations, or clock-like mechanisms.
Mental model
LRU asks which page has gone unused for the longest time—not which page entered memory earliest. Each reference refreshes a page's recency position.
How it works
- A page reference moves that page to the most-recently-used end of the logical order.
- When a fault needs a victim, exact LRU chooses the least-recently-used resident page.
- LRU is a stack algorithm: increasing the number of frames cannot increase its page-fault count for the same reference string.
- Exact per-access bookkeeping can be costly, especially for many cores and large page counts.
- Clock and generation-based policies approximate recency while reducing tracking overhead.
Steps
- With three frames, reference A, B, C; all three become resident.
- Reference A again; it is now the most recently used page.
- Reference D; B is the least recently used and is the eviction candidate.
- Record page faults consistently, counting only references to nonresident pages.
Real-world usage
- Solving memory-replacement reference strings.
- Reasoning about cache locality and recency-based policies.
- Understanding why production kernels use approximations rather than textbook exact LRU.
Common mistakes
- Evicting the oldest inserted page instead of the least recently used page.
- Failing to refresh recency on a hit.
- Assuming the word LRU guarantees optimal results for every workload.
Interview questions
How does LRU differ from FIFO?
LRU uses the time of the last access; FIFO uses the time of admission into the resident set.
What is LRU's stack property?
For a fixed reference string, the set of pages resident with k frames is contained in the resident set with k+1 frames, so adding frames cannot increase faults.