Replacement policies (LRU, FIFO, random): Visual walkthrough

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

Yeh page teen replacement policies — LRU, FIFO, aur Random — ko sirf boxes ki ek row se build karta hai. Hum dekhenge ki har policy apna choice kaise karti hai, ek access at a time, aur phir dekhenge FIFO kuch aisa karta hai jo impossible lagta hai — jab usse zyada room milta hai toh woh worse ho jaata hai. Har symbol pehle samjhaya jaata hai, phir use kiya jaata hai.

Step 1 — Shelf, slots, aur ek word jo hum har jagah reuse karenge

KYA. Cache ko boxes ki ek row ki tarah draw karo. Har box ko way kehte hain — yeh ek physical slot hai jo ek block (memory ka ek chunk jitna cache move karta hai) hold kar sakta hai. $n$ boxes wale set ko == $n$ -way associative== kehte hain. Yahan $n = 4$ hai.

KYU. Har policy jo hum study karte hain woh sirf ek sawaal ka alag jawaab hai: "chaar boxes full hain aur block $E$ andar aana chahta hai — kaun sa box khaali kiya jaayega?" Jab tak hum chaar boxes nahi dekh sakte, yeh sawaal pooch hi nahi sakte.

PICTURE (Figure s01). Chaar khaali boxes labelled way 0 … way 3, incoming stream $A, B, C, D, A, E$ ko ek orange queue ke roop mein unke upar draw karo aur "time →" arrow ke saath. Yeh access sequence hai, woh order jisme processor blocks maangta hai. Hum yeh same sequence LRU aur FIFO dono ko denge taaki difference purely policy ka ho.

Figure — Replacement policies (LRU, FIFO, random)

Figure s01 — Ek fresh 4-way set: neeche chaar khaali boxes (way 0 se way 3 tak), upar access sequence A B C D A E ek orange queue ke roop mein, left se right time mein flow karti hui.

Ek single request hit hoti hai agar block already kisi box mein hai, ya miss hoti hai agar nahi hai — aur full set par miss hi eviction (ek box khaali karna) force karti hai. Dekho 5.4.01-Cache-organizationand-addressing jisme bataya gaya hai ki address kaise decide karta hai ki kaun sa set choose hoga.

Step 2 — LRU ka ruler: recency counter, aur operations ka exact order

KYA. Har occupied box ko uske neeche ek chota number do: uska recency. Recency $0$ matlab "abhi touch kiya, sabse fresh block." Bada number matlab "zyada stale." Hum ise ek rule se update karte hain, aur — crucially — hum miss handle karne ka exact sequence fix karte hain.

KYU. LRU (Least Recently Used) uss block ko phenkna chahta hai jise sabse zyada time se kisi ne touch nahi kiya. Uske liye usse "kitne time pehle" measure karne ka tarika chahiye — recency woh ruler hai. Poore past ko measure karna kyun? temporal locality ki wajah se: haal mein use kiya gaya block dobara use hone ki sambhavna zyada hoti hai, isliye least recently used ko discard karna sabse safe hai. Lekin ruler akela policy nahi hoti: humein yeh bhi batana hoga ki hum ise kab read karte hain, counters ko kab age karte hain, aur brand-new block ko kya number milta hai.

PICTURE (Figure s02). Update rule seedha boxes se padho, phir neeche diya operational recipe padho.

Definition Ek access par operations ka exact order (yeh saari ambiguity door karta hai)

Jab access $t$ aaye, yeh in is order mein karo — evict-then-update:

Hit? Agar block already kisi box mein hai, woh box "time $t$ par accessed wali" hai: uski recency $0$ set karo, baaki har occupied box ko $+ 1$ se age karo (capped at $n - 1$ ), ho gaya. Koi eviction nahi.
Miss with an empty way? Block ko lowest-numbered empty way mein load karo. Phir us box ko "accessed wali" treat karo: uski recency $0$ set karo aur baaki har occupied box ko $+ 1$ se age karo. Koi eviction nahi.
Miss with a full set? Pehle current recencies padho aur victim choose karo = sabse badi recency wala box. Phir woh box khaali karo, nayi block usme load karo, aur finally update apply karo: nayi block ki recency $0$ set karo aur baaki har box ko $+ 1$ age karo.

