Replacement policies — LRU, LFU, FIFO, Random

4.1.11 · Coding › Computer Architecture (Deep)

WHY — policy ki zaroorat kyun hai?

Theoretical gold standard hai Belady's optimal (OPT/MIN): us block ko evict karo jiska next use future mein sabse door hai. Ye optimal hai lekin unimplementable hai (future knowledge chahiye). Saari real policies isko approximate karti hain.

WHAT — har policy kya decide karti hai

Figure — Replacement policies — LRU, LFU, FIFO, Random

HOW — ek hi trace, chaar alag jawaab

Cache capacity = 3. Access sequence: $A, B, C, A, D, B$ Miss = block present nahi (load karna padega, shayad evict bhi). Hit = already present hai.

LRU walk-through

Step	Access	Cache (MRU→LRU)	Hit/Miss	Evicted	Is step mein kyun?
1	A	A	miss	–	empty hai, A load karo
2	B	B,A	miss	–	abhi jagah hai
3	C	C,B,A	miss	–	ab full hai
4	A	A,C,B	hit	–	A most-recent position pe aa gaya
5	D	D,A,C	miss	B	B sabse zyada time se use nahi hua tha
6	B	B,D,A	miss	C	C ab LRU hai

Step 5 mein B kyun evict hua? Kyunki A abhi touch hua tha (step 4) aur C B ke baad, isliye B sabse zyada time se untouched pada tha. Yehi poora LRU rule hai.

FIFO walk-through (same trace)

Step	Access	Queue (oldest→newest)	Hit/Miss	Evicted	Is step mein kyun?
4	A	A,B,C	hit	–	FIFO hits ko ignore karta hai — order unchanged!
5	D	B,C,D	miss	A	A pehle enter kiya tha, chahe abhi use hua ho
6	B	C,D,B	miss? Nahi — B present hai? B evict hua? Nahi, B {B,C,D} mein hai → hit	–	B queue mein hai

Dono ka fark clearly: step 5 pe LRU A ko rakhta hai (abhi use hua) lekin FIFO A ko evict karta hai kyunki FIFO hit pe kabhi update nahi karta. Isi wajah se FIFO Belady's anomaly suffer kar sakta hai.

Stack Property & Belady's Anomaly

LRU qualify karta hai kyunki eviction sirf recency ordering pe depend karta hai, jo size ke saath change nahi hoti. FIFO ek queue pe depend karta hai jo size ke saath change hoti hai → koi inclusion nahi → anomaly possible.

Classic anomaly trace (FIFO): 1,2,3,4,1,2,5,1,2,3,4,5

3 frames → 9 misses
4 frames → 10 misses (zyada!)

Miss-rate intuition (formula, derived)

Cost vs benefit (engineering trade-off)

Policy	Future-prediction quality	Hardware cost	Anomaly-safe?
OPT	perfect (impossible)	–	yes
LRU	bahut accha	expensive (saare ways ki ordering chahiye)	yes
LFU	skewed access ke liye accha	counters per block	yes
FIFO	mediocre	sasta (ek pointer)	no
Random	mediocre	sabse sasta (koi metadata nahi)	yes

Common mistakes (Steel-manned)

Flashcards

Ek replacement policy kaun sa ek sawaal answer karti hai?

Jab cache (set) full ho, kaun sa block evict karna hai.

LRU kaun sa block evict karta hai?

Jo sabse zyada time se use nahi hua (least recently used).

LFU kaun sa block evict karta hai?

Jiska access-frequency count sabse chhota ho.

FIFO kaun sa block evict karta hai?

Jo cache mein sabse pehle enter kiya tha, usage ignore karke.

LRU aur FIFO mein key difference kya hai?

LRU hit pe recency update karta hai; FIFO hit pe kabhi reorder nahi karta.

Belady's optimal (OPT) policy kya hai?

Us block ko evict karo jiska next use future mein sabse door hai; optimal hai par unimplementable.

Belady's anomaly kya hai?

FIFO mein, cache frames badhane se miss count badh sakta hai.

Belady's anomaly se kaun si policies immune hain aur kyun?

LRU aur LFU — ye stack algorithms hain (chhote cache contents ⊆ bade).

AMAT formula batao.

AMAT = T_hit + (miss rate) × T_penalty.

Miss hone par bhi AMAT mein T_hit kyun rehta hai?

Miss hone par bhi pehle cache probe hoti hai, phir memory se fetch hota hai.

High associativity ke liye CPUs exact LRU kyun use nahi karte?

Full order track karne ke liye log2(n!) bits chahiye; pseudo-LRU (tree-PLRU, ~n−1 bits) sasta hai.

LFU cache pollution kya hai aur fix kya hai?

Stale blocks purane high counts ki wajah se kabhi evict nahi hote; fix hai aging/decay of counters.

Random surprisingly accha kyun hota hai?

Koi pathological worst case nahi aur zero metadata cost.

Recall Feynman: 12 saal ke bachhe ko samjhao

Teri bag mein sirf 3 kitaabein aati hain par tu nai kitaabein uthata rehta hai. Jab bag full ho aur 4th chahiye, toh ek wapas rakhni padegi. LRU: jo kitaab sabse zyada time se haath nahi lagayi, use wapas rakho. LFU: jise sabse kam baar khola, use rakho. FIFO: jis kitaab ko pehle pack kiya tha, use wapas rakho, chahe abhi padhi ho. Random: aankhein band karo aur koi ek nikalo. Clever trick: "best" choice hogi wo kitaab wapas rakhna jo sabse der baad chahiye — par future nahi dikta, isliye har method ek smart guess hai.

Connections

Cache Memory Fundamentals — sets, ways, blocks
Set-Associative Mapping — replacement sirf ek set ke andar matter karta hai
Belady's Optimal Algorithm — jo baseline beat nahi ho sakta
Page Replacement (OS) — virtual memory ke liye same policies
AMAT and Memory Hierarchy — miss rate leverage kyun hai
Pseudo-LRU and Tree-PLRU — practical hardware hack
Temporal and Spatial Locality — wo assumption jis par har policy tiki hai