Cache coherence — MESI protocol in multicore: Visual walkthrough

Everything below is a consequence of that rule plus one desire: do it with the least bus traffic.

Step 1 — The picture of the problem: private copies drift apart

WHAT. Two CPU cores, each with its own small private cache, both connected to one big slow DRAM. A "line" is just a 64-byte chunk of memory; a cache holds copies of some lines.

WHY. We start here because the whole protocol exists to fix exactly one failure: two caches holding the same address with different values. You have to see the failure before the cure makes sense.

PICTURE. In the figure, Core 0's cache says X = 5 and Core 1's cache says X = 9 for the same address. The red box marks the disagreement. DRAM (bottom) still says 5. Nobody is right, and no core knows it is wrong.

This links to Cache basics — tags, sets, lines for how a line is actually stored and found.

Step 2 — Turn the rule into a token you can hold

WHAT. We reframe SWMR as a physical object: imagine a write-token for each line. To write, a cache must physically hold that line's token. There is exactly one token per line.

WHY. SWMR says "only one writer at a time." The cleanest way to enforce exactly one of anything is a single physical token — if you can't produce the token, you can't write. This is the mental model the four states are secretly implementing.

PICTURE. The token (red) sits in Core 0. Core 0 may write. Core 1 has no token, so Core 1 may only read a read-only copy — and only if the token-holder allows readers.

Step 3 — Split "I have the only copy" into clean vs dirty → E and M

WHAT. Take situation 1 (sole owner, token held). We split it into two states by asking one yes/no question: does my copy still match DRAM?

WHY. Because eviction cost differs. If my sole copy equals DRAM, I can silently drop it — no write-back. If I have changed it, I must write it back or the value is lost. Tracking this distinction saves a whole memory write on every clean eviction. This is the Write-back vs write-through caches idea living inside one state bit.

PICTURE. Two boxes for the sole owner:

E (Exclusive) — sole copy, clean (equals DRAM). Nobody else has it.
M (Modified) — sole copy, dirty (I changed it; DRAM is now stale). The red arrow shows the write-back debt I owe DRAM.

Step 4 — Split "no copy / read-only copies" → I and S

WHAT. Now the other side. If I do not hold the write-token, I am in one of two states:

I (Invalid) — I hold no valid copy at all. As good as empty.
S (Shared) — I hold a read-only copy that matches DRAM; zero or more other caches may also hold it in S.

WHY. Reads are the common case and should be cheap and parallel. SWMR happily allows many readers, so multiple caches sharing a clean copy is legal and fast — every one of them is a local hit. I is just the honest label for "I don't have it."

PICTURE. Left: two caches both in S with the same value 5, DRAM also 5 — all agree, all read-only. Right: one cache in I (red, empty) — it will have to fetch on its next access.

Definition All four states, now derived

State	# copies	Clean/dirty	May write?
M	1 (this one)	dirty	yes (silently)
E	1 (this one)	clean	yes (silently, → M)
S	≥1	clean	no (must ask first)
I	0	—	no (must fetch first)

We invented no state by decree — each fell out of two yes/no splits of SWMR.

Step 5 — The broadcasts that move the token (snooping)

WHAT. How does a cache acquire the token or a read-copy? It shouts on the shared interconnect, and every other cache snoops (listens) and reacts. Three shouts are enough:

BusRd — "I want to read line A." (a read miss)
BusRdX — "I want line A to write it" (read-for-ownership) — this takes the token.
BusUpgr — "I already have A shared; invalidate everyone else so I can write" — this also takes the token, but skips fetching data I already hold.

WHY. A token is useless if it can't move. These broadcasts are how ownership transfers and how everyone else learns to step aside. Snooping means no central manager is needed on a bus (contrast Directory-based coherence, which tracks owners in a table instead). See Bus snooping and interconnects.

