A requester on a busy fabric issues a read and never gets an answer. Nothing has failed: every transfer in the system completes correctly. This one requester never wins arbitration, because someone with higher priority always wants the same resource at the same moment. In a design review it would have been called "low priority". On the bench it is called a hang.

How do you make sure every requester is eventually served, and how do you measure how fair an arbiter is?

The obvious answer, and why it breaks

The obvious notion of fairness is "everyone gets a turn eventually". But eventually is not a number. A requester that waits a million cycles has technically been served, and the system around it has long since failed. Useful fairness is a bound: an asking requester is served within a stated number of grants or cycles. And it has a second side, bandwidth: how big a share each requester gets when everyone wants more than the resource can give.

The idea: two measures

Starvation is an unbounded worst wait: some pattern of other traffic can keep a requester waiting for ever. Fixed priority starves whenever higher-priority requesters can ask continuously; round-robin cannot starve anyone, because the winner always moves to the back.

Build it: a fairness simulator

Four requesters share a resource for 12,000 cycles. Requesters 0 and 1 always ask; 2 and 3 ask in a random 60% of cycles. The model runs fixed priority, round-robin and weighted round-robin (weights 4, 2, 1, 1) and reports each requester's share and longest wait.

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56

"""Grant share and worst wait for three arbitration policies.

Four requesters share one resource for 12,000 cycles. Requesters 0 and 1 always
want it; requesters 2 and 3 want it in a random 60% of cycles. Each cycle the
arbiter grants one requester that is asking:
  fixed:    the lowest-numbered requester asking wins
  rr:       round-robin: the first asking requester after the last one granted
  weighted: weighted round-robin with weights 4, 2, 1, 1 (in each round of 8
            grants, each requester gets up to its weight, in turn)
It reports each requester's share of grants and its longest wait while asking.
"""
import random

N, CYCLES = 4, 12000


def run(policy):
    rng = random.Random(9)
    grants, wait, worst = [0] * N, [0] * N, [0] * N
    last, credit = N - 1, [4, 2, 1, 1]
    for _ in range(CYCLES):
        req = [True, True, rng.random() < 0.6, rng.random() < 0.6]
        g = None
        if policy == "fixed":
            g = next((i for i in range(N) if req[i]), None)
        elif policy == "rr":
            g = next(((last + k) % N for k in range(1, N + 1) if req[(last + k) % N]), None)
        else:
            if not any(req[i] and credit[i] for i in range(N)):
                credit = [4, 2, 1, 1]                      # start a new round
            g = next(((last + k) % N for k in range(1, N + 1) if req[(last + k) % N] and credit[(last + k) % N]), None)
            if g is not None:
                credit[g] -= 1
        for i in range(N):
            if req[i] and i != g:
                wait[i] += 1
                worst[i] = max(worst[i], wait[i])
            else:
                wait[i] = 0
        if g is not None:
            grants[g] += 1
            last = g
    return [x / CYCLES for x in grants], worst


results = {}
for policy in ("fixed", "rr", "weighted"):
    share, worst = run(policy)
    results[policy] = (share, worst)
    print(f"{policy:8s} share: " + " ".join(f"{x:5.2f}" for x in share) + "   worst wait: " + " ".join(f"{w:5d}" for w in worst))
fixed_share, fixed_worst = results["fixed"]
rr_share, rr_worst = results["rr"]
w_share, _ = results["weighted"]
assert fixed_share[1] == fixed_share[2] == fixed_share[3] == 0 and max(rr_worst) <= 3
assert w_share[0] > w_share[1] > w_share[2]
print("PASS: fixed priority starves everyone below requester 0; round-robin bounds every wait at 3; weights split the bandwidth on purpose")

It prints:

fixed    share:  1.00  0.00  0.00  0.00   worst wait:     0 12000    19    17
rr       share:  0.31  0.31  0.19  0.19   worst wait:     3     3     3     3
weighted share:  0.50  0.25  0.12  0.12   worst wait:     3     7     7     8
PASS: fixed priority starves everyone below requester 0; round-robin bounds every wait at 3; weights split the bandwidth on purpose

Under fixed priority, requester 0 asks every cycle and takes every grant; requester 1 waits all 12,000 cycles. Round-robin gives every requester a turn within 3 grants. The shares are unequal (0.31 against 0.19) only because 2 and 3 ask less often. Weighted round-robin splits bandwidth on purpose, half to requester 0, and still bounds every wait, at a few cycles more for the low-weight requesters.

Proving a bound

• Round-robin: after a requester starts asking, each other requester can be granted at most once before the pointer reaches it, so its wait is at most N − 1 grants.

• Weighted round-robin: about one round of the other requesters' weights, plus a little when a new round starts: with weights 4, 2, 1, 1 the model's low-weight requesters waited at most 7 or 8 grants.

• Multi-level systems: a requester's bound is the product of the bounds at every arbiter on its path, multiplied by how long each grant can hold the resource (lesson 8.5). Long bursts and locks turn short bounds into long ones.

How real systems chose

What breaks

A multi-level fabric (illustrative) used round-robin at every router, which looks fair. But traffic from a corner tile crossed six routers, and at each one it competed with traffic that had joined more recently and shared the same output equally. By the last router, the corner tile's share of a hot memory port was a few percent, and its latency was the worst in the system. Age-based arbitration, which favours the request that has waited longest overall, evened it out.

Key takeaways

• Fairness has two measures: a bounded worst wait, and bandwidth shares under saturation.

• Fixed priority starves lower requesters unless higher traffic is bounded; round-robin bounds every wait to N − 1 grants.

• Bounds compose along a path; long holds and many hops stretch them.

Related topics

• Part 8 overview: Sharing and Arbitration