Replacement policies (LRU, FIFO, random): Question bank

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

Yeh page tumhari intuition ke liye ek workout hai, arithmetic ke liye nahi. Neeche har item ek aisi jagah ko target karta hai jahan replacement policies padhne wale students aksar phisalte hain — koi hidden assumption, koi boundary case, ya koi "sach lagta hai lekin hai nahi" wala claim. Answer ko cover karo, pehle guess karo, phir reveal karo.

Shuru karne se pehle, ek quick vocabulary anchor taaki neeche koi bhi symbol aisa na ho jo tumne earn nahi kiya:

Woh ek idea jo neeche ke aadhe traps generate karta hai:

True or false — justify karo

Har baar reason do, sirf haan/nahi kabhi mat bolna.

TF1. "LRU aur FIFO hamesha same block evict karte hain."

False. Ye sirf tab agree karte hain jab insertions ke beech koi hit na ho; ek hit LRU ki recency list ko reorder karta hai lekin FIFO ki insertion queue ko untouched chhod deta hai, isliye hit ke baad ye alag-alag victims ko point kar sakte hain.

TF2. "Cache hit par, FIFO ko apna queue pointer update karna chahiye."

False. FIFO hits ko bilkul ignore karta hai — pointer sirf eviction par aage badhta hai. Yahi obliviousness FIFO ko cheap banati hai aur isliye woh ek freshly-used block ko bhi evict kar sakta hai.

TF3. "Bada cache kabhi bhi miss rate nahi badha sakta."

False for FIFO. Yeh Belady's Anomaly hai: FIFO bade cache ke saath zyada miss kar sakta hai kyunki extra capacity uske circular queue ke phase ko access pattern ke relative mein shift kar deti hai. LRU ke liye yeh sach HAI, jo ek stack algorithm hai.

TF4. "Random replacement mein history track karne ke liye koi hardware nahi, isliye usse bilkul bhi state nahi chahiye."

Mostly true, ek caveat ke saath. Yeh koi per-block recency ya insertion info store nahi karta, lekin isse ek chota pseudorandom source chahiye hota hai (jaise ek linear-feedback shift register) jo sets mein shared ho victim chunne ke liye.

TF5. "4-way set mein Exact LRU ke liye sirf 3 bits chahiye."

False — woh pseudo-LRU hai. Exact LRU ko 4 blocks order karne hote hain, roughly

lo g_{2} (4!) \approx 5

bits (ya naive counter method se

4 \times 2 = 8

bits). 3-bit (

n - 1

) figure tree-based approximation hai.

TF6. "Direct-mapped cache mein replacement policy koi farak nahi padti."

False. Direct-mapped cache 1-way hota hai: har address ka exactly ek possible slot hota hai, isliye evict karne ke liye sirf ek hi candidate hota hai. LRU, FIFO, aur Random sabhi ek hi forced eviction pe reduce ho jaate hain.

TF7. "LRU hamesha miss rate mein FIFO se aage rehta hai."

False. LRU aksar jeetta hai, lekin kuch access patterns ke liye FIFO tie kar leta hai ya thoda aage bhi nikal jaata hai; LRU ka advantage typical-case mein hai aur Belady's Anomaly na hone ki guarantee mein, nahi ki universal miss-rate dominance mein.

TF8. "Replacement policy AMAT ke hit time term ko affect karti hai."

False (essentially). Policy miss rate badlati hai, aur

AMAT = Hit Time + Miss Rate \times Miss Penalty

mein yeh middle term ko move karti hai. Hit time array/tag lookup se set hoti hai, na ki is baat se ki tum kaun sa block evict karoge.

TF9. "LRU ek accha idea hai kyunki yeh future predict karta hai."

Half-true. LRU predict nahi karta — yeh past ke repeat hone par bet lagata hai, temporal locality exploit karta hai. Jab locality absent ho (jaise ek streaming scan jo cache se bada ho), woh bet buri tarah harti hai.

Error dhundho

Har statement mein ek concrete mistake hai. Use naam do.

