Replacement policies (LRU, FIFO, random) — Hinglish notes

5.4.5 · Hardware › Memory Hierarchy & Caches

Overview

Jab ek cache full ho jaata hai aur ek naya block load karna hota hai, toh cache controller decide karta hai ki kaunsa existing block evict karna hai. Yeh decision replacement policy ke zariye hota hai. Teen fundamental strategies hain: Least Recently Used (LRU), First-In First-Out (FIFO), aur Random.

Replacement Policies Kyun Matter Karti Hain

Problem: Cache capacity < Memory size. Temporal locality ka matlab hai ki recently-used data dobara use hone ki probability zyada hai. Spatial locality ka matlab hai ki nearby data jaldi use hone waala hai. Ek replacement policy in patterns ko exploit karti hai taaki miss rate minimize ho.

Performance Impact:

Miss rate directly average memory access time (AMAT) ko affect karti hai: $AMAT = Hit Time + Miss Rate \times Miss Penalty$
Miss rate mein 1% ka fark memory-bound applications mein 10-20% performance difference de sakta hai
Replacement policy miss rate ko affect karti hai, lekin hardware cost bhi hoti hai

LRU (Least Recently Used)

LRU Kaise Kaam Karta Hai

Mechanism:

Har cache access ek timestamp update karta hai ya recency list ko reorder karta hai
Eviction pe, wo block choose karo jiska timestamp sabse purana ho / jo list ki tail pe ho
Hit ya miss (load ke baad) pe, us block ko most recently used mark karo

Yeh approach kyun? Temporal locality: recently-accessed data jaldi dobara access hone ki possibility zyada hai. Jis block ko sabse zyada time se touch nahi kiya, uski probability sabse kam hai ki wo next chahiye hoga.

LRU Behavior Ki Derivation

Ek 2-way set-associative cache consider karo jisme set mein blocks A aur B hain.

Access sequence: A, B, A, C

Access	Action	Recency Order (MRU → LRU)	Yeh step kyun?
A	A ko way 0 mein load karo	[A, -]	Pehla access, empty cache
B	B ko way 1 mein load karo	[B, A]	B MRU ban jaata hai, A ab LRU hai
A	A pe hit	[A, B]	A phir se MRU ban jaata hai, B ab LRU hai
C	B ko evict karo, C ko way 1 mein load karo	[C, A]	B LRU hai, isliye replace karo. C MRU ban jaata hai

Key insight: Har access recency structure ko reorder karta hai. Jis block ko sabse zyada time se touch nahi kiya, woh hamesha "cold" end pe hota hai.

LRU Implementation

Challenge: Recency track karne ka hardware cost hota hai.

Exact LRU (chhote n ke liye):

Counter method: Har block ka ek timestamp counter hota hai. Access pe, counter ko global time pe set karo; global time increment karo. Sabse chhote counter wale block ko evict karo.
- Cost: n counters of $lo g_{2} (time)$ bits each
Pseudo-LRU (tree-based): Binary tree banane ke liye $n - 1$ bits use karo. Har bit indicate karta hai ki kaun sa subtree zyada recently access hua. Access pe, root se block tak path ke bits flip karo.
- Cost: n-way set ke liye sirf $n - 1$ bits
- Approximation: exact LRU track nahi karta, lekin kaafi close hai

4-way set ke liye: Exact LRU ko 4 × 2 = 8 bits chahiye (2-bit counters). Pseudo-LRU ko 3 bits chahiye.

Worked example LRU Example: 4-way Set, Access Sequence A, B, C, D, A, E

Access	Cache State	Recency (0=MRU)	Action
A	[A, -, -]	[0, -, -, -]	A load karo
B	[A, B, -, -]	[1, 0, -, -]	B load karo, A age karta hai
C	[A, B, C, -]	[2, 1, 0, -]	C load karo, A aur B age karte hain
D	[A, B, C, D]	[3, 2, 1, 0]	D load karo, ab cache full hai
A	[A, B, C, D]	[0, 3, 2, 1]	A pe hit! A MRU ban jaata hai
E	[A, E, C, D]	[1, 0, 2, 3]	B ko evict karo (recency=3), E load karo
B kyun? A pe hit karne ke baad, recency order tha [A=0, D=1, C=2, B=3]. B LRU hai.

