With plenty of free memory, a fault means grab-a-free-page — hey, Operating System, you did it again! Under memory pressure, though, someone must be evicted, and the chooser is the replacement policy — historically one of the most consequential decisions in systems with tiny memories.
The Crux: How To Decide Which Page To Evict
How can the OS decide which page (or pages) to evict from memory? The replacement policy follows general principles — plus tweaks to dodge corner cases.22.1 Cache Management
Reframe: main memory holds a subset of all pages, so it is a cache for virtual pages. The goal — minimize misses (fetches from disk), maximize hits — is quantified by the average memory access time amat Average memory access time: AMAT = T_M + (P_miss × T_D). Because disk time dwarfs memory time (10ms vs 100ns), even a 0.1% miss rate drags performance toward disk speed — the arithmetic behind every replacement policy's stakes. defined in ch. 22 — open in glossary :
You always pay the memory cost; misses add the disk cost. And the disk cost is monstrous:
| miss rate | AMAT | reading | |
|---|---|---|---|
| 90% hits | 10% | ≈ 1 ms | disk speed |
| 99.9% hits | 0.1% | ≈ 10.1 µs | ~100× faster |
| 100% hits | 0% | 100 ns | memory speed |
Avoid misses, or run at the rate of the disk. Hence: policy.
22.2 The Optimal Replacement Policy
To judge any policy, first meet the unbeatable one. Belady’s optimal policy optimal replacement policy Belady's MIN: evict the page that will be accessed FURTHEST in the future — provably the fewest misses, unimplementable without clairvoyance, and indispensable as the yardstick that tells you how close to perfect (and when to stop tuning) a real policy is. defined in ch. 22 — open in glossary (he called it MIN): evict the page that will be accessed furthest in the future. The intuition is airtight — every other cached page gets referenced before that one, so keeping them serves more hits. It’s also unimplementable: the future is not generally known. (If you can build it, let the authors know; you can get rich together — or end up like the cold-fusion scientists.)
Run it, one decision at a time:
| Access | Hit/Miss? | Evict | Resulting Cache State |
|---|---|---|---|
| ▶ step through the trace, or run it all | |||
OPT: at the first eviction, the future says 0 comes almost immediately, 1 a little later, 2 furthest — evict 2. Result: 6 hits (54.5%, or 85.7% ignoring the three compulsory misses). FIFO: evicts 0 just because it was first in… and the very next access is 0. Result: 4 hits (36.4%). Same stream, same cache — the decision is everything.
The first three misses are unavoidable — compulsory (cold-start) misses compulsory miss A miss because the cache starts empty and this is the first reference to the item (a.k.a. cold-start miss) — no policy can avoid it; hit rates are sometimes quoted 'modulo compulsory'. defined in ch. 22 — open in glossary against an empty cache.
Aside: Types Of Cache Misses — The Three C’s
Architects sort misses into compulsory compulsory miss A miss because the cache starts empty and this is the first reference to the item (a.k.a. cold-start miss) — no policy can avoid it; hit rates are sometimes quoted 'modulo compulsory'. defined in ch. 22 — open in glossary (first-ever reference, empty cache), capacity capacity miss A miss because the cache ran out of space and had to evict — the kind replacement policies actually fight over. defined in ch. 22 — open in glossary (the cache ran out of room and evicted), and conflict conflict miss A miss caused by hardware placement restrictions (set-associativity). Doesn't arise in the OS page cache, which is fully associative — a page can live in any frame. defined in ch. 22 — open in glossary (hardware set-associativity limits where an item may live). The third kind never afflicts the OS page cache: it is fully associative — any page may occupy any frame.Tip: Comparing Against Optimal Is Useful
“My policy hits 80%” means little alone. “Optimal hits 82%” turns it into a result: you’re near the ceiling, and further tuning has little left to win. Knowing the ideal tells you both how much improvement remains and when to stop.22.3 A Simple Policy: FIFO
Early systems dodged the complexity: first-in, first-out. Pages join a queue on arrival; evict the oldest. Gloriously simple — and blind. Flip the chip in the widget above and watch FIFO throw out page 0 because it arrived first, one access before page 0 is needed again: 4 hits to optimal’s 6. FIFO simply cannot perceive that some pages are important.
Aside: Belady’s Anomaly
Bigger cache, better hit rate — surely? Belady, Nelson, and Shedler found a FIFO stream where a FOUR-page cache loses to a three-page one. Count it yourself:| Access | Hit/Miss? | Evict | Resulting Cache State |
|---|---|---|---|
| ▶ step through the trace, or run it all | |||
FIFO: 3 hits with 3 frames, TWO with 4 — a bigger cache made it worse (to the chagrin of Belady's co-authors, the anomaly bears only his name). Flip to LRU and the anomaly vanishes: 2 hits then 4, never worse — LRU's stack property guarantees a size-N+1 cache always contains the size-N cache's contents.
The cure is structural: LRU (next section’s star) has the stack property stack property A cache of size N+1 always contains the contents of the size-N cache (LRU has it; FIFO and random don't) — guaranteeing bigger caches never hurt, and enabling one-pass simulation of all sizes at once. defined in ch. 22 — open in glossary — a cache of size N+1 always contains the size-N cache — so more memory can never hurt it. FIFO and Random obey no such discipline, and Belady’s anomaly belady's anomaly The unsettling discovery that FIFO can get WORSE with a BIGGER cache (stream 1,2,3,4,1,2,5,1,2,3,4,5: size 4 loses to size 3). Policies with the stack property are immune. defined in ch. 22 — open in glossary is the price.
Check yourself
1.T_M = 100ns, T_D = 10ms. Compute AMAT at a 90% hit rate — and explain the lesson lurking in the answer.
2.Belady's optimal policy: what's the rule, and why is it both perfect and useless as a real policy?
3.On the canonical stream, the first three accesses (0, 1, 2) miss under EVERY policy. Why, and what are the Three C's these belong to?
4.On the same stream, FIFO manages 4 hits to optimal's 6. What's FIFO's structural blindness?
5.Belady's anomaly, and why LRU is immune: