Use this after working the examples, not instead of them. State letters summarise a protocol contract; the course model defines the assumptions behind this sheet.
State | Protocols | Read? | Write locally? | Responsibility |
|---|---|---|---|---|
I | MSI, MESI, MOESI | No | No | No usable cached copy. |
S | MSI, MESI, MOESI | Yes | No | Shared readable copy. In MOESI memory may be stale because an O cache is dirty-responsible. |
E | MESI, MOESI | Yes | Yes; E silently becomes M | Exclusive holder, clean; memory is current. |
M | MSI, MESI, MOESI | Yes | Yes | Exclusive holder and dirty-responsible holder; memory may be stale. |
O | MOESI | Yes | No | Dirty-responsible holder; other caches may hold S. |
Name | From, request | Waits for | Local accesses |
|---|---|---|---|
IS^D | I, GetS | Data (S, or E in MESI and MOESI) | None |
IM^D | I, GetM | Data with M | None |
SM^D | S, GetM | Data with M, usually permission-only | Loads hit, stores stall |
OM^D (MOESI, Part 8) | O, GetM | Data with M, permission-only | Loads hit, stores stall |
IS^D_I (Part 4) | IS^D, then Inv arrived (Inv-Ack already sent) | Data | The pending load uses the value once, then I |
MI^A / EI^A / SI^A | M, E or S, PutM / PutE / PutS | Put-Ack (after H writes memory for PutM) | Stall; answer Inv or Fwd from the writeback buffer |
II^A | MI^A, EI^A or SI^A, then lost the line to an Inv or Fwd-GetM | Put-Ack (H acks a Put from a non-holder with no change) | Stall |
Acks are collected at H, so the requester waits only for Data. The Primer collects them at the requester: IS^D, IM^AD, SM^AD.
Two cores, requests from C1 unless the row says otherwise. Read the protocol from the H entry: O entries exist only in MOESI.
Request at H | H entry before | H does | Data comes from | Result |
|---|---|---|---|---|
GetS | U | Reads memory | H | MSI: C1 S, H records S{C1}. MESI, MOESI: C1 E, H records exclusive(C1). |
GetS | S{C0} | Reads memory | H | C1 S, H records S{C0,C1}. |
GetS | exclusive(C0), C0 in E | Fwd-GetS to C0 | C0, via H | C0 E to S, H writes memory (value unchanged: H cannot tell E from M), C1 S, H records S{C0,C1}. |
GetS | exclusive(C0), C0 in M | Fwd-GetS to C0 | C0, via H | MSI, MESI: C0 M to S, H writes memory, both S. MOESI: C0 M to O, memory stays stale, H records O: C0, sharers {C1}. |
GetM | U | Reads memory | H | C1 M, H records exclusive(C1). |
GetM | S{C0} | Inv to C0, waits for Inv-Ack, reads memory | H | C0 I, C1 M, H records exclusive(C1). |
GetM (upgrade) | S{C0,C1} | Inv to C0, waits for Inv-Ack | None: permission-only Data | C0 I, C1 SM^D to M, H records exclusive(C1). |
GetM | exclusive(C0) | Fwd-GetM to C0 | C0, via H | C0 I, C1 M, H records exclusive(C1). |
GetM from C1 (in S) | O: C0, sharers {C1} | Fwd-GetM to C0 | C0, via H | C0 I, C1 M, H records exclusive(C1). |
GetM from C0 (in O) | O: C0, sharers {C1} | Inv to C1, waits for Inv-Ack | None: permission-only Data | C0 O to M, C1 I, H records exclusive(C0). |
Data from a holder travels through H in Parts 1 and 2; Part 3's forwarding lessons introduce direct data from holder to requester. Many directory protocols, including the Primer's, send it to the requester directly instead.
Evicting state | Message | H does | H entry after |
|---|---|---|---|
S | PutS, waits for Put-Ack | Removes the sharer | S{remaining} or U |
E | PutE, waits for Put-Ack | Nothing to write: memory is current | U |
M | PutM with data, waits for Put-Ack | Writes memory | U |
O | PutM with data, waits for Put-Ack | Writes memory | S{remaining sharers} or U |
Silent clean eviction of S or E is a Part 3 variant. A dirty line is never dropped without a PutM that H has accepted.
State | Entered when | If a Fwd or Inv for X arrives | Leaves on |
|---|---|---|---|
MI^A | M sent PutM; the WB entry holds the dirty data | Fwd-GetS: Data from the WB entry to H, go to SI^A. Fwd-GetM: Data from the WB entry, go to II^A. | Put-Ack: free the WB entry, go to I |
EI^A | E sent PutE (no data: memory is current) | Still answered: the line is held until Put-Ack | Put-Ack: go to I |
SI^A | S sent PutS, or MI^A answered a Fwd-GetS | Inv: send Inv-Ack, go to II^A | Put-Ack: go to I |
II^A | Lost the line to an Inv or Fwd-GetM while waiting | Nothing left to give up | Put-Ack, which H sends without changing the directory or memory because the Put came from a non-holder |
Loads and stores to X stall in all four states. Order for a dirty eviction: PutM, then H writes memory, then Put-Ack. A Fwd must search the WB entries as well as the array tags. Details: Eviction Versus Intervention.
Entry | Meaning |
|---|---|
U | No cached holder; memory authoritative |
S{C0,C1} | Read-only sharers; memory current (MSI, MESI) |
exclusive(C0) | C0 in E or M |
O: C0, sharers {C1} | MOESI: C0 dirty-responsible, C1 in S |
S{C0}, pend GetM C1, acks 0/1 | Transaction in progress, one acknowledgement still outstanding |
Situation | Check before accepting the result |
|---|---|
Cold read | Was the returned value sourced from an authoritative location, and what permission was granted? |
S-to-M upgrade | Were all other readers revoked and required acks received before writing? Data may already be present. |
Read of a dirty line | Did the dirty-responsible holder supply the current value? Did the named protocol update memory or retain O? |
Write-permission transfer | Did the previous exclusive holder give up permission, and is the latest value preserved, including in-flight data? |
Eviction | Was Put-Ack received, and did H accept dirty data before the cache discarded its last copy? |
Concurrent requests | Which transaction wins at H, and what does the other requester do while waiting? |
Class | Messages | Consuming one may wait on |
|---|---|---|
Requests | GetS, GetM, PutS, PutE, PutM | Forwards and responses |
Forwards | Inv, Fwd-GetS, Fwd-GetM | Response egress only |
Responses | Inv-Ack, Data, Put-Ack | Nothing: each pending entry reserved its response slot and data destination when it was allocated |
Rule: request < forward < response. Consuming a message may wait only on resources of a later class, so responses always sink. With one virtual network per class, deadlock-free routing inside each and endpoints that obey the rule, no protocol-message cycle can form (A Protocol Deadlock).
Failure | What you observe | Repair direction |
|---|---|---|
Protocol deadlock | A held/requested cycle through endpoint resources (pending entries, ingress queues), nothing enabled | Reserved response capacity, message classes, a virtual network per class |
Routing deadlock | Packets hold router buffers in a topology loop | Deadlock-free routing or an escape channel inside each virtual network |
Livelock | Messages move, no useful operation completes | A policy that lets one operation finish, such as performing the store before answering the Fwd |
Starvation | One eligible request bypassed without bound while others complete | Fair arbitration or bounded retries |
Backpressure | A finite stall that ends when capacity returns | None needed, if the downstream consumer eventually accepts |
Illustrative entry sizes from Full Bit-Vector Cost: 2 state bits plus the sharer record, tags and ECC excluded, MESI coverage only. The id field is 6 bits for 64 caches.
Format | Bits per entry, 64 caches | When a sharer does not fit | On a later GetM |
|---|---|---|---|
Full bit vector | 66 (2 + N) | Always fits | Inv to the exact sharers |
Four pointers, Dir_4 B | 31 (2 + 4 x (id + 1) + 1) | Set the overflow bit and grant | Inv to all N - 1 other caches; overflow clears only when the entry becomes exclusive |
Limited pointers, Dir_i NB | Pointer storage, no overflow bit | Invalidate one existing sharer and reuse its pointer | Inv to at most K caches; thrashes on widely read data |
Coarse vector, groups of 8 | 16 (2 + N/8 + an exact exclusive-holder id) | Pointer bits become group bits | Inv to every member of every set group |
Sparse directory | Any of the above plus an address tag | Entry eviction needs back-invalidation | As the entry format |
Four pointers are smaller than a full vector from 26 caches; groups of eight exceed four pointers from 233 caches. A sparse directory is sized against private-cache lines (coverage ratio about 1, commonly up to about 2), not against memory. Never drop a reader that does not fit.
X and Y in different lines, X = Y = 0 initially, plain loads and stores, no fences or dependencies. SB: C0 runs W(X)=1 then r1=R(Y), C1 runs W(Y)=1 then r2=R(X). MP: C0 runs W(X)=1 then W(Y)=1, C1 runs r1=R(Y) then r2=R(X). From Weak Models: Arm and RISC-V.
Model | SB r1 = r2 = 0 | MP r1 = 1, r2 = 0 |
|---|---|---|
SC | Forbidden | Forbidden |
TSO | Allowed | Forbidden |
Armv8-A | Allowed | Allowed |
RVWMO | Allowed | Allowed |
A fence between each core's store and load forbids SB 0,0 under TSO. MP under Armv8-A and RVWMO needs ordering on both sides: writer DMB ISH or STLR (Arm), FENCE w,w or an .rl AMO (RISC-V); reader DMB ISH, LDAR or an address dependency (Arm), FENCE r,r, an .aq LR or AMO, or an address dependency (RISC-V). A weak-model outcome never excuses a lost coherent value.
Course correspondence from Mapping ACE and CHI States and TileLink Permissions. ACE: AMBA AXI and ACE, Arm IHI 0022 Issue H.c. CHI: AMBA 5 CHI, Arm IHI 0050 Issue E.a. TileLink: SiFive TileLink Specification 1.8.1. Neither Arm document prints a MOESI mapping; the correspondence is the course's.
Course state | ACE | CHI | TileLink permission |
|---|---|---|---|
I | Invalid | I | None (N) |
S | SharedClean (SC) | SC | Branch (B) |
E (MESI, MOESI) | UniqueClean (UC) | UC | Tip (T) |
M | UniqueDirty (UD) | UD | Tip (T): dirty is not part of the permission |
O (MOESI) | SharedDirty (SD) | SD | Not mapped: TileLink permissions do not encode dirty |
No course equivalent | - | UCE (unique, no valid bytes), UDP (unique, dirty, partial) | Trunk (hierarchy only) |
ACE and CHI SC means only 'not responsible for memory': another cache may hold SD, so SC / 1 with memory = 0 can be legal. Equal names do not imply equal rules; read the specification section the lesson cites. Side-by-side behaviour (serialization point, completion acknowledgement, direct data transfer): Protocol Comparison Sheet.
Check | What it catches | Taught in |
|---|---|---|
Values, not states: compare every load and every usable copy with the golden value after every event | Wrong data under a legal-looking state vector | |
SWMR and the data-value invariant, both, at every event | Premature permission, and lost or stale values | |
Say where the checker observes (below the store buffer, or at the core with the named memory model) | False alarms on legal store-buffer forwarding | |
Inject each bug class and show the intended check fires | A checker that cannot fail | |
Race crosses hit in both orders: transient state x conflicting message x cause | Races random traffic rarely reaches | |
Non-zero antecedent counts, cover properties and witness traces | Vacuous passes | |
Liveness proved or checked separately, with the fairness assumption stated | A controller that never grants anything (safe but useless) | |
Every remaining hole proved unreachable or waived with an owner | Coverage percentages that hide the missing races |
Permission: is there at most one exclusive writer, with no independent readers during that write epoch? Value: does the next epoch start with the value from the end of the last write epoch? A legal-looking state vector can still contain the wrong data.
Choose a line and reconstruct its initial state and write history.
Find the first wrong returned value, premature permission, missing responsibility transfer or blocked dependency.
Align message IDs and deliveries with the directory's pending work.
Distinguish a permitted older observation under the named memory model from a genuine data-value violation.
State a targeted fix and which interleavings and checks would test it.
M/S violates the exclusive-writer rule in these protocols. O/S can be legal in MOESI because both are read-only and O holds dirty responsibility. The shared values must still match the value written at the end of the last write epoch.