Step-by-step reasoning:

E access miss hai → evict karna padega
Recency counters check karo: A=0, D=1, C=2, B=3
B ka recency sabse zyada hai (3) → least recently used
B ko E se replace karo, E ka recency 0 pe set karo
Baaki sabke recency counters increment karo

FIFO (First-In First-Out)

FIFO Kaise Kaam Karta Hai

Mechanism:

Ek queue pointer ya timestamp maintain karo jo insertion order indicate kare
Eviction pe, wo block choose karo jo cache mein sabse pehle aaya tha
Hit pe, order mein kuch nahi badlega (yeh LRU se key difference hai)

FIFO kyun? Simplicity. Access track karne ki zaroorat nahi, sirf insertion order.

FIFO Behavior Ki Derivation

Wohi 2-way set consider karo, access sequence: A, B, A, C

Access	Action	Queue Order (Head → Tail)	Yeh step kyun?
A	A load karo	[A, -]	A pehle enter karta hai
B	B load karo	[A, B]	B doosre number pe enter karta hai (queue ab [A, B] hai)
A	A pe hit	[A, B]	Order unchanged — FIFO hits ko ignore karta hai
C	A ko evict karo, C load karo	[B, C]	A pehle aaya tha, isliye A ko evict karo chahe recent hit hua ho

LRU se critical difference: A pe hit ne A ko queue ke peeche nahi shift kiya. FIFO insertion ke baad access patterns ke baare mein oblivious hai.

FIFO Implementation

Hardware: Har set ke liye single $⌈ lo g_{2} n ⌉$ -bit counter. Bahut sasta.

4-way set ke liye: 2-bit counter. 16-way ke liye: 4-bit counter.

Worked example FIFO Example: 4-way Set, Access Sequence A, B, C, D, A, E

Access	Cache State	Queue Order	QueuePtr	Action
A	[A, -, -, -]	[A]	1	A ko way 0 mein load karo
B	[A, B, -, -]	[A, B]	2	B ko way 1 mein load karo
C	[A, B, C, -]	[A, B, C]	3	C ko way 2 mein load karo
D	[A, B, C, D]	[A, B, C, D]	0	D ko way 3 mein load karo, pointer wrap karo
A	[A, B, C, D]	[A, B, C, D]	0	A pe hit! Queue mein koi change nahi
E	[E, B, C, D]	[B, C, D, E]	1	A ko evict karo (way 0), E load karo

A kyun? QueuePtr=0, way 0 ki taraf point karta hai jisme A hai. FIFO ko parwah nahi ki A abhi-abhi access hua tha.

LRU se contrast: LRU ne B ko evict kiya hota (wo block jo recently access nahi hua), lekin FIFO ne A ko evict kiya (sabse purana insertion).

Belady's Anomaly

Common mistake FIFO Mein Bade Cache Ke Saath Miss Rate Zyada Ho Sakti Hai!

Galat intuition: "Zyada cache capacity ka matlab hamesha kam misses."

Kyun sahi lagta hai: Bada cache zyada blocks hold karta hai, toh working set zyada capture hona chahiye.

Reality: FIFO Belady's Anomaly exhibit karta hai — cache size badhane se kuch access patterns ke liye miss rate badh sakti hai.

Example: Access sequence [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]

3-frame FIFO: 9 misses
4-frame FIFO: 10 misses Kyun? FIFO ki rigid insertion-order eviction blocks ko discard kar sakti hai ठीक us waqt jab unki dobara zaroorat padne wali hoti hai, aur capacity badhane se circular queue ka phase access pattern ke relative badal jaata hai.

