MESI - MOESI coherence protocols: Visual walkthrough

This is a deep-dive child of the parent MESI/MOESI note. If a word here is new, it gets defined here — you do not need the parent open.

Step 1 — The setup: two caches, one address

WHAT. Picture two CPU cores. Each core has its own tiny private notebook called a cache — a fast local copy of a few memory values so the core doesn't walk all the way to the big slow main memory every time.

WHY this picture. The whole problem only exists because copies are private. If both cores read straight from one shared memory, there is nothing to keep in sync. The moment we allow each core a private copy, we create the possibility of two copies of the same value that can disagree. So we draw the copies explicitly.

PICTURE. Below: main memory holds address $X$ with value $5$ . Two cores, Core 0 (blue) and Core 1 (orange), each have an empty cache slot for $X$ . A cache line is just one row of a cache — the unit the hardware tracks. Nothing is copied yet.

Step 2 — Watch it break: the stale-read bug

WHAT. Let both cores copy $X = 5$ into their caches. Then Core 0 writes $X = 9$ into its own cache only (fast — no trip to memory). Now Core 1 reads $X$ from its cache and gets $5$ .

WHY this step. This is the disease before the cure. We must see the wrong answer to know exactly what the protocol has to forbid. The bug is: two copies drifted apart, and a reader believed the old one.

PICTURE. The red $5$ in Core 1's cache is the stale value; the green $9$ in Core 0's cache is the truth. Memory still says $5$ too. Three different "current values" for one address — chaos.

Step 3 — The rule we must never break (SWMR)

WHAT. State the one law that, if obeyed, makes the bug impossible. It is called Single-Writer / Multiple-Reader.

WHY exactly this law. The bug in Step 2 had a writer (Core 0) active while a reader (Core 1) held a copy. Forbid that overlap and the bug cannot happen. We don't need anything fancier — this is the minimal rule.

PICTURE. A timeline for address $X$ . Green read-intervals (many cores allowed, overlapping fine) and orange write-intervals (exactly one core, exclusive). The rule: green and orange bands may never overlap in time.

Everything from here is mechanism — the smallest set of gadgets that keeps this timeline legal.

Step 4 — The bus and the two questions each line asks

WHAT. Give the caches a shared wire, the bus, that every cache can snoop (listen to). When one cache wants to read or write a line it announces it on the bus, and every other cache hears it and reacts. Then, to react correctly, each cache tags its copy of the line by answering two yes/no questions.

WHY a bus. SWMR is a global rule ("no one else is writing"), but each cache only knows about itself. The bus is how a cache learns what the others are doing without asking each one directly — it overhears the announcements. (Alternatives to a bus exist — see Snooping vs Directory-based protocols — but the logic is identical.)

WHY these two questions. SWMR cares about two things only: am I the sole holder? (so I can write without disturbing anyone) and is my copy already dirty? (so I know whether memory must be updated). Two yes/no questions → four combinations → four states.

exclusive vs shared Only copy? \times modified vs clean Dirty?

PICTURE. The bus as a horizontal rail joining both caches and memory, with the 2×2 table of answers floating above. Three cells fill with letters M, E, S; the fourth (dirty and shared) is greyed out as "impossible for now."

The greyed dirty + shared cell is deliberately empty. Remember it — Step 8 fills it.

Step 5 — Deriving the READ transitions

WHAT. A core issues a load (read). We work out what state it must land in, using only SWMR + the bus.

WHY split into two outcomes. When the reading cache is Invalid it must fetch the line, and it announces this with a BusRd ("I want to read $X$ "). What happens next depends on a single fact the bus reveals: does anyone else already hold this line?

Nobody else holds it → I am now the only copy of a clean value → land in E. Why E and not S? Because being provably alone is valuable — Step 6 shows it lets me write for free.
Someone else holds it → there are now two copies → both must be S (read mode, many readers). Any holder that was M must first write back its dirty value so I read the truth, and it drops to S.

Term-by-term, the read-miss rule:

my start state I "I want to read" BusRd ⎩ ⎨ ⎧ E S if bus stays quiet no sharer if someone answers sharer exists

PICTURE. Two mini-scenes side by side. Left: Core 0 alone → arrow $I \to E$ . Right: Core 1 reads while Core 0 already holds it → both end $S$ , with a small "write-back first if dirty" note.

Step 6 — Deriving the WRITE transitions (why E is the hero)

WHAT. A core issues a store (write). To write, SWMR demands it be the single writer, so every other copy must die (invalidate). The interesting part is: how much bus traffic does that cost? — and the answer depends on the starting state.

