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

This page is the exhaustive drill room for the parent topic. The parent taught the state machine; here we walk every kind of situation the protocol can face — every state you can start in, every bus event you can snoop, the weird zero/degenerate cases (self-writes, evictions, already-invalid lines), and the timing twists exam-setters love. If you can predict the outcome of all cells below, you own the protocol.

Before we start, the vocabulary we will lean on (all defined in the parent, restated here so no symbol is used unearned):

Related reading you may want open in another tab: Snooping vs Directory-based protocols, Write-back vs Write-through caches, False Sharing, MOESI in AMD, MESIF in Intel.

The scenario matrix

Coherence is a state machine, so "every scenario" = (starting state) × (event) × (protocol), plus the degenerate/timing edge cases. Here is the full grid we will cover. Each cell names the example that hits it.

Case class	Concrete situation	Covered by
Cold miss → sole owner	Read address nobody has	Ex 1 (step 1)
Cold miss → sharer	Read address someone else has	Ex 1 (step 2)
Silent upgrade	Write while E (zero bus traffic)	Ex 2
Write while Shared	Store from S needs invalidate	Ex 3
Write miss (I→M)	Store to a line you don't hold	Ex 4
Snoop BusRd while M (MESI)	Forced write-back, M→S	Ex 5
Snoop BusRd while M (MOESI)	M→O, cache-to-cache, no memory write	Ex 6
Owner shares again	Third reader off an O line	Ex 6 (extension)
Eviction of dirty line	O/M evicted → the one memory write	Ex 7
Degenerate: self write-write	Same core writes twice, no bus	Ex 8
Degenerate: already-I snoop	Bus event on a line you don't hold	Ex 8 (verify)
Real-world word problem	Producer/consumer flag	Ex 9
Exam twist: false sharing	Two vars, one line, ping-pong	Ex 10

Worked examples

Worked example Example 1 — Cold miss, sole owner

and cold miss with a sharer (cells 1–2) Setup: Fresh caches, memory holds X=5. Sequence: C0 reads X, then C1 reads X.

Forecast: Guess C0's state after step 1, and both states after step 2, before reading on.

C0 read, line is I → miss. C0 broadcasts BusRd. No cache answers "I have it."
- Why this step? SWMR (single-writer/multiple-reader) needs C0 to learn whether copies exist. Silence on the bus = it is the sole holder → C0 = E.
C1 read, line is I → miss. C1 broadcasts BusRd. Now C0 snoops it.
- Why C0 must react? C0 was E (claiming only copy). A second reader appears, so that claim is now false → C0: E→S. C1 receives the data and lands in S.
- Why not stay E? Because E means "provably the only one" — the moment two caches hold the line, both must drop to S.

Verify: Final = C0=S, C1=S. Both 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: Continue from Example 1: C0=S, C1=S, X=5. Now C0 writes X=9.

Forecast: Which message fires, and what happens to C1?

C0 store, line is S. S is read-only and possibly shared, so C0 cannot just write. It broadcasts BusRdX (Read-for-Ownership).
- Why BusRdX and not BusRd? SWMR: to become the single writer, every other copy must die. The X is precisely the "invalidate others" flag.
C1 snoops BusRdX while in S → C1: S→I. C0 then completes the store locally → C0: S→M.
- Why C1 goes I? Its copy would become stale the instant C0 writes, so it is discarded now.

Verify: Final = C0=M (dirty, X=9), C1=I. Exactly one writer, no valid stale copies. Memory still says 5 — that's fine, M means "I owe memory a write-back later." ✔

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

Setup: C0=M with X=9 (from Ex 3). C1's line is I. Now C1 writes X=12.

Forecast: C1 holds nothing — what must it fetch, and what happens to C0's dirty value?

C1 store, line is I → write miss. C1 broadcasts BusRdX.
- Why fetch at all if C1 is overwriting? The store may touch only part of the cache line; the rest of the line's bytes must be correct. RFO reads the current line in, then C1 writes its bytes.
C0 snoops BusRdX while in M. C0 must flush its dirty 9 first (else the only good copy is lost), then C0: M→I.
- Why flush before invalidating? M is the sole valid copy; discarding it without saving would corrupt memory.
C1 receives the line, applies its store → C1: I→M with X=12.

Verify: Final = C0=I, C1=M (X=12). One dirty owner, no stale copies. C0's 9 was safely passed along/written before dying. ✔

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

Setup: MOESI. C0=M (X=9), C1=I. C1 reads X. Then C2 also reads X.

Forecast: How many memory writes across both reads? Compare with Ex 5.

C1 read → BusRd. C0 snoops while M. MOESI allows dirty+shared, so C0 keeps 9, becomes the owner: C0: M→O, and forwards 9 cache-to-cache to C1. Memory is NOT touched. C1 → S.
- Why better? We skipped the memory round-trip; the dirty value lives on in O and only the owner is responsible for the eventual write-back.
C2 read → BusRd. C0 (now O) snoops. The owner supplies 9 again to C2, stays O. C2 → S.
- Why C0 stays O? Owner = "the one responsible for this dirty line + supplying it." More sharers don't change that role.

