Foundations — Cache miss types (compulsory, capacity, conflict)
5.4.9 · D1· Hardware › Memory Hierarchy & Caches › Cache miss types (compulsory, capacity, conflict)
Pehle yeh samajhna zaroori hai ki kyun misses hoti hain, isliye tum parent note ke vocabulary mein fluent hona chahiye: block, set, index, associativity, mod symbol , LRU, aur woh chhote letters with subscripts. Yeh page in sabko ek ek karke build karta hai, aur har concept pichle pe based hai.
1. Memory ek badi shelf ki tarah numbered boxes ke saath
Yeh topic ke liye kyun zaroori hai: parent note mein har access (0, 4, 0, 4…) ek address hai. Numbered boxes ke concept ke bina, sequences ka koi matlab nahi.
2. Block — woh chunk jo actually move karta hai
Tum kabhi bhi big shelf se sirf ek byte cache mein nahi laate. Yeh wasteful hoga. Iske bajaye memory fixed-size blocks mein kati hoti hai (jinhe lines bhi kehte hain).
Yeh topic ke liye kyun zaroori hai: parent 0, 4, 2 jaise sequences likhta hai — yeh block numbers hain, byte addresses nahi. Jab hum kehte hain "block 4 ka pehla ever touch," toh block woh cheez hai jo touch ho rahi hai. (Ek block mein neighbours ko laana exactly wahi hai jo Spatial and Temporal Locality exploit karta hai, aur block kitna bada hona chahiye yeh Cache Block Size Trade-offs mein hai.)
3. Cache — ek choti shelf numbered slots ke saath
Hit vs miss, naye words ke saath:
Yeh topic ke liye kyun zaroori hai: "miss types" tab hi samajh mein aate hain jab tum jaano ki miss = "slot mein nahi hai." Eviction woh event hai jo future miss ka cause banta hai, jo capacity aur conflict misses ka dil hai.
4. Block allowed kahan baith sakta hai? — index aur
Yeh woh mechanical rule hai jo conflict misses possible banati hai. Sabse simple cache mein, har block ka ek hi legal home slot hota hai, jo arithmetic se decide hota hai.
Iska feel — ke saath:
| Block | Home set | |
|---|---|---|
| 0 | 0 | 0 |
| 4 | 0 | 0 ← block 0 se collide karta hai! |
| 1 | 1 | 1 |
| 6 | 2 | 2 |
Block 0 aur block 4 ka yeh collision exactly parent ka Worked Example 1 hai.
5. Associativity — ek block ke kitne ghar ho sakte hain
Yeh topic ke liye kyun zaroori hai: conflict miss ki poori definition yahi hai ki "ek miss jo same size ki fully-associative cache avoid kar leti." Yeh jaane bina ki "fully-associative" ka matlab kya hai, yeh kehna possible nahi. Deeper mechanics Cache Associativity & Set Mapping mein hain.
6. LRU — jab set full ho toh kaun jaata hai
Jab ek set mein slots hain aur sab full hain lekin naya block chahiye, toh kisi ko jaana padega. Kaun? Ek replacement policy decide karti hai.
Yeh topic ke liye kyun zaroori hai: parent ka capacity example [1,2] aur [2,0] jaise states likhta hai — woh ordering LRU bookkeeping hai. Capacity miss classify karne ke liye tumhe fully-associative cache ko replacement policy ke saath simulate karna padta hai, aur LRU standard wali hai. Full detail: LRU and Replacement Policies.
7. symbols — misses ko cause ke hisaab se count karna
Ab parent ke formulas mein notation aati hai.
Prerequisite map
Equipment checklist
- Main ek byte address se block number nikaal sakta/sakti hoon ::: — divide karo aur round down karo.
- Main mod se index compute kar sakta/sakti hoon ::: ; jaise (remainder).
- Main jaanta/jaanti hoon ki direct-mapped mein do blocks collide kyun karte hain ::: woh same share karte hain, isliye dono ek hi single home slot chahte hain.
- Main teen associativity levels bata sakta/sakti hoon ::: direct-mapped = 1 slot/set, -way = slots/set, fully-associative = 1 set jo sab kuch hold kare.
- Main jaanta/jaanti hoon LRU kya evict karta hai ::: woh block jo sabse zyada time se unused pada hai (ordering ka LRU end).
- Main har C ka cure naam le sakta/sakti hoon ::: compulsory→prefetch/bigger block, capacity→bigger cache, conflict→more associativity.
- Main decomposition formula jaanta/jaanti hoon ::: .