Foundations — Replacement policies (LRU, FIFO, random)

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

Isse pehle ki tum LRU, FIFO, aur Random ko parent topic par compare karo, tumhare paas unka leaned-on har ek vocabulary piece hona chahiye. Hum ek ek karke build karenge, pehle picture.

1. Memory vs. Cache — shelf aur library

Figure dekho: daayein taraf ka bada teal box main memory hai — bahut badi, pahunchne mein slow. Baayein taraf ka chota orange box cache hai — sirf kuch slots, lekin CPU ussey almost instantly grab kar sakta hai.

Is topic ko ye kyun chahiye: replacement tab hi hota hai jab cache chota hota hai. Agar cache memory jitna bada hota, toh kabhi kuch evict nahi karna padta, aur ye poora topic gayab ho jaata. Smallness hi poori problem ki wajah hai.

2. Block — wo unit jo move karti hai

Hum har example mein blocks ko $A,B,C,D,\dots$ se label karte hain. Jab hum "load $A$" likhte hain, matlab hai: block $A$ ko main memory se copy karke ek cache slot mein daalo.

Is topic ko ye kyun chahiye: jo "item" tum evict karte ho wo hamesha ek poora block hota hai. Har access sequence (jaise $A,B,A,C$) mein letters block names hain. Agar tum nahi jaante ki block atomic unit hai, toh sequences ka koi matlab nahi hoga. Dekho 5.4.01-Cache-organizationand-addressing ki memory addresses blocks se kaise map hote hain.

3. Hit, Miss, aur Eviction — teen events

Picture mein decision ek fork ki tarah dikhti hai: "Kya block yahan hai?" → haan = hit (green path), nahi = miss (orange path) → "Kya koi free slot hai?" → nahi = pehle kisi ko evict karo.

Is topic ko ye kyun chahiye: replacement policy sirf eviction step par chalti hai. Hits kabhi ise trigger nahi karte. Misses ise tab trigger karte hain jab cache already bhar chuki hoti hai. Har policy usi ek red box ke liye exactly ek rule hai.

4. Set aur Way — kahan ek block reh sakta hai

N-way associative set mein $n$ slots hote hain (ways numbered $0,1,\dots ,n-1$). 2-way set mein 2 slots hote hain; 4-way set mein 4.

Figure mein cache rows (sets) aur columns (ways) ke roop mein draw ki gayi hai. Naya block apni row mein jaata hai, phir policy decide karti hai ki jab row bhar jaaye toh kaun sa column overwrite karna hai.

Is topic ko ye kyun chahiye: replacement hamesha ek within-a-set decision hota hai. Jab parent kehta hai "2-way set-associative cache with blocks A and B", matlab hai ek row jo do blocks rakhti hai — aur eviction usi do mein se choose karti hai. Number $n$ un candidates ki sankhya hai jinmein se policy choose karti hai.

5. Recency aur Insertion order — do clocks

Teeno policies mein bas itna fark hai ki wo kya yaad rakhti hain. "Purana" ke do notions hote hain, aur inhe confuse karna classic trap hai.

Is topic ko ye kyun chahiye: LRU aur FIFO mein poora fark kaun si clock dekhte hain ka hai. Ek block jo row mein das baar hit hua wo recency se "fresh" hai lekin insertion order se ab bhi "old" hai. Yahin woh gap hai jahan FIFO ek hot block ko bahar fek sakta hai.

6. Recency counter — LRU formula padhna

Parent LRU ko har block ke liye ek counter ke saath likhta hai:

${\text{Recency}}_i(t+1)=\{\begin{array}{ll}0& \text{if block }i\text{ accessed at time }t\\ \min ({\text{Recency}}_i(t)+1,n-1)& \text{otherwise}\end{array}$

Aao har symbol ko decode karein taaki ye plain English jaisa padhe.

• $i$ — kaun sa block (ek index, block number $0$ se $n-1$ tak).
• $t$ — time step: ek counter jo har access par ek ek karke badhta hai. $t$, phir $t+1$, matlab "abhi, phir agle pal".
• ${\text{Recency}}_i(t)$ — block $i$ se attached ek number: 0 matlab "abhi use hua", aur bada number matlab "zyada stale". Maximum $n-1$ matlab "sabse cold possible".
• Do-line brace $\{\begin{array}{l}\dots \end{array}$ matlab "upar wali line lo agar uski condition hold kare, warna neeche wali."
• $\min (x,n-1)$ — "$x$ lo, lekin kabhi $n-1$ se zyada mat hone do." Cap kyun? Kyunki $n$ blocks ke saath oldest possible rank $n-1$ hai; usse zyada jaana meaningless hai.
• $\mathrm{mod}n$ (baad mein FIFO mein use hota hai) — $n$ se divide karne ke baad remainder. Ye counter ko wrap around karta hai: $n=4$ ke liye, $0,1,2,3$ count karne ke baad $\mathrm{mod}4$ next value ko $0$ par wapas bhej deta hai. Aise hi ek pointer ways mein hamesha ke liye cycle karta hai.

Is topic ko ye kyun chahiye: $i$, $t$, $\min$, $\mathrm{mod}$, aur cases brace ko decode kiye bina, parent page par LRU aur FIFO update rules unreadable hain. Ab har symbol earn kiya ja chuka hai.

7. Miss rate aur AMAT — ye sab kaam kyun aata hai

Parent har policy ko is number ko kaise move karta hai usse measure karta hai, is formula se:

$\text{AMAT}=\text{Hit Time}+\text{Miss Rate}\times \text{Miss Penalty}$

• Hit Time — hit kitni der mein complete hoti hai (chota).
• Miss Penalty — miss hone par memory tak jaane ka extra cost (bada).
• Product $\text{Miss Rate}\times \text{Miss Penalty}$ wo average extra time hai jo har access mein add hota hai. Kyunki Miss Penalty bada hota hai, Miss Rate mein thodi si bhi drop badi win hoti hai — isliye hi ek smart eviction rule matter karta hai.

Is topic ko ye kyun chahiye: ye scoreboard hai. Har claim jaise "LRU beats FIFO on this trace" asliyat mein is number ke baare mein ek claim hai. Ye sab Temporal-and-spatial-locality par depend karta hai — wo reason ki past behavior future predict karta hai.

Foundations kaise topic ko feed karti hain

Equipment checklist

Daayein taraf cover karo; apne dimag mein picture se har ek yaad karo.

Aage: parent topic par wapas jao aur LRU/FIFO/Random mechanisms padho — wahan har symbol ab define ho chuka hai. Related prerequisites: Working-set-model, Cache-conscious-programming, 5.5.02-Virtual-memory-and-TLBs.