Visual walkthrough — MESI - MOESI coherence protocols

5.4.15 · D2 · Hardware › Memory Hierarchy & Caches › MESI - MOESI coherence protocols

Yeh parent MESI/MOESI note ka ek deep-dive child hai. Agar yahan koi word naya lagta hai, toh uski definition yahan hi di gayi hai — aapko parent note open karne ki zaroorat nahin.

---

Step 1 — Setup: do caches, ek address

KYA HAI. Do CPU cores imagine karo. Har core ke paas apna ek chhota private notebook hota hai jise cache kehte hain — memory ki kuch values ka ek fast local copy, taaki core ko baar baar bade slow main memory tak na jaana pade.

YEH PICTURE KYU. Poori problem sirf isliye exist karti hai kyunki copies private hain. Agar dono cores directly ek shared memory se read karein, toh sync karne ki koi zaroorat hi nahin. Jis moment hum har core ko private copy allow karte hain, hum ek hi value ki do copies ki possibility create karte hain jo aapas mein disagree kar sakti hain. Isliye hum copies ko explicitly draw karte hain.

PICTURE. Neeche: main memory address $X$ ko value $5$ ke saath hold kar rahi hai. Do cores hain — Core 0 (blue) aur Core 1 (orange) — dono ke paas $X$ ke liye ek empty cache slot hai. Ek cache line sirf cache ki ek row hoti hai — woh unit jise hardware track karta hai. Abhi tak kuch copy nahin hua.

---

Step 2 — Dekhte hain kaise toot ta hai: stale-read bug

KYA HAI. Dono cores $X=5$ ko apne caches mein copy kar lein. Phir Core 0, $X=9$ sirf apne cache mein likhta hai (fast — memory tak koi trip nahin). Ab Core 1, $X$ ko apne cache se read karta hai aur $5$ paata hai.

YEH STEP KYU. Yeh ilaaj se pehle ki bimari hai. Hum galat answer dekhna chahte hain taaki pata chale protocol ko exactly kya forbid karna hai. Bug yeh hai: do copies alag ho gayi, aur reader ne purani copy pe yakeen kar liya.

PICTURE. Core 1 ke cache mein laal $5$ stale value hai; Core 0 ke cache mein hara $9$ sach hai. Memory abhi bhi $5$ keh rahi hai. Ek address ke liye teen alag "current values" — chaos.

---

Step 3 — Woh rule jo kabhi nahin todna (SWMR)

KYA HAI. Ek aisa law batao jo, agar maana jaye, toh bug impossible ho jaaye. Ise Single-Writer / Multiple-Reader kehte hain.

EXACTLY YEH LAW KYU. Step 2 ka bug tab tha jab ek writer (Core 0) active tha aur reader (Core 1) ke paas copy thi. Us overlap ko forbid karo aur bug ho hi nahin sakta. Isse zyada fancy kuch nahin chahiye — yeh minimal rule hai.

PICTURE. Address $X$ ke liye ek timeline. Hare read-intervals (kaafi cores allowed, overlap theek hai) aur narangi write-intervals (exactly ek core, exclusive). Rule: hare aur narangi bands time mein kabhi overlap nahin kar sakte.

Yahan se sab kuch mechanism hai — gadgets ka sabse chhota set jo is timeline ko legal rakhta hai.

---

Step 4 — Bus aur do sawaal jo har line poochti hai

KYA HAI. Caches ko ek shared wire do — bus — jise har cache snoop (sun sakti) kar sakti hai. Jab ek cache kisi line ko read ya write karna chahti hai toh woh bus par announce karti hai, aur baaki sab caches sunti hain aur react karti hain. Phir, sahi tarike se react karne ke liye, har cache apni copy par do yes/no sawaalon ke jawab se tag lagaati hai.

BUS KYU. SWMR ek global rule hai ("koi aur nahin likh raha"), lekin har cache sirf apne baare mein jaanti hai. Bus se ek cache doosron ke kaam ke baare mein jaanti hai bina seedha pooche — woh announcements sun leti hai. (Bus ke alternatives exist hain — Snooping vs Directory-based protocols dekho — lekin logic same hai.)

YEH DO SAWAAL KYU. SWMR sirf do cheezein care karta hai: kya main akela holder hun? (taaki bina kisi ko disturb kiye likh sakun) aur kya meri copy dirty hai? (taaki pata ho memory update karni hai ya nahin). Do yes/no sawaal → chaar combinations → chaar states.

$$\underset{\text{exclusive vs shared}}{\underbrace{\text{Only copy?}}}\times \underset{\text{modified vs clean}}{\underbrace{\text{Dirty?}}}$$

