MESI - MOESI coherence protocols
WHY does coherence even need a protocol?
Imagine two cores, each with a private L1 cache, sharing address X = 5.
- Core 0 loads
X→ cachesX=5. - Core 1 loads
X→ cachesX=5. - Core 0 writes
X=9into its own cache (fast, no memory trip). - Core 1 now reads
Xfrom its cache → gets 5. ❌ Stale!
The hardware must guarantee the Single-Writer / Multiple-Reader (SWMR) invariant:
Coherence protocols enforce SWMR by tracking a state per cache line and snooping the shared bus (or directory) for what other caches do.
The MESI states — WHAT each letter means
Each cache line carries 2 bits of state:
WHY four states and not two? The naïve "Valid/Invalid" scheme forces a bus broadcast on every write. E is the clever optimization: if you are the only holder of a clean line, you can write silently (no bus traffic) by transitioning E→M. This is why loading a private variable then modifying it is cheap.
HOW state transitions work (derivation from SWMR)
We derive the transitions by asking: "What must happen to keep SWMR true?"
Local read (Core issues a load):
- If line is M/E/S → hit, stay.
- If I → read miss. Broadcast BusRd.
- If some other cache has it → they supply it (or memory does); you land in S. Any cache in M must write back first.
- If no one else has it → you land in E (you're the sole owner). WHY E? Because you now know you're exclusive, enabling later silent writes.
Local write (Core issues a store):
- If M → hit, stay M.
- If E → silently go E→M (no bus traffic!). WHY allowed? You're the only holder, so no one else needs invalidating.
- If S → broadcast BusRdX (Read-for-Ownership) to invalidate all other copies, then go S→M. WHY? SWMR: before writing you must be the single writer.
- If I → write miss: broadcast BusRdX, fetch data, invalidate others, land in M.
Snooped (remote) events — react to the bus:
- See BusRd while in M → someone wants to read; you must supply/flush → go M→S (and update memory).
- See BusRd while in E → go E→S (now shared).
- See BusRdX (or an invalidate) in ANY valid state → go → I. If you were M, write back first (don't lose the only good copy!).
MOESI — adding the O (Owned) state
WHY add O? In plain MESI, when a core in M is asked for a read (BusRd), it must transition M→S and write the dirty data back to memory. That write-back is expensive and often wasted (the value might change again soon).
With MOESI:
- On a BusRd, the M holder goes M→O instead of M→S. It keeps the dirty data, becomes the owner, and directly forwards data to the requester (cache-to-cache transfer). Memory is NOT updated. Requesters get S.
- Only when the owner is finally evicted does memory get written.
MOESI states: M, O, E, S, I (5 states, 3 bits).
Worked examples
Common mistakes (steel-manned)
Active recall
Recall Quick self-test (cover the answers!)
- Which single MESI state lets you write with no bus traffic? → E (E→M silent).
- What invariant do all coherence protocols enforce? → SWMR.
- Which state does MOESI add and what does it represent? → O, dirty-and-shared owner.
- What must an M-state line do when it snoops a BusRd (in MESI)? → write back and go M→S.
- In MOESI, on a BusRd the M line goes to ___ and forwards data instead of writing memory. → O.
Recall Feynman: explain to a 12-year-old
Imagine a class sharing one library book by photocopying pages into their notebooks. If everyone just reads their copy, fine. But if Aisha edits her copy, everyone else's notebook is now wrong. So we make a rule: before you edit, you shout "I'm editing! Everyone tear out that page!" (that's invalidate). If you're the only one who copied it, you can edit quietly. And 'Owned' (MOESI) is like: instead of running to the library to update the master book every time a friend asks, the person with the freshest edits just photocopies it for the friend directly — much faster.
Flashcards
What problem do cache coherence protocols solve?
State the SWMR invariant.
What do the letters MESI stand for?
What is the Exclusive (E) state and why does it exist?
Difference between M and E?
Difference between E and S?
What bus message is sent on a write to a Shared line?
What happens to an M line when it snoops a BusRd (in MESI)?
What does the O (Owned) state in MOESI represent?
Why is MOESI faster than MESI for shared dirty data?
Does BusRdX write the data to memory?
What state results from a read miss when no other cache holds the line?
List the 5 MOESI states.
Which MESI-impossible combination does O fill?
Connections
- Cache Coherence vs Memory Consistency — coherence = per-location ordering; consistency = across-location ordering.
- Snooping vs Directory-based protocols — how the messages are actually delivered/scaled.
- Write-back vs Write-through caches — M state only makes sense with write-back.
- False Sharing — coherence traffic caused by unrelated data on one line.
- MOESI in AMD and MESIF in Intel — real-world variants (F = Forwarder).
- Memory Hierarchy & Caches — parent chapter.
- Bus arbitration & interconnect — the medium that carries BusRd/BusRdX.
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Dekho, problem simple hai: har CPU core ka apna private cache hota hai, aur ek hi memory address kai caches me copy ho sakta hai. Agar Core 0 apne cache me X ko badal de aur Core 1 apne purane copy se padhe, toh Core 1 ko stale (purana) data milega — bilkul galat. Isko rokne ke liye hardware ek rule enforce karta hai jise SWMR kehte hain: kisi bhi ek address ko ek time pe ya toh sirf ek core write kar sakta hai, ya koi bhi write nahi aur multiple cores read kar sakte hain.
MESI protocol har cache line ko 4 states me se ek deta hai — M (dirty aur akela), E (clean aur akela), S (clean, doosre caches me bhi ho sakta hai), aur I (invalid, matlab data hai hi nahi). Sabse smart cheez E state hai: agar tumhare paas hi akli clean copy hai, toh tum bina bus pe koi message bheje silently E→M ho ke write kar sakte ho. Isi wajah se uncontended lock lena bahut sasta padta hai. Jab tumhe write karna ho aur line Shared ho, tab tum BusRdX bhejte ho jo baaki sab copies ko invalidate kar deta hai — tab jaake tum akle writer bante ho.
MOESI me ek extra state O (Owned) add hoti hai — yeh "dirty + shared" wali impossible combination ko fill karti hai jo MESI me nahi ho sakti. Fayda? MESI me jab koi doosra core dirty line ko read maangta hai, toh M-holder ko pehle memory me write-back karna padta hai (slow). MOESI me woh M→O ho jata hai aur data seedhe cache-to-cache forward kar deta hai, memory ko touch kiye bina. Memory tabhi update hoti hai jab owner line evict karta hai. Isiliye AMD chips MOESI use karte hain — shared dirty data ke liye fast.
Exam tip: agar question bole "dirty aur shared dono ek saath" — toh yeh MESI me impossible hai, MOESI ka O state hai. Aur yaad rakhna: BusRdX ka 'X' write nahi karta, woh sirf read karta hai aur doosron ko invalidate karta hai; actual store baad me local hota hai.