Brand-new block ko kaunsi recency milti hai? Hamesha $0$ — yeh, by definition, abhi access hua tha. Toh update tab apply hoti hai jab victim choose ho chuka hota hai, pehle nahi.

Figure s02 — LRU ka ruler: chaar boxes mein se har ek recency counter carry karta hai; green recency 0 (freshest) mark karta hai, red recency n−1 = 3 (oldest, the victim). Red down-arrow dikhata hai ki maximum recency wala box evict ho raha hai.

Step 3 — Watch karo LRU sequence A B C D A E run karta hai

KYA. $A, B, C, D, A, E$ ko chaar boxes ko do, har access fully handle hone ke baad har box ke neeche recency number draw karo (Step 2 ka evict-then-update recipe follow karte hue).

KYU. Yeh Step 2 ka payoff hai — hum dekhte hain counters age hote hain, $A$ par hit $A$ ko $0$ par reset karti hai, nayi block ka counter likhne se pehle victim choose hota hai, aur nayi block $E$ recency $0$ ke saath enter karti hai. Dhyan do ki pehle chaar accesses sirf empty ways fill karte hain; jab tak set full na ho tab tak koi eviction nahi hoti.

PICTURE (Figure s03). Coloured strip follow karo. Star eviction mark karta hai.

Access	Boxes (way0…way3)	Recency after	Kya hua
$A$	$A, -, -, -$	$0, -, -, -$	miss, empty way 0 → load $A$ , uski recency 0 set karo
$B$	$A, B, -, -$	$1, 0, -, -$	miss, empty way 1 → load $B$ (rec 0), $A$ ages to 1
$C$	$A, B, C, -$	$2, 1, 0, -$	miss, empty way 2 → load $C$ (rec 0), $A, B$ age
$D$	$A, B, C, D$	$3, 2, 1, 0$	miss, empty way 3 → load $D$ (rec 0), set ab full
$A$	$A, B, C, D$	$0, 3, 2, 1$	$A$ par hit → $A$ ko 0 reset karo, baaki $+ 1$ age
$E$	$A, E, C, D$	$1, 0, 3, 2$	miss, full → evict $⋆ B$ , load $E$ (rec 0), baaki $+ 1$ age

Aakhri row dhyaan se padhna (yeh fix hai). $E$ handle karne se pehle, recencies hain $A = 0, B = 3, C = 2, D = 1$ . Recipe follow karte hue:

Pehle victim choose karo in current values se: maximum $B = 3$ hai, toh ==LRU $B$ ko evict karta hai== (way 1). $A$ par recent hit ne use bacha liya.
Phir $E$ ko way 1 mein load karo aur update apply karo: $E$ ko recency $0$ milta hai; baaki har box $+ 1$ age hoti hai, toh $A : 0 \to 1$ , $C : 2 \to 3$ , $D : 1 \to 2$ .

Isse final row milti hai $[A = 1, E = 0, C = 3, D = 2]$ , yaani ways $0, 1, 2, 3$ par $[1, 0, 3, 2]$ . (Pichle draft mein $[1, 0, 2, 3]$ likha tha; woh sirf "update-then-evict" ordering mein sahi hota, jise humne explicitly reject kiya — hum survivors ko victim choose karne ke baad age karte hain, toh $C$ , $D$ se older hone ki wajah se, stalest survivor $3$ par end hota hai.)

Figure s03 — A B C D A E par LRU, chhe columns (ek per access). Har column way 0 se way 3 top to bottom dikhata hai apne recency number ke saath; $A$ par hit use 0 reset karti hai, aur final column $B$ evict karta hai (red, starred) aur $E$ recency 0 par enter karti hai.

