MESI - MOESI coherence protocols: Worked examples — Hinglish deep dive

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

Yeh page parent topic ke liye exhaustive drill room hai. Parent ne state machine sikhaya; yahan hum har tarah ki situation walk karte hain jo protocol face kar sakta hai — har state jisse tum start kar sakte ho, har bus event jo tum snoop kar sakte ho, weird zero/degenerate cases (self-writes, evictions, already-invalid lines), aur timing twists jo exam-setters ko bahut pasand hain. Agar tum neeche ke saare cells ka outcome predict kar sako, toh protocol tumhara ho gaya.

Shuru karne se pehle, woh vocabulary jo hum use karenge (sab parent mein define hai, yahan dobara bata rahe hain taaki koi symbol bina explain ke na aaye):

Related reading jo tum doosre tab mein kholna chahoge: Snooping vs Directory-based protocols, Write-back vs Write-through caches, False Sharing, MOESI in AMD, MESIF in Intel.

Scenario matrix

Coherence ek state machine hai, isliye "har scenario" = (starting state) × (event) × (protocol), plus degenerate/timing edge cases. Yeh hai woh complete grid jo hum cover karenge. Har cell us example ka naam deta hai jo us case ko hit karta hai.

Case class	Concrete situation	Covered by
Cold miss → sole owner	Aisa address read karo jो kisi ke paas nahi	Ex 1 (step 1)
Cold miss → sharer	Aisa address read karo jo kisi aur ke paas hai	Ex 1 (step 2)
Silent upgrade	E mein likhte hue (zero bus traffic)	Ex 2
Write while Shared	S se store ko invalidate chahiye	Ex 3
Write miss (I→M)	Aisi line mein store karo jo tumhare paas nahi	Ex 4
Snoop BusRd while M (MESI)	Forced write-back, M→S	Ex 5
Snoop BusRd while M (MOESI)	M→O, cache-to-cache, memory write nahi	Ex 6
Owner shares again	O line se teesra reader	Ex 6 (extension)
Eviction of dirty line	O/M evict hona → woh ek memory write	Ex 7
Degenerate: self write-write	Same core do baar likhta hai, no bus	Ex 8
Degenerate: already-I snoop	Bus event aisi line par jo tumhare paas nahi	Ex 8 (verify)
Real-world word problem	Producer/consumer flag	Ex 9
Exam twist: false sharing	Do variables, ek line, ping-pong	Ex 10

Worked examples

Worked example Example 1 — Cold miss, sole owner

aur cold miss with a sharer (cells 1–2) Setup: Fresh caches, memory mein X=5 hai. Sequence: C0 reads X, phir C1 reads X.

Forecast: Step 1 ke baad C0 ki state guess karo, aur step 2 ke baad dono states, aage padhne se pehle.

C0 read, line is I → miss. C0 BusRd broadcast karta hai. Koi cache jawab nahi deta "mere paas hai."
- Yeh step kyun? SWMR (single-writer/multiple-reader) ke liye C0 ko jaanna hoga ki copies exist karti hain ya nahi. Bus par silence = yeh sole holder hai → C0 = E.
C1 read, line is I → miss. C1 BusRd broadcast karta hai. Ab C0 use snoop karta hai.
- C0 ko react kyun karna padega? C0 E mein tha (claim karta tha only copy). Ek doosra reader aata hai, toh woh claim ab false hai → C0: E→S. C1 ko data milta hai aur woh S mein land karta hai.
- E mein kyun nahi rehta? Kyunki E ka matlab hai "provably the only one" — jis pal do caches line hold karte hain, dono ko S par drop karna hoga.

Verify: Final = C0=S, C1=S. Dono clean, read-only, memory unchanged (X=5). SWMR holds: multiple readers, zero writers. ✔

Figure — MESI - MOESI coherence protocols

Worked example Example 3 — Write while Shared (cell "write while Shared")

Setup: Example 1 se continue: C0=S, C1=S, X=5. Ab C0 X=9 write karta hai.

Forecast: Kaun sa message fire hoga, aur C1 ka kya hoga?

C0 store, line is S. S read-only aur possibly shared hai, isliye C0 seedha write nahi kar sakta. Woh BusRdX (Read-for-Ownership) broadcast karta hai.
- BusRdX kyun aur BusRd kyun nahi? SWMR: single writer banne ke liye, baaki har copy ko khatam hona chahiye. X precisely "invalidate others" flag hai.
C1 snoops BusRdX while in S → C1: S→I. C0 phir locally store complete karta hai → C0: S→M.
- C1 I kyun ho jaata hai? Iska copy stale ho jaata jis pal C0 likhta, isliye use ab discard karte hain.

