Who owns a request that cannot enter?

Backpressure means the receiver has no space, so the sender keeps the request and does not send it yet. Rejection (a NACK) means the receiver saw the request, did not keep it, and the sender must retry. Queueing means the receiver kept the request and will serve it later. These outcomes need different local state, even if all make the processor wait.

X started at 0. C0's read A has been accepted: C0 is IS^D, C1 is I, H is U with A pending, memory = 0. If C1 wants to write, A keeps the active slot. C1 waits at the sender under backpressure, retries after a NACK, or waits in a reserved H queue if accepted there. None of these gives it write permission.

The last row is a separate checkpoint after C0 stored 1 and sent it to H; it does not follow from the rows above. It shows why a rule for refusing requests cannot be applied to dirty data that H has already accepted: H must keep that buffer until it has passed the data on.

A NACKed request can be rejected forever (starvation), or two retriers can keep displacing each other (livelock). Common remedies: reserve a slot or retry token at NACK time, or serve oldest first.

Credits: the sender holds one credit per free receiver slot and sends only with a credit, so that buffer never overflows and never needs a NACK.

Deadlock: requests wait for each other in a cycle and none moves. Livelock: messages keep moving but no request completes. Starvation: others complete but one request never does. Backpressure: a full receiver makes the sender hold its message. Part 5 goes deeper into all four.

Credits describe capacity, not coherence permission

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

capacity = 1
state = {"credits": capacity, "pending": "A", "grant": None, "data": None}
def send():
    assert state["credits"] > 0
    state["credits"] -= 1
def return_credit():
    assert state["credits"] < capacity
    state["credits"] += 1
def receive_grant(transaction, value):
    if transaction != state["pending"] or state["grant"] is not None:
        return False
    state["grant"], state["data"] = transaction, value
    return True
def may_store():
    return state["grant"] == state["pending"] and state["data"] is not None
assert not may_store()
send()
assert state["credits"] == 0 and not may_store()
return_credit()
assert state["credits"] == capacity and not may_store()
assert not receive_grant("old", 99)
assert not may_store()
assert receive_grant("A", 0)
assert may_store()
assert not receive_grant("A", 99)
assert state["data"] == 0
print("PASS: only a matching grant, not returned credit, enables the store")

Simulation: a sender stalls on zero credits

The waveform below is simulation output for a sender that starts with 2 credits (one per free receiver slot) and has three messages to send. It sends only when it holds a credit; a credit returned in a cycle is counted after that edge's send decision. One slot is one clock cycle.

How to read it: three messages become pending in slot 2. valid is high in slots 3 and 4, and credits drops from 2 to 1 to 0 while pending drops to 1. From slot 5 valid stays low: a message is waiting but there is no credit, so the sender holds it (backpressure, not a NACK). credit_return pulses in slot 6 and credits is 1 in slot 7. In slot 8 the third message goes out and credits and pending both return to 0. The returns in slots 10 and 12 bring credits back to 1 and then 2, with nothing left to send.

A returned credit is not an Inv-Ack or a grant. It must match the actual buffer lifecycle: a controller can move a received request into a protected pending entry, and return the credit, long before the whole coherence transaction completes.

A protocol that uses explicit rejection must specify whether the request was accepted, which identity the retry carries, how fairness is ensured and what response is expected. Never blindly resend an already accepted GetM merely because it is slow: duplicate grants or repeated invalidations can result.

Related topics

• Shared course model

• Queued requests and required Inv handling