Fairness

Chapter 17.2 built a policy that rotates. Describing what it buys has needed the word "fair" twice, and both times the word was deferred.

What exactly does fairness mean here, and what has to be true for the claim to hold?

1. Two Properties, and Neither Is Called "Fairness"

Write down what you actually want before choosing a policy. Here are two candidates that sound similar and are not.

SERVICE. A requester that remains eligible eventually receives a grant.

BOUNDED LOSING RUN. A requester that remains eligible loses at most N consecutive arbitration opportunities before it is chosen.

The second implies the first and the first does not imply the second. "Eventually" admits any finite delay, including one long enough to miss every deadline in the system. A design review that accepts "eventually" has accepted nothing measurable.

For this module's round-robin policy the bound is structural and small. The scan starts one past the history and takes the first eligible requester, so before the preference can return to any requester it must have passed the other NREQ - 1 positions. With three requesters that is at most two lost opportunities in a row; with two, at most one.

That is the property this chapter claims, and it is the only one. Not equal grants. Not equal bandwidth. Not equal anything.

2. The Assumptions, Written Out

No arbiter can manufacture progress. A selection policy chooses among requesters at moments it does not control, so every bound it offers is conditional on those moments occurring.

A2 is the one that is not about the arbiter, and it is the one that fails in practice. Chapter 16.4 measured a master that held CYC_O for sixty clocks — conformant under PERMISSION 3.05, "MASTER interfaces MAY assert [CYC_O] indefinitely" — and a perfect round-robin selector would have changed nothing about it, because there were no events for it to decide.

Say that plainly, because it is the most useful sentence in the chapter:

A selection policy and a release policy are orthogonal. Round robin does not solve a master that never releases; it decides who is next when there is a next.

RECOMMENDATION 3.05 is the closest B3 comes to acknowledging this, and it is advisory: "Keeping [CYC_O] asserted may lead to arbitration problems. It is therefore recommended that [CYC_O] is not indefinitely asserted."

3. RTL — Measuring in Opportunities, Not Clocks

A fairness measurement taken in clocks is not a measurement of the arbiter. A requester that waits forty clocks because the slave inserted wait states for somebody else has not been treated badly by the policy. The instrument has to count decisions.