Verify: Final = C0=O, C1=S, C2=S, memory still 5 (0 memory writes). Versus MESI which would have paid 1 (or more) memory writes for the same reads. ✔

Worked example Example 7 — Eviction of the owner: the

one memory write (cell "eviction of dirty line") Setup: From Ex 6: C0=O (9), C1=S, C2=S, memory=5. C0 needs this cache set for a new address → it evicts the owned line.

Forecast: Where does the dirty 9 go? Do C1/C2 change?

C0 evicts an O line. O is dirty, so on eviction C0 writes 9 back to memory, then → I.
- Why now and not earlier? MOESI defers the write-back to the last possible moment — precisely when the dirty owner is about to disappear.
C1, C2 are untouched — they stay S. But there is now no owner.
- Edge case: one of them may be promoted to owner on the next snoop, or memory (now 9, clean) simply supplies future readers. Either way SWMR holds because they're all read-only.

Verify: Final = C0=I, C1=S, C2=S, memory=9 (the single deferred write). Total memory writes for the whole Ex 6+7 saga = 1, deferred maximally. ✔

Worked example Example 8 — Degenerate cases: self write-write, and a snoop on an Invalid line

Setup: (a) C0=M (X=9) writes X=20, then writes X=21. (b) Separately, C3=I snoops a BusRdX for X.

Forecast: How many bus messages for the two consecutive self-writes? What does C3 do?

(a) First store, line is M. Already dirty and sole owner → stay M, write locally. 0 messages.
Second store, still M. Same reasoning → stay M, X=21. 0 messages.
- Why no traffic at all? M already satisfies SWMR (single owner, no other copies). Nothing to coordinate.
(b) C3 in I snoops BusRdX. C3 holds nothing valid → stay I, no action, no flush.
- Why nothing? You can't lose data you don't have, and there's nothing to invalidate. Invalid is the "absorb-everything, do-nothing" state.

Verify: Bus messages for both self-writes = 0 total. C3 stays I and issues 0 responses. Final value in C0 = 21. ✔

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

Setup: Core P (producer) fills a buffer, then sets ready=1. Core C (consumer) spins reading ready until it sees 1. Initially ready=0, both caches I. Trace the coherence traffic on ready.

Forecast: How many times does the line for ready bounce between caches (ping-pong count) in MESI, from C's first spin to seeing 1?

C reads ready (I→miss). BusRd, nobody has it → C = E, sees 0. Keeps spinning: repeated reads are hits in E, no bus traffic while C holds it.
P writes ready=1 (I→miss, a store). P broadcasts BusRdX. C snoops while in E → C: E→I. P → M with 1. (bounce #1: line moved to P)
C's next spin read misses (I). BusRd. P snoops while M →
- MESI: P flushes, P: M→S, C → S, sees 1. (bounce #2: line back to C)

Verify: Ping-pong count from C-first-read to C-sees-1 = 2 bus transfers (P grabs it to write, C grabs it back to read). This is the fundamental cost of a flag hand-off, and is why tight spin loops on a soon-to-change flag still cost only a couple of transfers, not one per spin. ✔

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

Setup: Variables a and b are different addresses but sit in the same 64-byte cache line. C0 repeatedly writes only a; C1 repeatedly writes only b. Each does N=1000 writes, strictly alternating C0, C1, C0, C1, …

Forecast: They never touch the same variable — so guess: zero coherence traffic, or a storm?

C0 writes a. Needs the whole line in M → BusRdX, invalidates C1's copy. C0 → M.
C1 writes b. But its line copy was just invalidated → write miss → BusRdX, pulls the line from C0 (flush/forward), invalidates C0. C1 → M.
This repeats every single alternation.
- Why so bad? Coherence tracks whole cache lines, not individual variables. Even though a and b never overlap, they share a line, so every write ping-pongs it. See False Sharing.

Verify: With strict alternation over 2N writes, each write after the first forces one line transfer → BusRdX count = 2N − 1 = 1999 transfers for the pair. Fix: pad a and b onto separate cache lines → transfers drop to 0 in steady state. ✔

Active recall

Recall Cover the answers and predict each cell

Two reads on a fresh line: final states? ::: Both S (first went E, dropped to S on the second reader).
Bus messages for E→M silent upgrade? ::: 0.
Store from S uses which message? ::: BusRdX (invalidate others), then S→M.
M snoops a BusRd in MESI vs MOESI? ::: MESI: flush + M→S (memory write). MOESI: M→O, cache-to-cache, no memory write.
When is the deferred MOESI memory write finally paid? ::: On eviction of the O (or M) line.
False sharing: why traffic despite different variables? ::: Coherence is per cache line, not per variable.
Snoop event on an I line? ::: Do nothing — no data to lose or invalidate.