The E in MESI, and the exam table

What MSI pays for a private variable

Start from the machine of lesson 35: every cache controller snoops the bus, and a cache line is Modified (the only copy, dirty), Shared (a clean copy that others may also hold) or Invalid. In table form, with the replacement column that every exam table needs:

Now give P0 a loop over an array x that no other processor ever touches:

LOOP: LD    F2, 0(R1)    ; x[i]
      FADD  F2, F2, F4   ; + c
      SD    F2, 0(R1)    ; x[i]
      ADDUI R1, R1, 8    ; next
      BNE   R1, R2, LOOP

Assumptions: 64-byte blocks, 8-byte doubles, x private to P0, and P0's cache large enough for all of x.

Follow one block under MSI. The first LD misses: a Read Miss goes on the bus, memory answers, and the block arrives in S — the only state MSI has for a block that was read. The first SD is then a write hit on a Shared line, and Shared means "others may hold a copy". So P0 broadcasts an Invalidate and waits for the bus before the store can complete. Nobody is listening. The other seven LD/SD pairs of the block hit in M.

Two bus transactions per block, one of them useless, and a store that waits for it. The notes sum it up: "MSI wasted both bandwidth (spurious invalidations) and time (delayed private writes)" (p. 458). Nor is this a corner case: stack data, local variables and many heap objects are private to one thread, and the notes call private blocks "the common case" (p. 458).

Exclusive: the only copy, and clean

MESI adds one state. A line is Exclusive when this cache holds the only copy and that copy is clean, identical to memory. A read miss lands in E when no other cache holds the block, and in S when one does. The payoff comes at the first write: E goes to M silently, with no bus transaction, because nobody else has a copy to invalidate. The notes call it "the main benefit of MESI over MSI" (p. 458).

Seen this way, a state is three yes/no facts about a line: valid, dirty, the only copy. A valid line can be dirty and alone (M), clean and alone (E) or clean and maybe shared (S); add Invalid and there are four states, which still fit in the two state bits per line that MSI already spent on three. The new state costs no storage in the cache.

How does a cache know it is alone?

It cannot find out on its own; it must ask while its own miss is on the bus. During a Read Miss every other cache looks the block up in its tags anyway, to see whether it must react. MESI adds a wire for the answer, the shared line: every snooper that finds the block pulls it high. If the line stays low, the requester takes E. If anyone pulls it, the requester takes S — and an E holder drops to S as well, because it is no longer alone.

So the whole hardware price of E is one bus line and the logic that drives it, and it buys a silent first write to every private block. The same page of the notes also misplaces where the idea came from:

Exclusive = the only copy, and clean: the cache may write it without telling anyone.

The MESI machine, arc by arc

The bus transactions keep the names that lesson 35, the notes and the papers use: a Read Miss; a Write Miss, which fetches the block and invalidates every other copy in one transaction (a read-exclusive); and an Invalidate, sent by a write hit on a Shared line. Other texts write them BusRd, BusRdX and BusUpgr, the processor's own accesses PrRd and PrWr, and a write-back Flush. Here is the MSI table again with what MESI changes:

Read the E row against the S row. A write hit in S needs an Invalidate; in E it needs nothing. A snooped Read Miss leaves S alone but takes E down to S, since the line is no longer the only copy. Everything else matches, and nothing in either row is ever written back: both are clean.

Three write-backs, all from M

Memory gets a block back only from a Modified line, and only in three situations (p. 461):

1. the line is replaced, because its processor needs the other block: M → I with a write-back;
2. another processor's Read Miss for the block is snooped: the owner writes it back and both end in S, so memory is up to date again;
3. another processor's Write Miss is snooped: the owner writes back and goes to I, and the new owner writes at once, so memory is stale again.

E, S and I never write back: E and S are clean, and I holds nothing.

The exam table: one row, six moves

Every MESI exercise of the past papers opens with the same sentence, up to the number of processors. The June 2026 paper (Quiz 7, p. 12): "Let's consider the following access patterns on a 4-processor system with a direct-mapped, write-back cache with one cache block per processor and a two-cache block memory. Assume the MESI protocol is used, with write-back caches, write-allocate, and write-invalidate of other caches."

Three phrases decide the table. One cache block per processor: an access to the other block is a miss that throws the current block out. Write-allocate: a write miss first brings the block into the cache (lesson 23). Write-invalidate: a writer invalidates every other copy. Each row then holds the state of every cache as "state (block)" — Mod (1), Excl (0), Shared (0), or Invalid with no block — and, for each memory block, whether memory holds its latest value.