Fix: Stack algorithms use karo jaise LRU, jo guarantee karte hain ki capacity badhne pe miss rate monotonically decrease hogi.

Random Replacement

Random Kaise Kaam Karta Hai

Mechanism:

Ek pseudorandom number generator (PRNG) ya linear feedback shift register (LFSR) use karo
Eviction pe, random index $i \in [0, n - 1]$ generate karo
Way $i$ pe maujood block ko evict karo

Random kyun? Jab workload unpredictable ya adversarial ho, koi bhi deterministic policy exploit ki ja sakti hai. Random worst-case patterns avoid karta hai.

Random Behavior Ki Derivation

Ek n-way set ke liye, har block ki eviction probability:

$P (evict block i) = \frac{1}{n}$

Kisi specific block ko evict karne se pehle expected number of accesses (agar use dobara access nahi kiya jaata):

$E [lifetime] = n evictions$

Yeh formula kyun? Har eviction ek independent trial hai jisme success probability $\frac{1}{n}$ hai. Yeh geometric distribution hai: expected number of trials = $\frac{1}{p} = n$ .

Random Implementation

Hardware: Chhota LFSR (e.g., 16-way set ke liye 4-bit) ya cycle counter ke low bits use karo. Bahut sasta: ~10 gates.

Worked example Random Example: 4-way Set, Access Sequence A, B, C, D, A, E

Assume karo PRNG generate karta hai: [-, -, -, 2]

Access	Cache State	Random Eviction	Action
A	[A, -, -, -]	-	A ko way 0 mein load karo
B	[A, B, -, -]	-	B ko way 1 mein load karo
C	[A, B, C, -]	-	C ko way 2 mein load karo
D	[A, B, C, D]	-	D ko way 3 mein load karo
A	[A, B, C, D]	-	A pe hit
E	[A, B, E, D]	way 2 (C)	C ko evict karo (randomly chosen), E load karo

C kyun? PRNG output 2 → way 2 evict karo. Koi bhi way [0, 1, 2, 3] equal probability ke saath ho sakta tha.

Deterministic policies se contrast:

LRU B ko evict karta (least recently used)
FIFO A ko evict karta (oldest insertion)
Random ne C ko evict kiya (coin flip)

Comparison: LRU vs FIFO vs Random

Policy	Miss Rate	Hardware Cost	Anomalies	Best For
LRU	Zyaadaatar workloads ke liye sabse kam	Sabse zyada (counters/trees)	Koi nahi (stack algorithm)	Temporal locality
FIFO	Medium	Sabse kam (single counter)	Belady's Anomaly	Streaming / sequential access
Random	Medium-high	Bahut kam (LFSR)	Koi nahi (probabilistic)	Adversarial / unpredictable workloads

Yeh Differences Kyun Hain?

LRU temporal locality exploit karta hai:

Recent accesses future accesses predict karte hain
Tab best hai jab working set cache mein fit ho aur reuse exhibit kare
Cost: Har access pe state update karna padta hai

FIFO access patterns ignore karta hai:

Sirf insertion order track karta hai
Sequential scans (streaming data) ke liye theek kaam karta hai
Tab fail karta hai jab blocks initial load ke baad reuse hote hain
Cost: Sirf evictions pe update

Random worst-case avoid karta hai:

Koi bhi pathological access pattern 100% miss rate cause nahi kar sakta
Performance sabhi patterns ke across average hoti hai
Cost: Minimal hardware, koi state updates nahi

Worked Example: Detailed Trace Comparison

Setup: 4-way set-associative cache, access sequence:

A, B, C, D, E, B, A, B, F, G

Teeno policies trace karte hain:

LRU Trace

