Replacement policies (LRU, FIFO, random): Exercises

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

Yeh page Replacement policies (LRU, FIFO, Random) ke liye ek self-test workout hai. Har problem ek cognitive level pe graded hai — sirf policy ko pehchanne se lekar unhe design aur prove karne tak.

Har solution ek collapsible [!recall]- callout ke andar chhupa hua hai. Pehle khud try karo, phir reveal karo. Har level ke baad ek [!mistake] warning hai us level ke classic trap ke baare mein.

Prerequisites jo open rakhne chahiye: 5.4.01-Cache-organizationand-addressing, Temporal-and-spatial-locality, Working-set-model.

Level 1 — Recognition

Exercise 1.1 (L1)

Ek cache set full hai. Ek naya block load karna hai. Har policy kaun se existing block ko evict karti hai? LRU, FIFO, Random mein se har ek ke liye single sentence ka rule batao.

Recall Solution

LRU: us block ko evict karo jo sabse zyada time se access nahi hua (sabse purani use).
FIFO: us block ko evict karo jo sabse pehle load hua (sabse purani insertion), chahe haal hi mein kitni bhi baar use hua ho.
Random: ek uniformly random block ko evict karo, koi bhi history track nahi karte.

Exercise 1.2 (L1)

Hit hone par, teeno policies mein se kaun apna bookkeeping update karta hai, aur kaun kuch nahi karta?

Recall Solution

LRU — update karta hai: hit block most recently used ban jaata hai (front pe reorder ho jaata hai).
FIFO — kuch nahi karta: insertion order hits se unchanged rehta hai.
Random — kuch nahi karta: update karne ke liye koi history hai hi nahi.

Yeh ek line hi LRU aur FIFO ke beech ka poora fark hai. LRU access par react karta hai; FIFO sirf insertion par react karta hai.

Exercise 1.3 (L1)

Ek 4-way set exact LRU with 2-bit counters per block use karta hai. Har set mein kitne bookkeeping bits hain? Doosra cache usi 4-way set ke liye tree pseudo-LRU use karta hai — kitne bits hain, aur kyun utni hi number?

Recall Solution

Exact LRU: har way ke liye ek 2-bit counter $\Rightarrow 4 \times 2 = 8$ bits.
Tree pseudo-LRU: $n - 1 = 4 - 1 = 3$ bits.

Usi set ke liye FIFO ko sirf $⌈ lo g_{2} 4 ⌉ = 2$ bits chahiye (pure set ke liye ek pointer).

Tree ke liye $n - 1$ bits kyun? $n = 4$ ways ko ek chhote binary tree ke chaar leaves ki tarah socho. Ek single leaf choose karne ke liye tum root se neeche walk karte ho, har internal node par ek left/right choice lete ho: pehli choice left pair ya right pair pick karti hai, doosri choice us pair ke andar ek way pick karti hai. $n$ leaves wale binary tree mein exactly $n - 1$ internal nodes hote hain, aur har internal node ek bit store karta hai ("kaun sa child zyada recently touch hua — evict karne ke liye doosri taraf jao"). Toh $4$ leaves $\to 3$ internal nodes $\to 3$ bits. Har access par tum root-to-leaf path ke bits ko flip karte ho taaki woh recently-used block se door point karein; eviction par tum bits follow karke pseudo-oldest leaf tak pohonchte ho. Isliye $n - 1$ bits kaafi hain exact LRU ke $n lo g_{2} n$ bits ki jagah.

Level 2 — Application

Exercise 2.1 (L2)

Ek 2-way set, pehle empty, LRU use karta hai. Access sequence trace karo: A B A C B. Final cache contents aur misses ki count batao.

Recall Solution

Recency [MRU → LRU] ke roop mein dikhaya gaya hai (freshest → eviction candidate).

Access	Hit/Miss	Cache	Recency (MRU→LRU)
A	✘	[A, –]	[A]
B	✘	[A, B]	[B, A]
A	✔	[A, B]	[A, B]
C	✘ evict B	[A, C]	[C, A]
B	✘ evict A	[C, B]	[B, C]

