Replacement policies — LRU, LFU, FIFO, Random
WHY do we even need a policy?
The theoretical gold standard is Belady's optimal (OPT/MIN): evict the block whose next use is farthest in the future. It's optimal but unimplementable (needs future knowledge). All real policies approximate it.
WHAT each policy decides
HOW they work — a single trace, four answers
Cache capacity = 3. Access sequence: A miss = block not present (must load, maybe evict). A hit = already present.
LRU walk-through
| Step | Access | Cache (MRU→LRU) | Hit/Miss | Evicted | Why this step? |
|---|---|---|---|---|---|
| 1 | A | A | miss | – | empty, load A |
| 2 | B | B,A | miss | – | still room |
| 3 | C | C,B,A | miss | – | full now |
| 4 | A | A,C,B | hit | – | A moves to most-recent |
| 5 | D | D,A,C | miss | B | B was least-recently-used |
| 6 | B | B,D,A | miss | C | C now LRU |
Why evict B at step 5? Because A was just touched (step 4) and C after B, so B sat untouched longest. That's the entire LRU rule.
FIFO walk-through (same trace)
| Step | Access | Queue (oldest→newest) | Hit/Miss | Evicted | Why this step? |
|---|---|---|---|---|---|
| 4 | A | A,B,C | hit | – | FIFO ignores hits — order unchanged! |
| 5 | D | B,C,D | miss | A | A entered first, even though just used |
| 6 | B | C,D,B | miss? No — B present? B was evicted? No, B still in {B,C,D}→ hit | – | B is in queue |
Steel-man the difference: at step 5 LRU keeps A (just used) but FIFO evicts A because FIFO never updates on a hit. This is exactly why FIFO can suffer Belady's anomaly.
The Stack Property & Belady's Anomaly
LRU qualifies because eviction depends only on recency ordering, which doesn't change with size. FIFO depends on a queue that does change with size → no inclusion → anomaly possible.
The classic anomaly trace (FIFO): 1,2,3,4,1,2,5,1,2,3,4,5
- 3 frames → 9 misses
- 4 frames → 10 misses (more!)
Miss-rate intuition (formula, derived)
Cost vs benefit (the engineering trade-off)
| Policy | Future-prediction quality | Hardware cost | Anomaly-safe? |
|---|---|---|---|
| OPT | perfect (impossible) | – | yes |
| LRU | very good | expensive (needs ordering of all ways) | yes |
| LFU | good for skewed access | counters per block | yes |
| FIFO | mediocre | cheap (one pointer) | no |
| Random | mediocre | cheapest (no metadata) | yes |
Common mistakes (Steel-manned)
Flashcards
What single question does a replacement policy answer?
LRU evicts which block?
LFU evicts which block?
FIFO evicts which block?
Key difference between LRU and FIFO?
What is Belady's optimal (OPT) policy?
What is Belady's anomaly?
Which policies are immune to Belady's anomaly and why?
State the AMAT formula.
Why does AMAT keep T_hit even on a miss?
Why don't CPUs use exact LRU for high associativity?
What is LFU cache pollution and its fix?
Why is Random surprisingly good?
Recall Feynman: explain to a 12-year-old
Your backpack holds only 3 books but you keep grabbing new ones. When it's full and you want a 4th, you must put one back. LRU: return the book you haven't touched in the longest time. LFU: return the one you've opened the fewest times. FIFO: return whichever you packed first, even if you just read it. Random: close your eyes and pull one out. The clever trick: the "best" choice would be to return the book you won't need for the longest time — but you can't see the future, so each method is a smart guess.
Connections
- Cache Memory Fundamentals — sets, ways, blocks
- Set-Associative Mapping — replacement only matters within a set
- Belady's Optimal Algorithm — the unbeatable baseline
- Page Replacement (OS) — same policies for virtual memory
- AMAT and Memory Hierarchy — why miss rate is leverage
- Pseudo-LRU and Tree-PLRU — the practical hardware hack
- Temporal and Spatial Locality — the assumption every policy rides on
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Dekho, cache mein limited slots hote hain. Jab cache full ho jata hai aur ek naya block laana ho, to kisi purane block ko nikalna padta hai — yahi decision replacement policy karti hai. Bas ek hi sawaal: "victim kaun banega?" Char popular tareeke hain — LRU, LFU, FIFO aur Random.
LRU kehta hai: jo block sabse lambe time se use nahi hua, usko nikaalo (recent past future ka achha guess hota hai). LFU kehta hai: jiska access count sabse kam hai usko nikaalo (popular cheez popular rahegi). FIFO kehta hai: jo pehle aaya tha wahi pehle jaayega, chahe abhi use hua ho ya nahi. Random to bas aankh band karke kisi ko bhi utha deta hai. Sabse bada farak: hit hone par LRU order update karta hai, FIFO nahi — isliye FIFO mein wo ajeeb Belady's anomaly aa sakti hai, jisme cache bada karne par misses badh jaate hain. LRU aur LFU "stack algorithm" hain, unme yeh problem kabhi nahi hoti.
Yeh sab matter kyun karta hai? Kyunki AMAT = T_hit + miss_rate × T_penalty. Memory penalty bahut bada hota hai (100 ns vs 1 ns), to agar achhi policy miss rate thoda bhi kam kar de, total speed kaafi improve ho jaati hai. Asli CPUs exact LRU use nahi karte (bahut bits lagte hain), instead pseudo-LRU use karte hain jo sasta aur "kaafi achha" hota hai. Random bhi underrated hai — koi worst case nahi, aur metadata zero. Exam aur interview dono mein yeh trade-off (quality vs hardware cost vs anomaly-safety) clearly samajhna zaroori hai.