LRU Approximation Algorithms
You'll learn why operating systems use clever approximations instead of perfect LRU tracking.
Why Approximate LRU?
True LRU requires tracking the exact order of every page access—expensive in both time and hardware. Operating systems need a practical middle ground: algorithms that achieve LRU-like behavior without the overhead. Think of it like estimating which groceries in your fridge are oldest by checking dates occasionally, rather than writing down every time you touch each item.
Clock Algorithm (Second-Chance)
The Clock algorithm treats pages as sitting in a circular list (like hours on a clock). Each page has a reference bit set to 1 when accessed:
- A "clock hand" pointer sweeps around
- When replacement is needed, the hand checks the current page's bit
- If bit = 1: give it a "second chance" by setting bit to 0, move hand forward
- If bit = 0: this page hasn't been used recently, replace it
This approximates LRU because frequently-used pages keep getting their bits set to 1, surviving many sweeps.
Second-Chance Refinement
The second-chance algorithm is essentially the same concept, sometimes with additional state (like a dirty bit to prefer clean pages). Both names refer to the core idea: give pages one more opportunity before eviction.
The Approximation Trade-off
These algorithms don't perfectly identify the least recently used page—they find a page that's not recently used, which is often good enough. The hardware cost? Just one bit per page and a simple pointer.
Key Takeaway: Clock and second-chance algorithms efficiently approximate LRU using a single reference bit per page and a circular scan, balancing performance with implementation simplicity.