Access	Cache State	Recency Order (MRU→LRU)	Hit/Miss	Yeh step kyun?
A	[A, -, -, -]	[A]	Miss	Cold start, A load karo
B	[A, B, -, -]	[B, A]	Miss	B load karo, A 1 se age karta hai
C	[A, B, C, -]	[C, B, A]	Miss	C load karo aur B age karta hai
D	[A, B, C, D]	[D, C, B, A]	Miss	D load karo, cache ab full hai
E	[E, B, C, D]	[E, D, C, B]	Miss	A ko evict karo (LRU), E load karo
B	[E, B, C, D]	[B, E, D, C]	Hit	B MRU pe move ho jaata hai
A	[E, B, A, D]	[A, B, E, D]	Miss	C ko evict karo (LRU), A load karo
B	[E, B, A, D]	[B, A, E, D]	Hit	B MRU pe move ho jaata hai
F	[E, B, A, F]	[F, B, A, E]	Miss	D ko evict karo (LRU), F load karo
G	[G, B, A, F]	[G, F, B, A]	Miss	E ko evict karo (LRU), G load karo

Total: 8 misses, 2 hits

FIFO Trace

Access	Cache State	Queue (head→tail)	QueuePtr	Hit/Miss	Yeh step kyun?
A	[A, -, -, -]	[A]	1	Miss	A ko way 0 mein load karo
B	[A, B, -, -]	[A, B]	2	Miss	B ko way 1 mein load karo
C	[A, B, C, -]	[A, B, C]	3	Miss	C ko way 2 mein load karo
D	[A, B, C, D]	[A, B, C, D]	0	Miss	D ko way 3 mein load karo
E	[E, B, C, D]	[B, C, D, E]	1	Miss	A ko evict karo (ptr=0), E load karo
B	[E, B, C, D]	[B, C, D, E]	1	Hit	Queue mein koi change nahi
A	[E, A, C, D]	[C, D, E, A]	2	Miss	B ko evict karo (ptr=1), A load karo
B	[E, A, B, D]	[D, E, A, B]	3	Miss	C ko evict karo (ptr=2), B load karo
F	[E, A, B, F]	[E, A, B, F]	0	Miss	D ko evict karo (ptr=3), F load karo
G	[G, A, B, F]	[A, B, F, G]	1	Miss	E ko evict karo (ptr=0), G load karo

Total: 9 misses, 1 hit

Note: FIFO step 7 pe B ko evict karta hai chahe B abhi-abhi access hua tha (hit). Isliye FIFO doosre B access pe miss karta hai.

Random Trace

Assume karo PRNG outputs: [-, -, -, 1, -, 0, 3, 2, 1]

Access	Cache State	Random Way	Hit/Miss	Yeh step kyun?
A	[A, -, -, -]	-	Miss	A ko way 0 mein load karo
B	[A, B, -, -]	-	Miss	B ko way 1 mein load karo
C	[A, B, C, -]	-	Miss	C ko way 2 mein load karo
D	[A, B, C, D]	-	Miss	D ko way 3 mein load karo
E	[A, E, C, D]	1 (B)	Miss	B ko evict karo (random), E load karo
B	[A, E, C, D]	-	Miss	B ko way 1 mein load karo (abhi-abhi evict hua!)
A	[A, E, C, D]	-	Hit	A abhi bhi cache mein hai
B	[A, E, C, B]	3 (D)	Miss	D ko evict karo (random), B load karo
F	[A, E, F, B]	2 (C)	Miss	C ko evict karo (random), F load karo
G	[A, G, F, B]	1 (E)	Miss	E ko evict karo (random), G load karo

Total: 9 misses, 1 hit

Random ne B ko evict kiya ठीक pehle jab use dobara chahiye tha (unlucky), lekin chance se LRU ke kuch smart evictions avoid kiye.

Summary

Miss rates:

LRU: 80% (8/10 misses) — best performance
FIFO: 90% (9/10 misses) — yahan worst, recently-hit B ko evict karne ki wajah se
Random: 90% (9/10 misses) — FIFO ke comparable

Key observation: LRU ka advantage B pe hue do hits se aata hai. Recently-accessed blocks rakh ke, LRU pehle hit ke baad B ko re-fetch karne se bachta hai. FIFO aur Random recent access track nahi karte, isliye B ko evict karte hain aur misses suffer karte hain.

