Cache coherence — MESI protocol in multicore: Worked examples

Before we start, a one-line refresher of the alphabet so no symbol is used un-earned:

Recall The four state letters (say them out loud)

M — I hold the only valid copy and it is dirty (memory is stale). ::: M = Modified. E — I hold the only copy and it is clean (matches memory). ::: E = Exclusive. S — read-only, possibly shared with others, clean. ::: S = Shared. I — this line is garbage, a miss. ::: I = Invalid. The three broadcasts: BusRd = "I want to read"; BusRdX = "read to write" (also called RFO); BusUpgr = "I already share it, invalidate the others".

The scenario matrix

Every coherence event is one of these case classes. Think of each row as a "sign/quadrant" the way arctan has quadrants — MESI has states you start in × event that hits you.

#	Case class	Starting state	Trigger	Key outcome to test
C1	Cold read, no sharer	I	own read miss	must land in E, not S
C2	Cold read, sharer exists	I	own read miss	must land in S
C3	Silent write (the E win)	E	own write hit	M, zero bus traffic
C4	Write to a shared line	S	own write hit	BusUpgr, others → I
C5	Snooped read on dirty data	M	see BusRd	flush (cache-to-cache) + → S
C6	Snooped write (invalidate)	S/E/M	see BusRdX	→ I
C7	Degenerate eviction	E vs M	line replaced	E = silent drop, M = must write back
C8	Read-your-own repeatedly	M/E/S	own read hit	no state change, no bus traffic
C9	Limiting case: false-sharing storm	ping-pong	alternating writes	throughput collapse, different bytes
C10	Real-world twist: atomic RMW / lock	I or S	BusRdX for RMW	why atomics force ownership

The 8 examples below cover all ten cells (some examples hit two).

Example A — cold read with no sharer → E (cell C1)

