Two cores cannot do it on their own: a core that already holds M has no reason to send another GetM. So this experiment uses three cores. C0 and C2 alternate GetM on X (a lock ping-pong): each takes the line from the other, then requests it again as soon as it loses it. Fixed priority ranks both above C1, so H always has a higher-priority eligible GetM and C1's queued GetM is never selected. Keep the course's single conflicting transaction at H: each selected transaction completes before the next decision. C1's request stays queued and eligible throughout.
A fair policy needs an explicit definition of eligibility. A request dropped for lack of a pending entry never enters the ingress queue (the queue a request enters before arbitration), so fairness at that arbiter does not protect it. Likewise, an admitted request does not complete merely because its selection was fair: its Invs or Fwds, responses, data storage and grant still need service.
Policy, three cores | Selection rule | C1 consequence |
|---|---|---|
Fixed priority, C0 and C2 above C1 | Choose C0 or C2 whenever either is eligible | C1 is bypassed indefinitely while C0 and C2 keep alternating. |
Three-source round-robin | After each selection, the next source in the order C0, C1, C2 gets top priority | A continuously eligible C1 is selected within three decisions: at most two other transactions precede it. |
Round-robin only inside the ingress queue | Rotate only among requests already in that queue | Says nothing about a C1 request unable to enter that queue. |
ORDER = [0, 1, 2] # round-robin order C0, C1, C2
RANK = {0: 0, 2: 1, 1: 2} # fixed priority: C0 and C2 above C1
def run(policy, start, steps=12):
holder, pointer, c1_waiting, winners = None, start, True, []
for _ in range(steps):
# Lock ping-pong: whichever of C0, C2 lacks M asks again.
eligible = [c for c in (0, 2) if c != holder]
if c1_waiting:
eligible.append(1)
if policy == "fixed":
winner = min(eligible, key=RANK.get)
else:
winner = next(ORDER[(pointer + k) % 3] for k in range(3)
if ORDER[(pointer + k) % 3] in eligible)
pointer = (winner + 1) % 3
winners.append(winner)
holder = winner
if winner == 1:
c1_waiting = False
return winners
fixed = run("fixed", 0)
assert fixed == [0, 2] * 6 and 1 not in fixed # C1 starves
for start in ORDER:
rr = run("rr", start)
assert rr.index(1) < 3 # within three decisions
print("PASS: fixed priority starves C1 under ping-pong, round-robin serves it")The program checks finite prefixes; the rotating rule supplies the three-decision argument for this three-source setup. Eventual completion also assumes eventual reliable delivery, fair service at each receiving node, reserved completion resources and eventual acceptance by each receiver. Without an upper bound on that work, three decisions is not a cycle bound.
Arbitration decides when C1's request starts, never whether C0's newest value may be skipped: see QoS Classes and Coherence for the dirty-holder case.
The response can still be blocked by routing, receive capacity or unfair service at the receiving node. Admission fairness addresses one stage, not the whole dependency path.