Starvation

Chapter 17.3 measured a requester losing twelve consecutive opportunities under fixed priority, on a twenty-step trace. A longer window does not make that number smaller.

When does a long wait stop being a long wait?

1. What a Finite Simulation Can and Cannot Establish

Starvation is a claim about all future time. A simulation runs for a finite number of clocks. Those two facts do not meet, and pretending otherwise is the most common dishonesty in an arbitration write-up.

What a trace can do:

• demonstrate the mechanism — show the denial happening, repeatedly, for a reason you can name;
• count — opportunities offered, opportunities taken, longest consecutive run;
• rule out the alternatives — show the requester was eligible, that events occurred, and that the bus was live.

What a trace cannot do: establish that the denial continues forever. No number of clocks does that.

The unbounded part is an argument about the policy, and for fixed priority it is two sentences long: the policy selects the lowest eligible index and records nothing; therefore if a lower index is eligible at every future opportunity, the higher index is selected at none of them. The trace shows the mechanism; the policy is what removes the bound.

This chapter prints those two conclusions separately, and so should any report you write.

2. Simulation — SIM G: The Mechanism, Counted

CPU (index 0) and IO (index 2) both hold permanent work. The DMA (index 1) copies throughout. 240 clocks, fixed priority.

  === SIM G - the fixed-priority starvation mechanism ===
    CPU (index 0) and IO (index 2) both hold permanent work.
    The DMA (index 1) copies throughout. 240 clocks.

    requester   opportunities  won  lost  longest losing run
      CPU              35        35     0            0
      DMA              33        33     0            0
      IO               63         1    62           62

    IO's longest wait in CLOCKS                    249
    arbitration events 81   of which contested 62
    the bus never stopped: shared-bus ACKs         68

    WHAT THIS TRACE SHOWS
      the IO master was eligible at 63 opportunities and was
      chosen at 1 of them. That is a demonstration over a
      finite window, not a proof about all future time.

    WHAT THE POLICY SHOWS
      fixed priority selects the lowest eligible index. The
      IO master is index 2. Nothing in the policy records that
      it has been waiting, so if a lower index is eligible at
      every future opportunity, the IO master is chosen at
      none of them. The trace demonstrates the mechanism; the
      policy is what makes it unbounded.

Reading it

The IO master was eligible at 63 arbitration opportunities and chosen at 1. Its longest run of consecutive denial was 62.

Read the other two rows first, because they are what make this a policy result rather than a busy-bus result. The CPU: 35 opportunities, 35 grants, longest losing run 0. The DMA: 33 opportunities, 33 grants, longest losing run 0. Neither of them ever lost. Every event they were eligible for, they won.

That is fixed priority doing exactly what it says. The IO master is index 2. The CPU is index 0 and the DMA is index 1, and between them they were eligible at almost every event. Nothing in the policy records that the IO master has been waiting, so nothing ever changes.

Two numbers in the same output are the honest boundaries of the claim.

the bus never stopped: shared-bus ACKs 68. Sixty-eight transfers completed during the window. This system is making progress at full rate. Whatever is wrong with it, it is not stopped.

IO's longest wait in CLOCKS 249. That number is larger than the 240-clock window because it includes the configuration phase before it. It is also the wrong number to reason about, and Section 6 says why: it contains every wait state the slave inserted for somebody else. 62 opportunities is the arbiter's contribution; 249 clocks is the arbiter's contribution plus the slave's.

The output separates the two conclusions deliberately. What this trace shows is 63 opportunities and 1 grant — a finite, countable demonstration. What the policy shows is that a policy with no memory of waiting has no mechanism that ends the denial. Neither sentence is derivable from the other, and a report that merges them is claiming a proof it does not have.

3. Simulation — SIM H: The Same Workload, Round Robin

Identical stimulus, identical masters, identical slave, identical 240 clocks. One parameter changed.

  === SIM H - the same workload under round robin ===

    requester   opportunities  won  lost  longest losing run
      CPU              46        25    21            1
      DMA              43        22    21            1
      IO               41        21    20            1

    IO's longest wait in CLOCKS                    9
    arbitration events 81   of which contested 62

    side by side, the IO master only
      policy        grants  longest losing run  longest wait
      fixed             1              62             249
      round robin      21               1               9

    The clock column and the opportunity column say different
    things. A wait in clocks includes every wait state the
    slave inserted for somebody else; a wait in opportunities
    is the arbiter's decision and nothing else.

