Which resource is held while another is requested?

Extend the course model with Y in a different line and finite H resources: one pending entry P and one shared ingress slot Q (ingress: the buffer where an arriving message waits before H processes it). An arriving request keeps Q until it can allocate P. A response also needs Q to enter H, although it would service the already allocated P. This is the deliberately bad resource policy.

C0 also has one egress slot T0 (egress: the outgoing buffer where a message waits for the network to carry it), reserved for its response before it accepts the forward. Once T0 holds Data(1), the cache gives up the line and shows I. T0 is transport storage, not a cache copy and not H's slot Q. Reliable transport keeps the payload while it waits for Q, so the blocked value is Data(1) in flight to H.

Use MSI. Warm-up from X = 0: C0 acquired M and stored 1, C1 is invalid for X, memory = 0. Y starts at 0, uncached. Use the four-hop route of Three-Hop Versus Four-Hop: C0 returns the forwarded data to H. C1 requests X while C0 independently misses on Y. In this selected arrival order C1's GetM wins P, and C0's GetS(Y) reaches Q before C0's Data(1).

Break the dependency with genuinely reserved response capacity

Compare a corrected design with Qreq and Qresp. When H allocates P for X, it also reserves one Qresp slot and a protected data destination for X's response. Qreq may hold Y, but X's response enters Qresp and is processed using the existing P, never needing another free P. H keeps the accepted data until its grant is delivered, releases P, then services Y. This removes the dependency from Qreq to X's response.

The corrected run completes under A1-A6 (assumptions), chiefly A3: the Qresp slot is reserved when P is allocated, and response handling never needs another P. Separate queues without that reservation would merely redraw the problem.

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42

from itertools import permutations
MSGS = ("GetM X", "Data X", "GetS Y")
def run(order, reserved):
    s = {"P": None, "Q": None, "Qresp": None, "net": {"GetM X", "GetS Y"}, "done": set()}
    def slot(m):
        return "Qresp" if reserved and m == "Data X" else "Q"
    def can_deliver(m):
        return m in s["net"] and s[slot(m)] is None
    def internal():
        for b in ("Q", "Qresp"):
            if s[b] == "Data X":          # response uses the existing P
                s[b], s["P"] = None, None  # grant to C1, delivery known (A6)
                s["done"].add("X")
                return True
        if s["Q"] in ("GetM X", "GetS Y") and s["P"] is None:
            req, s["Q"] = s["Q"], None
            if req == "GetM X":
                s["P"] = "X"
                s["net"].add("Data X")     # Fwd-GetM, C0 answers into the network
            else:
                s["done"].add("Y")         # memory-sourced, P used and freed
            return True
        return False
    for m in order:
        while internal():
            pass
        if m not in s["net"]:
            return None                    # order not realisable
        if not can_deliver(m):
            break
        s["net"].remove(m)
        s[slot(m)] = m
    while internal():
        pass
    stuck = not any(can_deliver(m) for m in s["net"])
    return s["done"], stuck
shared = [r for r in (run(o, False) for o in permutations(MSGS)) if r]
fixed = [r for r in (run(o, True) for o in permutations(MSGS)) if r]
assert len(shared) == len(fixed) == 3
assert any(stuck and "X" not in done for done, stuck in shared)
assert all(done == {"X", "Y"} for done, _ in fixed)
print("PASS: shared Q can deadlock, reserved Qresp completes X and Y in every order")

The explorer delivers the three messages in every realisable order, taking H's internal moves (allocate P, consume a response) whenever they are enabled. With the shared Q, the order GetM X, GetS Y, Data X stops with no enabled move and X incomplete. With Qresp reserved per P, every order completes both X and Y. It checks this small model only, not a production fabric.

Related topics

• Shared course model

• Pending-entry admission