Here is the hardest kind of row, done slowly: row 2 of January 2026, "P0: write block 0", where P0 holds Excl (1) and P1 holds Mod (0).

1. Hit or miss? P0's line holds block 1 and P0 wants block 0: a write miss. A hit needs the same block, in a valid state.

2. Replacement first. P0's Excl (1) is clean, so it leaves silently: no bus transaction, and memory at bl. 1 stays Yes. Had it been Mod (1), P0 would write block 1 back before anything else.

3. The request. One Write Miss goes on the bus: fetch block 0 and invalidate every other copy.

4. The others react. P1 holds block 0 Modified, so it writes it back and goes Invalid. On a snooped Read Miss instead, an Excl or Mod copy would drop to Shared (Mod writing back first) and a Shared copy would stay.

5. The requester's state. A write ends in Mod: P0 takes Mod (0) directly. A read miss would end in Excl if nobody else held the block, in Shared otherwise.

6. The memory columns. Block 0 is No: P0 holds it Modified. P1's write-back made memory fresh for an instant, and P0's write made it stale again. Block 1 is Yes: nobody holds it Modified. The row reads Mod (0) | Invalid | No | Yes.

Hits are shorter. A read hit changes nothing. A write hit in Mod changes nothing; in Excl it turns the line into Mod with no bus transaction; in Shared it puts an Invalidate on the bus, every other copy goes Invalid, and the writer goes to Mod.

"Memory at bl. b up to date?" is No exactly while some cache holds block b in Mod, and Yes in every other row.

The February 2025 exercise runs the same moves on four processors; rows 1 and 2 are given in the paper:

Row 5 is E paying off: P0 writes block 1 with nothing on the bus. Under MSI, row 1 would have left P0 in Shared and row 5 would have cost an Invalidate. Row 6 also shows what a read of the other block leaves alone: block 0 stays No to the last row, because P1 still owns it and nothing forced a write-back. The notes' walkthrough gets every cell right, but one of its sentences describes the protocol wrongly, and another invites a misreading:

The trap at T = 4, and three more

Back to the puzzle. At T = 3 of January 2026 both caches hold Shared (0), and row 4 is "P0: read block 1". The six moves: a read miss; P0's Shared (0) is clean, so it leaves silently; a Read Miss for block 1 that no cache answers, so P0 takes Excl (1). And P1? It snoops the row's only transaction, but that Read Miss is about block 1: nothing on the bus mentions block 0. A silent replacement is silent for everyone, so P1 cannot learn that it is now alone — and the machine has no arc from S to E.

So the answer to the hook is no: P1 stays Shared (0). A cache can learn that it is alone at one moment only: while its own miss is on the bus. Later it can hear that it is no longer alone, from another cache's miss, but never that the others have gone. The price would arrive if P1 wrote block 0 next: a write hit in S, so it would broadcast an Invalidate that no cache needs — MSI's waste, back for one write (row 6 of the second exercise below does exactly this). MESI accepts that, because avoiding it would mean announcing every clean replacement on the bus: a transaction spent to save, at best, a later one.

Three more cells the tables keep testing:

• A write miss invalidates everybody. Every other copy of the block becomes Invalid, Shared ones included. Line 5 of the June 2026 quiz forgets this; it is in the exam section below.
• A snooped read of a Mod block refreshes memory. The owner writes back and both end Shared, so memory flips to Yes (January 2026, T = 3, 11 and 14).
• A write miss on a Mod block leaves memory stale. The owner writes back, but the new owner writes at once: No (T = 2 and 13).

Why the bus cannot grow

Every row you filled relied on one thing: all caches see every transaction, in one order, on one bus. That is how a requester learns from the shared line whether it is alone, and how two writers are put in order — whoever gets the bus first invalidates the other. It is also why snooping stops scaling. Every miss and every Invalidate goes to all processors, every cache must check its tags against each of them, and the bus carries one transaction at a time with a bandwidth that does not grow with the number of processors (the physical side of this is in lesson 33).

The January 2026 paper asked for this comparison in its Question 1 (the model answer is in the exam section). The skeleton of the answer:

The notes' answer puts the reach of snooping at "typically up to 16 or 32" processors (p. 495). Beyond that, each block needs one place that records which caches hold it, so that a request goes only where the copies are. That place is the directory of lesson 37.