PICTURE. Core 1 shouts BusRdX (red) onto the bus. Core 0, holding M, hears it, flushes its dirty value onto the bus (so Core 1 gets the freshest data, not stale DRAM), then drops to I. The token has moved.

Step 6 — The full state machine, one core's view

WHAT. Stitch Steps 3–5 together. Solid arrows = transitions caused by this core's own load/store. Dashed arrows = transitions forced by snooping another core's broadcast.

WHY. Every arrow is now justified: own-write needs the token (silent from E/M, BusRdX/BusUpgr otherwise); own-read needs a copy (BusRd, landing in E if alone or S if shared); snooped-write kicks you to I; snooped-read demotes M/E down to S so a reader can join.

PICTURE. All four states as nodes; solid red arrows for own actions, dashed black for snoop reactions. Trace I → E → M → S → I — that is exactly Worked Example 1's counter race.

Step 7 — Edge & degenerate cases (never leave a gap)

WHAT. Four corners the happy path glosses over. Each is a legal, must-handle scenario.

WHY. The contract says every scenario, every sign of every input, must be shown — the reader may never hit an unlisted case.

PICTURE. Four mini-panels, the currently-firing case circled in red.

Silent eviction of E or S. A clean copy (E or S) equals DRAM, so dropping it needs zero bus traffic — no write-back, no announcement. Only M must write back on eviction (it owes DRAM the dirty data).
Two cores read the same line at once. The interconnect serializes the two BusRd requests. The first may briefly land in E; the moment the second BusRd is snooped, the first demotes E → S. End state: both S. There is never a real tie — the bus imposes an order.
Write to a line you hold in S. You do not issue BusRdX (you already have the data); you issue the cheaper BusUpgr — "just invalidate the others." Data isn't refetched; only ownership changes.
False sharing (degenerate performance case). Core 0 writes byte 0, Core 1 writes byte 63, same line. Coherence is per-line, so each write steals the whole token: the line ping-pongs M-on-Core0 ↔ M-on-Core1 forever, though the cores touch disjoint bytes. Correct, but catastrophically slow. Fix: pad to alignas(64).

The one-picture summary

The whole protocol compressed: the four states arranged by two questions — "Do I hold the write-token?" (left = yes, right = no) and "Does my copy match DRAM?" (top = clean, bottom = dirty/absent). Every arrow is either a solid own-action or a dashed snoop-reaction. If you can redraw this square, you can rebuild MESI.

Recall Feynman retelling — say it to a 12-year-old

Imagine every 64-byte chunk of memory has one golden ticket. Little offices (caches) each keep photocopies of chunks so they don't run to the giant slow warehouse (DRAM) every time.

You can only change a page if you're physically holding its golden ticket. That's the whole safety rule.

If you hold the ticket and your copy still matches the warehouse, you're Exclusive — calm, clean, alone. Scribble on it and you become Modified — now your copy is the only correct one and the warehouse is out of date, without even telling anyone, because you already knew nobody else had a copy.
If you don't hold the ticket but you've got a read-only photocopy that matches, you're Shared — you and friends can all read at once, nobody may write.
If your drawer is empty, you're Invalid — go fetch.

To grab the ticket you shout on the loudspeaker: "I want to write chunk A!" (BusRdX), or if you already have a read-copy, just "everyone tear up your copies of A!" (BusUpgr). Everyone listens (snoops); whoever had the only changed copy quickly hands you their fresh version directly (cache-to-cache) so you don't read the stale warehouse, then throws their copy away.

Two traps: coherence only promises everyone agrees about each chunk's timeline — it does not promise the ordering between different chunks (that's the Memory consistency models job, needing fences and atomics). And it works per whole page, so two people scribbling on different lines of the same page fight over the one ticket endlessly — false sharing. Give each hot variable its own page.

Related tickets systems: Directory-based coherence keeps a registry instead of shouting; MOESI and MESIF extensions add an "Owned/Forward" ticket so shared-but-dirty data can be passed around without a warehouse trip.