Reading it

The comparison table at the bottom is the chapter in four numbers.

And look at what round robin cost the other two. Under fixed priority the CPU and DMA lost nothing: 35/35 and 33/33. Under round robin they won 25 of 46 and 22 of 43, with a longest losing run of 1 each. Round robin did not create service for the IO master out of nothing. It took it from the other two, which is the correct and unglamorous description of what a rotating preference does.

That is why "round robin is better" is not a conclusion this module draws. The two policies encode different statements about the system. Fixed priority says one requester's deadline outranks another's, and keeps saying it. Round robin says no requester should be preferred twice in a row. If the CPU in this system had a hard deadline, the round-robin column is the one that breaks it.

One number deserves separate attention: round robin's longest losing run is 1, and the structural bound for three requesters is 2. The trace came in under the bound. That is a check on the implementation, not a tightening of the property — a different arrival pattern reaches 2 and is still correct.

4. Starvation Is Not Deadlock

This distinction is worth an interview question on its own, and the evidence for it is one line of SIM G's output.

the bus never stopped: shared-bus ACKs 68.

That last row is the interesting one. B3 does name deadlock, and it names one specific cause — OBSERVATION 3.35:

If the SLAVE supports the [ERR_O] or [RTY_O] signals, but the MASTER does not support these signals, deadlock may occur.

and it asks the integrator to design against it — RECOMMENDATION 3.10:

Design INTERCON modules to prevent deadlock conditions. One solution to this problem is to include a watchdog timer function that monitors the MASTER's [STB_O] signal, and asserts [ERR_I] or [RTY_I] if the cycle exceeds some pre-defined time limit.

So the specification's only named liveness concern is a signal-support mismatch, and its suggested remedy is a watchdog on STB_O. Neither has anything to do with arbitration, and a watchdog on STB_O would not detect SIM G at all — the IO master's STB_O is asserted the whole time, its cycle never exceeds a limit because its cycle never starts.

The practical consequence is a debugging rule. A stuck master with a busy bus is starvation; a stuck master with a quiet bus is something else. Look at the global termination count before looking at the arbiter.

5. Arbitration Wait Is Not Slave Wait

Two masters can both be "waiting" and be in completely different situations.

A master that OWNS the path and is waiting for ACK_I is in a transaction wait. Its STB_O is asserted, the slave has the request, and Chapter 9.1 is the relevant material. The arbiter has already served it.

A master that is REQUESTING and has not become owner is in an arbitration wait. Its CYC_O is asserted, nothing of it has reached a slave, and Chapter 16.3 established that it cannot tell the difference from the outside. The arbiter has not served it.

From the master's own pins these look identical: CYC_O high, STB_O high, no termination. The distinguishing evidence is the owner.

This is why the probe counts opportunities and the bus monitor counts clocks, and why SIM G prints both. 62 and 249 are different measurements of different things, and only the first is about the arbiter.

6. RTL — The Monitor That Establishes "Not Deadlock"

The claim "the bus never stopped" needs an instrument, and it needs to cover all three masters.

