This section builds one straightforward MSI protocol twice: first on a simple system model whose atomicity properties keep the specification tiny, then on the baseline model, where relaxing just one property already multiplies the transient states. The inefficiencies you’ll notice are the motivation for everything in §7.3–7.6.
7.2.1 High-level specification
Three stable states — MSI — with a writeback cache; the block is owned by the LLC/memory unless some cache holds it in M. Loads hit in S and M; stores hit only in M. The FSMs below (the book’s Figures 7.1 and 7.2) show only stable states and the bus requests that move them; memory’s states use cache-centric names — the merged IorS says “no cache holds M.”
7.2.2 The simple model: Atomic Requests + Atomic Transactions
The system is chapter 2’s baseline with the network fixed as a bus (the book’s Figure 7.3 — essentially the SGI Challenge):
Two atomicity properties tame the protocol:
- Atomic Requests atomic requests System property that a coherence request is ordered in the same cycle it is issued, eliminating any gap between issue and serialization. defined in Chapter 7 — open in glossary : a request is ordered the cycle it is issued — a block’s state can’t change between issue and serialization.
- Atomic Transactions atomic transactions System property that a subsequent request for a block may not appear until the current transaction's response completes. defined in Chapter 7 — open in glossary : no subsequent request for the same block may appear until the current transaction’s response completes.
The result: only three cache transient states (IS^D, IM^D, SM^D — request already ordered, data pending) and one at memory. Explore both controllers — the shaded cells marked “(A)” are impossible because transactions are atomic:
Figures 7.1 + transients (recreated): simple MSI cache controller
Solid = stable state · dashed = transient · click a state or an arrow.
Table 7.5 (recreated): simple snooping — cache controller
| Core events | Bus: own transaction | Bus: other cores | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| State | Load | Store | Replacement | Own-GetS | Own-GetM | Own-PutM | Data (for own request) | Other-GetS | Other-GetM | Other-PutM |
Cell format: action / next state (next state omitted when unchanged) · blank = event ignored · shaded = impossible. Click any cell or state chip.
Click a transition cell for its plain-English explanation, or a state chip for its invariants.
Figure 7.2 (recreated): memory controller stable states
Solid = stable state · dashed = transient · click a state or an arrow.
Table 7.6 (recreated): simple snooping — memory controller
| Bus events | ||||
|---|---|---|---|---|
| State | GetS | GetM | PutM | Data from owner |
Cell format: action / next state (next state omitted when unchanged) · blank = event ignored · shaded = impossible. Click any cell or state chip.
Click a transition cell for its plain-English explanation, or a state chip for its invariants.
Key behaviors worth reading off the tables: a Data response comes from the memory controller or from a cache in M; an S cache ignores GetS (memory answers) but invalidates on GetM; an M cache answers both — sending data to requestor + memory on GetS (ownership returns to memory), to the requestor alone on GetM. Evictions: S→I is silent; M→I issues a PutM with the data (the only valid copy can’t be dropped).
Try it: the running example
Table 7.7’s scenario — C1 loads, C2 stores, C1 loads again — as a live system. Step through the preset, then experiment freely (watch the data values expose stale memory):
Simple snooping MSI — one block, atomic bus
Core C1
—
Core C2
—
LLC / Memory
data: v0
Bus timeline (one block; atomic requests + atomic transactions)
- ·Reset: all caches I, LLC/memory IorS holding v0.
At the end of the preset: C1 and C2 both hold S, and the LLC/memory — refreshed by C2’s response to the final GetS — owns the block in IorS.
7.2.3 The baseline model: non-atomic requests
Real implementations put message queues between cache controllers and the bus — so a request is issued now but ordered later, opening the window of vulnerability window of vulnerability Without Atomic Requests, the gap between issuing a request and its serialization, during which another core's request may be ordered first and change the block's state. defined in Chapter 7 — open in glossary . (Atomic Transactions still hold; §7.5 drops those too.) The protocol grows new ^AD states — issued, waiting to observe own request, then data — during which the block is effectively still in its old state:
Table 7.8 (recreated): baseline MSI — cache controller (click the SM^AD × Other-GetM cell!)
| Core events | Bus: own transaction | Bus: other cores | Bus: own transaction | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
| State | Load | Store | Replacement | Own-GetS | Own-GetM | Own-PutM | Other-GetS | Other-GetM | Other-PutM | Own Data Response |
Cell format: action / next state (next state omitted when unchanged) · blank = event ignored · shaded = impossible. Click any cell or state chip.
Click a transition cell for its plain-English explanation, or a state chip for its invariants.
Three stories to find in that table:
- I→S: Issue GetS (IS^AD, effectively I — other requests ignored) → observe Own-GetS (IS^D, logically S: the transaction is ordered) → Data → S, load performs.
- S→M hijacked: in SM^AD, loads still hit — but if an Other-GetM is serialized first, our copy dies: → IM^AD, no more hits. This window is also why an Upgrade transaction is easy with Atomic Requests and painful without: an Upgrade that lost its S copy suddenly needs data, and the LLC/memory in IorS can’t tell (the book’s sidebar traces a three-core interleaving where this bites).
- M→I complicated: PutM issued → MI^A, where the block is effectively still M — so the cache keeps answering others’ requests. If a GetS/GetM intervenes, it responds and slides to II^A, and when its stale PutM finally appears it must send NoData — its data would overwrite newer values, but silence would strand the memory controller in a transient state:
Table 7.9 (recreated): baseline MSI — memory controller (X^D reverts to X on NoData)
| Bus events | |||||
|---|---|---|---|---|---|
| State | GetS | GetM | PutM | Data | NoData |
Cell format: action / next state (next state omitted when unchanged) · blank = event ignored · shaded = impossible. Click any cell or state chip.
Click a transition cell for its plain-English explanation, or a state chip for its invariants.
Note the naming exception: memory’s M^D means “revert to M if NoData arrives, go to IorS if Data arrives” — the controller must remember which stable state to fall back to.
7.2.4–7.2.5 The running example, and what simplicity cost
The baseline running example (the book’s Table 7.10) ends exactly like the simple one — both cores in S, memory in IorS — with one visible difference: both cores issue their requests concurrently and change state immediately (IS^AD, IM^AD), with the bus later deciding that C1’s GetS wins serialization.
The simplicity scorecard: Atomic Transactions erased every “(A)” cell — §7.5 shows the redesign when they’re gone — and the missing Upgrade transaction means every S→M store pays for a full data transfer it doesn’t need.
Check yourself
1.Flashback (pop quiz Q6): 'In an MSI snooping protocol, a cache block may only be in one of three coherence states.' True or false?
2.What do the simple model's two atomicity properties say, and what does each buy?
3.In the baseline protocol, a cache in SM^AD (upgrading S→M) observes an Other-GetM before its own GetM. What happens, and why?
4.Why does a cache in II^A send a NoData message (rather than its data, or nothing) when it finally observes its own PutM?
5.A cache holds a block in M and observes an Other-GetS. Why must it send data to the requestor AND to memory?
6.Why can an S block be evicted SILENTLY, while an M block cannot?