A target with 4 slots serves many requesters with plain retry: if it is full, it says "try again". With 2 requesters, a rejected request waits a few cycles at most. With 32, the bus fills with retries, and one unlucky request is rejected 587 times in a row before it gets in. Nothing is deadlocked: the target is busy every cycle. One requester is never lucky.
How does retry turn into livelock, and how do protocols stop it?
The obvious argument for retry is that a target always frees slots eventually, so every retry eventually succeeds. That is true on average. For any one requester, success depends on its retry arriving at the right moment, ahead of everyone else's. With many requesters retrying as fast as they can, there is no bound on how often one can lose: livelock for that requester, and a storm of wasted attempts for the system.
Policy | After a rejection | Wasted attempts | Worst wait |
|---|---|---|---|
Immediate retry | Try again next cycle | Grows with the number of requesters | Unbounded |
Random back-off | Wait a random time, growing with each failure | Small | Bounded in practice, not guaranteed |
Reservation (protocol credit) | Wait to be told a slot is reserved, then retry once (lesson 9.7) | At most one per request | Bounded: one rejection plus a turn in the queue |
Ageing | Each retry carries its age; the target prefers the oldest | Moderate | Bounded |
A target holds 4 requests and finishes one every 2 cycles; it is always the bottleneck. The model varies the number of requesters and compares immediate retry, exponential random back-off, and a protocol credit, counting rejected attempts per completion and the longest run of rejections suffered by one request.
"""Retry storms: a target with few slots, many requesters, and three retry policies.
A target holds 4 requests and finishes one every 2 cycles. N requesters each want
to send requests continuously. A request that finds the target full is rejected.
immediate: retry next cycle
backoff: wait a random 1..2^k cycles after the k-th consecutive rejection (k <= 6)
credit: a rejected requester is queued; when a slot frees, it is reserved for
the oldest queued requester, which is told to retry (a protocol credit)
Reports rejected attempts per completion and the longest run of rejections any
single requester suffered before getting in.
"""
import random
def run(policy, n, cycles=20000):
rng = random.Random(4)
SLOTS, SERVICE = 4, 2
inq, wait_until, rejects_in_row, run_len = 0, [0] * n, [0] * n, [0] * n
queue, reserved, done, rejects, worst = [], {}, 0, 0, 0
for t in range(cycles):
if inq and t % SERVICE == 0: # target finishes one request
inq -= 1; done += 1
if policy == "credit" and queue:
g = queue.pop(0)
reserved[g] = True; inq += 1; run_len[g] = 0 # slot reserved and filled by the granted retry
order = list(range(n)); rng.shuffle(order)
for i in order:
if t < wait_until[i] or reserved.get(i) or (policy == "credit" and i in queue):
continue
if inq < SLOTS:
inq += 1; rejects_in_row[i] = 0; run_len[i] = 0
else:
rejects += 1
run_len[i] += 1; worst = max(worst, run_len[i])
if policy == "immediate":
wait_until[i] = t + 1
elif policy == "backoff":
rejects_in_row[i] = min(rejects_in_row[i] + 1, 6)
wait_until[i] = t + 1 + rng.randrange(2 ** rejects_in_row[i])
else:
queue.append(i)
for i in list(reserved): # a granted retry has been accepted
del reserved[i]
return rejects / max(done, 1), worst
ns = [2, 4, 8, 16, 32]
table = {}
print("requesters: " + " ".join(f"{n:5d}" for n in ns))
for policy in ("immediate", "backoff", "credit"):
rows = [run(policy, n) for n in ns]
table[policy] = rows
print(f"{policy:9s} rejects per completion: " + " ".join(f"{r:5.1f}" for r, _ in rows) + " longest rejection run: " + " ".join(f"{w:5d}" for _, w in rows))
imm, crd = table["immediate"], table["credit"]
assert imm[-1][0] > 10 * imm[0][0] and max(r for r, _ in crd) <= 1.01 and max(w for _, w in crd) == 1
print("PASS: immediate retries waste more attempts, and starve some requests longer, as requesters grow; a protocol credit bounds both")It prints:
requesters: 2 4 8 16 32
immediate rejects per completion: 3.0 7.0 15.0 31.0 63.0 longest rejection run: 23 73 117 417 587
backoff rejects per completion: 0.9 1.4 2.0 3.0 4.5 longest rejection run: 17 19 48 30 57
credit rejects per completion: 1.0 1.0 1.0 1.0 1.0 longest rejection run: 1 1 1 1 1
PASS: immediate retries waste more attempts, and starve some requests longer, as requesters grow; a protocol credit bounds bothThroughput is the same in every case: the target finishes one request every 2 cycles whatever the policy. What differs is waste and fairness. Immediate retry wastes about 2N − 1 attempts per completion and lets one request lose 587 times in a row. Back-off cuts waste sharply but still lets an unlucky request wait dozens of rounds. The protocol credit guarantees at most one rejection per request.
Protocol | Retry |
|---|---|
Original AHB | SPLIT and RETRY responses on a multi-master bus; a retried master tried again. AHB-Lite, a single-master version, removed both. |
AMBA CHI | Retry plus a protocol credit: a rejected request is guaranteed to be accepted when retried with the granted credit (lesson 9.7). |
Classic shared Ethernet | Random exponential back-off after collisions. |
A system (illustrative) used immediate retry at a shared cache controller. Two processors that always issued their requests on the same clock edge after each rejection kept colliding with each other, and both lost repeatedly to a third requester that arrived at a different phase. The fix was a protocol credit list at the controller; random back-off would have broken the symmetry too, but without a guarantee.
The target is the bottleneck, finishing one request every 2 cycles regardless; the policies differ only in wasted attempts and in how long individual requests wait.
It breaks their symmetry: with different random delays they stop retrying on the same cycle.
Plain retry avoids deadlock but can livelock: wasted attempts grow with load and individual requests can lose indefinitely.
Random back-off cuts waste but gives no hard bound; reservation (protocol credits) or ageing does.
Measure the worst-case rejection run under saturation, not the average.