Misses = 4 (sirf doosra A hit hai). Final contents: {C, B}. C wale step par note karo: B LRU tha (A ko abhi re-hit kiya gaya tha), isliye B evict hota hai — A nahi.

Exercise 2.2 (L2)

Wahi 2-way set aur wahi sequence A B A C B, lekin ab FIFO use karo. Final contents aur miss count?

Recall Solution

Queue [Head(oldest) → Tail(newest)] ke roop mein dikhaya gaya. Hits queue ko untouched chodti hain.

Access	Hit/Miss	Cache	Queue
A	✘	[A, –]	[A]
B	✘	[A, B]	[A, B]
A	✔	[A, B]	[A, B]
C	✘ evict A	[C, B]	[B, C]
B	✔	[C, B]	[B, C]

Misses = 3. Final contents: {C, B}. C wale step mein A evict hota hai — sabse purani insertion — chahe A abhi-abhi hit hua tha. Isse B bach gaya, toh final B ek hit hai. Yahan FIFO, LRU se jeet jaata hai (3 vs 4 misses) sirf pattern ki kismat se.

Exercise 2.3 (L2)

AMAT (Average Memory Access Time) compute karo ek cache ke liye jisme Hit Time = 2 ns, Miss Penalty = 100 ns, aur Miss Rate $4% = 0.04$ hai. Phir, agar ek behtar policy miss rate ko $3%$ tak le jaaye, toh naya AMAT kya hoga aur percentage improvement kya hogi?

Recall Solution

AMAT ka matlab Average Memory Access Time hai — ek memory access mein average kitne time units lagte hain, fast hits aur slow misses ko milaakar.

Formula yaise decompose kyun hota hai. Har access pehle cache try karta hai, isliye hamesha Hit Time pay karta hai. Accesses ka ek fraction (Miss Rate) miss karta hai aur slower level se fetch karna padta hai, upar se Miss Penalty pay karke. Saare accesses ka average lene par, expected extra cost hai (fraction jo miss karti hai) $\times$ (ek miss ki cost) $=$ Miss Rate $\times$ Miss Penalty. Guaranteed hit cost add karo aur milta hai: $AMAT = Hit Time + Miss Rate \times Miss Penalty$ Yeh sirf ek expected value hai: base cost jo sabko pay karni padti hai, plus ek penalty weighted by kitni baar lagti hai.

Values daalo: $AMAT_{4%} = 2 + 0.04 \times 100 = 2 + 4 = 6 ns$ $AMAT_{3%} = 2 + 0.03 \times 100 = 2 + 3 = 5 ns$ Improvement $= \frac{6 - 5}{6} = 0.1 \overline{6} \approx 16.7%$ faster average access. A "mere" 1-percentage-point ki drop in miss rate ne average access time ko ek-sixth se kaat diya — exactly isliye replacement policy matter karti hai. Hit Time kahan se aata hai ke liye 5.4.01-Cache-organizationand-addressing dekho.

Level 3 — Analysis

Exercise 3.1 (L3)

Ek 3-way set LRU use karta hai. A B C A B D E B A trace karo. Miss count aur final set batao.

Recall Solution

Recency [MRU→LRU]. Full set = 3 blocks.

Access	H/M	Cache	Recency
A	✘	{A}	[A]
B	✘	{A,B}	[B,A]
C	✘	{A,B,C}	[C,B,A]
A	✔	{A,B,C}	[A,C,B]
B	✔	{A,B,C}	[B,A,C]
D	✘ evict C	{A,B,D}	[D,B,A]
E	✘ evict A	{B,D,E}	[E,D,B]
B	✔	{B,D,E}	[B,E,D]
A	✘ evict D	{B,E,A}	[A,B,E]

Misses = 6. Final set: {B, E, A}. D wala step dekho: LRU order tha [B,A,C], isliye C (LRU) mar jaata hai. Phir E A ko kick karta hai (A age hokar LRU ban gaya tha). Phir A miss ke roop mein wapas aata hai — LRU ne ise ek step pehle hi discard kar diya tha.

