Multicore coherence protocols: Worked examples — Coding deep dive

This page is a drill through every case class that multicore coherence protocols can throw at you. We start from the parent note 4.1.27 and go deeper: not one or two happy-path traces, but every corner — every state a block can be in, every bus event that can hit it, the zero/degenerate cases (eviction, self-write), the limiting behaviour (N cores all reading), and the exam twists.

Before you read a single worked example, meet the vocabulary as verbs and nouns you can picture, so no symbol is ever used before it is earned.

Why do we even need three different shouts instead of one? Because the cost differs. A plain read must not kick everyone else out (that would be wasteful) — so BusRd. A write from nothing must both fetch the data and clear others — BusRdX. A write from a shared copy already has the data, so it only needs the clearing half — BusUpgr, the cheapest write shout. Matching the shout to the situation is the entire art.

The scenario matrix

Every worked example below is tagged with the cell of this matrix it exercises. Together they cover every cell.

#	Case class	The specific corner	Example
A	Cold read, sole owner	I → load, nobody else has it	Ex 1 (MESI E)
B	Cold read, sharers exist	I → load, someone already has it	Ex 2
C	Write from Shared	S → M, must invalidate others	Ex 2, Ex 3
D	Write from Exclusive/Modified	E → M or M → M, silent, zero traffic	Ex 1
E	Snoop while Modified	another core reads my dirty line	Ex 3 (MSI), Ex 6 (MOESI)
F	Degenerate: eviction	dirty line thrown out → write-back; clean → silent	Ex 4
G	Degenerate: false sharing	two vars, one line, ping-pong	Ex 5
H	Limiting: N readers	all cores read, all end in S	Ex 7
I	Real-world word problem	producer/consumer flag	Ex 8
J	Exam twist: coherence ≠ correctness	reordering across two locations	Ex 9

Worked examples

Cell A + D — MESI: exclusive read, then a free write

Worked example Example 1 — the whole point of the E state

Machine uses MESI. Line for x is uncached everywhere: (I, I), memory clean. P0 reads x, then P0 writes x. Count the bus transactions.

Forecast: how many shouts total — 2, 1, or 0 for the write?

P0 reads x. Why this step? P0 has I (nothing), so a read miss forces a shout: BusRd. The bus samples the shared line — a wire that goes high if any other cache has this block. No one does → line low. Why does "line low" matter? It tells P0 it is the sole owner of a clean copy → load as E, not S. State: (E, I). 1 transaction so far.
P0 writes x. Why no shout? E already means "only I have it, and it matches memory." Nobody else could be holding a stale copy, so there is nobody to invalidate. P0 silently flips E → M. State: (M, I), memory now stale. 0 extra transactions.

Verify: total bus transactions $= 1$ (only the initial BusRd). Compare MSI: it would load as S, then the write needs a BusUpgr → 2 transactions. MESI saved exactly 1. Sanity: a single-threaded workload (only P0 ever touches x) pays coherence traffic only on the first miss, then runs free — that is precisely why real chips (Snooping vs Directory protocols) implement E.

Cell B + C — MSI: two readers, then one writer

Worked example Example 2 — the classic MSI four-step

Machine uses MSI. Start (I, I). P0 reads x → P1 reads x → P0 writes x. Give every state and shout.

Forecast: what state is P1 left in after P0's write?

P0 reads x. Why? miss → BusRd; MSI has no E, so a clean copy is always S. (S, I).
P1 reads x. Why BusRd again? P1 has I. It broadcasts BusRd; P0 (in S) keeps its copy, memory supplies (or P0 does) the data. (S, S). Cell B: sharers existed, so both stay S.
P0 writes x. Why BusUpgr and not BusRdX? P0 already has the data (it is in S) — it only lacks write permission. The cheap shout BusUpgr invalidates P1 without refetching. P0 → M, P1 → I. (M, I), memory stale. Cell C.

Verify: shouts issued = BusRd, BusRd, BusUpgr = 3 total, 1 of them an invalidate. P1 ends in I (its stale copy was dropped). Any later PrRd on P1 will miss and refetch the fresh value — coherence preserved. ✓