// ─────────────────────────────────────────────────────────────────────────
// wb_arb_bus_mon — Module 16's bus invariants and B3's checkable rules,
// carried forward across THREE masters.
//
// Module 16 shipped two instruments for a two-master system. Reusing them
// unchanged here would leave a blind spot on the third requester: a
// termination leaked to the IO master, or a request context taken from it,
// would not have been counted. A checker with a blind spot is worse than
// no checker, so the checks are restated for three.
//
// LOCAL INVARIANTS (Chapter 16.3) - no rule in B3 states any of these.
//   v_no_owner       a phase presented while nobody owns the path
//   v_nonowner_term  a master saw a termination it did not earn
//   v_context        the shared request fields did not all come from the
//                    owner (RULE 3.60 names the set; keeping the set
//                    together is the interconnect's job and unstated)
//
// SPEC-DERIVED (the only three an arbitration study can check against B3)
//   v_stb_wo_cyc     RULE 3.25 - STB_O presented without CYC_O
//   v_term_wo_cyc    RULE 3.30 - a slave answered with CYC_I negated
//   v_multi_term     RULE 3.45 - more than one of ACK/ERR/RTY at once
//
// There is no rule to check an arbiter against. That is the point.
// ─────────────────────────────────────────────────────────────────────────
module wb_arb_bus_mon #(
  parameter int unsigned AW = 12,
  parameter int unsigned DW = 32,
  parameter int unsigned SW = DW/8
) (
  input  logic          clk_i,
  input  logic          rst_i,
  input  logic          m0_cyc_i, m0_stb_i, m0_we_i,
  input  logic [AW-1:0] m0_adr_i,
  input  logic [DW-1:0] m0_dat_i,
  input  logic [SW-1:0] m0_sel_i,
  input  logic          m0_ack_i, m0_err_i, m0_rty_i,
  input  logic          m1_cyc_i, m1_stb_i, m1_we_i,
  input  logic [AW-1:0] m1_adr_i,
  input  logic [DW-1:0] m1_dat_i,
  input  logic [SW-1:0] m1_sel_i,
  input  logic          m1_ack_i, m1_err_i, m1_rty_i,
  input  logic          m2_cyc_i, m2_stb_i, m2_we_i,
  input  logic [AW-1:0] m2_adr_i,
  input  logic [DW-1:0] m2_dat_i,
  input  logic [SW-1:0] m2_sel_i,
  input  logic          m2_ack_i, m2_err_i, m2_rty_i,
  input  logic          s_cyc_i, s_stb_i, s_we_i,
  input  logic [AW-1:0] s_adr_i,
  input  logic [DW-1:0] s_dat_i,
  input  logic [SW-1:0] s_sel_i,
  input  logic          s_ack_i, s_err_i, s_rty_i,
  input  logic [1:0]    owner_i,
  output int unsigned   v_no_owner_o,
  output int unsigned   v_nonowner_term_o,
  output int unsigned   v_context_o,
  output int unsigned   v_stb_wo_cyc_o,
  output int unsigned   v_term_wo_cyc_o,
  output int unsigned   v_multi_term_o,
  output int unsigned   n_ack_o, n_err_o, n_rty_o
);
  logic t0, t1, t2, s_term;
  assign t0 = m0_ack_i || m0_err_i || m0_rty_i;
  assign t1 = m1_ack_i || m1_err_i || m1_rty_i;
  assign t2 = m2_ack_i || m2_err_i || m2_rty_i;
  assign s_term = s_ack_i || s_err_i || s_rty_i;

  logic [2:0] term3;
  assign term3 = {s_ack_i, s_err_i, s_rty_i};

  logic ctx_bad;
  always_comb begin
    ctx_bad = 1'b0;
    if (s_stb_i) begin
      case (owner_i)
        2'd1: ctx_bad = (s_adr_i != m0_adr_i) || (s_we_i != m0_we_i)
                     || (s_sel_i != m0_sel_i)
                     || (s_we_i && (s_dat_i != m0_dat_i));
        2'd2: ctx_bad = (s_adr_i != m1_adr_i) || (s_we_i != m1_we_i)
                     || (s_sel_i != m1_sel_i)
                     || (s_we_i && (s_dat_i != m1_dat_i));
        2'd3: ctx_bad = (s_adr_i != m2_adr_i) || (s_we_i != m2_we_i)
                     || (s_sel_i != m2_sel_i)
                     || (s_we_i && (s_dat_i != m2_dat_i));
        default: ctx_bad = 1'b0;
      endcase
    end
  end

  always_ff @(posedge clk_i) begin
    if (rst_i) begin
      v_no_owner_o <= 0; v_nonowner_term_o <= 0; v_context_o <= 0;
      v_stb_wo_cyc_o <= 0; v_term_wo_cyc_o <= 0; v_multi_term_o <= 0;
      n_ack_o <= 0; n_err_o <= 0; n_rty_o <= 0;
    end else begin
      if (s_cyc_i && s_stb_i && owner_i == 2'd0)
        v_no_owner_o <= v_no_owner_o + 1;
      // summed, never assigned twice: leaked terminations arrive at every
      // non-owner on the same clock and two assignments would keep one.
      v_nonowner_term_o <= v_nonowner_term_o
        + ((t0 && owner_i != 2'd1) ? 1 : 0)
        + ((t1 && owner_i != 2'd2) ? 1 : 0)
        + ((t2 && owner_i != 2'd3) ? 1 : 0);
      if (ctx_bad) v_context_o <= v_context_o + 1;
      v_stb_wo_cyc_o <= v_stb_wo_cyc_o
        + ((m0_stb_i && !m0_cyc_i) ? 1 : 0)
        + ((m1_stb_i && !m1_cyc_i) ? 1 : 0)
        + ((m2_stb_i && !m2_cyc_i) ? 1 : 0)
        + ((s_stb_i  && !s_cyc_i)  ? 1 : 0);
      if (!s_cyc_i && s_term) v_term_wo_cyc_o <= v_term_wo_cyc_o + 1;
      if (term3 != 3'b000 && term3 != 3'b100 && term3 != 3'b010
          && term3 != 3'b001)
        v_multi_term_o <= v_multi_term_o + 1;
      if (s_ack_i) n_ack_o <= n_ack_o + 1;
      if (s_err_i) n_err_o <= n_err_o + 1;
      if (s_rty_i) n_rty_o <= n_rty_o + 1;
    end
  end
endmodule

Reading it

Three local invariants and three specification rules, restated for three masters.

The termination counters are what Section 4 rests on. n_ack_o, n_err_o and n_rty_o count completions on the shared path, and a non-zero n_ack_o during a denial window is the evidence that separates starvation from deadlock. It is two lines of counter and it answers the most expensive question in the chapter.

The header explains why this module exists rather than reusing Module 16's pair. Those instruments were built for two masters. Wired unchanged into a three-master system they would not have watched the IO master at all — a termination leaked to it, or a request context taken from it, would have gone uncounted. A checker with a blind spot is worse than no checker, because it reports a pass.

Note what is in the spec-derived half and what is not. RULE 3.25, RULE 3.30 and RULE 3.45 are checkable. There is no fourth check, because there is no fourth rule — B3 contains nothing an arbiter can violate. Chapter 17.5 runs this monitor over five arbiters including three broken ones and reports the result.

7. Avoiding It

Four levers, in the order a design review should consider them.

1. Choose a policy with a bound. Round robin's structural bound is NREQ - 1 consecutive losses, under A1–A4 — Chapter 17.3. This is the lever people reach for first and it is only one of four.

2. Bound the tenure. A selection policy is useless if opportunities are rare. If one master holds CYC_O for a hundred clocks, a perfect selector still leaves the others waiting a hundred clocks, and that is a release-policy fix: shorter cycles, a maximum burst length, or a rule that a held cycle yields. Chapter 16.4 measured a master that held it indefinitely, conformantly.

3. Check the assumptions actually hold. A1 to A4 are not decoration. A requester that drops its request between events will be skipped — correctly — and look starved. An arbiter whose state is reset by something else is fixed priority with extra logic.

4. Reduce what is shared. Chapter 16.4 measured four accesses that acquired ownership zero times because they never crossed the interconnect. A requester that does not contend cannot be starved, and this lever costs no arbitration logic at all.

What is deliberately not in this list, because each is a design space rather than a fix and none is built here: priority ageing (a requester's effective priority rises with waiting), weighted or deficit schemes (grants allocated in proportion), request-count limits (a cap on consecutive wins), and quality-of-service classes. All of them are real, all of them cost state and verification, and all of them are still local policy that B3 says nothing about.

8. Common Mistakes

"Starvation means waiting a long time."

Why it is incomplete: a long wait with a bound is a latency problem. Starvation is denial with no mechanism that ends it. The measurement that distinguishes them is the bound, not the magnitude.

"Starvation is deadlock."

Why it is wrong: SIM G's bus completed 68 transfers while one master received one grant. The system was progressing at full rate. Deadlock is nothing completing; B3 names it and attributes it to an ERR/RTY support mismatch, not to arbitration.

"A simulation proved the master starves forever."

Why it is wrong: a finite trace cannot establish an infinite claim. It demonstrates the mechanism and counts the denials; the unboundedness is an argument about the policy. Write the two sentences separately.

"Starvation is a Wishbone protocol error."

Why it is wrong: the word does not appear in the specification, and nothing forbids the condition. Every transfer in SIM G was conformant — RULE 3.25, RULE 3.30 and RULE 3.45 all clean. The starving master's own behaviour was conformant too.

"A watchdog will catch it."

Why it is wrong here: RECOMMENDATION 3.10's watchdog monitors STB_O and fires when a cycle exceeds a time limit. The starved master's cycle never starts. A watchdog aimed at the right thing — time since last grant — would catch it, but that is a different instrument and B3 does not describe it.

"Round robin solves starvation."

Why it is wrong: it bounds the losing run under A1–A4. With A2 violated — an owner that never releases — round robin provides nothing, because no selection is ever made. Selection policy and release policy are orthogonal.

"The victim should time out and report an error."

Why it is a trap: it can, and Chapter 10.4 is the mechanism. But a starved master is not failing — it will complete correctly the moment it is served, exactly as Chapter 16.4's DMA did. A timeout converts a scheduling problem into a spurious failure, and the threshold is a number nobody has justified.

9. Interview Reasoning

"What is starvation, precisely?"

A requester remains eligible and receives no service, with no mechanism in the policy or workload that ends the denial. Not a long wait. The distinguishing feature is the absence of a bound, not the size of the number.

"How is it different from deadlock?"

The system is still progressing. In starvation, other requesters complete transfers at full rate; a bus trace looks healthy. In deadlock nothing completes. Check the global termination count first — it separates them in one number.

"Can a protocol-correct Wishbone system starve a master?"

Yes, and this chapter measured one. Every transfer conformant, every rule clean, one master denied 62 consecutive opportunities. B3 constrains the shape of a transfer and says nothing about who gets to make one.

"How would you prove a lower-priority master can starve under fixed priority?"

Two separate arguments. Demonstrate the mechanism in a trace — eligible at N opportunities, chosen at few — and then argue from the policy that nothing ends it: the selector reads only the eligibility vector, records no history of waiting, so a continuously eligible lower index is selected at no opportunity. The trace alone is not the proof.

"Can an arbiter solve starvation if the current owner never releases CYC_O?"

No, and this is the question that separates people who have built one. No release means no arbitration event, which means no selection. PERMISSION 3.05 permits exactly that master, and the fix is a release policy, not a selector.

"A master is stuck. What do you look at, in order?"

Is the bus busy? If yes, it is not deadlock. Is the stuck master the owner? If yes, it is a slave wait — Module 9. If no, count its lost opportunities. If the count is rising, it is arbitration; if it is zero, the master is not asking and the problem is in the master.

10. Understanding Check

SIM G's bus completed 68 transfers while the IO master received one grant. What do you call this and what do you not call it?

Starvation, not deadlock. The system progressed at full rate; a single requester was denied. A bus trace alone would have looked entirely healthy.

The CPU and DMA both show a longest losing run of 0 in SIM G. What does that tell you?

They never lost an arbitration event they were eligible for. Between them they were eligible at nearly every event, and fixed priority ranks both above the IO master. The victim's run is the mirror of theirs.

Why is 249 clocks the wrong number to quote, and 62 the right one?

249 includes every wait state the slave inserted for other masters. It is a measurement of the whole system. 62 counts only the decisions the arbiter made and did not award to this requester — the arbiter's own contribution.

Your arbiter is round robin and a requester still misses its deadline. Where do you look first?

At tenure lengths, not at the policy. Round robin bounds the number of opportunities lost, not the time between opportunities. If other masters hold long tenures, the victim wins every opportunity it gets and still waits. That is lever 2 in Section 7.

Someone proposes adding priority ageing. What do you ask before agreeing?

What property it is supposed to guarantee, and what it costs. Ageing adds per-requester state, a comparison, and a whole new class of tuning. If the requirement is "a bounded losing run", round robin already provides it for less — ageing earns its place when the requirement is a bound expressed in time rather than in opportunities, which is a different claim needing tenure bounds too.

11. What's Next

Four chapters have described policies, properties and their failure modes, and each has shown one piece of RTL in isolation.

How do those pieces go together so that arbitration stays correct under real transfer timing?

Chapter 17.5 — Arbitration Logic assembles the system: selection separable from ownership, one client stimulus run against both policies with everything downstream identical, an integrated audit across every situation in the module, and a negative-control gate in which three broken arbiters and one correct one are all found perfectly conformant by a specification checker.