LRU Page Replacement
Evict whatever has gone unused longest, betting that the recent past predicts the future.
Skip to the animationLRU evicts the page that has gone unused the longest, betting that the recent past predicts the near future. It is the best policy that can actually be implemented — and it is still too expensive to implement exactly.
The idea
Optimal replacement needs to know the future. LRU makes the one substitution available: use the past as a mirror of the future. If a page has not been touched for a long time, it probably will not be touched soon; if it was used a moment ago, it probably will be again.
That bet is not arbitrary. It is exactly the principle of locality — programs spend most of their time in loops and touch clustered data — which is the same assumption that makes CPU caches work. LRU is the page-level version of it.
LRU is Optimal run backwards over the reference string. Optimal looks forward to the farthest next use; LRU looks backward to the farthest last use.
How to actually implement it
Getting the *right* answer is easy. Getting it without destroying performance is not, because the bookkeeping happens on every memory reference, not just on faults.
- Counters
- The CPU keeps a logical clock; every page-table entry gets a time-of-use field written on each reference. Eviction scans for the smallest. Cost: a memory write per reference, plus a full scan per fault.
- Stack of page numbers
- Keep a doubly linked list; on each reference, move that page to the top. The bottom is always the LRU victim, so no search is needed — but six pointers change on every single reference.
- Approximations (what real systems do)
- Hardware gives each page one reference bit, set on access. The second-chance / clock algorithm sweeps a pointer round the frames, clearing set bits and evicting the first page it finds with a clear one. Enhanced second-chance adds the modify bit and prefers evicting clean pages, since dirty ones must be written to disk first.
No commodity CPU provides enough hardware for exact LRU. Every production kernel uses an approximation from that last row.
Why it never suffers Belady's anomaly
LRU is a stack algorithm: the set of pages resident with n frames is always a subset of the set resident with n + 1 frames. The n most-recently-used pages are the top n of one ordering, and adding a frame just takes one more from the same list — it cannot rearrange the earlier ones.
Because that subset property holds, more frames can only ever reduce faults. Optimal is a stack algorithm too; FIFO is not, which is exactly why FIFO can get worse with more memory.
Where the bet fails
LRU's assumption breaks on sequential scans. Read a large file straight through and every page is used exactly once and never again — but each one arrives as “most recently used” and evicts genuinely hot pages on its way past. This is why real kernels do not use plain LRU on the page cache, adding scan resistance (two-list schemes like Linux's active/inactive lists, or ARC) on top.
Advantages and disadvantages
Advantages
- Consistently close to Optimal on real workloads, because real programs have locality.
- A stack algorithm, so it can never suffer Belady's anomaly.
- Needs no knowledge of the future — only of what already happened.
Disadvantages
- Exact implementation requires work on every memory reference, not just on faults.
- Needs hardware support that no ordinary CPU provides, so it is always approximated.
- Defeated by sequential scans, which flush the useful pages with data used exactly once.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.