Exercise 3.2 (L3)

Wahi 3-way set, wahi sequence A B C A B D E B A, lekin FIFO. Miss count aur final set? Exercise 3.1 se compare karo.

Recall Solution

Queue [Head→Tail], hits frozen.

Access	H/M	Cache	Queue
A	✘	{A}	[A]
B	✘	{A,B}	[A,B]
C	✘	{A,B,C}	[A,B,C]
A	✔	{A,B,C}	[A,B,C]
B	✔	{A,B,C}	[A,B,C]
D	✘ evict A	{B,C,D}	[B,C,D]
E	✘ evict B	{C,D,E}	[C,D,E]
B	✘	{C,D,E}→{E,D,B}*	[D,E,B]
A	✘ evict D	{E,B,A}	[E,B,A]

*B wale step par queue ka head C hai, isliye C evict hota hai, B us slot mein load hota hai. Misses = 7. Final set: {E, B, A}. Comparison: LRU = 6 misses, FIFO = 7. Yahan LRU jeetta hai kyunki usne exploit kiya ki A aur B reuse ho rahe the (temporal locality — Temporal-and-spatial-locality dekho), jabki FIFO ne A ko insertion order ke hisaab se blindly evict kar diya.

Exercise 3.3 (L3)

Ek paragraph mein explain karo kyun LRU kabhi bhi Belady's Anomaly suffer nahi kar sakta, inclusion property ke idea ka use karke.

Recall Solution

LRU ek stack algorithm hai: kisi bhi moment par, size $k$ ke cache mein jo blocks hain woh hamesha size $k + 1$ ke cache mein jo blocks hote us trace par, uska ek subset hote hain. Formally, saare blocks ko ek bade stack mein recency ke hisaab se order karo; ek size- $k$ cache exactly us stack ke top $k$ blocks rakhta hai. Cache ko $k + 1$ tak badhana sirf agla block add karta hai — chhote cache ne jo rakha tha woh kabhi remove nahi hota. Isliye koi bhi block jo $k$ frames mein hit tha woh $k + 1$ frames mein bhi hit rahega. Hits sirf add ho sakte hain, kabhi lose nahi ho sakte $\Rightarrow$ misses capacity mein monotonically non-increasing hain. FIFO mein yeh property nahi hai kyunki uska "stack" (insertion order) capacity badhne par nest nahi karta.

Level 4 — Synthesis

Exercise 4.1 (L4)

FIFO ke liye Belady's Anomaly reproduce karo. Classic reference string 1 2 3 4 1 2 5 1 2 3 4 5 aur fully-associative cache (ek set) use karke, dikhao ki 3 frames mein 4 frames se kam misses hote hain. Dono miss counts report karo.

Recall Solution — 3 frames

Queue [Head→Tail]. ✘ = miss.

Ref	H/M	Frames	Evict
1	✘	{1}	–
2	✘	{1,2}	–
3	✘	{1,2,3}	–
4	✘	{2,3,4}	1
1	✘	{3,4,1}	2
2	✘	{4,1,2}	3
5	✘	{1,2,5}	4
1	✔	{1,2,5}	–
2	✔	{1,2,5}	–
3	✘	{2,5,3}	1
4	✘	{5,3,4}	2
5	✔	{5,3,4}	–

3-frame misses = 9.

Recall Solution — 4 frames

Ref	H/M	Frames	Evict
1	✘	{1}	–
2	✘	{1,2}	–
3	✘	{1,2,3}	–
4	✘	{1,2,3,4}	–
1	✔	{1,2,3,4}	–
2	✔	{1,2,3,4}	–
5	✘	{2,3,4,5}	1
1	✘	{3,4,5,1}	2
2	✘	{4,5,1,2}	3
3	✘	{5,1,2,3}	4
4	✘	{1,2,3,4}	5
5	✘	{2,3,4,5}	1

