No. Selecting a request starts obligations; it does not make the intended cache state real. Reset MSI: C0 and C1 I, H U, memory = 0. C0 sends GetS A and C1 sends GetM B. In this example A reaches H first; H queues B and completes A before starting B's invalidation.
C0 wins a read grant, not permanent priority. C1 waits until A's Data is delivered, then H invalidates C0, collects its acknowledgement, reads memory for B and grants C1 write permission. This first trace uses the grant-delivery rule of Parts 1 to 3. The section 'When the grant-delivery rule is dropped' below shows what a real protocol does instead.
Step | C0 state / value | C1 state / value | H directory | Memory | Newest data |
|---|---|---|---|---|---|
Initial | I / - | I / - | U | 0 | memory: 0 |
1. GetS A at H | IS^D / - | I / - | U, pend GetS C0 | 0 | memory: 0 |
2. GetM B at H | IS^D / - | IM^D / - | U, pend GetS C0, queued GetM C1 | 0 | memory: 0 |
H reads memory | IS^D / - | IM^D / - | U, pend GetS C0, queued GetM C1 | 0 | memory: 0, Data(0) in flight to C0 |
3. Data at C0 | S / 0 | IM^D / - | U, pend GetS C0, queued GetM C1 | 0 | C0 and memory: 0 |
(assumed) grant delivered | S / 0 | IM^D / - | S{C0}, queued GetM C1 | 0 | C0 and memory: 0 |
L. Load | S / 0 | IM^D / - | S{C0}, queued GetM C1 | 0 | C0 and memory: 0 |
4. Inv at C0 | I / - | IM^D / - | S{C0}, pend GetM C1, acks 0/1 | 0 | memory: 0 |
5. Inv-Ack at H | I / - | IM^D / - | U, pend GetM C1, acks 1/1 | 0 | memory: 0 |
H reads memory for B | I / - | IM^D / - | U, pend GetM C1, acks 1/1 | 0 | memory: 0, Data(0) in flight to C1 |
6. Data at C1 | I / - | M / 0 | U, pend GetM C1, acks 1/1 | 0 | C1 and memory: 0 |
(assumed) grant delivered | I / - | M / 0 | exclusive(C1) | 0 | C1 and memory: 0 |
L. Local store | I / - | M / 1 | exclusive(C1) | 0 | C1: 1 |
memory = 0 is current throughout because no store happens before C1's L. If B reached H first, H would serve B first and A would wait: the order in which the cores sent their requests does not decide the order at H.
With no FIFO order between messages, Inv could reach C0 before its older granting Data. A naive cache in IS^D might acknowledge the Inv as if it held nothing, then install the late S grant after C1 has become writable: C0 would read a stale copy for ever. The grant-delivery rule avoids this by waiting. Real protocols do not assume H can see delivery, so they use one of the remedies below.
The course model promised that Part 4 shows what real protocols do instead of the grant-delivery rule. There are two choices: the requester handles an Inv or Fwd that arrives before its Data (traces a and b), or the requester sends H a completion message so H knows the grant was delivered (trace c). In traces a and b H sends A's Data and starts B at once. Each numbered arrow is a delivered message, so an arrow's number is when it arrives, not when it was sent.
IS^D_I is the Primer's name for a cache that was in IS^D and has received an Inv. It remembers the Inv, uses the Data for the one pending load when it arrives, and then drops the copy and becomes I. C0 handles the Inv at once: it sends Inv-Ack without waiting for Data. That is safe because C0 has no readable copy, and the late Data is used once and never installed. The pending load is ordered before B's store, since it returns the value B replaces.
Step | C0 state / value | C1 state / value | H directory | Memory | Newest data |
|---|---|---|---|---|---|
Initial | I / - | I / - | U | 0 | memory: 0 |
1. GetS A at H | IS^D / - | I / - | U, pend GetS C0 | 0 | memory: 0 |
2. GetM B at H | IS^D / - | IM^D / - | U, pend GetS C0, queued GetM C1 | 0 | memory: 0 |
H reads memory | IS^D / - | IM^D / - | U, pend GetS C0, queued GetM C1 | 0 | memory: 0, Data(0) in flight to C0 |
H starts B | IS^D / - | IM^D / - | S{C0}, pend GetM C1, acks 0/1 | 0 | memory: 0, Data(0) in flight to C0 |
3. Inv at C0 (handled: Inv-Ack sent) | IS^D_I / - | IM^D / - | S{C0}, pend GetM C1, acks 0/1 | 0 | memory: 0, Data(0) in flight to C0 |
4. Inv-Ack at H | IS^D_I / - | IM^D / - | U, pend GetM C1, acks 1/1 | 0 | memory: 0, Data(0) in flight to C0 |
5. Data at C0, L. pending load returns 0 | I / - | IM^D / - | U, pend GetM C1, acks 1/1 | 0 | memory: 0 |
H reads memory for B | I / - | IM^D / - | U, pend GetM C1, acks 1/1 | 0 | memory: 0, Data(0) in flight to C1 |
6. Data at C1 | I / - | M / 0 | U, pend GetM C1, acks 1/1 | 0 | C1 and memory: 0 |
(assumed) grant delivered | I / - | M / 0 | exclusive(C1) | 0 | C1 and memory: 0 |
L. Local store | I / - | M / 1 | exclusive(C1) | 0 | C1: 1 |
H may also deliver step 6 before step 5. The result is the same: C1 may store 1 before C0's load returns 0, and that load is still ordered before the store.
Now both requests are writes. C0 sends GetM A from I, C1 sends GetM B. H sends A's Data and at once forwards B to C0, its new exclusive holder. Fwd-GetM reaches C0 while it is still in IM^D. C0 cannot answer: it has neither the data nor the permission. It stalls the Fwd (holds it in its incoming queue) until Data arrives, performs its store, then answers. The stall cannot deadlock, because the Data it waits for is already in flight and depends on nothing C0 must do, provided the held Fwd does not block the queue that delivers Data.
Step | C0 state / value | C1 state / value | H directory | Memory | Newest data |
|---|---|---|---|---|---|
Initial | I / - | I / - | U | 0 | memory: 0 |
1. GetM A at H | IM^D / - | I / - | U, pend GetM C0 | 0 | memory: 0 |
2. GetM B at H | IM^D / - | IM^D / - | U, pend GetM C0, queued GetM C1 | 0 | memory: 0 |
H reads memory | IM^D / - | IM^D / - | U, pend GetM C0, queued GetM C1 | 0 | memory: 0, Data(0) in flight to C0 |
H starts B | IM^D / - | IM^D / - | exclusive(C0), pend GetM C1 | 0 | memory: 0, Data(0) in flight to C0 |
3. Fwd-GetM at C0 (stalled) | IM^D / - | IM^D / - | exclusive(C0), pend GetM C1 | 0 | memory: 0, Data(0) in flight to C0 |
4. Data at C0 (Fwd still stalled) | M / 0 | IM^D / - | exclusive(C0), pend GetM C1 | 0 | C0 and memory: 0 |
L. Local store | M / 1 | IM^D / - | exclusive(C0), pend GetM C1 | 0 | C0: 1 |
C0 handles the Fwd | I / - | IM^D / - | exclusive(C0), pend GetM C1 | 0 | Data(1) in flight to H |
5. Data at H | I / - | IM^D / - | exclusive(C0), pend GetM C1 | 0 | H buffer: 1, Data(1) in flight to C1 |
6. 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 |
L. Local store | I / - | M / 2 | exclusive(C1) | 0 | C1: 2 |
The store before the answer is the policy from Simultaneous Upgrades: a cache that receives its M grant performs at least the stalled store before it processes a Fwd or Inv for X.
Instead of handling early Inv and Fwd, the requester tells H when its grant has arrived. It sends a completion message (called Complete here; real protocols use names such as Unblock or CompAck) after it installs the Data. H keeps the next transaction for X waiting until the completion arrives. The core uses its data at once, so the completion is off the requester's critical path. The cost is one extra message per transaction and a line that stays busy at H one leg longer.
Step | C0 state / value | C1 state / value | H directory | Memory | Newest data |
|---|---|---|---|---|---|
Initial | I / - | I / - | U | 0 | memory: 0 |
1. GetS A at H | IS^D / - | I / - | U, pend GetS C0 | 0 | memory: 0 |
2. GetM B at H | IS^D / - | IM^D / - | U, pend GetS C0, queued GetM C1 | 0 | memory: 0 |
H reads memory | IS^D / - | IM^D / - | U, pend GetS C0, queued GetM C1 | 0 | memory: 0, Data(0) in flight to C0 |
3. Data at C0 | S / 0 | IM^D / - | U, pend GetS C0, queued GetM C1 | 0 | C0 and memory: 0 |
L. Load | S / 0 | IM^D / - | U, pend GetS C0, queued GetM C1 | 0 | C0 and memory: 0 |
4. Complete at H | S / 0 | IM^D / - | S{C0}, pend GetM C1, acks 0/1 | 0 | C0 and memory: 0 |
5. Inv at C0 | I / - | IM^D / - | S{C0}, pend GetM C1, acks 0/1 | 0 | memory: 0 |
6. Inv-Ack at H | I / - | IM^D / - | U, pend GetM C1, acks 1/1 | 0 | memory: 0 |
H reads memory for B | I / - | IM^D / - | U, pend GetM C1, acks 1/1 | 0 | memory: 0, Data(0) in flight to C1 |
7. Data at C1 | I / - | M / 0 | U, pend GetM C1, acks 1/1 | 0 | C1 and memory: 0 |
(assumed) grant delivered | I / - | M / 0 | exclusive(C1) | 0 | C1 and memory: 0 |
L. Local store | I / - | M / 1 | exclusive(C1) | 0 | C1: 1 |
Stall means the event waits in the cache's incoming queue until the state changes. Rows are the requester's transient states in this course (acks collected at H).
State | Load | Store | Inv | Fwd-GetS / Fwd-GetM | Data |
|---|---|---|---|---|---|
IS^D | Stall | Stall | Cannot occur under the grant-delivery rule, see the early-Inv section. Without it: send Inv-Ack, go to IS^D_I (trace a). | Cannot occur under the grant-delivery rule, see the early-Inv section. Without it, only after an E grant (MESI, MOESI): stall until Data. | Pending load returns the value, go to S. |
IM^D | Stall | Stall | Cannot occur: an IM^D cache is not on H's sharer list, so H forwards to it rather than invalidating it. | Cannot occur under the grant-delivery rule, see the early-Inv section. Without it: stall until Data, perform the store, then answer (trace b). | Go to M, perform the stalled store first. |
SM^D | Hit | Stall | Send Inv-Ack, go to IM^D (store intent kept). | Cannot occur: H forwards only to an exclusive holder. | Go to M, perform the stalled store first. |
IS^D_I | Stall | Stall | Cannot occur: the Inv was already acknowledged. | Cannot occur. | Pending load returns the value, drop the copy, go to I. |
At step 5 it has received the read grant and has now revoked that installed permission. It could not safely acknowledge before step 3 without a transient state that remembers the Inv and drops the copy after one use: otherwise the late Data could install a stale readable copy.