Verify: Final = C0=M (dirty, X=9), C1=I. Exactly ek writer, koi valid stale copy nahi. Memory abhi bhi 5 kehti hai — theek hai, M matlab "main memory ko baad mein write-back karunga." ✔

Worked example Example 4 — Write miss, I→M (cell "write miss")

Setup: C0=M X=9 ke saath (Ex 3 se). C1 ki line I hai. Ab C1 X=12 write karta hai.

Forecast: C1 ke paas kuch nahi hai — use kya fetch karna padega, aur C0 ki dirty value ka kya hoga?

C1 store, line is I → write miss. C1 BusRdX broadcast karta hai.
- Fetch kyun karein agar C1 overwrite kar raha hai? Store cache line ke sirf ek part ko touch kar sakta hai; line ke baaki bytes correct hone chahiye. RFO current line ko read karta hai, phir C1 apne bytes likhta hai.
C0 snoops BusRdX while in M. C0 ko pehle apna dirty 9 flush karna hoga (warna ek hi acha copy kho jaayega), phir C0: M→I.
- Invalidate karne se pehle flush kyun? M sole valid copy hai; use save kiye bina discard karna memory corrupt kar deta.
C1 line receive karta hai, apna store apply karta hai → C1: I→M X=12 ke saath.

Verify: Final = C0=I, C1=M (X=12). Ek dirty owner, koi stale copy nahi. C0 ka 9 safely pass on/write ho gaya khatam hone se pehle. ✔

Worked example Example 6 — Wahi read, MOESI: M→O, no memory write (cell "M snoops BusRd, MOESI" + owner-shares-again)

Setup: MOESI. C0=M (X=9), C1=I. C1 X read karta hai. Phir C2 bhi X read karta hai.

Forecast: Dono reads mein kitni memory writes hoti hain? Ex 5 se compare karo.

C1 read → BusRd. C0 snoops while M. MOESI dirty+shared allow karta hai, isliye C0 9 rakhta hai, owner ban jaata hai: C0: M→O, aur 9 cache-to-cache C1 ko forward karta hai. Memory touch NAHI hoti. C1 → S.
- Behtar kyun? Humne memory round-trip skip ki; dirty value O mein rehti hai aur sirf owner eventual write-back ke liye zimmedar hai.
C2 read → BusRd. C0 (ab O mein) snoops. Owner dobara C2 ko 9 supply karta hai, O mein rehta hai. C2 → S.
- C0 O mein kyun rehta hai? Owner = "is dirty line ke liye zimmedar aur use supply karne wala." Zyada sharers us role ko nahi badlaate.

Verify: Final = C0=O, C1=S, C2=S, memory abhi bhi 5 (0 memory writes). Jabki MESI uhi reads ke liye 1 (ya zyada) memory writes pay karta. ✔

Worked example Example 7 — Owner ka eviction: woh

ek memory write (cell "eviction of dirty line") Setup: Ex 6 se: C0=O (9), C1=S, C2=S, memory=5. C0 ko ek naye address ke liye yeh cache set chahiye → woh owned line evict karta hai.

Forecast: Dirty 9 kahan jaata hai? C1/C2 badlaate hain kya?

C0 ek O line evict karta hai. O dirty hai, isliye eviction par C0 memory mein 9 write-back karta hai, phir → I.
- Ab kyun, pehle kyun nahi? MOESI write-back ko last possible moment tak defer karta hai — exactly tab jab dirty owner gayab hone wala ho.
C1, C2 untouched rehte hain — woh S mein rehte hain. Lekin ab koi owner nahi hai.
- Edge case: unhe se koi agle snoop par owner promote ho sakta hai, ya memory (ab 9, clean) sirf future readers ko supply karta hai. Dono ways mein SWMR holds kyunki sab read-only hain.

Verify: Final = C0=I, C1=S, C2=S, memory=9 (single deferred write). Pure Ex 6+7 saga ke liye total memory writes = 1, maximally deferred. ✔

Worked example Example 8 — Degenerate cases: self write-write, aur Invalid line par snoop

Setup: (a) C0=M (X=9) X=20 write karta hai, phir X=21 write karta hai. (b) Alag se, C3=I X ke liye ek BusRdX snoop karta hai.

Forecast: Do consecutive self-writes ke liye kitni bus messages? C3 kya karta hai?