Forecast: guess the ending state and the transaction count before reading on. (Two-state MSI thinkers will guess S — watch why that's wrong.)

Core 0 misses (its line is I) and broadcasts BusRd. Why this step? I means "no data"; the only way to get data is to ask the bus. The read miss table row for I says: issue BusRd.
Every other cache snoops. Core 1 is I → it says nothing (no "shared" signal on the bus). Why this step? The bus carries a shared line that any responder asserts if it holds a copy. Nobody asserts it here.
Core 0 reads the "no sharers" response and therefore installs the line as E. Why this step? This is the whole point of the E state: if I'm provably alone, I mark myself Exclusive so my next write can be silent.

Verify: exactly 1 bus transaction (the BusRd). Ending state = E. SWMR holds trivially — one clean reader, zero writers.

Example B — cold read while another core already shares → S (cell C2)

Forecast: E or S? And does Core 1's state change?

Core 0 misses, broadcasts BusRd. Why this step? Same as before — I has no data.
Core 1 snoops the BusRd while in S. Snoop table: S + BusRd → stay S, and it asserts the shared line. Why this step? A read by someone else does not threaten a read-only copy, so S stays S — but it must announce "a sharer exists" so the requester knows not to go Exclusive.
Core 0 sees "sharer present" → installs S (value 7). Why this step? Because a sharer exists, the E optimization is invalid; going E would be a lie ("I'm alone") that breaks SWMR the moment Core 0 tries a silent write.

Verify: Ending states: Core 0 = S, Core 1 = S. Two read-only copies, zero writers → SWMR satisfied.

Example C — the silent write, MESI's signature move (cell C3, and C8 for the reads)

Forecast: how many broadcasts total? A two-state design would need one for the write.

X = 1 while in E. E + write hit → silent → M. Zero bus transactions. Why this step? E already proved "I'm the only copy". So invalidating others is a no-op — there are no others. We just flip the state letter and mark the data dirty.
load X (M, read hit). M + read hit → stay M, no bus traffic. Why this step? I own the freshest copy; reading it is a pure local hit.
load X again. Same — stay M, no bus traffic. (This is cell C8: reading your own line is free.)

Verify: total bus transactions for all three instructions = 0. Contrast MSI, which would spend 1 BusUpgr on step 1. Savings = 1 transaction — exactly the E-state win from the parent's Example 2.

Forecast: which broadcast — BusRd, BusRdX, or BusUpgr? And what happens to Core 1?

Core 0 write hit in S → issue BusUpgr (not BusRdX!) → go M. Why this step? Core 0 already has the data, it just needs permission to be sole writer. BusUpgr means "invalidate the others, I keep my copy" — cheaper than BusRdX which also drags data.
Core 1 snoops BusUpgr (an invalidate) while in S → S → I. Why this step? SWMR forbids "one writer + other readers". So the instant Core 0 becomes writer, every reader must be invalidated. Core 1's 7 is now garbage.
Core 0 completes the write locally: value 9, state M, memory still stale.

Verify: Ending states: Core 0 = M (value 9), Core 1 = I. Exactly one writer, zero readers → SWMR holds. Bus transactions = 1 (the BusUpgr).

Figure — Cache coherence — MESI protocol in multicore

Example E — snooped read on dirty data (cache-to-cache) (cell C5)

Forecast: if you guessed "from DRAM", you just handed the program a stale 0. Predict what MESI does instead.

Core 1 misses, broadcasts BusRd. Why this step? Standard read miss.
Core 0 snoops BusRd while in M. Snoop table: M + BusRd → flush the dirty line + go S. Why this step? Core 0 owns the only correct value. If it stayed silent, DRAM's stale 0 would win. The flush is mandatory: it hands 1 to Core 1 (cache-to-cache) and also updates DRAM.
Core 1 installs S with value 1; Core 0 is now S. Why this step? We transition from "single writer (M)" to "multiple readers (S,S)" — a legal SWMR move.

Verify: value Core 1 reads = 1 (not the stale DRAM 0). Ending states: both S. DRAM is now also 1 (write-back happened during flush). One correct timeline for X.

Example F — the degenerate eviction: E is free, M is not (cell C7)

Forecast: does a clean eviction ever touch the bus? Does a dirty one?

(a) Evict from E. Clean means the cache's copy equals DRAM. Silently drop to I — 0 bus transactions. Why this step? Writing back would just re-store the identical bytes DRAM already has. Pointless, so MESI skips it. This is why the M/E split exists.
(b) Evict from M. Dirty means the cache holds the only correct value (5) and DRAM is stale (2). Must write back 5 to DRAM, then go I — 1 bus transaction. Why this step? Dropping silently would lose the write entirely — the SWMR "single writer owns truth" contract requires that truth be preserved before the line disappears.

Verify: eviction cost — (a) 0 transactions, (b) 1 transaction (the write-back). After (b), DRAM holds 5. This is the exact payoff of distinguishing M from E: clean evictions are free.

Forecast: they never touch the same byte — surely there's no conflict? Predict the state of the line after each write.

Core 0 writes counter[0] → BusRdX/BusUpgr, line → M on Core 0; Core 1's copy → I. Why this step? Coherence tracks whole lines, never individual bytes. From MESI's view, "the line" changed — it cannot tell byte 0 from byte 4.
Core 1 writes counter[1] → BusRdX; Core 0 flushes (M→I), Core 1 → M. Why this step? Same line, so Core 1 must take ownership, forcing Core 0 out — even though the bytes are disjoint.
Core 0 writes counter[0] again → BusRdX; Core 1 flushes (M→I), Core 0 → M. The line ping-pongs. Why this step? Each write re-triggers a full ownership transfer. The line bounces between cores every iteration.

Verify: over N interleaved writes, coherence transactions ≈ N (one ownership move per write) instead of ~0 if the counters were on separate lines. Fix: alignas(64) each counter → transactions drop to ~0. Nothing about the values is wrong; only throughput collapses.

Example H — the exam twist: atomic read-modify-write (cell C10)

Forecast: an atomic is "read then write". The read part could be a plain S hit — so why does MESI refuse to leave it there?

The atomic demands exclusive ownership up front → issue BusRdX (read-for-ownership) even though data is already present in S. Why this step? An atomic RMW must guarantee no other core writes between the read and the write. Only owning the line exclusively (M) makes that window uninterruptible. Sharing (S) would allow Core 1 to sneak a write in.
Core 1 snoops BusRdX while in S → S → I. Why this step? Same C6 rule: taking write-ownership invalidates all sharers.
Core 0 performs read-modify-write locally in M, then (if using cmpxchg) either commits or retries — but crucially the whole RMW happened while it was the single writer. Why this step? This is how a lock or counter stays correct: MESI's SWMR is what makes "atomic" atomic at the cache level. Ordering across addresses still needs fences — see Memory consistency models.

Verify: Ending states: Core 0 = M, Core 1 = I. Bus transactions = 1 (the BusRdX). SWMR holds throughout the RMW → the increment is not lost even if Core 1 raced it.

Recall Self-test: name the cell, then the ending state

Core in E does a write. State + bus traffic? ::: M, zero bus transactions (silent, cell C3). Core in M snoops a BusRd. State + what happens to the data? ::: flush cache-to-cache, drop to S (cell C5). Evicting a clean E line — how many write-backs? ::: zero — silent drop (cell C7a). Two threads write different bytes of one line — what breaks? ::: throughput via false-sharing ping-pong; correctness is fine (cell C9). Why does an atomic RMW on an S line issue BusRdX? ::: to own the line exclusively so no one writes mid-RMW (cell C10).

See also: Bus snooping and interconnects · Write-back vs write-through caches · Directory-based coherence · MOESI and MESIF extensions · Cache basics — tags, sets, lines.