SE1. "Access sequence A, B, A, C mein 2-way set ke liye, FIFO B ko evict karta hai."

Wrong victim. FIFO sabse pehle inserted block ko evict karta hai, jo A hai — A par hit use bachata nahi. LRU B ko evict karta; student ne dono policies ko swap kar diya.

SE2. "Pseudo-LRU exact same victim track karta hai jaise true LRU, bas kam bits ke saath."

'Exact same' galat hai. Tree-based pseudo-LRU ek approximation hai; yeh kabhi-kabhi alag (sach mein sabse purana nahi) block choose kar sakta hai. Yeh "close enough" hai, identical nahi.

SE3. "FIFO ko insertion order yaad rakhne ke liye har block ke liye ek counter chahiye."

Over-built. FIFO ko ek chota

⌈ lo g_{2} n ⌉

-bit pointer per set chahiye, per block nahi — akela pointer hi next victim ko identify karta hai jab yeh ways se cycle karta hai.

SE4. "Random replacement ke saath, miss rate unpredictable hai aur isliye real chips ke liye useless hai."

Wrong conclusion. Random ka per-run victim unpredictable hai, lekin uski average miss rate stable hoti hai aur aksar LRU ke kaafi kareeb hoti hai — isliye yeh real high-associativity caches mein use hota hai jahan LRU bahut expensive ho.

SE5. "Abhi-accessed block ke liye LRU ka recency counter

n - 1

set hona chahiye."

Ulta hai. Abhi-accessed block most recently used hai, isliye uski recency

0

par reset hoti hai; victim woh block hai jiska recency

n - 1

ke barabar hai.

SE6. "Belady's Anomaly prove karta hai ki zyada capacity ke saath LRU bhi worse ho sakta hai."

Misattributed. Yeh anomaly FIFO (aur non-stack policies) ki property hai. LRU ek stack algorithm hai aur guaranteed monotone hai — zyada capacity uski miss count kabhi nahi badhati.

SE7. "Write par, LRU recency update nahi karta kyunki writes reads nahi hain."

False distinction. LRU recency kisi bhi access par update karta hai, read ya write. Yeh write policies ke saath interact karta hai lekin recency touch hamesha hota hai.

Why questions

WHY1. FIFO hits se oblivious kyun rehta hai jabki LRU unpar react karta hai?

Kyunki ye dono alag questions ka jawab dete hain: FIFO arrival time track karta hai (jab block enter karta hai tab se fixed), isliye hit kuch nahi badalta; LRU last-use time track karta hai, aur hit ek use hai, isliye block ko "most recent" mein move karna zaroori hai.

WHY2. Exact LRU high associativity (jaise 16-way) wale caches mein rarely kyun use hota hai?

Bookkeeping cost tezi se badhti hai (roughly

lo g_{2} (n!)

bits per set) aur har access par poore set ko reorder karna padta hai. High

n

par yeh area aur latency mein expensive hota hai, isliye designers pseudo-LRU ya Random prefer karte hain.

WHY3. Miss rate mein 1% change bahut bada performance change kyun kausi hai?

Kyunki ek miss hit time ke relative mein ek huge miss penalty cost karta hai; AMAT formula mein miss-rate term us bade penalty se multiply hoti hai, isliye chhoti miss-rate swings memory-bound runtime ko dominate karti hain (aksar 10–20%).

WHY4. LRU temporal locality ko exploit kyun karta hai lekin directly spatial locality ko nahi?

LRU decide karta hai kaun sa block rakhna hai, aur temporal locality kehti hai ki recently-touched blocks dobara aate hain — yahi woh recency signal hai jo LRU padhta hai. Spatial locality block size se capture hoti hai (neighbors ko saath load karna), jo ek alag design lever hai.

WHY5. Random koi history ignore karne ke bawajood good enough kyun ho sakta hai?

Ek bade associative set mein, randomly ek aisa block evict hone ki odds kam hain jo abhi reuse hone wala ho, aur working set aksar baaki ways mein survive kar jaata hai — isliye average miss rate LRU ke kaafi kareeb rehti hai bina kisi tracking hardware ke.

