Stealing the future's idea: why LRU works
In the last guide you met the optimal algorithm: when memory is full, evict the page that will not be used again for the longest time. It produces the fewest possible faults on any reference string, which is exactly why it is the benchmark every other policy is measured against. But it has a fatal flaw — it needs to know the future, and no real OS can see what pages a program will touch tomorrow. So OPT is unrealizable; it lives only in the simulator, as a yardstick.
LRU — Least Recently Used — is the clever workaround. Since we cannot look forward, we look backward: evict the page that has gone the longest without being touched. The bet behind this is locality of reference, the deep observation that programs do not touch memory at random. A page used a moment ago is very likely to be used again soon (a loop variable, the top of the stack), while a page untouched for ages is probably done. So LRU uses the recent past as a cheap forecast of the near future — the past is a mirror that OPT cannot afford but LRU can.
A bonus: LRU never suffers Belady's anomaly
Recall the unsettling surprise from guide 2: with FIFO, giving a process more frames can sometimes make it fault more, the result called Belady's anomaly. LRU is provably immune to this. The reason is a tidy property called the stack property: with LRU, the set of pages that would be resident with k frames is always a subset of the set that would be resident with k+1 frames. Adding a frame never throws out a page that a smaller memory would have kept.
Policies with this property are called stack algorithms, and both LRU and OPT are members. For any stack algorithm, more frames can only reduce faults or leave them unchanged — never increase them. This is a real, practical reason engineers reach for LRU-style policies over FIFO: not only does LRU usually fault less, it also behaves monotonically, so capacity-planning intuition ("buy more RAM, fault less") actually holds. FIFO is not a stack algorithm, which is exactly why it can misbehave.
The catch: exact LRU is too expensive to build
If LRU is so good, why does almost no real OS implement it exactly? Because "least recently used" requires tracking the order in which pages were touched, and that order changes on every single memory access — not just on a fault. To do it precisely you would either timestamp every access (so on eviction you scan for the oldest stamp) or maintain a doubly linked list and move a page to the front on each reference. Either way, the hardware would have to do real bookkeeping work for every load and store the CPU executes — billions per second.
That is the trade-off in a nutshell: making the eviction decision smart costs you on every access, where you can least afford it. No mainstream MMU keeps per-page timestamps updated in hardware, and doing it in software would mean trapping into the kernel on every reference — absurdly slow. So exact LRU is the policy everyone wants and nobody pays for. The practical move is to give up precise ordering and settle for a coarse, cheap signal that says merely "was this page touched recently or not?" — and that question, it turns out, the hardware will answer almost for free.
The reference bit and the second-chance idea
Almost every MMU offers a free helper alongside the dirty bit: a reference bit (also called the access or use bit) in each page-table entry. The rule is simple — whenever the hardware touches a page, for a read or a write, it sets that page's reference bit to 1, automatically. The OS never has to watch individual accesses; it just gets to read these bits later. The reference bit is the coarse signal we wanted: a 1 means "used since I last looked," a 0 means "not used in that window." It cannot tell you the order of touches, only the rough fact of recency.
The second-chance algorithm builds an LRU-ish policy out of this one bit. Run plain FIFO, but before you actually evict the oldest page, peek at its reference bit. If the bit is 0, the page really has not been used lately — evict it, just as FIFO would. If the bit is 1, the page was used recently, so it does not deserve to die yet: give it a second chance. Clear its reference bit to 0 and move on to the next-oldest page, repeating the same test. A page with its bit set keeps surviving until it has gone one full sweep without being touched.
Notice the elegant effect: a page that keeps getting used keeps getting its bit re-set by the hardware between sweeps, so it keeps earning second chances and stays resident — exactly the behaviour LRU wants. A page nobody touches eventually meets the hand with a 0 bit and gets evicted. We have rebuilt the spirit of LRU using a single free bit and a FIFO order, with no per-access bookkeeping at all.
The clock: second chance, drawn as a circle
Second chance has one awkward implementation detail: a real queue would force you to physically move a page from the front to the back when it survives, which is fiddly. The clock algorithm is the same idea with a beautiful packaging. Arrange all the frames in a circle, like numbers on a clock face, and keep a single pointer — the clock hand — pointing at one of them. The hand only ever moves forward, sweeping round and round; nothing is reordered. That is all the clock is: second chance with the queue bent into a ring so survivors need no shuffling.
find_victim(): # frames arranged in a ring; 'hand' points at one
loop forever:
page = frame_at(hand)
if reference_bit(page) == 0:
evict page # found the victim; this frame is reused
advance hand one step # leave hand just past the new page
return page
else:
reference_bit(page) = 0 # clear bit: this is its "second chance"
advance hand one step # keep sweeping
# A burst of all-1 bits is impossible to loop on forever: each pass
# clears bits, so within at most one full revolution some bit is 0.Two honest edge cases. First, if every page has its reference bit set when a fault hits, the hand makes a full revolution, clearing every bit to 0, and then evicts the page it started on — so in that worst case the clock degenerates exactly into FIFO. Second, a sharper version weighs the reference bit together with the dirty bit, preferring to evict pages that are both unused and clean (no write-back needed) before unused-but-dirty ones — the cheap-eviction trick from guide 1, folded right into the sweep. Real kernels often run several hands or several priority classes, but the heart is always this one-bit, no-reorder loop.
Aging: squeezing more recency out of more bits
The plain reference bit has one weakness: it is a single bit, so it cannot tell apart two pages that were both used "sometime" in the last sweep — it has no sense of how long ago. The aging algorithm fixes this by giving each page a small counter, say 8 bits, and updating it on a regular timer tick. At each tick, shift every page's counter right by one, then drop that page's current reference bit into the newly vacated top bit, and clear the reference bit. The counter becomes a short history: a 1 high up means "used recently," a 1 low down means "used a while ago," all zeros means "cold."
Because newer references land in the high bits and old ones march downward and fall off, the counter, read as a binary number, ranks pages almost the way true LRU would: evict the page with the smallest counter. Aging is still an approximation — its resolution is the timer interval, and the counter forgets anything older than its bit-width — but with a handful of bits it tracks recency far more finely than a single bit can, getting strikingly close to exact LRU at a tiny, fixed cost per tick rather than per access.
Be careful not to confuse aging with the counting-based policies (LFU/MFU), which count how OFTEN a page is used rather than how RECENTLY. Frequency counting is tempting but fragile: a page used heavily during startup can hoard a huge count and then linger forever despite never being touched again. Recency, the thing LRU and aging track, usually predicts the near future better than raw frequency does — which is why the LRU family, approximated by clock and aging, is what real systems lean on.