Worked examples — Replacement policies (LRU, FIFO, random)

5.4.5 · D3 · Hardware › Memory Hierarchy & Caches › Replacement policies (LRU, FIFO, random)

Yeh page Replacement policies ke liye "sab kuch daal do" wali drill hai. Hum sirf ek accha sa sequence dobara nahi chalayenge — hum har us situation ko dhundhenge jo ek replacement policy face kar sakti hai, aur har ek ko end tak work out karenge.

Shuru karne se pehle, teen plain-word reminders taaki koi symbol akela na aaye:

Agar inme se kuch shaky lagta hai, to parent note unhe zero se build karta hai — pehle wahan jaao, phir yahan wapas aao.

---

Scenario matrix

Har replacement question inhi case classes mein se ek hai. Neeche hamare examples ko us cell ke saath label kiya gaya hai jo woh hit karte hain, aur milke yeh sab cover karte hain.

#	Case class	Tricky kyun hai	Covered by
C1	Cold cache / empty ways	Abhi tak koi eviction nahi — blocks kahan jaate hain?	Ex 1
C2	Hit vs miss divergence	LRU aur FIFO tab tak agree karte hain jab tak ek purane block pe hit nahi hoti	Ex 2
C3	Ek trace pe teenon policies	Same input, teen alag victims	Ex 3
C4	Degenerate: 1-way (direct mapped)	Policy irrelevant ho jaati hai	Ex 4
C5	Limiting: fully associative / repeated block	Warm-up ke baad koi miss nahi	Ex 5
C6	Belady's anomaly (FIFO)	Bada cache → zyada misses	Ex 6
C7	Random: expected miss count	Jawab ek probability hai, fixed number nahi	Ex 7
C8	Real-world word problem (AMAT)	Miss-rate difference ko nanoseconds mein convert karo	Ex 8
C9	Exam twist: pseudo-LRU true LRU se disagree karta hai	Sasta approximation alag victim choose karta hai	Ex 9

---

Example 1 — Cold cache, koi eviction nahi (C1)

Forecast: padhne se pehle evictions ki count guess karo.

1. Access P → miss, empty ways exist. Yeh step kyun? Replacement policy sirf tabhi fire hoti hai jab set full ho. Free ways hone par hum bas lowest empty one fill karte hain. P → way 0.
2. Access Q → miss, way 1 free. Q → way 1.
3. Access R → miss, way 2 free. R → way 2.

Jawab: 3 misses, 0 evictions, way 3 abhi bhi empty.

Verify: ways used = 3, set size = 4, to $3\le 4$ ⇒ koi eviction zaroori nahi. ✓

---

Example 2 — Woh hit jo LRU ko FIFO se alag karti hai (C2)

Forecast: kya dono same block evict karte hain? Guess karo.

Figure dekho — upar ka track LRU hai (hit pe reorder karta hai), neeche wala FIFO hai (frozen order).

1. Load A, load B — dono policies ab $\{A,B\}$ hold karti hain, aur A purana wala hai. Kyun? Pehle do accesses empty ways fill karte hain; abhi decide karne ki koi zaroorat nahi.
2. Access A (hit). Yeh pivot kyun hai: LRU A ko most-recently-used (MRU) pe move karta hai, to B sabse thanda ban jaata hai. FIFO hits ko ignore karta hai, to A abhi bhi insertion ke hisaab se sabse purana hai.
3. Access C (miss → evict):
   • LRU B ko throw out karta hai (recency ke hisaab se sabse thanda).
   • FIFO A ko throw out karta hai (arrival ke hisaab se sabse purana), bhale hi A abhi-abhi use hua tha.

Jawab: LRU B evict karta hai, FIFO A evict karta hai.

Verify: trace ke baad, LRU set = $\{A,C\}$, FIFO set = $\{B,C\}$ — alag hain, yeh confirm karta hai ki hit exactly wahin hai jahan policies diverge karti hain. ✓

---

Example 3 — Teenon policies, ek trace (C3)

Forecast: LRU ke under kaunsa block sabse safe hai? FIFO ke under kaunsa?

1. LRU victim. Kyun: use ke hisaab se sabse thande ko evict karo. Woh hai D (least recently used).
2. FIFO victim. Kyun: sabse pehle insert hue ko evict karo. Yahan A sabse pehle insert hua tha, to FIFO A ko evict karta hai — woh jise LRU safest manta hai.
3. Random victim. Kyun: 4 ways pe uniform, to A, B, C, D mein se koi bhi $\frac{1}{4}$ probability ke saath.