(a) Pehla store, line is M. Already dirty aur sole owner → M mein rehta hai, locally write karta hai. 0 messages.
Doosra store, abhi bhi M. Wahi reasoning → M mein rehta hai, X=21. 0 messages.
- Traffic bilkul kyun nahi? M already SWMR satisfy karta hai (single owner, koi doosri copy nahi). Coordinate karne ki zaroorat nahi.
(b) C3 in I snoops BusRdX. C3 ke paas kuch valid nahi → I mein rehta hai, koi action nahi, koi flush nahi.
- Kuch nahi kyun? Woh data kho nahi sakte jo tumhare paas hai hi nahi, aur invalidate karne ke liye kuch nahi hai. Invalid "sab-absorb-karo, kuch-mat-karo" state hai.

Verify: Dono self-writes ke liye bus messages = 0 total. C3 I mein rehta hai aur 0 responses issue karta hai. C0 mein final value = 21. ✔

Worked example Example 9 — Real-world word problem: producer / consumer flag

Setup: Core P (producer) ek buffer fill karta hai, phir ready=1 set karta hai. Core C (consumer) ready read karta rehta hai jab tak use 1 na mile. Initially ready=0, dono caches I. ready par coherence traffic trace karo.

Forecast: MESI mein, C ke pehle spin se 1 dekhne tak ready ki line kaafi baar caches ke beech bounce karti hai (ping-pong count)?

C ready read karta hai (I→miss). BusRd, kisi ke paas nahi → C = E, 0 dekhta hai. Spinning jaari hai: E mein baar baar reads hits hain, koi bus traffic nahi jab tak C use hold karta hai.
P ready=1 write karta hai (I→miss, ek store). P BusRdX broadcast karta hai. C snoop karta hai jab E mein hai → C: E→I. P → M 1 ke saath. (bounce #1: line P ki taraf gayi)
C ki agli spin read miss karti hai (I). BusRd. P snoop karta hai jab M mein hai →
- MESI: P flush karta hai, P: M→S, C → S, 1 dekhta hai. (bounce #2: line C ke paas wapas)

Verify: C-first-read se C-sees-1 tak ping-pong count = 2 bus transfers (P use write ke liye grab karta hai, C use read ke liye wapas grab karta hai). Yeh ek flag hand-off ki fundamental cost hai, aur isliye tight spin loops jaldi-se-badlne-wale flag par abhi bhi sirf couple of transfers cost karte hain, har spin par ek nahi. ✔

Worked example Example 10 — Exam twist: false sharing (cell "false sharing")

Setup: Variables a aur b alag addresses par hain lekin same 64-byte cache line mein baithte hain. C0 baar baar sirf a write karta hai; C1 baar baar sirf b write karta hai. Har ek N=1000 writes karta hai, strictly alternating C0, C1, C0, C1, …

Forecast: Woh kabhi same variable nahi chhuote — toh guess karo: zero coherence traffic, ya storm?

C0 a write karta hai. Poori line M mein chahiye → BusRdX, C1 ki copy invalidate karta hai. C0 → M.
C1 b write karta hai. Lekin uski line copy abhi invalidate ho gayi → write miss → BusRdX, C0 se line pull karta hai (flush/forward), C0 ko invalidate karta hai. C1 → M.
Yeh har alternation par repeat hota hai.
- Itna bura kyun? Coherence poore cache lines track karta hai, individual variables nahi. Chahe a aur b kabhi overlap na karein, woh ek line share karte hain, isliye har write use ping-pong karta hai. Dekho False Sharing.

Verify: 2N writes mein strict alternation ke saath, pehle ke baad har write ek line transfer force karta hai → BusRdX count = 2N − 1 = 1999 transfers pair ke liye. Fix: a aur b ko alag cache lines par pad karo → steady state mein transfers 0 ho jaate hain. ✔

Active recall

Recall Answers cover karo aur har cell predict karo

Fresh line par do reads: final states? ::: Dono S (pehla E gaya, doosre reader par S mein drop hua).
E→M silent upgrade ke liye bus messages? ::: 0.
S se store kaun sa message use karta hai? ::: BusRdX (doosron ko invalidate karo), phir S→M.
M, MESI vs MOESI mein BusRd snoop karta hai? ::: MESI: flush + M→S (memory write). MOESI: M→O, cache-to-cache, koi memory write nahi.
Deferred MOESI memory write aakhir kab pay hoti hai? ::: O (ya M) line ke eviction par.
False sharing: alag variables hone ke bawajood traffic kyun? ::: Coherence cache line per hota hai, variable per nahi.
I line par snoop event? ::: Kuch mat karo — koi data khoone ya invalidate karne ke liye nahi hai.