4-frame misses = 10.

Result: 3 frames mein 9 misses vs 4 frames mein 10 misses — zyada cache, zyada misses. Yahi Belady's Anomaly hai. Neeche figure dono curves plot karta hai taaki tum crossover dekh sako.

Figure — Replacement policies (LRU, FIFO, random)

Exercise 4.2 (L4)

Usi reference string 1 2 3 4 1 2 5 1 2 3 4 5 par, LRU ko 3 frames aur 4 frames ke saath run karo. Confirm karo ki LRU stack property obey karta hai (misses zyada frames ke saath increase nahi hote).

Recall Solution — LRU, 3 frames

Recency [MRU→LRU]. Full set = 3 blocks.

Ref	H/M	Frames	Recency (MRU→LRU)	Evict
1	✘	{1}	[1]	–
2	✘	{1,2}	[2,1]	–
3	✘	{1,2,3}	[3,2,1]	–
4	✘	{2,3,4}	[4,3,2]	1
1	✘	{3,4,1}	[1,4,3]	2
2	✘	{4,1,2}	[2,1,4]	3
5	✘	{1,2,5}	[5,2,1]	4
1	✔	{1,2,5}	[1,5,2]	–
2	✔	{1,2,5}	[2,1,5]	–
3	✘	{2,5,3}	[3,2,5]	1
4	✘	{5,3,4}	[4,3,5]	2
5	✔	{5,3,4}	[5,4,3]	–

✘ rows count karo: refs 1,2,3,4 (4 misses), phir 1,2,5 (3 aur = 7), phir 3,4 (2 aur = 9). Final 5 ek hit hai. LRU 3-frame misses = 9. Teeno ✔ rows mid-sequence mein blocks 1 aur 2 par hits hain (steps 8, 9) aur 5 par final hit (step 12).

Recall Solution — LRU, 4 frames

Ref	H/M	Frames	Recency (MRU→LRU)	Evict
1	✘	{1}	[1]	–
2	✘	{1,2}	[2,1]	–
3	✘	{1,2,3}	[3,2,1]	–
4	✘	{1,2,3,4}	[4,3,2,1]	–
1	✔	{1,2,3,4}	[1,4,3,2]	–
2	✔	{1,2,3,4}	[2,1,4,3]	–
5	✘	{1,2,4,5}	[5,2,1,4]	3
1	✔	{1,2,4,5}	[1,5,2,4]	–
2	✔	{1,2,4,5}	[2,1,5,4]	–
3	✘	{1,2,3,5}	[3,2,1,5]	4
4	✘	{1,2,3,4}	[4,3,2,1]	5
5	✘	{2,3,4,5}	[5,4,3,2]	1

✘ rows count karo: 1,2,3,4 (4) phir 5 (5) phir 3,4,5 (3 aur = 8). LRU 4-frame misses = 8.

Check: 3-frame LRU = 9 misses, 4-frame LRU = 8 misses. Kyunki $8 \leq 9$ hai, misses capacity ke saath increase nahi hue — stack property hold karti hai, exactly jaisa Exercise 3.3 predict karta hai. FIFO anomaly (9 → 10) ko LRU ke clean 9 → 8 se compare karo.

Level 5 — Mastery

Exercise 5.1 (L5)

Repeating pattern A B A B A B … consider karo. Ek 2-way set jisme pehle se {A, B} hai, har access ek hit hai — kabhi koi eviction nahi. Ab wahi pattern A B A B … ke liye 1-way (direct-mapped) version consider karo, yaani ek slot jiske liye A aur B compete karte hain. 1-way cache par is pattern ki miss rate kya hai, aur kya policy choice (LRU / FIFO / Random) isse badalta hai?

Recall Solution