Jawab: LRU → D, FIFO → A, Random → chaaron mein se koi bhi ($p=0.25$ each).

Verify: LRU aur FIFO same 4-block set ke opposite ends choose karte hain (D vs A), jo possible sabse zyada disagreement hai — sanity confirmed. ✓

---

Example 4 — Degenerate: 1-way (direct mapped) (C4)

Forecast: kya koi policy yahan help kar sakti hai?

1. Access X → miss, single slot mein load karo.
2. Access Y → miss, evict karna zaroori hai — lekin sirf ek block hai, X. Kyun: $n=1$ ke saath, "full slots mein se kaun sa?" ka exactly ek jawab hai. X evict karo.
3. Access X → miss (X abhi-abhi evict hua tha), Y evict karo.
4. Access Y → miss, X evict karo.

Jawab: dono LRU aur FIFO ke liye 4 misses — identical.

Recall n=1 pe policy choice meaningless kyun hai?

Question: Ek way ke saath, LRU, FIFO, aur Random sab same kyun behave karte hain? ::: Sirf ek full slot hai choose karne ke liye, to har policy ka "pick a victim" step wahi same block return karta hai. Set size $n$ kaise choose kiya jaata hai uske liye cache organization dekho.

Verify: $n=1\Rightarrow$ victim set ka size 1 hai $\Rightarrow$ sab policies deterministic aur equal hain. Miss count = 4. ✓

---

Example 5 — Limiting case: repeated block / poora fit hota hai (C5)

Forecast: warm-up ke baad, har pass mein kitne misses?

1. Pehla pass: 4 compulsory misses (cold slots fill hote hain).
2. Doosra pass aur aage: poora working set $\{A,B,C,D\}$ 4 ways mein fit ho jaata hai. Misses kyun ruk jaati hain: koi access kabhi paanchwe block ki zaroorat nahi karti, to koi eviction kabhi trigger nahi hoti — koi policy invoke nahi hoti.

Jawab: miss rate $\to 0$ jaise passes $\to \infty$; forever exactly 4 total misses.

Verify: working set size $=4=$ ways, to working set fit hota hai; steady-state miss rate $=4/(\text{passes}\times 4)\to 0$. ✓

---

Example 6 — FIFO ke under Belady's Anomaly (C6)

Forecast: kaunsa cache size kam misses deta hai? ("obvious" jawab galat hai.)

Figure dono ko side by side run karta hai; har column ek access hai, ✗ ek miss mark karta hai.

Neeche ki tables mein, ✗ = miss (block present nahi tha, eviction fire ho sakti hai) aur ✓ = hit (block already cache mein tha, kuch nahi badla).

3-frame FIFO trace (frames oldest→newest listed):

Access	1	2	3	4	1	2	5	1	2	3	4	5
Hit/Miss	✗	✗	✗	✗	✗	✗	✗	✓	✓	✗	✗	✓

Count: 9 misses (3 hits).

4-frame FIFO trace:

Access	1	2	3	4	1	2	5	1	2	3	4	5
Hit/Miss	✗	✗	✗	✗	✓	✓	✗	✗	✗	✗	✗	✗

Count: 10 misses (2 hits).

4-frame row padhna: accesses 1 aur 2 (5th aur 6th columns) hits hain kyunki 1, 2, 3, 4 sab 4 frames mein fit ho jaate hain. Lekin phir 5 ne 1 ko evict kiya, aur us point se aage 1, 2, 3, 4, 5 mein se har ek theek baad mein arrive karta hai jab use throw out kiya gaya tha — to final 5 bhi ek miss hai. Woh aakhri column woh extra miss hai jo 3-frame cache ne nahi uthaya tha.

1. 4-frame version worse kyun karta hai? Yeh step kyun: FIFO arrival age se evict karta hai, usefulness se nahi. Bada cache 1 aur 2 ko zyada der tak alive rakhta hai, lekin yeh circular queue ka phase shift kar deta hai to blocks (1, 2) theek pehle evict ho jaate hain jab unhe reuse kiya jaata.
2. Fix: LRU ek "stack algorithm" hai aur yeh anomaly nahi dikha sakta — iski miss count size ke saath kabhi nahi badhti.

Jawab: 3 frames → 9 misses, 4 frames → 10 misses. Anomaly confirmed.

Verify: =VERIFY= block is exact trace pe dono FIFO caches simulate karta hai aur $9$ aur $10$ check karta hai. ✓

---

Example 7 — Random replacement: expected misses (C7)

Forecast: kya doosra access (A) hamesha hit hai?