Recall Ek 12-saal ke bachche ko samjhao

Imagine karo tumhare paas ek chhota sa backpack hai jisme sirf 4 school books rakh sakte ho, lekin tumhe poore din 10 alag-alag books access karni hain.

LRU (Least Recently Used): Jab bhi koi book use karte ho, use backpack ke aage push kar dete ho. Bilkul peeche wali book woh hai jise tune sabse zyada time se touch nahi kiya. Jab nayi book chahiye aur backpack full ho, peeche wali book hata dete ho. Yeh bahut achha kaam karta hai kyunki zyaadaatar tum same books baar baar use karte ho, toh jo abhi-abhi use ki usse rakhna sahi hai!

FIFO (First-In First-Out): Tum apni books us order mein rakhte ho jisme pehle rakhi thi. Jab nayi book chahiye, hamesha pehle rakhi book hataate ho, chahe tum use ek minute pehle use kiya ho! Yeh ek conveyor belt jaisa hai — pehle book in, pehle book out. Yeh track karna bahut aasaan hai (bas yaad raho kaun si book pehle aayi thi), lekin kabhi kabhi aise books hataate ho jo jaldi chahiye hoti hain.

Random: Aankhen band karke koi bhi book pull kar lo jab jagah chahiye. Koi strategy nahi! Kabhi lucky hote ho aur aisi book hataate ho jo nahi chahiye. Kabhi aisi hataate ho jo dobara use hone wali thi. Average pe theek kaam karta hai, aur kuch yaad rakhne ki zaroorat nahi.

Best strategy tumhare pattern pe depend karti hai: agar same books zyada reuse karte ho (jaise homework ke liye textbooks), LRU jeetta hai. Agar sirf order mein ek baar books padh rahe ho (jaise library book list), FIFO theek hai. Agar koi tricky tareekon se books badhalta rehta hai, Random trick hone se bachata hai.

Advanced: Practical Hybrid Policies

Real processors aksar approximations use karte hain:

Pseudo-LRU (PLRU)

LRU ordering approximate karne ke liye tree-based bits
Intel Core, AMD Ryzen L2/L3 caches ke liye PLRU use karte hain
Cost: n-way ke liye $n - 1$ bits, vs. true LRU ke liye $n lo g n$

Not Recently Used (NRU)

Har block per ek reference bit, periodically clear hota hai
Koi bhi block jiska ref bit = 0 ho, evict karo
Kuch TLBs aur page tables mein use hota hai

Clock Algorithm

Ek hand pointer ke saath circular buffer
Eviction pe, clockwise scan karo, ref bits clear karo, ref=0 wale pehle block ko evict karo
OS page replacement mein use hota hai (LRU approximate karta hai)

Connections

5.4.01-Cache-organizationand-addressing — Replacement policy ek set ke andar operate karti hai
5.4.03-Write-policies-(write-through,-write-back) — Eviction ko dirty blocks handle karne padte hain
5.4.06-Cache-coherence-protocols — Replacement coherence state ke saath interact karta hai
5.5.02-Virtual-memory-and-TLBs — Same replacement concepts TLBs aur page tables pe bhi apply hote hain
Temporal-and-spatial-locality — LRU temporal locality exploit karta hai; FIFO isse miss karta hai
Working-set-model — Optimal cache size working set pe depend karti hai; LRU better adapt karta hai
Cache-conscious-programming — Programmers LRU ke liye optimize kar sakte hain inner loops mein data reuse karke

#flashcards/hardware

Cache replacement policy kya hoti hai aur kyun chahiye? :: Ek policy jo decide karti hai ki jab cache full ho aur naya block load karna ho tab kaun sa block evict karna hai. Isliye chahiye kyunki cache capacity limited hai aur hume choose karna padta hai ki kaun se blocks rakhen taaki miss rate minimize ho.

LRU ka full form kya hai aur yeh kya evict karta hai?

Least Recently Used. LRU us block ko evict karta hai jo sabse zyada time se access nahi hua.

