In this course, yes: PutS or PutE, then wait for Put-Ack. Real protocols choose between the two approaches below. Silent eviction applies only to clean copies: an M or O line always leaves with PutM carrying the data.
Notified eviction (PutS, PutE): course default | Silent clean eviction: variant |
|---|---|
H keeps exact sharer lists. | Saves one message and its Put-Ack per clean eviction. |
No wasted Inv to a cache that no longer holds the line. | Removes the race between a PutS and an Inv for the same line. |
Lets a sparse directory or snoop filter free its entry. | Costs a stale sharer bit and, later, a wasted Inv/Inv-Ack round trip. |
Start (MSI) after a completed cold read: C0 S / 0, C1 I / -, H S{C0}, memory = 0. C0 evicts X and sends PutS. The eviction states are defined on the topic hub.
Step | C0 state / value | C1 state / value | H directory | Memory | Newest data |
|---|---|---|---|---|---|
0. Start | S / 0 | I / - | S{C0} | 0 | C0 and memory: 0 |
C0 evicts X | SI^A / - | I / - | S{C0} | 0 | memory: 0, PutS in flight to H |
1. PutS at H | SI^A / - | I / - | S{C0}, pend PutS C0 | 0 | memory: 0 |
H removes C0, sends Put-Ack | SI^A / - | I / - | U | 0 | memory: 0 |
2. Put-Ack at C0 | I / - | I / - | U | 0 | memory: 0 |
MESI E works the same way with PutE: from C0 E / 0, H exclusive(C0), memory = 0, C0 moves to EI^A and sends PutE (no data). H records U and sends Put-Ack. Memory is current because the line was E, not M: had C0 stored, the line would be M and leave with PutM.
C0 cannot re-request X until Put-Ack arrives, because loads and stores to X stall in SI^A, so a new copy of X at C0 cannot overlap this PutS. If C1's GetM reaches H first, H sends Inv to C0. If an Inv for X reaches C0 in SI^A, C0 still sends Inv-Ack (and moves to II^A), and the later PutS from a non-sharer just gets Put-Ack.
Under a silent policy C0 drops its S copy with no message. H still records S{C0}: a stale sharer bit. Memory is current, so no value is lost, but the next write pays for the stale bit. Same start: C0 S / 0, C1 I / -, H S{C0}, memory = 0.
Step | C0 state / value | C1 state / value | H directory | Memory | Newest data |
|---|---|---|---|---|---|
0. Start | S / 0 | I / - | S{C0} | 0 | C0 and memory: 0 |
C0 drops X silently | I / - | I / - | S{C0} | 0 | memory: 0 |
1. GetM at H | I / - | IM^D / - | S{C0}, pend GetM C1, acks 0/1 | 0 | memory: 0 |
2. Inv at C0 | I / - | IM^D / - | S{C0}, pend GetM C1, acks 0/1 | 0 | memory: 0 |
3. Inv-Ack at H | I / - | IM^D / - | U, pend GetM C1, acks 1/1 | 0 | memory: 0 |
H reads memory | I / - | IM^D / - | U, pend GetM C1, acks 1/1 | 0 | memory: 0, Data(0) in flight to C1 |
4. 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 |
C0 in I must still reply Inv-Ack, otherwise H would wait for ever. The cost is a wasted Inv/Inv-Ack round trip on C1's write, and a stale sharer bit that stays in H until the next write to X clears it.
Victim | May it be dropped silently? | What must hold |
|---|---|---|
Clean S | Only in a protocol that allows stale sharer bits | Memory is current, and a cache in I answers Inv with Inv-Ack. |
Clean E | Only in a protocol that defines it | H still records exclusive(C0). A later Fwd-GetS or Fwd-GetM reaching C0 in I needs a 'no copy' reply, which is not in this course's message set. H may then use memory only because the line was E, not M. A PutM still in flight from a real M copy must be distinguished first (Part 4). This is why many protocols, this course included, send PutE. |
M or O | Never | The dirty data must go to H with PutM and Put-Ack must arrive before the WB entry is freed. |
With a stale S{C0} memory is still current, so the worst case is a wasted Inv and Inv-Ack. Recording U while C0 holds M / 1 hides a writer and the only copy of 1: H would grant another cache permission and serve the stale 0 from memory.