1. Access C → miss (C present nahi hai), uniformly random block evict karo: A ya B, dono $p=\frac{1}{2}$ ke saath. Kyun: Random history ignore karta hai; victim ek fair coin flip hai.
2. Access A → step 1 pe depend karta hai:
   • Agar C ne A evict kiya (prob $\frac{1}{2}$): set hai $\{C,B\}$, to A ek miss hai.
   • Agar C ne B evict kiya (prob $\frac{1}{2}$): set hai $\{C,A\}$, to A ek hit hai.
3. Expected misses $=\underset{\text{C hamesha miss}}{\underbrace{1}}+\underset{\text{A}}{\underbrace{\frac{1}{2}\cdot 1+\frac{1}{2}\cdot 0}}=1+\frac{1}{2}=\frac{3}{2}$.

Jawab: expected misses $=\frac{3}{2}=1.5$.

Verify: $1+\frac{1}{2}(1)+\frac{1}{2}(0)=1.5$. ✓

---

Example 8 — Word problem: miss rate ko time mein convert karna (C8)

Forecast: 1-point miss-rate gap — badi baat hai ya nahi?

Parent se formula yaad karo: $\text{AMAT}=\text{Hit Time}+\text{Miss Rate}\times \text{Miss Penalty}$

1. LRU: ${\text{AMAT}}_{\text{LRU}}=1+0.04\times 100=1+4=5\text{ ns}$. Kyun: miss rate $=0.04$ directly plug karo; $\times 100$ har miss ko uski 100 ns cost mein convert karta hai.
2. FIFO: ${\text{AMAT}}_{\text{FIFO}}=1+0.05\times 100=1+5=6\text{ ns}$.
3. LRU ka Speedup $=\frac{6-5}{6}=\frac{1}{6}\approx 16.7\%$. Slow wale se kyun divide karo: percent improvement us baseline ke against measure hota hai jise tum replace kar rahe ho (FIFO).

Jawab: ${\text{AMAT}}_{\text{LRU}}=5$ ns, ${\text{AMAT}}_{\text{FIFO}}=6$ ns, LRU $\approx 16.7\%$ faster hai.

Verify: units: $\text{ns}+(\text{unitless})\times \text{ns}=\text{ns}$ ✓. =VERIFY= mein numeric check. ✓

---

Example 9 — Exam twist: pseudo-LRU true LRU se disagree karta hai (C9)

Forecast: kya 3-bit approximation true LRU se match karega?

Figure tree dikhata hai: har bit ek arrow hai jo recently-used side ki taraf point karta hai; victim ko root se opposite arrows follow karke dhundha jaata hai.

1. True LRU victim. Kyun: least-recent access evict karo. Order hai $w_2>w_0>w_3>w_1$, to sabse thanda hai $w_1$.
2. Access order se pseudo-LRU bits reconstruct karo.
   • Root bit: left pair $\{w_0,w_1\}$ ka last access $w_0$ tha (overall 2nd); right pair $\{w_2,w_3\}$ ka $w_3$ tha (overall 3rd). Right pair zyada recently touch hua tha ⇒ root right point karta hai. To victim search left jaati hai.
   • Left-pair bit: $\{w_0,w_1\}$ ke andar, $w_0$ touch hua tha (position 2), $w_1$ baad mein dobara touch nahi hua — to pair bit $w_0$ ki taraf point karta hai ⇒ victim doosra wala hai, $w_1$.
3. Compare. Yahan pseudo-LRU bhi $w_1$ pe land karta hai.

Jawab: dono true-LRU aur pseudo-LRU is baar $w_1$ evict karte hain — lekin pseudo-LRU sirf per-pair recency track karta hai, to ek alag access order ke saath (jaise $w_0,w_2,w_1,w_3$) yeh true coldest block miss kar sakta hai. Yeh ek approximation hai, sasta (3 bits vs 8 bits) lekin exact nahi.

Recall Cost comparison

Question: Ek 4-way set ke liye, exact LRU vs pseudo-LRU ko kitne bits chahiye? ::: Exact LRU: 4 counters × 2 bits = 8 bits. Pseudo-LRU: 3 bits (n−1). Victim often same hota hai, lekin hamesha nahi.

Verify: bit counts $4\times 2=8$ aur $4-1=3$; dono methods is trace ke liye $w_1$ pe agree karte hain. ✓

---

Recap clozes

• Woh ek case jahan LRU, FIFO aur Random sab identically behave karte hain woh hai 1-way (direct-mapped) cache.
• FIFO Belady's anomaly suffer kar sakta hai, jahan bada cache zyada misses deta hai.
• Random ke under expected misses ke liye ek probability calculation chahiye, fixed count nahi.