5.4.14 · D5 · HinglishMemory Hierarchy & Caches
Question bank — Cache coherence problem
5.4.14 · D5· Hardware › Memory Hierarchy & Caches › Cache coherence problem
Shuru karne se pehle, ek reminder un vocabulary words ka jo tumhe blur nahi karni chahiye:
- Valid copy ::: ek cached line jiska stored value true logical value ke barabar ho; read safely usse return kar sakti hai.
- Stale copy ::: ek cached line jis par core abhi bhi trust karta hai, lekin jiska value kahin aur likhe gaye latest write se ab match nahi karta.
- Propagation / serialization ::: coherence ke do hisse — kya write kabhi doosron tak pahunchti hai, aur kya saare cores ek hi address par writes ke order par agree karte hain.
True ya false — justify karo
Write-through caches cache coherence problem ko khatam kar deti hain.
False. Write-through memory ko fresh rakhti hai, lekin ye doosre cores ki cached copies ko kabhi touch nahi karti, isliye reader apni stale line hi return karta rehta hai — cache-vs-cache gap bana rehta hai.
Coherence aur consistency ek hi property ke do naam hain.
False. Coherence ek single address ko caches ke across govern karti hai; consistency alag-alag addresses par operations ki ordering ko govern karti hai. Ek bina doosre ke hold ho sakti hai.
Agar har core sirf read-only data use kare, tab bhi tumhe ek coherence protocol ki zaroorat hogi.
False. Jab koi write hi nahi hai to koi stale copy nahi hogi — har valid copy hamesha barabar rahegi, isliye coherence invariant ko koi khatra nahi.
Sirf ek core aur ek cache wala system bhi cache incoherence se suffer kar sakta hai.
False. Incoherence ke liye ek address ki do ya zyada private copies chahiye; akela cache kisi se disagree nahi kar sakta (haalaanki woh memory ke muqable stale ho sakta hai — woh alag issue hai).
Write-invalidate aur write-update ek hi program ke liye identical bus traffic produce karte hain.
False. Ek line par baar baar writes — ek invalidate vs. kai update broadcasts ka kharch hota hai; tight producer/consumer sharing reverse kar deti hai ki kaun sasta hai. Traffic access pattern par depend karta hai.
"Write propagation" akela ek system ko coherent kehne ke liye kaafi hai.
False. Tumhe write serialization bhi chahiye — saare cores ko us location par writes ek hi order mein observe karne chahiye, warna do cores alag final values maan sakte hain.
Ek dirty write-back line ka matlab hai main memory momentarily galat hai.
True. Write-back nayi value cache mein rakhta hai aur memory update defer karta hai, isliye memory flush hone tak peeche reh jaati hai — yeh memory-vs-cache gap hai, cache-vs-cache se alag.
Har write par saare caches ko nayi value broadcast karna (update protocol) coherence guarantee karta hai.
True, yeh barabar valid copies restore kar deta hai — lekin yeh aksar wasteful hota hai, bus par writes spray karta hai jo koi currently read nahi kar raha.
Error dhundo
"A ne write-through se X=10 likha, isliye B ab 10 read karega."
Error yeh hai: write-through memory update karta hai, B ki cache ko nahi. B ki apni copy abhi bhi stale 10-was-5 hai, isliye B tab tak 5 read karega jab tak usse invalidate ya update nahi kiya jaata.
"Invalidate update se hamesha better hai, koi exception nahi."
Error yeh hai: "hamesha." Tight sharing mein (ek baar likho, turant baar baar padho), invalidate reader ko har round mein miss par force karta hai; update isse avoid karta hai. Pattern decide karta hai.
"Write-back aur koi protocol nahi hone par, sirf B ki cache stale hai; memory theek hai."
Error yeh hai: memory bhi stale hai — write-back ne A ki dirty line flush nahi ki, isliye cache-vs-cache aur memory-vs-cache dono values abhi bhi 5 read karti hain.
"Coherence guarantee karta hai ki agar main X likhun phir Y likhun, to sabko X, Y se pehle dikhega."
Error yeh hai: yeh ek cross-address ordering claim hai — yeh consistency ka sawaal hai, coherence ka nahi. Coherence sirf ek hi location par writes order karta hai.
"Ek update protocol ek write par ek message bhejta hai, isliye X par teen writes ke liye teen bhejta hai; invalidate bhi teen bhejta hai."
Error yeh hai: pehli write ke baad invalidate exclusive ownership grant kar deta hai, isliye agli do writes silent hoti hain — teen nahi, ek message.
"Kyunki B ne X kabhi nahi likha, B ki copy stale nahi ho sakti."
Error yeh hai: staleness ka matlab out of date hona hai, na ki kisne likha. B ki untouched copy us pal stale ho jaati hai jis pal A X likhta hai. :::
"Invalidate B ki read ko fresh value ke saath hit mein badal deta hai."
Error yeh hai: invalidate usse forced miss mein badalta hai; miss hi hai jo fresh value fetch karta hai. Value fresh hai kyunki hit deny kiya gaya.
Why ke sawaal
Problem ko private caches kyun chahiye, na ki sirf koi bhi caches?
Kyunki incoherence alag-alag copies ke beech disagreement hai. Ek single shared cache ek address ke liye ek copy rakhta hai, isliye sync se bahar girne ke liye kuch nahi.
Write-propagation ke upar write-serialization kyun chahiye?
Propagation sirf yeh promise karta hai ki writes pahunche; ek common order ke bina, do cores writes W1,W2 alag orders mein apply kar sakte hain aur alag final values par aa sakte hain.
Real CPUs (MESI wagera) update ke bajaay invalidate kyun chunte hain?
Real workloads ek hi line bar bar likhte hain (loops, counters); invalidate ek burst of writes par ek baar charge karta hai, update per write pay karta hai — invalidate bus traffic par better scale karta hai.
Ek read "miss" actually fix kyun ho sakti hai naa ki failure?
Kyunki invalidate ke baad stale copy gone ho jaati hai; miss woh mechanism hai jo core ko garbage trust karne ke bajaay true value par wapas laata hai.
Coherence invariant sirf valid copies ko compare kyun karta hai?
Ek invalidated line "mujh par trust mat karo" mark hai, isliye usme koi bhi leftover bits ho sakte hain bina kuch violate kiye — invariant sirf un copies ke beech agreement demand karta hai jo ek read return kar sakti hai.
Dirty lines ko memory mein flush karna akele system ko coherent kyun nahi banata?
Flushing memory-vs-cache gap band karta hai, lekin doosre cores abhi bhi apni cached copies read karte hain, memory nahi — cache-vs-cache gap ko invalidate ya update chahiye.
Edge cases
Agar do cores "ek saath" same X likhein to kya hota hai?
Protocol unhe ek order mein serialize karna chahiye (bus ya directory ke zariye); exactly ek write ownership race jeetta hai, aur saare cores woh ek agreed order observe karte hain.
Agar ek core aisi line likhta hai jo kisi aur cache mein nahi hai?
Kisi invalidate ki zaroorat hi nahi — koi aur valid copy hai hi nahi, isliye invariant pehle se hold karta hai; write purely local hai (yeh MESI mein "Exclusive" state ka faayda hai).
Agar X aur Y ek hi cache line mein hain lekin cores alag variables touch karte hain?
Protocol poori lines track karta hai, isliye X par write Y wali line ko bhi invalidate kar deta hai — cores ek aisi line ke liye ladte hain jise woh logically share nahi karte. Yeh false sharing hai.
Kya ek read-only shared line kabhi invalidate hoti hai?
Tab tak nahi jab tak koi usse write na kare. Kai cores ek saath same clean copy rakh sakte hain; pehli write hi baaki sab ko invalidate trigger karti hai.
Kya coherence yeh kehti hai ki ek write bilkul kab visible hogi?
Nahi — sirf yeh ki woh eventually visible ho jaayegi (propagation) aur ek consistent order mein (serialization). Addresses ke across precise timing consistency models ka kaam hai.
Agar ek core X read kare, invalidate ho jaaye, phir koi nayi write ke bina dobara read kare?
Uski pehli copy drop ho gayi, isliye doosri read miss hoti hai aur same valid value re-fetch karta hai — sahi hai lekin slower; yeh pure invalidation overhead hai, koi incoherence nahi.
Kya snooping vs. directory isko affect karta hai ki coherence hold karta hai ya nahi?
Nahi — dono same invariant enforce karte hain; woh differ karte hain kaise invalidate/update doosre caches tak pahunchti hai (broadcast vs. targeted), jo scalability ko affect karta hai, correctness ko nahi.