WHY case-by-case. The cost of becoming the sole writer is exactly the cost of getting rid of the other copies. So we sort by "how many other copies exist right now," which is precisely what the current state tells us.

From E → I already know I'm alone. Nobody to invalidate. Go E → M silently — zero bus messages. This is the entire payoff of having an E state.
From M → already the sole dirty owner. Just write again; stay M.
From S → others may hold copies. Broadcast BusRdX (Read-for-Ownership) to invalidate them all, then S → M.
From I → I don't even have the data. Broadcast BusRdX: fetch the line and invalidate others, then land in M.

E silent M, S BusRdX M, I BusRdX M

Here $BusRdX$ = "read the data into me and invalidate everyone else's copy." The X does not mean write; the store itself happens locally after the line arrives.

PICTURE. Three write scenes stacked: green silent arrow $E \to M$ (no bus), and two red $BusRdX M$ arrows from $S$ and $I$ that reach across the bus to slam other caches to $I$ .

Step 7 — Deriving the SNOOP (react-to-others) transitions

WHAT. So far a cache acted because it wanted something. Now it must react to what it overhears on the bus — this is the other half of keeping SWMR true globally.

WHY. SWMR is a two-sided contract: when you become a writer, others must step back. Step 6 was the "I write" side; this is the "someone else acts, I comply" side.

I hold M, I hear a BusRd (someone wants to read): I have the only good copy, so I write it back to memory (or forward it) and drop M → S — now we share a clean value.
I hold E, I hear a BusRd: no write-back needed (I was clean), just E → S.
I hold any valid state (M/E/S) and hear a BusRdX or an invalidate: someone is about to write → my copy must die → → I. If I was M, I write back first so the only good copy isn't lost.

M BusRd S, E BusRd S, (M, E, S) BusRdX I

PICTURE. The full MESI state machine assembled: four nodes M, E, S, I with every arrow from Steps 5–7 labelled by its bus event and colour-coded (solid = this core's action, dashed = snooped reaction).

Recall Check: which state writes with no bus traffic?

Which single MESI state upgrades to M silently? ::: E (E→M), because you are provably the only holder.

Step 8 — The degenerate case that invents MOESI's O

WHAT. Look again at Step 7's first rule: an M line hearing a BusRd must write the dirty data all the way back to memory before sharing it. When a value is read repeatedly by others (a hot shared variable), we pay that slow memory write again and again — often only for the value to be overwritten soon after.

WHY this is a real degenerate cost. Memory is far slower than a cache-to-cache hop over the bus. Writing back on every share is the worst case for shared-but-dirty data. The greyed cell from Step 4 (dirty + shared) was "impossible" only because we had no state to name it. Give it a name and the problem dissolves.

New snoop rule for a shared read:

M BusRd O (forward data to reader, memory not updated); reader \to S

Memory is written back only when the owner is finally evicted.

PICTURE. Left: MESI path — M line sends its value all the way down to slow memory (red, long arrow), then M→S. Right: MOESI path — M→O keeps the dirty value and forwards it sideways straight to the reader (green, short arrow); memory untouched.

The one-picture summary

Everything above compressed: the 2×2 "two questions" grid gave us M, E, S, I; SWMR forced the arrows; the one impossible cell became O. Read the arrows solid (my action) vs dashed (I overheard something).

Recall Feynman retelling — the whole walkthrough in plain words

Two friends each photocopy a page from one library book (Step 1). Trouble: if one edits her copy and the other keeps reading his, he's now reading a lie (Step 2). So we make one law: while someone edits, nobody else may hold a copy; while people only read, nobody edits (Step 3, SWMR). To obey it, everyone shouts their intentions across the room — a shared bus — and each labels their page with two facts: am I the only one who has this page? and have I scribbled on it? Two yes/no facts make four labels: I (no page), S (clean, others might have it), E (clean, only me), M (scribbled, only me) (Step 4). When you want to read and have nothing, you shout "BusRd"; if nobody answers you're alone → E, otherwise you share → S (Step 5). When you want to write, you must be the only one, so if you're already E you scribble quietly for free, but from S or I you first shout "BusRdX — everyone tear out that page!" then edit → M (Step 6). When you overhear someone else's shout, you comply: heard a read? drop to S (writing back if you'd scribbled); heard a BusRdX? throw your page away → I (Step 7). Finally, instead of running to the library to update the master book every time a friend asks for your scribbled page, just photocopy your fresh version straight to your friend and keep owning it — that's the O state, and you only update the master when you finally throw your page out (Step 8).

Related deep context: Cache Coherence vs Memory Consistency, Bus arbitration & interconnect, and the whole Memory Hierarchy & Caches backdrop.