Step 4 — FIFO ka ruler: ek single pointer, aur hits kuch nahi badlate

KYA. Chaar recency counters phenko. Poore set ke liye sirf ek number rakho: queue pointer, jise $QueuePtr$ likhte hain, jo bas yaad rakhta hai "kaun sa box aage khaali hoga." Yeh fresh, khaali set par $QueuePtr (0) = 0$ se start hota hai — pointer way 0 par shuru hota hai.

KYU. FIFO (First-In First-Out) arrival order se evict karta hai — pehle andar aaya woh pehle bahar jaata hai, jaise lunch queue. Yeh kabhi nahi dekhta ki block dobara use hua ya nahi. Koi hits ko ignore karne wali policy kyun chahega? Cost: FIFO ko sirf $⌈ lo g_{2} n ⌉$ bits per set chahiye instead of ek counter per box — $n = 4$ ke liye woh ek single 2-bit number hai.

PICTURE (Figure s04). Pointer chaar boxes ke around circle mein ghoomta hai.

Formula FIFO pointer update

$QueuePtr (t + 1) = {(QueuePtr (t) + 1) mod n QueuePtr (t) if this access is a miss that loads a block if this access is a hit$

$QueuePtr$ — arrow; yeh kya karta hai: us box ko point karta hai jo next mein ek block receive karega (aur, jab set full ho, woh box jo pehle evict hoga).
$+ 1$ — ek block load karne ke baad (chahe empty way mein ho ya evicted victim par), next box par step karo.
$mod n$ — box $n - 1$ se box $0$ par wrap karo, boxes ko circle banana.
bottom line — ek hit arrow ko frozen rakhti hai. FIFO ki poori personality yahi hai.

Pointer sirf evictions par nahi, har load par kyun advance karta hai: arrow arrival order mark karta hai. Jab set fill hoti hai (accesses jo empty ways mein load karte hain), arrow aage step karta hai yeh record karne ke liye ki agla arrival kahan jaayega. Jab set full ho jaati hai, arrow usi rhythm mein step karta rehta hai — ab har step oldest survivor ko victim bhi naam karta hai. Dono phases "ek block load hua" hain, isliye dono pointer 1 se advance karte hain; sirf hits use freeze karti hain. FIFO ko tie-break ki zaroorat nahi: single pointer hamesha exactly ek box naam karta hai.

Figure s04 — FIFO ka ruler: ek orange arrow (queue pointer) way 0 par start hota hai, chaar boxes ke around clockwise ghoomta hai. Ek curved gray arrow way 3 se way 0 par circular wrap dikhata hai.

Step 5 — Watch karo FIFO same sequence A B C D A E run karta hai

KYA. Same input, same boxes, lekin ab sirf state arrow hai, $QueuePtr (0) = 0$ se start karta hai.

KYU. Dono policies mein identical stream run karne se difference sirf ek decision par isolate hoti hai. $A$ par hit kuch nahi karti, yeh dekho.

PICTURE (Figure s05). Arrow orange marker hai; star eviction hai.

Access	Boxes	QueuePtr after	Kya hua
$A$	$A, -, -, -$	1	miss, empty way 0 mein load, arrow steps →1
$B$	$A, B, -, -$	2	miss, empty way 1 mein load, arrow →2
$C$	$A, B, C, -$	3	miss, empty way 2 mein load, arrow →3
$D$	$A, B, C, D$	0	miss, empty way 3 mein load, arrow wraps →0
$A$	$A, B, C, D$	0	$A$ par hit — arrow frozen, kuch nahi move kiya
$E$	$E, B, C, D$	1	miss, set full, arrow=0 → way 0 ( $⋆ A$ ) evict, $E$ load, arrow →1

Kaun sa box mara? Arrow way 0 par tha, jisme $A$ tha. Toh ==FIFO $A$ ko evict karta hai== — bilkul wahi block jo LRU ne abhi bachaya tha. FIFO ne recent hit kabhi notice nahi ki. Dhyan do ki pointer paanchon loads (chaar fills aur eviction) par advance hua lekin ek hit par khada raha — bilkul Step 4 wala rule.

Figure s05 — Same stream par FIFO, chhe columns. Orange arrow har access ke baad QueuePtr dikhata hai; $A$ -hit column mein arrow move nahi karta, aur $E$ column mein way 0 ( $A$ , red, starred) evict hota hai aur 1 par step karta hai.

Step 6 — Teesri policy: Random, koi ruler hi nahi

KYA. Random replacement koi bhi history nahi rakhta — na recency counters, na queue pointer. Full set mein miss par woh uniformly at random ek victim choose karta hai (har box equally likely) aur usse overwrite karta hai. Empty way mein miss par woh abhi bhi lowest empty way fill karta hai (Step 1 ka shared insertion rule); sirf jab set full ho tab randomness kaam aati hai. Hits kuch nahi karte.

KYU. Jab tum predict nahi kar sakte future, tum guess karne se mana kar dete ho aur coin flip karte ho. Yeh dono alternatives se sasta hai — ek tiny pseudorandom bit source, zero per-block state — aur yeh un pathological patterns se immune hai jo FIFO ko trap karte hain (Step 8), kyunki uska koi rhythm nahi hai jise pattern fight kar sake.

PICTURE (Figure s06). Chaar full boxes; ek spinner uss box ki taraf point karta hai jo coin flips choose karta hai. Usi $A, B, C, D, A, E$ stream par, $E$ miss par Random $A, B, C, D$ mein se kisi bhi ko evict kar sakta hai — har ek probability $\frac{1}{4}$ ke saath. Koi single "the answer" nahi hai: yahi poora point hai.

Figure s06 — Random replacement: chaar full boxes A,B,C,D mein se har ek $p = 1/4$ labelled hai, centre mein ek orange spinner ek box ki taraf point karta hai — $E$ miss par uniformly random victim.

Step 7 — Ek yardstick taaki hum miss counts compare kar sakein

KYA. Miss rate clearly define karo: accesses ka woh fraction jo misses the. Aur ise memory ki cost ke andar place karo.

KYU. Hum kehte rehte hain ek policy "better" hai. Better matlab fewer misses, kyunki misses slow hote hain. Yeh step humein yardstick deta hai finale se pehle.

PICTURE (Figure s07). Ek bar jisme hit time ek chota green segment hai aur miss penalty ek lamba red segment; miss rate yeh measure karta hai ki tum red wala kitni baar pay karte ho.

Figure s07 — Bar ke roop mein AMAT: ek chota green "Hit Time" segment phir ek lamba red "Miss Penalty" segment jo Miss-Rate fraction of the time pay hota hai. Kam miss rate matlab kam red penalties.

Naively aap sochenge: zyada boxes → zyada blocks kept → kam misses. LRU ke liye yeh guaranteed true hai — aur iska reason ek naam hai jo hum abhi define karte hain, anomaly se pehle, kyunki yeh poori explanation hai.

Definition Fully associative, aur stack-algorithm property (inhe use karne se pehle define kiya)

Fully associative ::: ek cache (ya ek single "frame pool") jisme koi bhi block kisi bhi slot mein reh sakta hai — exactly ek set hai jisme saare slots hain, toh ek block har doosre block ke saath compete karta hai, sirf un logon ke saath nahi jo ek set mein map karte hain. Steps 8–9 mein hum "frames" ka ek fully-associative pool use karte hain (frame = us ek bade set mein ek slot) taaki sirf replacement policy evictions decide kare, bina address-mapping ke count muddy kiye.
Stack algorithm ::: ek replacement policy stack algorithm hai agar, har access sequence ke liye, size $k$ ke cache mein woh jo blocks rakhta hai woh hamesha size $k + 1$ ke cache mein jo blocks rakhta hai uska subset ho. Simple words: ek bada cache woh sab kuch rakhta hai jo chote wale ne rakha tha, plus zyada — woh kabhi koi block nahi drop karta jo chote wale ne rakha tha.
- LRU ek stack algorithm hai → ek bada cache sirf misses remove kar sakta hai, add nahi kar sakta → LRU ko kabhi Belady's Anomaly nahi ho sakta.
- FIFO nahi hai stack algorithm → uski size- $k$ contents size- $(k + 1)$ contents se arbitrarily differ kar sakti hain → anomaly possible hai, jaise Steps 8–9 dikhayenge.

Step 8 — Belady's Anomaly, 3 frames: 9 misses

KYA. Fully-associative FIFO use karo (abhi define kiya: ek bada frames ka pool, koi bhi block kisi bhi frame mein) classic stream ke saath $1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5$ aur teen frames ke saath. Misses count karo.

KYU. Yeh anomaly ka setup half hai. Humein pehle 3-frame count chahiye taaki 4-frame count se compare kar sakein.

PICTURE (Figure s08). Baara columns, har ek woh access ke baad hit/miss verdict dikhata hai; misses red mein marked.

FIFO trace karo (pehle empty frames fill karo, phir oldest arrival evict karo; hits reorder nahi karte):

step	1	2	3	4	1	2	5	1	2	3	4	5
hit/miss	M	M	M	M	M	M	M	H	H	M	M	H

Yeh hai 9 misses 12 mein se. $1$ aur $2$ par do hits end ke paas woh hain jo ise bachate hain.

Figure s08 — Classic stream par 3-frame fully-associative FIFO. 12 columns mein se har ek requested block hai, red boxes = miss, green = hit; tally 9 misses padhta hai.

Step 9 — Belady's Anomaly, 4 frames: 10 misses (impossible-feeling result)

KYA. Same stream, same fully-associative FIFO, ab chaar frames ke saath. Phir se misses count karo.

KYU. Humne capacity add ki — ek aur frame — expecting ki misses kam honge. Dekho yeh worse ho jaata hai. Yeh degenerate case hai jo "bigger is always better" intuition ko tod deta hai, aur yeh exactly isliye possible hai kyunki FIFO stack algorithm nahi hai (Step 7).

PICTURE (Figure s09). Same baara columns, ek extra frame; extra room shift karta hai kaun sa block har eviction par oldest hai, toh blocks theek reuse hone se pehle pheke jaate hain.

step	1	2	3	4	1	2	5	1	2	3	4	5
hit/miss	M	M	M	M	H	H	M	M	M	M	M	M

Yeh hai 10 misses — teen frames se ek zyada.

Figure s09 — Identical stream par 4-frame fully-associative FIFO. s08 jaisa same red/green column layout, lekin tally ab 10 misses padhta hai — 3-frame cache se worse.

Ek-picture summary

KYA. Ek figure jo teeno verdicts stack karta hai: same stream, LRU vs FIFO vs Random victims side by side, plus anomaly bars $9 \to 10$ .

KYU. Is page par sab kuch do facts par reduce hota hai — har policy kaun sa ruler use karti hai, aur kya hota hai jab ruler usage ignore karta hai.

Figure s10 — Poora page compressed: teen labelled boxes (LRU→evicts B using USAGE, FIFO→evicts A using ARRIVAL, Random→any of A–D using NOTHING) left par, aur right par do bars jo FIFO ke 9 misses ko 3 frames par 10 misses at 4 frames tak badhte dikhate hain — woh anomaly jo LRU ki stack property forbid karti hai.

Recall Feynman retelling — plain words mein wapas bolo

Chaar slots wali ek shelf ki picture lo. Jab tak shelf mein khaali slots hain, har policy wahi boring kaam karti hai: nayi book next khaali slot mein daal do. Interesting decision sirf tab hoti hai jab shelf full ho aur ek nayi book aaye — ek book girni chahiye.

LRU har book ke neeche ek chota "last touched" number likhta hai. Jab miss eviction force karti hai, woh pehle woh numbers padhta hai aur sabse zyada ignore ki gayi book choose karta hai, phir newcomer ko us jagah load karta hai aur use fresh stamp karta hai (number 0) jabki baaki har book ek se age hoti hai. Ek book dobara padhna uska number reset karta hai, toh dobara padhna use protect karta hai. Hamare run mein, $A$ dobara padhne ka matlab tha $B$ (sabse zyada time se untuched) gir gaya — aur baad mein $C$ , older survivor, stalest survivor $3$ par ban gaya.

FIFO lazier aur sasta hai: woh ek arrow rakhta hai jo bas yaad rakhta hai kiska jaane ka waqt hai, strictly arrival order se. Arrow slot 0 par start hota hai aur har baar jab ek book load hoti hai aage step karta hai, shelf ke around circle mein wrap karta hai; ek book dobara padhna uske liye kuch nahi karta. Toh exact same run mein, $A$ — woh book jise humne abhi dobara padha tha — dhakke se bahar nikal gayi, kyunki woh pehle aayi thi.

Random koi notes nahi rakhta: jab shelf full ho woh coin flip karta hai aur coin jo slot naam karti hai use evict kar deta hai. Sabse sasta, kabhi kabhi unlucky, lekin impossible hai trap karna.

Phir twist: FIFO ke saath, shelf ko ek paanchwa slot dene se ek nasty repeating stream par zyada books girine lagin (10 instead of 9), kyunki extra slot ne arrow ki rhythm shift kar di taaki books theek unse ek step pehle phenki jaayein jab chahiye thi. Yahi Belady's Anomaly hai. LRU is tarah kabhi behave nahi kar sakta — yeh ek "stack algorithm" hai, matlab ek bada cache hamesha woh sab kuch rakhta hai jo chote wale ne rakha — aur yahi reason hai ki hardware LRU-style rules par rely karta hai unki higher cost ke bawajood.

Ek line: LRU usage measure karta hai (safe, expensive); FIFO sirf arrival measure karta hai (cheap, zyada memory milne par worse hone mein trickable); Random kuch nahi measure karta (cheapest, coin-flip).

Recall Quick self-test

Jab set mein abhi bhi empty ways hain, miss par har policy kya karti hai? ::: The same thing — fill the lowest-numbered empty way; no eviction. Policies sirf tab differ karti hain jab set full ho. On an LRU full-set miss, do we choose the victim before or after writing the new block's recency? ::: Before — evict-then-update: recencies padho, max ko victim choose karo, nayi block load karo, phir ise 0 set karo aur survivors ko age karo. LRU ke under freshly loaded block ko kaunsi recency milti hai? ::: 0 — yeh definition se abhi access hua tha. Step 5 mein $A$ par hit ke baad, FIFO next miss par kaun sa block evict karta hai, aur kyun? ::: $A$ (way 0) — queue pointer 0 par baitha tha aur FIFO hit ignore karta hai; sirf arrival order decide karta hai. LRU Belady's Anomaly kyun kabhi nahi dikha sakta? ::: LRU ek stack algorithm hai — uski size- $k$ contents hamesha uski size- $(k + 1)$ contents ka subset hoti hain, toh zyada capacity sirf misses remove kar sakti hai, add nahi kar sakti. A,B,C,D,A,E mein LRU kaun sa block evict karta hai, aur $A$ kyun nahi? ::: $B$ ; $A$ par hit ne $A$ ki recency 0 reset kar di, $B$ (recency 3) ko least recently used bana diya. Same stream par, $E$ miss par Random kaun sa block evict karta hai? ::: $A, B, C, D$ mein se koi bhi, har ek probability $\frac{1}{4}$ ke saath — Random koi history nahi rakhta, toh koi single answer nahi hai.

Related depth: exact vs pseudo-LRU cost trade-offs Cache-conscious-programming mein tie in hote hain; policies 5.4.03-Write-policies-(write-through,-write-back), 5.4.06-Cache-coherence-protocols ke saath interact karti hain, aur 5.5.02-Virtual-memory-and-TLBs mein page frames ke liye dobara aate hain.