PICTURE. Bus ek horizontal rail ke roop mein dono caches aur memory ko join karta hai, oopar 2×2 table of answers float kar raha hai. Teen cells M, E, S se bhar jaati hain; chautha cell (dirty aur shared) grey hai — "abhi ke liye impossible."

Grey wala dirty + shared cell deliberately khaali hai. Ise yaad rakho — Step 8 use bharta hai.

---

Step 5 — READ transitions derive karna

KYA HAI. Ek core load (read) issue karta hai. Hum sirf SWMR + bus use karke decide karte hain ki woh kis state mein land karega.

DO OUTCOMES KYU. Jab reading cache Invalid hoti hai toh use line fetch karni padti hai, aur woh BusRd ("main $X$ read karna chahta hun") announce karta hai. Aage kya hoga yeh ek fact par depend karta hai jo bus reveal karta hai: kya koi aur already is line ko hold kar raha hai?

• Koi aur nahin rakhta → main ab ek clean value ki akeli copy hun → E mein land karo. E kyun, S kyun nahin? Kyunki provably akele hona valuable hai — Step 6 dikhata hai isse free mein likh sakte hain.
• Koi aur rakhta hai → ab do copies hain → dono S mein honi chahiye (read mode, kaafi readers). Jo holder M mein tha woh pehle apni dirty value write back karega taaki main sahi cheez padhu, aur woh S mein drop ho jaayega.

Term-by-term, read-miss rule:

$$\underset{\text{meri start state}}{\underbrace{I}}\stackrel{\underset{\text{"main read karna chahta hun"}}{\underbrace{\text{BusRd}}}}{\to }\{\begin{array}{ll}E& \text{if }\underset{\text{bus quiet rehti hai}}{\underbrace{\text{no sharer}}}\\ S& \text{if }\underset{\text{koi jawab deta hai}}{\underbrace{\text{sharer exists}}}\end{array}$$

PICTURE. Do mini-scenes side by side. Left: Core 0 akela → arrow $I\to E$. Right: Core 1 read karta hai jabki Core 0 already hold kar raha hai → dono $S$ end karte hain, saath mein ek chhota "pehle write-back agar dirty ho" note.

---

Step 6 — WRITE transitions derive karna (kyun E hero hai)

KYA HAI. Ek core store (write) issue karta hai. Likhne ke liye, SWMR demand karta hai ki woh single writer ho, toh baaki saari copies ko khatam (invalidate) karna padega. Interesting part yeh hai: iska kitna bus traffic lagta hai? — aur jawab starting state par depend karta hai.

CASE-BY-CASE KYU. Sole writer banne ki cost exactly doosri copies khatam karne ki cost hai. Toh hum sort karte hain "abhi kitni doosri copies hain" ke hisaab se, jo precisely current state batata hai.

• E se → mujhe pehle se pata hai main akela hun. Koi invalidate karne ki zaroorat nahin. E → M silently — zero bus messages. E state rakhne ka yahi poora faayda hai.
• M se → pehle se dirty sole owner hun. Dubara likho; M mein raho.
• S se → doosre copies rakh sakte hain. BusRdX (Read-for-Ownership) broadcast karo unhe invalidate karne ke liye, phir S → M.
• I se → mere paas data bhi nahin hai. BusRdX broadcast karo: line fetch karo aur doosron ko invalidate karo, phir M mein land karo.

$$E\stackrel{\text{silent}}{\to }M,S\stackrel{\text{BusRdX}}{\to }M,I\stackrel{\text{BusRdX}}{\to }M$$

Yahan $\text{BusRdX}$ = "data mere paas lao aur baaki sabki copy invalidate karo." X ka matlab write nahin hai; actual store locally hota hai baad mein jab line aa jaati hai.

PICTURE. Teen write scenes stack kiye: green silent arrow $E\to M$ (no bus), aur do laal $\stackrel{\text{BusRdX}}{\to }M$ arrows jo $S$ aur $I$ se bus ke paas jaake doosre caches ko $I$ par slam karte hain.

---

Step 7 — SNOOP (doosron par react) transitions derive karna

KYA HAI. Abhi tak ek cache tab action leti thi jab use kuch chahiye hota tha. Ab use react karna hai jo woh bus par sun rahi hai — yeh SWMR ko globally true rakhne ka doosra aadha hai.

KYU. SWMR ek do-taraf ka contract hai: jab aap writer bante ho, doosron ko peechhe hatna padta hai. Step 6 "main likhta hun" wala side tha; yeh "koi aur kuch karta hai, main comply karta hun" wala side hai.

• Main M hold kar raha hun, BusRd sunta hun (koi read karna chahta hai): mere paas akeli achhi copy hai, toh main use memory mein write back karta hun (ya forward karta hun) aur M → S drop ho jaata hun — ab hum ek clean value share karte hain.
• Main E hold kar raha hun, BusRd sunta hun: write-back ki zaroorat nahin (main clean tha), bas E → S.
• Main koi bhi valid state (M/E/S) mein hun aur BusRdX ya invalidate sunta hun: koi likhne wala hai → meri copy khatam honi chahiye → → I. Agar main M tha, main pehle write back karta hun taaki akeli achhi copy na kho jaaye.

$$M\stackrel{\text{BusRd}}{\to }S,E\stackrel{\text{BusRd}}{\to }S,(M,E,S)\stackrel{\text{BusRdX}}{\to }I$$

PICTURE. Poori MESI state machine assembled: chaar nodes M, E, S, I ke saath Steps 5–7 ke har arrow par bus event label aur colour-code (solid = is core ka action, dashed = snooped reaction).

Recall Check: kaun si state bina bus traffic ke likhti hai?

Kaun sa single MESI state silently M mein upgrade hota hai? ::: E (E→M), kyunki aap provably akele holder hote ho.

---

Step 8 — Woh degenerate case jo MOESI ka O invent karta hai

KYA HAI. Step 7 ka pehla rule dobara dekho: ek M line jo BusRd sunta hai, share karne se pehle dirty data memory mein poora write back karna padta hai. Jab ek value baar baar doosron ke dwara read hoti hai (ek hot shared variable), hum woh slow memory write baar baar bharte hain — aksar sirf isliye ki value jaldi overwrite ho jaaye.

YEH REAL DEGENERATE COST KYU HAI. Memory cache-to-cache bus hop se kaafi slow hai. Har share par write back karna shared-but-dirty data ka worst case hai. Step 4 ka grey cell (dirty + shared) "impossible" sirf isliye tha kyunki hum usse naam dene wala state nahin tha. Naam do aur problem khatam.

Shared read ke liye naya snoop rule:

$$M\stackrel{\text{BusRd}}{\to }O(\text{data reader ko forward karo, memory }\text{update nahin}\text{ hoti});\text{reader}\to S$$

Memory tab write back hoti hai jab owner finally evict hota hai.

PICTURE. Left: MESI path — M line apni value poori tarah neeche slow memory tak bhejti hai (red, lamba arrow), phir M→S. Right: MOESI path — M→O dirty value rakhta hai aur use seedha reader ko sideways forward karta hai (green, chhota arrow); memory untouched.

---

Ek-picture summary

Upar sab kuch compress karke: 2×2 "do sawaal" grid ne M, E, S, I diya; SWMR ne arrows force kiye; ek impossible cell O ban gayi. Arrows solid (mera action) vs dashed (maine kuch sun liya) padhiye.

Recall Feynman retelling — poora walkthrough seedhe alfaazon mein

Do dost ek library book se ek page photocopy karte hain (Step 1). Problem: agar ek apni copy edit kare aur doosra apni copy padhta rahe, toh woh jhooth padh raha hai (Step 2). Toh hum ek law banate hain: jab koi edit kare, kisi aur ke paas copy na ho; jab log sirf padh rahe hon, koi edit na kare (Step 3, SWMR). Ise maanne ke liye, sab apni intentions poore kamre mein chillate hain — ek shared bus — aur har koi apne page par do cheezein likhta hai: kya sirf mere paas yeh page hai? aur kya maine isme kuch likha hai? Do yes/no cheezein chaar labels banati hain: I (koi page nahin), S (clean, doosron ke paas bhi ho sakta hai), E (clean, sirf mere paas), M (likha hua, sirf mere paas) (Step 4). Jab aap read karna chahte ho aur kuch nahin hai, tum chillate ho "BusRd"; agar koi jawab na de tum akele ho → E, warna share karo → S (Step 5). Jab aap write karna chahte ho, aapko akele hona zaroori hai, toh agar aap E mein hain toh quietly likh sakte ho free mein, lekin S ya I se pehle chillana padta hai "BusRdX — sab log woh page faad do!" phir edit karo → M (Step 6). Jab aap kisi aur ki awaaz sun'te ho, comply karte ho: read suna? S mein drop karo (agar likha tha toh write back karo); BusRdX suna? apna page phenko → I (Step 7). Aakhir mein, har baar jab koi dost aapka likha hua page maange toh library jaake master book update karne ke bajaye, seedha apna fresh version photocopy karke unhe do aur ownership rakhho — yeh O state hai, aur master sirf tab update hota hai jab aap finally apna page phenko (Step 8).

Related deep context: Cache Coherence vs Memory Consistency, Bus arbitration & interconnect, aur poora Memory Hierarchy & Caches backdrop.