WHY6. FIFO ka pointer modulo-

n

arithmetic kyun use karta hai?

Pointer ways

0, 1, \dots, n - 1

se cycle karta hai aur aakhri way ke baad

0

par wrap karna zaroori hai —

(ptr + 1) mod n

ek circular queue implement karta hai, jo FIFO ke "next-oldest becomes the victim" behavior se match karta hai.

WHY7. Replacement policies poore cache mein nahi, ek set ke andar kyun operate karti hain?

Ek address sirf ek specific set mein map ho sakta hai (uske index bits yeh fix karte hain), isliye eviction candidates exactly us set ke

n

ways hote hain — policy ko kabhi doosre sets ke blocks consider nahi karne padte.

Edge cases

EC1. Cache abhi full nahi hua — LRU kaun sa block evict karta hai?

Abhi koi nahi. Jab tak ek empty way exist karta hai, har policy naye block ko free slot mein load karti hai; eviction logic sirf tab fire hoti hai jab set ke saare

n

ways occupied ho jaayein.

EC2.

n = 1

(direct-mapped) — LRU, FIFO, aur Random kya karte hain?

Teeno identical behavior par collapse ho jaate hain: single resident block hi single candidate hai, isliye woh hamesha victim hota hai. Policy choice meaningless hai.

EC3. Exact same block baar baar access hota hai (A, A, A, ...) — har policy kaisi behave karti hai?

Pehle load ke baad sab hits hain: LRU A ko baar baar most-recent mark karta rehta hai (koi eviction nahi), FIFO apni queue frozen chhod deta hai (koi eviction nahi), Random kabhi invoke nahi hota. Koi bhi policy differences nazar nahi aatey.

EC4. Access sequence set se badi ho aur koi reuse na ho (pure streaming scan) — policies compare kaisi hoti hain?

Sab ke liye har access ek compulsory/capacity miss hai; LRU ki samajhdaari kuch hासil nahi karti kyunki past kabhi repeat nahi hota. Yahan Random bhi LRU se match karta hai — LRU ko locality chahiye, aur yahan koi hai hi nahi.

EC5. Set mein do blocks ki LRU ke under equal recency ho — kaun jeetta hai?

Yeh true LRU mein ho hi nahi sakta, kyunki har access ek distinct last-use time deta hai. Yeh sirf approximations (pseudo-LRU) mein hota hai, jahan ek fixed tie-break rule choose karta hai; baat yeh hai ki exact LRU ek strict total order rakhta hai.

EC6. Write-back ke under ek write-allocate miss — replacement badlta hai kya?

Victim choice unchanged rehti hai (same policy), lekin ek dirty victim ko evict karne par pehle memory mein write-back zaroori hota hai, us particular eviction ka cost badha deta hai, haalaanki policy logic identical hai.

EC7. Replacement policy TLB ya page replacement ke saath kaise interact karti hai?

Page frames ke liye ek level upar same LRU/FIFO/Random ideas dobara aate hain — aur Belady's Anomaly originally wahan describe ki gayi thi. Concepts transfer hote hain; hardware aur time scales alag hain.

Recall Jaane se pehle self-test karo

Kaun si policy hits par react karti hai, aur kaun si unhe ignore karti hai? ::: LRU react karta hai (recency update karta hai); FIFO hits ignore karta hai.
Kaun si policy Belady's Anomaly suffer kar sakti hai? ::: FIFO (aur doosri non-stack policies), LRU kabhi nahi.
Recency value $n - 1$ kya mark karti hai? ::: Least-recently-used block — LRU victim.
Teeno policies kab identical behave karti hain? ::: Direct-mapped ( $n = 1$ ) cache mein, ya pure no-reuse streaming scan par.

Related depth: Cache-conscious-programming dikhata hai ki programmers access patterns ko kaise shape karte hain taaki hardware jo bhi policy use kare woh actually working set ko rakhe; 5.4.06-Cache-coherence-protocols multi-core sharing mein eviction ka role add karta hai.