Cell C + E — MSI: writer meets a snoop on its dirty line

Worked example Example 3 — a second reader forces M → S

Continue Example 2 from (M, I) (P0 dirty). Now P1 reads x.

Forecast: does memory get updated during this read? Where does P0 end up?

P1 reads x. Why? P1 has I → BusRd on the wire.
P0 snoops the BusRd while in M. Why can't P0 stay M? M means exclusive — but a second reader is appearing, so exclusivity is gone. P0 must supply the fresh data to P1 (memory is stale, so P0 is the only correct source) and write back to memory so it becomes clean. P0: M → S. What it looks like: the dirty page is photocopied to P1 and the master notebook is corrected in the same breath.
Result: (S, S), memory now clean.

Verify: after the step both cores hold identical clean copies, memory matches. If we then asked "did any core read stale data?" — no: P1's read returned P0's most recent write (write-propagation property). ✓ Contrast MOESI in Ex 6, which skips the write-back here.

Cell F — Degenerate: eviction (dirty vs clean)

Worked example Example 4 — what happens when a line is thrown out

A cache must evict a line to make room. Consider two sub-cases in MESI: (a) the victim line is in M; (b) the victim line is in S or E.

Forecast: which sub-case causes a memory write, and why exactly one of them?

(a) Evict an M line. Why a write-back? M means "memory is stale — I hold the only correct value." Discarding it silently would lose the data. So eviction of M issues a write-back to DRAM first, then the line becomes I.
(b) Evict an S or E line. Why silent? S and E are both clean — memory already matches this copy. Nothing to save. The line just becomes I with no bus transaction.

Verify: memory-writes-on-eviction: M → 1 write-back; E → 0; S → 0. This is the operational difference between E and M that the parent-note mistake box warns about: they look identical ("only I have it") but differ precisely on the dirty bit → eviction cost. ✓

Worked example Example 5 — two independent variables, one hot line

int a, b; sit in the same 64-byte line. P0 loops writing a; P1 loops writing b. Neither reads the other's variable.

Forecast: since a and b are logically independent, is there any coherence traffic at all?

P0 writes a. Why does it invalidate P1? Coherence tracks whole lines, not bytes. The line holding a also holds b, so P0's BusRdX/BusUpgr puts P0 in M and forces P1 → I — even though P1 cares only about b. State: (M, I).
P1 writes b. P1 is now I on that line → it must shout BusRdX, pulling the line back, P0 → I. State: (I, M).
Repeat forever: the line ping-pongs. Each write is effectively a coherence miss.

Verify: invalidations per iteration ≈ 2 (one each way), so throughput collapses toward main-memory latency (~100× slower than an uncontended write). The fix is padding: alignas(64) int a; alignas(64) int b; puts them on separate lines → invalidations per iteration drop to 0. ✓

Cell E — MOESI: the Owned state defers the write-back

Worked example Example 6 — same snoop as Ex 3, but AMD-style

Machine uses MOESI. P0 holds x in M (dirty), P1 has I. P1 reads x.

Forecast: does memory get written now (like MSI/MESI) — or later?

P1 reads x → BusRd. P0 snoops it while in M.
P0 supplies the data cache-to-cache to P1. Why not write back to memory now? MOESI adds O (Owned): "I still hold the dirty master copy and I take responsibility to feed sharers." P0: M → O (stays dirty), P1: I → S. Memory stays stale. What it looks like: P0 photocopies its page to P1 but keeps the ink correction to itself — the master notebook is not yet fixed.
The costly DRAM write-back is deferred until P0 finally evicts the O line.

Verify: memory writes during this read: MESI = 1 (Ex 3), MOESI = 0. MOESI trades one extra state for saved DRAM bandwidth whenever a dirty line is shared before eviction. ✓ Uniqueness of the dirty copy still holds: at most one cache is in M or O per line.

Cell H — Limiting case: N cores all read

Worked example Example 7 — a read-only broadcast, scaled up