LRU ki generally sabse kam miss rate kyun hoti hai?

LRU temporal locality exploit karta hai — recently accessed data dobara jaldi access hone ki probability zyada hai, isliye recent blocks rakhne se hit probability maximize hoti hai.

LRU ka hardware cost trade-off kya hai? :: LRU ko har access ke liye recency track karna padta hai (counters ya trees), isliye yeh hardware complexity ke mamle mein sabse mehenga policy hai.

FIFO ka full form kya hai aur yeh kya evict karta hai?

First-In First-Out. FIFO us block ko evict karta hai jo sabse pehle load hua tha, cache ko queue ki tarah treat karta hai.

FIFO LRU se sasta kyun hai?

FIFO ko sirf insertion order track karne ke liye har set mein single counter chahiye, aur cache hits pe update nahi karta, isliye hardware aur energy cost kam hoti hai.

Belady's Anomaly kya hai?

Ek phenomenon jisme cache capacity badhane se FIFO replacement ke under kuch access patterns ke liye miss rate badh jaati hai.

LRU Belady's Anomaly kyun suffer nahi karta?

LRU ek stack algorithm hai — k-way cache ke contents, same access sequence ke under (k+1)-way cache ke subset hote hain, jo monotonic miss rate improvement guarantee karta hai.

Random replacement policy kya hai?

Ek policy jo set mein se uniformly random block evict karti hai PRNG ya LFSR use karke, bina kisi history tracking ke.

Random replacement deterministic policies se kab better hoti hai?

Adversarial ya highly unpredictable workloads mein jahan koi bhi deterministic pattern exploit kiya ja sakta hai, aur hardware simplicity ke liye.

n-way cache mein Random replacement ke under har block ki eviction probability kya hai?

Har block ke liye 1/n (uniform distribution).

Pseudo-LRU (PLRU) kya hai?

LRU ka ek approximation jo binary tree of bits (n-way ke liye n-1 bits) use karta hai jo indicate karta hai ki kaun sa subtree zyada recently access hua, hardware cost reduce karne ke liye.

Jab koi block access (hit) hota hai toh FIFO LRU se alag kaise behave karta hai?

FIFO hit pe eviction order nahi badhlta — queue order insertion time pe based rehta hai. LRU accessed block ko most-recently-used position pe move karta hai.

LRU ka recency counter update rule kya hai?

Block i access karne pe, Recency_i = 0 (MRU) set karo. Baaki sab blocks ke recency counters increment karo (woh age karte hain). Maximum recency wale block ko evict karo.

AMAT (Average Memory Access Time) ka formula kya hai?

AMAT = Hit Time + (Miss Rate × Miss Penalty). Replacement policy miss rate ko affect karti hai.

Cache replacement ke context mein stack algorithm kya hota hai?

Ek policy jisme size-k cache ke contents, same access sequence ke liye size-(k+1) cache ke subset hote hain, jo capacity ke saath monotonic miss rate improvement ensure karta hai.

FIFO ka hardware implementation kya hai?

Har set mein single modulo-n counter (queue pointer) jo ways [0, n-1] ke through cycle karta hai, har eviction pe advance hota hai.

Random ka hardware implementation kya hai?

Ek chhota PRNG ya LFSR jo har eviction pe random way index [0, n-1] generate karta hai.

4-way cache mein access sequence [A, B, C, D, E] ke saath, E access pe LRU kaun sa block evict karta hai?

A (us point pe least recently used block).

Isi scenario mein, FIFO kaun sa block evict karta hai?

A (pehla block load hua, kyunki queue [A, B, C, D] hai).

Reuse wale workloads ke liye FIFO ki LRU se zyada miss rate kyun ho sakti hai?

FIFO recently-accessed blocks ko sirf isliye evict kar sakta hai kyunki woh pehle load hue the, recent access pattern ko ignore karta hai jo suggest karta hai ki unhe jaldi dobara chahiye hoga.