What if the last ack arrives before the bytes?

A zero acknowledgement count means the specified revocations are complete. It does not make missing data appear. The converse is equally important: receiving the current value does not prove another cache has lost permission. This example keeps both dependencies at H, so the final Data still combines a usable value with the M grant.

Warm-up from X = 0: a previous write of 1 was completed and cleaned to memory, and C0 then obtained S / 1. Now C0 S / 1, C1 I / -, H S{C0}, memory = 1, MSI. C1 requests GetM A. H starts a memory read and sends an invalidation, then receives Inv-Ack before the memory read returns. Only A is active; a conflicting request would wait. Memory is authoritative because the old holder is clean S, not a dirty exclusive cache.

Not the course's convention: in the Primer's directory protocol, invalidated caches send Inv-Acks straight to the requester, and Data carries the number of acks to expect. The requester waits in IM^AD or SM^AD. Because there is no FIFO order, an Inv-Ack can arrive before the Data that says how many to expect, so the requester keeps a signed counter: each early Inv-Ack decrements it below zero, and the ack count in Data adds back. The requester completes when Data has arrived and the counter is zero.

Count identities, not just packets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def receive(entry, transaction, kind, responder=None, value=None):
    if transaction != entry["id"]:
        return False
    if kind == "ack":
        if responder not in entry["waiting"]:
            return False
        entry["waiting"].remove(responder)
    elif kind == "data":
        if value is None or entry["data"] is not None:
            return False
        entry["data"] = value
    else:
        return False
    return True
def ready(entry):
    return not entry["waiting"] and entry["data"] is not None
for order in [("ack", "data"), ("data", "ack")]:
    entry = {"id": "A", "waiting": {"C0"}, "data": None}
    assert not ready(entry)
    assert not receive(entry, "old", "ack", responder="C0")
    assert not receive(entry, "old", "data", value=99)
    for position, kind in enumerate(order):
        assert receive(entry, "A", kind, responder="C0", value=0)
        assert ready(entry) == (position == 1)
    assert not receive(entry, "A", "ack", responder="C0")
    assert not receive(entry, "A", "data", value=99)
    assert entry["data"] == 0 and ready(entry)
print("PASS: both arrival orders require matching acks and present data")

Simulation: two acks, data in between

The waveform below is simulation output for H's pending entry in a three-core variant of the model: C0 and C2 hold X in S, memory is authoritative, and C1 sends GetM. H collects two Inv-Acks and the memory data. Here the data arrives between the two acks, whereas in the table above the ack came first. One slot is one clock cycle.

How to read it: C1's GetM is accepted in slot 1. In slot 2 the entry is pending, inv_sent pulses (Inv to C0 and C2) and acks_left is 2. C0's Inv-Ack in slot 4 brings acks_left to 1 in slot 5. The memory read returns in slot 6, so data_valid is high in slots 7 and 8, but grant stays low: one ack is still missing. C2's Inv-Ack in slot 8 brings acks_left to 0 in slot 9, and grant (Data with M permission to C1) pulses in that same slot while pending and data_valid clear. store_done rises in slot 10: C1's store completes only after the grant.

The code checks both arrival orders and rejects stale identities and duplicate responses without changing the accepted value. A counter can replace the expected-responder set only if each required response is counted exactly once.

Related topics

• Shared course model

• Compare: permission-only upgrade