MESI, 8 cores, line uncached. Cores read x one after another: P0, P1, …, P7. No writes.

Forecast: what state is each core in at the end?

P0 reads. Shared line low → E. (E, I, I, I, I, I, I, I).
P1 reads. Why does P0 change? P0 snoops P1's BusRd, sees it is no longer sole owner → E → S silently. P1 loads as S (shared line now high). (S, S, I, …).
P2…P7 read. Each BusRd finds the line already shared → each loads as S; existing sharers stay S.
Final: all 8 in S, memory clean.

Verify: bus reads issued = 8 (one miss each). Invalidations = 0 (nobody wrote). This is the good limiting case: read-only shared data scales freely — any number of cores can hold S simultaneously with zero coherence conflict. The state degrades from E→S exactly once (at the second reader), never again. ✓

Cell I — Real-world word problem: producer/consumer flag

Worked example Example 8 — a "done" flag between two threads

P0 (producer): data = 42; ready = 1; P1 (consumer): while(ready==0){} use(data); Assume data and ready are on different cache lines. Trace the coherence events for ready.

Forecast: how many times does the ready line change hands before P1 exits the loop?

P1 spins on ready. First read miss → BusRd → P1 loads ready=0 as E (or S). Subsequent spins are cache hits — no bus traffic while it stays 0. (This is why spin-loops don't melt the bus: coherence lets a reader camp on a clean copy silently.)
P0 writes ready=1. P0 must gain write permission → BusRdX/BusUpgr → P1's line → I. P0: M.
P1's next spin read misses (it is now I) → BusRd → fetches fresh ready=1, P0 downgrades M → S, loop exits.

Verify: the ready line transferred exactly once from producer to consumer (step 2 invalidate + step 3 refetch = one hand-off). Coherence guarantees P1 eventually sees ready=1 (write propagation). ✓ But — see Ex 9 — coherence alone does not guarantee P1 sees data=42 before ready=1.

Cell J — Exam twist: coherence ≠ correctness

Worked example Example 9 — why Example 8 still needs a fence

Same producer/consumer as Ex 8. The CPU/compiler is allowed to reorder P0's two independent stores (data and ready are different addresses). Suppose the machine's consistency model permits ready=1 to become visible before data=42.

Forecast: can P1 read ready==1 and yet see the old data? Coherence said everyone sees the latest value…

What coherence guarantees: for data alone, and for ready alone, every core sees a single consistent value in a serialized order. Both lines are individually coherent.
What coherence does NOT guarantee: the relative order of a write to data versus a write to ready — those are two different locations. Coherence orders accesses per location, never across locations.
The bug: if ready=1 propagates first, P1 exits the loop and reads a stale data — a coherent-but-wrong result.
The fix: insert a release fence in P0 (after data, before ready) and an acquire fence in P1 — see Atomic operations and fences. This forbids the reordering; now ready=1 visible ⟹ data=42 visible.

Verify: count the properties. Coherence delivered = 2 (per-location correctness of data and of ready). Ordering-across-locations delivered by coherence = 0 — that is the consistency model's job. The steel-manned mistake in the parent note ("coherence makes my program correct") is exactly this cell: correct per location, unsafe across locations without synchronization. ✓

Recall Rapid self-test across the whole matrix

Which cell: a solely-owned clean line written with zero bus traffic? ::: Cell D — MESI E → M silent (Ex 1). Which cell: eviction that costs a DRAM write? ::: Cell F — evicting an M line (Ex 4a). Which cell: two independent variables killing performance? ::: Cell G — false sharing (Ex 5); fix with padding. Which cell: a coherent program that is still buggy? ::: Cell J — ordering across two locations needs a fence (Ex 9). In MOESI, what state lets a dirty owner feed sharers without a write-back? ::: O (Owned) — Cell E, Ex 6. When N cores all just read, what state do they all end in and how many invalidations occur? ::: All S, zero invalidations (Cell H, Ex 7).

Back to the parent: 4.1.27 Multicore coherence protocols · related: Cache memory hierarchy · Bus arbitration.