// ─────────────────────────────────────────────────────────────────────────
// wb_arb_probe — the arbitration-event audit.
//
// SIMULATION ONLY. int counters, no synthesis intent, and none of it is a
// Wishbone feature. A silicon version would be narrow counters behind a
// status register.
//
// It answers four questions no single signal answers:
//
//   1. WHAT DID THE POLICY DECIDE, AND WAS IT RIGHT? An independent
//      reference model recomputes the expected winner from the eligibility
//      vector and its OWN history and compares. It is not wired to the
//      arbiter's pointer, so a pointer that updates on the wrong event is
//      caught rather than mirrored.
//   2. WAS EVERY GRANT DESERVED? A grant must go to a requester that was
//      asking at that event.
//   3. WAS THE OWNER RETAINED? No owner change while a presented phase is
//      unanswered.
//   4. HOW LONG DID SOMEBODY WAIT - IN OPPORTUNITIES, NOT CLOCKS?
//
// The fourth is the one that makes policy measurable. A requester that
// waits forty clocks because the slave inserted wait states has not been
// treated badly by the arbiter. A requester that was eligible at twelve
// acquisition opportunities and chosen at none of them has. Counting raw
// clocks conflates arbitration wait with slave wait, which is why
// Chapter 17.3 counts opportunities instead.
// ─────────────────────────────────────────────────────────────────────────
module wb_arb_probe #(
  parameter bit POLICY = 1'b0        // reference model: 0 fixed, 1 RR
) (
  input  logic        clk_i,
  input  logic        rst_i,
  input  logic [2:0]  elig_i,        // {io, dma, cpu}
  input  logic        arb_event_i,
  input  logic        commit_i,
  input  logic [1:0]  grant_i,       // 0 = CPU, 1 = DMA, 2 = IO
  input  logic [1:0]  owner_i,
  input  logic        s_cyc_i, s_stb_i, s_ack_i, s_err_i, s_rty_i,
  // violations
  output int unsigned v_grant_no_req_o,
  output int unsigned v_policy_wrong_o,
  output int unsigned v_owner_change_active_o,
  // events
  output int unsigned arb_events_o,
  output int unsigned contested_o,
  // per requester
  output int unsigned gr0_o, gr1_o, gr2_o,
  output int unsigned opp0_o, opp1_o, opp2_o,
  output int unsigned lost0_o, lost1_o, lost2_o,
  output int unsigned maxlost0_o, maxlost1_o, maxlost2_o,
  output logic [1:0]  ref_hist_o
);
  // Named request bits: a bit-select of a vector inside an always_* block
  // draws an Icarus sensitivity warning, so each is named once.
  logic q0, q1, q2;
  assign q0 = elig_i[0];
  assign q1 = elig_i[1];
  assign q2 = elig_i[2];

  logic [1:0] ref_last_q;
  assign ref_hist_o = ref_last_q;

  logic [1:0] prev_owner_q;
  logic       prev_active_q;
  int unsigned run0_q, run1_q, run2_q;

  // ── the independent reference model ──
  logic [1:0] ref_sel;
  logic       ref_valid;
  always_comb begin
    ref_valid = q0 || q1 || q2;
    ref_sel   = 2'd0;
    if (!POLICY) begin
      // fixed priority: the lowest eligible index
      if      (q0) ref_sel = 2'd0;
      else if (q1) ref_sel = 2'd1;
      else         ref_sel = 2'd2;
    end else begin
      // round robin: scan from one past the history, wrapping
      case (ref_last_q)
        2'd0: begin
          if      (q1) ref_sel = 2'd1;
          else if (q2) ref_sel = 2'd2;
          else         ref_sel = 2'd0;
        end
        2'd1: begin
          if      (q2) ref_sel = 2'd2;
          else if (q0) ref_sel = 2'd0;
          else         ref_sel = 2'd1;
        end
        default: begin
          if      (q0) ref_sel = 2'd0;
          else if (q1) ref_sel = 2'd1;
          else         ref_sel = 2'd2;
        end
      endcase
    end
  end

  logic term, contested, granted_eligible;
  assign term      = s_ack_i || s_err_i || s_rty_i;
  assign contested = (q0 + q1 + q2) > 1;
  always_comb begin
    case (grant_i)
      2'd0:    granted_eligible = q0;
      2'd1:    granted_eligible = q1;
      default: granted_eligible = q2;
    endcase
  end

  logic won0, won1, won2;
  assign won0 = commit_i && (grant_i == 2'd0);
  assign won1 = commit_i && (grant_i == 2'd1);
  assign won2 = commit_i && (grant_i == 2'd2);

  always_ff @(posedge clk_i) begin
    if (rst_i) begin
      v_grant_no_req_o <= 0; v_policy_wrong_o <= 0;
      v_owner_change_active_o <= 0;
      arb_events_o <= 0; contested_o <= 0;
      gr0_o <= 0; gr1_o <= 0; gr2_o <= 0;
      opp0_o <= 0; opp1_o <= 0; opp2_o <= 0;
      lost0_o <= 0; lost1_o <= 0; lost2_o <= 0;
      maxlost0_o <= 0; maxlost1_o <= 0; maxlost2_o <= 0;
      ref_last_q <= 2'd0;
      prev_owner_q <= 2'd0; prev_active_q <= 1'b0;
      run0_q <= 0; run1_q <= 0; run2_q <= 0;
    end else begin
      // 3. retention
      if (owner_i != prev_owner_q && prev_owner_q != 2'd0
          && owner_i != 2'd0 && prev_active_q)
        v_owner_change_active_o <= v_owner_change_active_o + 1;
      prev_owner_q  <= owner_i;
      prev_active_q <= s_cyc_i && s_stb_i && !term;

      if (arb_event_i) begin
        arb_events_o <= arb_events_o + 1;
        if (contested) contested_o <= contested_o + 1;
        if (q0) opp0_o <= opp0_o + 1;
        if (q1) opp1_o <= opp1_o + 1;
        if (q2) opp2_o <= opp2_o + 1;

        if (commit_i) begin
          if (!granted_eligible) v_grant_no_req_o <= v_grant_no_req_o + 1;
          if (grant_i != ref_sel || !ref_valid)
            v_policy_wrong_o <= v_policy_wrong_o + 1;
          ref_last_q <= grant_i;
          if (won0) gr0_o <= gr0_o + 1;
          if (won1) gr1_o <= gr1_o + 1;
          if (won2) gr2_o <= gr2_o + 1;
        end

        // 4. eligible at this opportunity and not chosen
        if (q0 && !won0) begin
          lost0_o <= lost0_o + 1;
          run0_q  <= run0_q + 1;
          if (run0_q + 1 > maxlost0_o) maxlost0_o <= run0_q + 1;
        end else if (won0) run0_q <= 0;
        if (q1 && !won1) begin
          lost1_o <= lost1_o + 1;
          run1_q  <= run1_q + 1;
          if (run1_q + 1 > maxlost1_o) maxlost1_o <= run1_q + 1;
        end else if (won1) run1_q <= 0;
        if (q2 && !won2) begin
          lost2_o <= lost2_o + 1;
          run2_q  <= run2_q + 1;
          if (run2_q + 1 > maxlost2_o) maxlost2_o <= run2_q + 1;
        end else if (won2) run2_q <= 0;
      end
    end
  end
endmodule

Reading it

Four questions, and the fourth is the one this chapter needs.

opp0/1/2_o counts opportunities at which a requester was eligible. lost0/1/2_o counts those at which it was eligible and not chosen. maxlost0/1/2_o is the longest consecutive run of them — the number the bounded-losing-run property is about.

None of these is a clock count. They advance only under arb_event_i, so a slave that stalls the bus for twenty clocks contributes nothing to them. That is the separation Chapter 16.2 drew between arbitration wait and slave wait, turned into two different counters.

The reference model is the other half of the module and it is deliberately independent. It keeps its own ref_last_q, recomputes the expected winner from the eligibility vector, and compares. It is not wired to the arbiter's pointer, so an arbiter whose history updates on the wrong event is caught even on the many clocks where it happens to agree.

One implementation detail is a scar. The counters that test more than one requester on the same clock are summed into one assignment rather than written by separate if statements. Two non-blocking assignments to one target keep only the last, and a leak or a loss that hits several requesters at once would have been counted once. Chapter 16.2 shipped that bug in the previous module's probe and it halved a number the checker existed to report.

4. Simulation — SIM F: One Trace, Two Policies

Both policies are driven from the same array, one decision per clock, with the eligibility written out step by step. Nothing about the masters, their duty cycles or the slave's latency enters this experiment — so any difference in the result is the policy and only the policy.

  === SIM F - one trace, two policies ===
    identical eligibility on both, one decision per clock.

    step  CPU DMA   fixed  round robin
      0     1   1     CPU    CPU
      1     1   1     CPU    DMA
      2     1   1     CPU    CPU
      3     1   1     CPU    DMA
      4     1   1     CPU    CPU
      5     1   1     CPU    DMA
      6     1   1     CPU    CPU
      7     1   1     CPU    DMA
      8     1   1     CPU    CPU
      9     1   1     CPU    DMA
     10     1   0     CPU    CPU
     11     1   0     CPU    CPU
     12     1   1     CPU    DMA
     13     1   1     CPU    CPU
     14     0   1     DMA    DMA
     15     1   1     CPU    CPU
     16     1   1     CPU    DMA
     17     1   1     CPU    CPU
     18     1   1     CPU    DMA
     19     1   1     CPU    CPU

    service sequence
      fixed        CCCCCCCCCCCCCCDCCCCC
      round robin  CDCDCDCDCDCCDCDCDCDC

    measure                            fixed  round robin
      grants to CPU                      19        11
      grants to DMA                       1         9
      longest run of contested CPU wins  12         1
      DMA opportunities asked and lost   17         9
      longest run of DMA asking, losing  12         1

    ASSUMPTIONS THIS TRACE MAKES EXPLICIT
      A1 a decision is taken on every step
      A2 the eligibility shown is the eligibility used
      A3 the history is not reset between steps
    Under A1-A3, and on THIS trace, the two-requester
    round-robin policy never lets one requester lose more
    than 1 contested opportunity in a row.

Reading it

The two service sequences are the result, and they should be read as strings.

fixed        CCCCCCCCCCCCCCDCCCCC
round robin  CDCDCDCDCDCCDCDCDCDC

The DMA appears once in the first string. Step 14 — the only step at which the CPU was not asking. Fixed priority did not choose the DMA even once while the CPU was eligible, across eighteen opportunities.

The second string alternates, and its two irregularities are both correct. CC at steps 10–11 is the DMA not asking. The D at 14 is the CPU not asking. Everywhere both were eligible, the preference moved.

Now the measurements, in the only units that mean anything here.

The bottom row is the property. Under fixed priority the DMA was eligible and denied twelve times consecutively. Under round robin, once. The bound for two requesters is one, and the trace agrees with it.

The trace agreeing with the bound is not the same as the bound being proved. This is one 20-step trace. The bound comes from the structure of the scan — the preference cannot return to a requester without passing the others — and it holds only under A1 to A4. The trace is a check on the implementation, not a proof of the policy.

And notice what round robin did not deliver: 11 against 9, not 10 against 10. Equal grants were never the property. What the policy provides — under A1 to A4, for two requesters — is that no requester is preferred twice in a row among those asking, and at steps 10, 11 and 14 one of them was not asking. A policy claim that survives a trace with departures is worth more than one that only holds when everybody is present.

5. Fairness Is Not Equal Bandwidth

This is the distinction that causes the most expensive misunderstandings, and the arithmetic makes it obvious once stated.

A grant buys a tenure. A tenure is not a fixed amount of work.

So the chain of implications people assume is false at every link:

equal grants ⇏ equal cycles ⇏ equal transfers ⇏ equal bytes ⇏ equal bandwidth

Round robin equalises the first term only. It is a policy about opportunities to own, and it has no view whatsoever on what a requester does with one. A master that holds one tenure for forty clocks and a master that holds one for three have been treated identically by the arbiter — and any statement about bandwidth requires measuring tenure lengths, which is Module 22's subject and is not measured here.

The practical consequence for a design review: if the requirement is expressed in bandwidth, an arbitration policy alone cannot satisfy it. You also need a bound on tenure length, which is a property of the masters and the release rule rather than of the selector.

6. How to Write a Fairness Claim

A claim worth reviewing has four parts, and dropping any one of them makes it unfalsifiable.

Under A1–A4, this three-requester round-robin policy guarantees that a continuously eligible requester loses at most two consecutive arbitration opportunities.

The policy — three-requester round robin, this scan, this history rule. The property — bounded losing run, not service, not equality. The bound — two, which is NREQ - 1. The assumptions — A1 to A4, each of which can be checked independently of the arbiter.

What that sentence deliberately does not say: nothing about clocks, nothing about bytes, nothing about what happens if a master holds CYC_O forever, and nothing about what a different number of requesters gives you.

Compare it with "the arbiter is fair", which cannot be tested, cannot be reviewed, and cannot be violated.

7. Common Mistakes

"Round robin guarantees fairness."

Why it is incomplete: which property, under which assumptions, for how many requesters? A guarantee with no assumptions attached is either wrong or vacuous. Under A2 alone — an owner that never releases — the policy provides nothing at all.

"Fairness is a Wishbone property."

Why it is wrong: the word does not occur in the specification. Arbitration methodology is the end user's, and so is every property of it.

"Equal grant counts means equal performance."

Why it is wrong: Section 5. A grant is an opportunity to own, and tenures are not equal. Measuring performance is Module 22, and it needs tenure lengths this chapter did not take.

"If the arbiter is fair, nobody can starve."

Why it is wrong: only under the exact definition and assumptions. With A2 violated, every requester but one is denied indefinitely by a perfectly fair selector — because the selector is never consulted. Chapter 17.4 measures this distinction directly.

"Our regression shows a balanced service distribution, so the arbiter is fair."

Why it is dangerous: an aggregate distribution hides consecutive denial. Twelve losses in a row and twelve losses spread out produce the same total. The property is about the run length, so measure the run length.

"Fixed priority is unfair and should not be used."

Why it is wrong: fixed priority encodes a real system statement — one requester's deadline matters more. A display engine that must not miss a scanline and a debug port are not interchangeable. The policy is a choice about what the system values, not an error.

8. Interview Reasoning

"What does 'fair' mean in your arbiter?"

The right answer names a property. "A continuously eligible requester loses at most NREQ - 1 consecutive arbitration opportunities, under these four assumptions" — and then the assumptions. An answer that says "everyone gets a turn" invites the follow-up "within how long?", which is the real question.

"What assumptions does a bounded-wait claim need?"

That the requester keeps asking; that the current owner eventually releases; that an arbitration event follows the release; and that the arbiter's state is not reset in between. The second is not about the arbiter at all, and it is the one that fails.

"Does round robin guarantee equal bandwidth?"

No, and it does not attempt to. It rotates ownership opportunities. Tenure length, phases per tenure, byte selects and slave latency all sit between an opportunity and a byte. Equal bandwidth is a requirement on the masters and the release policy, not on the selector.

"Your arbiter is round robin and a master is still missing its deadline. Where do you look?"

At tenure lengths and at A2 first, not at the policy. If other masters hold long tenures, the victim's opportunities are rare even though it wins every one it gets. Opportunities per unit time is a release-policy property; which requester wins an opportunity is the selector's.

"How would you prove a fairness property rather than observe it?"

Observation gives you a trace; the property comes from the structure. Here: the scan starts one past the history and returns to a requester only after passing the others, so the run length is bounded by NREQ - 1. Then check the implementation against a reference model and check the bound with a counter — which is what this module's negative-control gate does, including validating the checker against a policy that lacks the property.

9. Understanding Check

Round robin gave the CPU 11 grants and the DMA 9 on a trace where both asked at 18 of 20 steps. Is that a failure of the policy?

No. At steps 10 and 11 the DMA was not asking and at step 14 the CPU was not. The property is about consecutive losses while eligible, and that number was 1. Equal counts were never claimed.

A requester holds CYC_O indefinitely. Your arbiter is round robin. What happens to the others?

They wait indefinitely, and the arbiter is blameless. A2 is violated: no arbitration event occurs, so no selection is made. This is a release-policy problem and no selector can fix it.

Your colleague reports "average wait 6 clocks" as evidence of fairness. What is missing?

The unit and the distribution. Clocks include slave latency incurred for other masters; opportunities do not. And an average hides the longest run, which is the only number the property constrains.

Under what circumstance would you deliberately choose a policy with no bound?

When the system's requirement is a ranking, not a bound. If one requester must never be delayed by another, fixed priority states that directly. You then own the consequence for the requester at the other end, which Chapter 17.4 measures.

10. What's Next

A bounded losing run is a property a policy can have. Fixed priority does not have it, and this chapter measured a run of twelve.

What happens when that run has no bound at all — and how is that different from a system that has stopped?

Chapter 17.4 — Starvation takes the measurement to a longer window, separates a long wait from an unbounded one, and separates both from deadlock. It also makes explicit what a finite simulation can and cannot establish about something that by definition never ends.