Not in a single FSM register. The controller must keep pending identities, data, expected responses and scheduling decisions across stalls. The diagram below describes H, not the core-side MSHR. Private controllers have their own tag and state array, MSHRs and WB entries, and must search all of them when an Inv or Fwd arrives.
Reserve resources before accepting work. The directory answers who may hold X; the pending record answers what this transaction still owes; the data buffer protects the value. Response matching checks which operation a message completes. Scheduling chooses eligible work; a grant is not eligible merely because it would free a queue.
Use the B3 checkpoint of the four-hop route in Three-Hop Versus Four-Hop. X initially 0; C0 previously stored 1 and has given up its permission for C1's request B. H has accepted Data(1), C1 is still IM^D, and memory = 0. This is a resource snapshot, not another message trace.
Step | C0 state / value | C1 state / value | H directory | Memory | Newest data |
|---|---|---|---|---|---|
Dirty data at H, B pending | I / - | IM^D / - | exclusive(C0), pend GetM C1 | 0 | H buffer: 1 |
Grant blocked at output | I / - | IM^D / - | exclusive(C0), pend GetM C1 | 0 | H buffer: 1, Data(1) waiting in H's output queue |
Data at C1 | I / - | M / 1 | exclusive(C0), pend GetM C1 | 0 | C1: 1 |
(assumed) grant delivered | I / - | M / 1 | exclusive(C1) | 0 | C1: 1 |
Resource | Required fact at the pending checkpoint | Unsafe shortcut |
|---|---|---|
Directory | Old exclusive permission was given up | Declare U because both array tags read I. |
Pending table | B, line X, requester C1, response generation, remaining grant work | Reuse the entry based only on ack count. |
Protected data | Value 1, kept until C1's Data is sent | Overwrite the buffer because memory also has an address for X. |
Output path | Grant's identity, payload and explicit permission, kept under stalls | Treat a send attempt as delivered completion. |
Matcher | Late responses cannot complete a reused transaction | Match every message only by line address. |
An output stall must preserve the grant and its data. A full queue can block new admission, but responses and Inv and Fwd handling need a path that does not wait behind new requests. Separate physical queues alone do not prove deadlock freedom; finite buffers, arbitration and credits can still form cycles. Fairness and eventual service must be designed in; a box labelled scheduler does not provide them.
In this snapshot B is the selected transaction; later requests for X wait at H until B's grant has been delivered. The newest value stays in H's buffer while it waits, and H must not reuse the entry before that completion.
The pending identity and completion state, the newest payload in protected storage, and the retained output obligation. The old cache's revoked permission does not justify clearing them while memory is stale.