1 slot ke saath, A aur B har access par conflict karte hain: A load karna B evict karta hai, B load karna A evict karta hai. Kyunki consecutive accesses hamesha alag hain (A, B, A, B…), har access ek miss hai. $Miss rate = 100% = 1.0$ Policy irrelevant hai: evict karne ke liye sirf ek candidate hai, toh LRU, FIFO aur Random teeno wahi (ek hi) block evict karte hain. Miss rate teeno ke liye $1$ hai. Lesson: replacement policy sirf tab matter karti hai jab victim ka koi choice ho, yaani associativity $\geq 2$ ho. Ek pathological conflict (working set > ways) har policy ko defeat karta hai — software isse kaise avoid karta hai ke liye Working-set-model aur Cache-conscious-programming dekho.

Exercise 5.2 (L5)

Random ka expected-value analysis. Ek 4-way set ${B_{1}, B_{2}, B_{3}, B_{4}}$ blocks ke saath full hai. Unme se exactly ek, maano $B_{1}$ , woh block hai jo agle time chahiye hoga (current miss ka naya block load hone ke baad). Assume karo $B_{1}$ most-recently-used block bhi hai. Random replacement ke under, hum $B_{1}$ (jaldi chahiye hone wala block) ko evict karne aur ek extra future miss cause karne ki probability kya hai? Ideal LRU se compare karo.

Recall Solution

Random 4 ways mein se har ek ko equal probability se pick karta hai, isliye $P_{Random} (evict B_{1}) = \frac{1}{4} = 0.25.$ Random yahan $25%$ time galat choice karta hai.

Ideal LRU: hume bataya gaya hai ki $B_{1}$ most-recently-used block hai. LRU hamesha least-recently-used block evict karta hai, jo $B_{2}, B_{3}, B_{4}$ mein se koi ek hoga — MRU block kabhi nahi. Isliye $P_{LRU} (evict B_{1}) = 0.$

Comparison: Random ke paas hot block throw away karne ki $0.25$ probability hai; LRU ke paas $0$ hai. Yeh gap — self-inflicted extra misses ka $25%$ vs $0%$ — exactly woh payoff hai jo history track karne ka milta hai. LRU hardware bits spend karta hai yeh protection khareedne ke liye, aur yeh tab payoff karta hai jab temporal locality hold karti hai (jo block abhi use hua woh sach mein dobara chahiye hone ki zyada probability hai).

Exercise 5.3 (L5)

Design synthesis. Tumhe ek low-power embedded core ke L1 data cache ke liye replacement policy choose karni hai: 4-way associative, tight bit budget, hard real-time latency requirement (har access fixed number of cycles mein complete hona chahiye). Argue karo ki kaun si policy choose karni chahiye aur har requirement ke against justify karo.

Recall Solution

Recommended: tree pseudo-LRU (ya plain FIFO agar bits sach mein scarce hain).

Bit budget: exact LRU ko $4 \times 2 = 8$ bits/set chahiye; tree pseudo-LRU ko $3$ bits/set chahiye; FIFO ko $2$ bits/set chahiye. Pseudo-LRU $3$ bits mein exact-LRU miss rate ke kaafi close hai — bits-vs-performance ka ek strong point.
Real-time latency: teeno (LRU counter update, FIFO pointer, pseudo-LRU bit-flip) hardware mein O(1) constant-time hain — koi bhi policy pipeline stall nahi karti, isliye fixed-cycle requirement inme se kisi se bhi meet hoti hai.
Miss rate: locality-rich embedded workloads par pseudo-LRU, FIFO ko beat karta hai (jo Belady-style bad phases risk karta hai) aur Random ke $\sim 25%$ mis-evictions ko bhi beat karta hai.
Jab FIFO jeetta hai: agar silicon area dominant constraint hai aur workloads streaming hain (little reuse, isliye LRU ki history kuch nahi khareedti), toh FIFO ka 2-bit cost optimal hai. Verdict: tree pseudo-LRU choose karo — 3 bits, constant-time, near-LRU miss rate, koi anomaly worries nahi. 5.4.03-Write-policies-(write-through,-write-back) mein write-behavior sizing aur 5.4.06-Cache-coherence-protocols mein multi-core effects se relate karo.