Knowing the value is insufficient when C1 may still read its copy. H is the home for line X: it records holders and serializes conflicting transactions for this line. A directory directs requests to possible holders rather than asking every cache to inspect each request. Its entry describes permissions elsewhere; it is neither the data value nor a private-cache state.
Use the two-core, 64-byte-line course model. Its reset has X = 0 in memory and no cached copy. This worked example begins at a legal later snapshot: both caches hold S / 0, H records S{C0,C1}, and memory is still 0. That is an idle read epoch with no writer. The snapshot is a precondition, not an additional unshown transaction sequence.
Entry field | Values | Meaning |
|---|---|---|
State | U, S or exclusive (2 bits) | No cached copy, read-only copies only, or one exclusive holder (E or M) that may write |
Sharer bits | One bit per cache (2 bits here) | Which caches may hold a copy; a set bit means possibly present, not newest value |
Exclusive holder id | Encoded in the sharer bits | When the state is exclusive, exactly one sharer bit is set and it names the exclusive holder, so no separate id field is needed |
So S{C0,C1} is state S with both sharer bits set, and exclusive(C0) is state exclusive with only C0's bit set. A MOESI directory must also name the dirty-responsible O holder alongside the sharers (written O: C0, sharers {C1}), which costs extra bits. Choosing Snoop or Directory computes what this entry costs per line.
The S/S upgrade (C0 sends GetM, H sends Inv to C1, C1's Inv-Ack returns to H, H sends permission-only Data to C0) is traced with every state and value in Epochs and Serialization. Here we follow only what that trace does to H's entry, using its step numbers. Sharer bits are written C0 then C1.
Step in that trace | State field | Sharer bits (C0 C1) | Pending part | Why |
|---|---|---|---|---|
0. Read epoch | S | 1 1 | none | Both caches may hold read-only copies |
1. GetM at H | S | 1 1 | pend GetM C0, acks 0/1 | H records the upgrade and sends Inv to C1 |
2. Inv at C1 | S | 1 1 | pend GetM C0, acks 0/1 | No message reached H, so nothing changes, although C1 is already I |
3. Inv-Ack at H | S | 1 0 | pend GetM C0, acks 1/1 | C1's bit is cleared only now: S{C0} |
4. Data at C0 | S | 1 0 | pend GetM C0, acks 1/1 | The requester has its grant, H keeps the pending entry |
(assumed) grant delivered | exclusive | 1 0 | none | exclusive(C0): the single set bit names the exclusive holder |
Two properties of the entry show up here. A set bit means 'possibly present', so C1's bit stays set at step 2 although C1 has invalidated: H learns that only at step 3. And the final store at C0 sends nothing, so exclusive(C0) is the same entry for a clean or a dirty holder (E (MESI, MOESI) silently becoming M). Delivery and grant-delivery assumptions: see the course model.
The course model collects Inv-Acks at H, so this upgrade takes four serial legs: GetM to H, Inv to C1, Inv-Ack to H, Data to C0. The Primer, second edition, chapter 8 instead sends Inv-Acks straight to the requester and puts the expected ack count in Data, which H sends in parallel with the Inv; the same upgrade then takes three serial legs: GetM, Inv, Inv-Ack to C0. Both are legal. The course uses H-collected acks so that one node holds all the pending work, at the cost of one extra leg on every upgrade with sharers.
Ack routing | Serial legs | Who counts acks | When C0 may store |
|---|---|---|---|
Acks to H (this course) | 4: GetM, Inv, Inv-Ack to H, Data | H's pending entry | On Data, which H sends only after the last ack |
Acks to requester (Primer) | 3: GetM, Inv, Inv-Ack to C0 | C0, from the count in Data | When it holds Data and every ack (SM^AD) |
No. A sharer bit means 'possibly present', and H may change its entry only when a message reaches it. C1's invalidation is unconfirmed until its Inv-Ack arrives at step 3, so clearing the bit at step 2 would let H treat an unconfirmed revocation as done. Keeping a bit set too long costs at most an extra Inv; clearing it too early can grant M beside a live reader.