Fairness & Starvation

Chapter 10 · Section 10.5 · Arbitration

1. The Engineering Problem

You inherit a memory controller with a four-master arbiter — CPU, DMA, display, debug — and a verification suite that is, on paper, thorough. It drives random request patterns for a million cycles and checks two things every cycle: that grant is one-hot (never two masters granted at once), and that the granted master is the one the arbitration policy names as the winner. It passes. Every assertion is green. The arbiter is functionally correct.

It is also a fixed-priority arbiter, and the CPU is at index 0. When you finally build the system and run a real workload, the display controller — index 2 — drops frames. Trace it and you find the DMA and CPU keep the memory port busy the whole time; the display's requests are asserted for thousands of cycles and never granted. The arbiter did nothing wrong by its own definition: every cycle it granted the highest-priority asserting master, and the highest-priority master was almost always busy. The suite verified that this happened correctly — one-hot, right winner — a million times over. What it never asked was whether the display would ever be served at all.

That gap is the whole subject of this page. Functional correctness is a property of a single cycle — given this request vector and this state, is this grant right? You can check it with a combinational reference model and it will pass on an arbiter that starves half its clients. Fairness is a property of behaviour over time — will a requester that keeps asking eventually be granted, and will the long-run grant counts match the intended shares? No single-cycle check can see it. To catch starvation you must measure the passage of time — how long a request has been waiting — and drive the arbiter into the corner where unfairness actually appears: sustained, adversarial contention where everyone asks at once. This page defines those temporal properties precisely and builds the checkers that catch what the functional suite could not.

   // The functional suite checks two SINGLE-CYCLE properties, every cycle:
   //   (1) one-hot:      $onehot0(grant)             // never two winners
   //   (2) right winner: grant == policy_reference(req, state)
   // A fixed-priority arbiter passes BOTH forever. It is functionally correct.
 
   // What it NEVER checks — a TEMPORAL property spanning many cycles:
   //   (3) bounded wait: if req[i] stays high, grant[i] happens within K cycles.
   //
   // Under sustained load req[0]=req[1]=1 forever, grant is always 4'b0001 or
   // 4'b0010; req[2] (display) asserts for 10,000 cycles and is NEVER granted.
   // No single-cycle assertion fires. The chip hangs in the field.
   //   (the checkers this page builds — a CONTINUOUS-wait counter + max-wait bound)

2. Mental Model

3. Pattern Anatomy

A fairness checker is not part of the arbiter — it is a monitor that wraps around it, watching req and grant every cycle and accumulating temporal state the arbiter itself does not keep. It has four parts, one per property, plus the stimulus discipline that makes them meaningful.

The per-requester continuous-wait counter — the stopwatch. For each requester i there is a counter wait_cnt[i]. The rule is exact and the exactness is the whole point: wait_cnt[i] increments on every cycle that req[i] is high AND grant[i] is low, and resets to 0 only when grant[i] is high (the requester is served). It does not reset when req[i] toggles, drops, or re-asserts — only a grant clears it. This counts continuous ungranted-while-requesting time, which is exactly the quantity a bounded-wait property is about. A counter that instead resets on any req[i] edge measures something else entirely and misses starvation — that is the DebugLab of §7 and the broken/correct contrast of §4b.

The max-wait (bounded-wait) assertion. Alongside each counter is a bound MAX_WAIT — the largest wait the policy promises. Every cycle the checker asserts wait_cnt[i] <= MAX_WAIT; the moment any counter exceeds it, the assertion fires and names the starving requester. For a round-robin arbiter you set MAX_WAIT = N - 1 (its proven bound); the assertion passes. For a fixed-priority arbiter no finite bound survives contention — set any MAX_WAIT and the low-priority counter will blow through it — so the same assertion fires and flags the starvation. This single line is what turns 'it feels unfair' into a hard, reproducible failure.

The grant-count histogram. A per-requester counter grant_count[i] increments each time grant[i] fires. After a long sustained run the checker compares the histogram to the expected shares: for round-robin the counts should be within one of each other (equal shares); for weighted, proportional to the weights. A skewed histogram — one requester with almost all the grants, others near zero — is throughput unfairness, and for a starving requester its bucket is zero. The histogram is checked over a long window on purpose: over a short window the counts are noise (§6).

The work-conservation assertion. A one-line invariant checked every cycle: if any request is active and the resource is free, some grant must be asserted — req != 0 implies grant != 0. This catches the arbiter that idles the resource while work waits (a stalled pointer, a missing wrap-around fallback, a deadlocked handshake). It is cheap and always on.

Why the stimulus must be adversarial. The four measurements above are only as good as the traffic that drives them. Under light, random, low-duty stimulus a fixed-priority arbiter looks fair: the high-priority master is idle often enough that the low-priority ones slip through, every wait counter stays small, and the histogram looks balanced. The starvation is real but latent — it only manifests when the high-priority master is busy enough to lock everyone else out. So a fairness testbench drives the worst case on purpose: every requester asserting continuously (req = all-ones), held for many rounds. That is the condition the field will eventually produce and the only condition under which the wait counters run long enough to expose the bound violation. Comparing the three chapter arbiters under this stimulus is the headline result: fixed priority (10.1) has unbounded wait and starves the low index; round-robin (10.2) has bounded wait <= N-1; weighted (10.3) has bounded, proportional service. The checker distinguishes them not by inspecting their RTL but by watching their stopwatches.

4. Real RTL Implementation

This is the core of the page. We build two things — (a) a reusable fairness checker (a per-requester continuous-wait counter, a max-wait assertion, a grant-count histogram, and a work-conservation check) wrapped around an arbiter under sustained all-active stimulus, shown passing on a round-robin arbiter and failing on a fixed-priority arbiter (parameterized N); and (b) the broken checker vs the correct checker — a wait counter that resets on a req toggle versus one that counts continuous ungranted-while-requesting time — and each is shown in SystemVerilog, Verilog, and VHDL. The arbiter DUTs are the ones from 10.1 and 10.2: both have the interface input [N-1:0] req, output [N-1:0] grant, one-hot grant, parameterized N; this page instantiates them, it does not re-derive them.

Two disciplines run through every block. First, the checker is a clocked monitor — the wait counters and grant counts are registered state updated with non-blocking assignment on the clock, sampling the same req/grant the arbiter presents. Second, the counters use the exact continuous-wait rule — increment while requesting-and-ungranted, reset only on grant — because it is that rule, and only that rule, that measures the quantity a bounded-wait property is about.

4a. The reusable fairness checker — passes round-robin, fails fixed-priority, three ways

The checker instantiates an arbiter, drives it with a sustained all-active request, and runs the four measurements. It is written to bind to either DUT: point it at the round-robin arbiter with MAX_WAIT = N-1 and it passes; point it at the fixed-priority arbiter and the low-priority counter exceeds any MAX_WAIT and it fails, naming the starving requester.

   module fairness_check #(
       parameter int N        = 4,                  // number of requesters
       parameter int MAX_WAIT = N-1,                // bounded-wait promise (RR: N-1)
       parameter int RUN      = 200                 // sustained-load cycles to observe
   )(
       input  logic         clk,
       input  logic         rst,                    // synchronous, active-high
       input  logic [N-1:0] req,                    // what the arbiter sees
       input  logic [N-1:0] grant                   // what the arbiter produced (one-hot)
   );
       // The STOPWATCH: continuous ungranted-while-requesting cycles, per requester.
       int wait_cnt    [N];                         // resets ONLY on a grant to i
       int max_seen    [N];                         // high-water mark, for reporting
       int grant_count [N];                         // the HISTOGRAM bucket per requester
       int errors = 0;
 
       always_ff @(posedge clk) begin
           if (rst) begin
               foreach (wait_cnt[i])    wait_cnt[i]    <= 0;
               foreach (max_seen[i])    max_seen[i]    <= 0;
               foreach (grant_count[i]) grant_count[i] <= 0;
           end else begin
               for (int i = 0; i < N; i++) begin
                   if (grant[i]) begin
                       grant_count[i] <= grant_count[i] + 1;   // HISTOGRAM: served once more
                       wait_cnt[i]    <= 0;                     // STOPWATCH RESET: only on grant
                   end else if (req[i]) begin
                       // requesting AND ungranted this cycle -> keep counting CONTINUOUS wait.
                       wait_cnt[i]    <= wait_cnt[i] + 1;
                       if (wait_cnt[i] + 1 > max_seen[i]) max_seen[i] <= wait_cnt[i] + 1;
                   end
                   // note: req[i] LOW while ungranted does NOT reset wait_cnt here, because
                   // we only advance it when req[i] is high; a requester that stops asking
                   // simply stops its stopwatch. A grant is the ONLY thing that clears it.
               end
           end
       end
 
       // MAX-WAIT ASSERTION (the bounded-wait / no-starvation property). Fires the
       // instant any requester's continuous wait exceeds the promised bound.
       always_ff @(posedge clk) if (!rst) begin
           for (int i = 0; i < N; i++)
               assert (wait_cnt[i] <= MAX_WAIT)
                   else begin
                       $error("FAIL: starvation - req %0d waited %0d cycles > MAX_WAIT=%0d",
                              i, wait_cnt[i], MAX_WAIT);
                       errors++;
                   end
       end
 
       // WORK CONSERVATION: any active request must produce some grant this cycle.
       always_ff @(posedge clk) if (!rst)
           assert (!(|req) || (|grant))
               else begin $error("FAIL: work-conservation - req=%b but grant=0", req); errors++; end
   endmodule

The clocked testbench is where the headline result lives. It drives all requesters always active for the whole run, then checks the histogram for balance. Binding the checker to the round-robin arbiter passes on every property; binding it to the fixed-priority arbiter makes the max-wait assertion fire and leaves the low-priority histogram buckets at zero.

   module fairness_check_tb;
       localparam int N        = 4;
       localparam int RUN      = 200;
       localparam int MAX_WAIT = N-1;               // round-robin promise
       logic         clk = 1'b0, rst;
       logic [N-1:0] req, grant;
 
       // Swap the DUT to switch the result:
       //   rr_arbiter  -> PASS (bounded wait <= N-1, balanced histogram)
       //   fp_arbiter  -> FAIL (req 2,3 starve; max-wait assertion fires; buckets 0)
       rr_arbiter #(.N(N)) dut (.clk(clk), .rst(rst), .req(req), .grant(grant));
 
       // The checker binds to the SAME req/grant the arbiter sees.
       fairness_check #(.N(N), .MAX_WAIT(MAX_WAIT), .RUN(RUN)) chk
           (.clk(clk), .rst(rst), .req(req), .grant(grant));
 
       always #5 clk = ~clk;
 
       initial begin
           rst = 1'b1; req = '0;
           @(posedge clk); #1; rst = 1'b0;
 
           // ADVERSARIAL SUSTAINED STIMULUS: every requester asks, every cycle, for
           // the whole run. This is the ONLY stimulus under which starvation appears.
           req = '1;
           repeat (RUN) @(posedge clk);
 
           // THROUGHPUT FAIRNESS: after a long sustained run under round-robin every
           // bucket should be within one grant of the others (equal shares). Under
           // fixed priority, req[0] hoards them and req[2],req[3] read ZERO.
           begin
               int lo = chk.grant_count[0], hi = chk.grant_count[0];
               for (int i = 1; i < N; i++) begin
                   if (chk.grant_count[i] < lo) lo = chk.grant_count[i];
                   if (chk.grant_count[i] > hi) hi = chk.grant_count[i];
               end
               assert ((hi - lo) <= 1)
                   else $error("FAIL: histogram skew - shares span %0d..%0d (unfair)", lo, hi);
           end
 
           if (chk.errors == 0) $display("PASS: bounded wait <= %0d, work-conserving, balanced histogram", MAX_WAIT);
           else                 $display("FAIL: %0d fairness violations (starvation detected)", chk.errors);
           $finish;
       end
   endmodule

The Verilog checker is identical in intent; the differences are reg/integer typing, per-requester counters as arrays, and the self-check spelled as if (wait_cnt > MAX_WAIT) $display("FAIL...") instead of assert. The continuous-wait rule — increment while requesting-and-ungranted, reset only on grant — is the same.

   module fairness_check #(
       parameter N        = 4,
       parameter MAX_WAIT = 3,                       // = N-1 for round-robin; set by TB
       parameter RUN      = 200
   )(
       input  wire         clk,
       input  wire         rst,                      // synchronous, active-high
       input  wire [N-1:0] req,
       input  wire [N-1:0] grant
   );
       integer wait_cnt    [0:N-1];                  // continuous ungranted-while-requesting
       integer grant_count [0:N-1];                  // histogram bucket
       integer errors;
       integer i;
 
       initial errors = 0;
 
       always @(posedge clk) begin
           if (rst) begin
               for (i = 0; i < N; i = i + 1) begin
                   wait_cnt[i]    <= 0;
                   grant_count[i] <= 0;
               end
           end else begin
               for (i = 0; i < N; i = i + 1) begin
                   if (grant[i]) begin
                       grant_count[i] <= grant_count[i] + 1;    // served -> histogram++
                       wait_cnt[i]    <= 0;                      // RESET only on a grant
                   end else if (req[i]) begin
                       wait_cnt[i]    <= wait_cnt[i] + 1;        // continuous ungranted wait
                   end
               end
           end
       end
 
       // MAX-WAIT self-check: print FAIL the instant continuous wait exceeds the bound.
       // (Sampled AFTER the counter update, so it reads the just-incremented value.)
       always @(posedge clk) if (!rst) begin
           for (i = 0; i < N; i = i + 1)
               if (wait_cnt[i] > MAX_WAIT) begin
                   $display("FAIL: starvation - req %0d waited %0d > MAX_WAIT=%0d", i, wait_cnt[i], MAX_WAIT);
                   errors = errors + 1;
               end
           // WORK CONSERVATION: any request but no grant is a stalled resource.
           if ((|req) && !(|grant)) begin
               $display("FAIL: work-conservation - req=%b grant=0", req);
               errors = errors + 1;
           end
       end
   endmodule

   module fairness_check_tb;
       parameter N        = 4;
       parameter PW       = 2;
       parameter MAX_WAIT = 3;                       // N-1
       parameter RUN      = 200;
       reg          clk, rst;
       reg  [N-1:0] req;
       wire [N-1:0] grant;
       integer      i, lo, hi;
 
       // rr_arbiter -> PASS; fp_arbiter (fixed priority) -> FAIL (req 2,3 starve).
       rr_arbiter #(.N(N), .PW(PW)) dut (.clk(clk), .rst(rst), .req(req), .grant(grant));
 
       fairness_check #(.N(N), .MAX_WAIT(MAX_WAIT), .RUN(RUN)) chk
           (.clk(clk), .rst(rst), .req(req), .grant(grant));
 
       initial clk = 1'b0;
       always #5 clk = ~clk;
 
       initial begin
           rst = 1'b1; req = {N{1'b0}};
           @(posedge clk); #1; rst = 1'b0;
 
           // ADVERSARIAL SUSTAINED STIMULUS: all requesters assert for the whole run.
           req = {N{1'b1}};
           repeat (RUN) @(posedge clk);
 
           // THROUGHPUT FAIRNESS: histogram spread must be <= 1 under round-robin.
           lo = chk.grant_count[0]; hi = chk.grant_count[0];
           for (i = 1; i < N; i = i + 1) begin
               if (chk.grant_count[i] < lo) lo = chk.grant_count[i];
               if (chk.grant_count[i] > hi) hi = chk.grant_count[i];
           end
           if ((hi - lo) > 1) begin
               $display("FAIL: histogram skew - shares span %0d..%0d (unfair)", lo, hi);
               chk.errors = chk.errors + 1;
           end
 
           if (chk.errors == 0) $display("PASS: bounded wait, work-conserving, balanced histogram");
           else                 $display("FAIL: %0d fairness violations (starvation)", chk.errors);
           $finish;
       end
   endmodule

In VHDL the checker uses numeric_std: the wait counters and histogram buckets are integer arrays updated in a clocked process, and the self-check is assert ... report ... severity error. The continuous-wait rule is expressed exactly the same way — increment on requesting-and-ungranted, reset only on a grant.

   library ieee;
   use ieee.std_logic_1164.all;
   use ieee.numeric_std.all;
 
   entity fairness_check is
       generic (
           N        : positive := 4;
           MAX_WAIT : natural  := 3                            -- = N-1 for round-robin
       );
       port (
           clk   : in std_logic;
           rst   : in std_logic;                              -- synchronous, active-high
           req   : in std_logic_vector(N-1 downto 0);
           grant : in std_logic_vector(N-1 downto 0)
       );
   end entity;
 
   architecture check of fairness_check is
       type int_arr is array (0 to N-1) of integer;
   begin
       monitor : process (clk)
           variable wait_cnt    : int_arr := (others => 0);   -- continuous ungranted wait
           variable grant_count : int_arr := (others => 0);   -- histogram bucket
       begin
           if rising_edge(clk) then
               if rst = '1' then
                   wait_cnt    := (others => 0);
                   grant_count := (others => 0);
               else
                   for i in 0 to N-1 loop
                       if grant(i) = '1' then
                           grant_count(i) := grant_count(i) + 1;   -- served -> histogram++
                           wait_cnt(i)    := 0;                     -- RESET only on grant
                       elsif req(i) = '1' then
                           wait_cnt(i)    := wait_cnt(i) + 1;       -- continuous ungranted wait
                       end if;
                       -- MAX-WAIT ASSERTION: fire on the first bound violation.
                       assert wait_cnt(i) <= MAX_WAIT
                           report "FAIL: starvation - a requester exceeded MAX_WAIT" severity error;
                   end loop;
                   -- WORK CONSERVATION: any request must produce some grant.
                   assert (req = (req'range => '0')) or (grant /= (grant'range => '0'))
                       report "FAIL: work-conservation - req active but grant = 0" severity error;
               end if;
           end if;
       end process;
   end architecture;

   library ieee;
   use ieee.std_logic_1164.all;
   use ieee.numeric_std.all;
 
   entity fairness_check_tb is
   end entity;
 
   architecture sim of fairness_check_tb is
       constant N        : positive := 4;
       constant MAX_WAIT : natural  := 3;                     -- N-1
       constant RUN      : natural  := 200;
       signal clk   : std_logic := '0';
       signal rst   : std_logic;
       signal req   : std_logic_vector(N-1 downto 0);
       signal grant : std_logic_vector(N-1 downto 0);
   begin
       -- Bind rr_arbiter to PASS; bind fp_arbiter (fixed priority) to FAIL.
       dut : entity work.rr_arbiter
           generic map (N => N)
           port map (clk => clk, rst => rst, req => req, grant => grant);
 
       chk : entity work.fairness_check
           generic map (N => N, MAX_WAIT => MAX_WAIT)
           port map (clk => clk, rst => rst, req => req, grant => grant);
 
       clk <= not clk after 5 ns;
 
       stim : process
       begin
           rst <= '1'; req <= (others => '0');
           wait until rising_edge(clk); wait for 1 ns; rst <= '0';
 
           -- ADVERSARIAL SUSTAINED STIMULUS: every requester asserts for the whole run.
           req <= (others => '1');
           for c in 0 to RUN-1 loop
               wait until rising_edge(clk);
           end loop;
 
           report "fairness_check run complete (any severity-error above = starvation)" severity note;
           wait;
       end process;
   end architecture;

4b. The broken checker vs the correct checker — reset-on-toggle vs continuous wait

The most dangerous failure on this page is not a broken arbiter — it is a broken checker that passes a broken arbiter. The signature broken checker resets its wait counter whenever req[i] toggles (any edge on the request line) instead of only when the requester is granted. Under light, bursty stimulus a low-priority request naturally drops for a cycle now and then; each drop resets the counter, so it never accumulates enough continuous wait to reach the bound — even while the requester is being starved. Here is the broken counter beside the correct one, in each language.

   // BROKEN: wait_cnt resets on ANY change of req[i]. A requester whose req blinks
   //         (light/bursty traffic) keeps resetting its own stopwatch and NEVER
   //         reaches MAX_WAIT even while it is being starved. The checker passes a
   //         starving arbiter -> false confidence.
   module wait_cnt_bad #(parameter int N = 4)(
       input  logic clk, rst,
       input  logic [N-1:0] req, grant,
       output int   wait_cnt [N]
   );
       logic [N-1:0] req_q;                          // previous req, to detect toggles
       always_ff @(posedge clk) begin
           req_q <= req;
           for (int i = 0; i < N; i++) begin
               if (rst)                    wait_cnt[i] <= 0;
               else if (req[i] != req_q[i]) wait_cnt[i] <= 0;   // BUG: reset on TOGGLE
               else if (req[i] && !grant[i]) wait_cnt[i] <= wait_cnt[i] + 1;
           end
       end
   endmodule
 
   // CORRECT: wait_cnt resets ONLY on a grant to i. It measures CONTINUOUS
   //          ungranted-while-requesting time, which is exactly the bounded-wait
   //          quantity -> a starved requester's counter climbs past MAX_WAIT.
   module wait_cnt_good #(parameter int N = 4)(
       input  logic clk, rst,
       input  logic [N-1:0] req, grant,
       output int   wait_cnt [N]
   );
       always_ff @(posedge clk)
           for (int i = 0; i < N; i++) begin
               if (rst)              wait_cnt[i] <= 0;
               else if (grant[i])    wait_cnt[i] <= 0;                  // reset ONLY on grant
               else if (req[i])      wait_cnt[i] <= wait_cnt[i] + 1;    // continuous wait
           end
   endmodule

   module wait_bug_tb;
       localparam int N = 4;
       logic         clk = 1'b0, rst;
       logic [N-1:0] req, grant;
       int           wc_bad [N], wc_good [N];
       int           errors = 0;
 
       // A fixed-priority arbiter: req[0] hoards; req[3] is starved under contention.
       fp_arbiter #(.N(N)) dut (.clk(clk), .rst(rst), .req(req), .grant(grant));
 
       wait_cnt_bad  #(.N(N)) bad  (.clk(clk), .rst(rst), .req(req), .grant(grant), .wait_cnt(wc_bad));
       wait_cnt_good #(.N(N)) good (.clk(clk), .rst(rst), .req(req), .grant(grant), .wait_cnt(wc_good));
 
       always #5 clk = ~clk;
 
       initial begin
           rst = 1'b1; req = '0; @(posedge clk); #1; rst = 1'b0;
           // req[0],req[1] hammer; req[3] asks but BLINKS every few cycles (bursty).
           for (int c = 0; c < 60; c++) begin
               req[0] = 1'b1; req[1] = 1'b1; req[2] = 1'b0;
               req[3] = (c % 5 != 0);                 // drops one cycle in five -> toggles
               @(posedge clk); #1;
           end
           // The BAD counter for req[3] keeps resetting on the blink -> stays small,
           // reports 'fair'. The GOOD counter sees continuous ungranted time -> large.
           assert (wc_good[3] > N-1)
               else begin $error("correct counter should show req 3 starving"); errors++; end
           if (wc_bad[3] <= N-1)
               $display("PASS: broken counter (wc_bad[3]=%0d) HID starvation the correct one (wc_good[3]=%0d) caught",
                        wc_bad[3], wc_good[3]);
           else
               $display("note: stimulus did not trigger the reset-on-toggle blind spot");
           if (errors == 0) $display("PASS: continuous-wait counter exposes starvation reset-on-toggle misses");
           else             $display("FAIL: %0d errors", errors);
           $finish;
       end
   endmodule

The Verilog contrast is the same story with reg/integer state and a stored req_q to detect the toggle. The one-line difference — reset on req[i] != req_q[i] versus reset on grant[i] — is the whole bug.

   // BROKEN: reset on any req toggle -> bursty traffic hides starvation.
   module wait_cnt_bad #(parameter N = 4)(
       input  wire clk, rst,
       input  wire [N-1:0] req, grant,
       output reg  [31:0]  wait0, wait3            // expose two buckets for the TB
   );
       reg [N-1:0] req_q;
       always @(posedge clk) begin
           req_q <= req;
           if (rst) begin wait0 <= 0; wait3 <= 0; end
           else begin
               if (req[0] != req_q[0])       wait0 <= 0;              // BUG: reset on toggle
               else if (req[0] && !grant[0]) wait0 <= wait0 + 1;
               if (req[3] != req_q[3])       wait3 <= 0;              // BUG: reset on toggle
               else if (req[3] && !grant[3]) wait3 <= wait3 + 1;
           end
       end
   endmodule
 
   // CORRECT: reset ONLY on a grant -> continuous ungranted wait climbs past the bound.
   module wait_cnt_good #(parameter N = 4)(
       input  wire clk, rst,
       input  wire [N-1:0] req, grant,
       output reg  [31:0]  wait0, wait3
   );
       always @(posedge clk) begin
           if (rst) begin wait0 <= 0; wait3 <= 0; end
           else begin
               if (grant[0])      wait0 <= 0;             // reset ONLY on grant
               else if (req[0])   wait0 <= wait0 + 1;     // continuous wait
               if (grant[3])      wait3 <= 0;
               else if (req[3])   wait3 <= wait3 + 1;
           end
       end
   endmodule

   module wait_bug_tb;
       parameter N = 4;
       reg          clk, rst;
       reg  [N-1:0] req;
       wire [N-1:0] grant;
       wire [31:0]  wc_bad0, wc_bad3, wc_good0, wc_good3;
       integer      c, errors;
 
       fp_arbiter #(.N(N)) dut (.clk(clk), .rst(rst), .req(req), .grant(grant));
 
       wait_cnt_bad  #(.N(N)) bad  (.clk(clk), .rst(rst), .req(req), .grant(grant),
                                    .wait0(wc_bad0),  .wait3(wc_bad3));
       wait_cnt_good #(.N(N)) good (.clk(clk), .rst(rst), .req(req), .grant(grant),
                                    .wait0(wc_good0), .wait3(wc_good3));
 
       initial clk = 1'b0;
       always #5 clk = ~clk;
 
       initial begin
           errors = 0;
           rst = 1'b1; req = {N{1'b0}}; @(posedge clk); #1; rst = 1'b0;
           for (c = 0; c < 60; c = c + 1) begin
               req[0] = 1'b1; req[1] = 1'b1; req[2] = 1'b0;
               req[3] = (c % 5 != 0);                 // req[3] blinks -> toggles
               @(posedge clk); #1;
           end
           // Correct counter must show req[3] starving (well past N-1); bad one must not.
           if (wc_good3 <= N-1) begin
               $display("FAIL: correct counter missed starvation wc_good3=%0d", wc_good3);
               errors = errors + 1;
           end
           if (wc_bad3 <= N-1)
               $display("PASS: reset-on-toggle counter HID starvation (bad=%0d) that continuous-wait caught (good=%0d)",
                        wc_bad3, wc_good3);
           if (errors == 0) $display("PASS: continuous-wait counter exposes what reset-on-toggle misses");
           else             $display("FAIL: %0d errors", errors);
           $finish;
       end
   endmodule

In VHDL the same contrast uses a stored req_q signal and two integer counters. Resetting on req(i) /= req_q(i) is the broken rule; resetting only on grant(i) = '1' is the correct one.

   library ieee;
   use ieee.std_logic_1164.all;
   use ieee.numeric_std.all;
 
   -- BROKEN: resets on any req(3) toggle -> a blinking (bursty) request keeps
   --         clearing its own stopwatch and never reaches the bound while starving.
   entity wait_cnt_bad is
       port ( clk, rst : in std_logic;
              req, grant : in std_logic_vector(3 downto 0);
              wait3      : out integer );
   end entity;
   architecture check of wait_cnt_bad is
   begin
       process (clk)
           variable w   : integer := 0;
           variable rq  : std_logic := '0';         -- previous req(3)
       begin
           if rising_edge(clk) then
               if rst = '1' then
                   w := 0;
               elsif req(3) /= rq then
                   w := 0;                           -- BUG: reset on TOGGLE
               elsif (req(3) = '1') and (grant(3) = '0') then
                   w := w + 1;
               end if;
               rq := req(3);
               wait3 <= w;
           end if;
       end process;
   end architecture;
 
   -- CORRECT: resets ONLY on a grant -> continuous ungranted wait climbs past MAX_WAIT.
   entity wait_cnt_good is
       port ( clk, rst : in std_logic;
              req, grant : in std_logic_vector(3 downto 0);
              wait3      : out integer );
   end entity;
   architecture check of wait_cnt_good is
   begin
       process (clk)
           variable w : integer := 0;
       begin
           if rising_edge(clk) then
               if rst = '1' then           w := 0;
               elsif grant(3) = '1' then   w := 0;           -- reset ONLY on grant
               elsif req(3) = '1' then     w := w + 1;       -- continuous ungranted wait
               end if;
               wait3 <= w;
           end if;
       end process;
   end architecture;

   library ieee;
   use ieee.std_logic_1164.all;
   use ieee.numeric_std.all;
 
   entity wait_bug_tb is
   end entity;
 
   architecture sim of wait_bug_tb is
       constant N : positive := 4;
       signal clk   : std_logic := '0';
       signal rst   : std_logic;
       signal req   : std_logic_vector(N-1 downto 0);
       signal grant : std_logic_vector(N-1 downto 0);
       signal wbad3, wgood3 : integer;
   begin
       dut : entity work.fp_arbiter
           generic map (N => N)
           port map (clk => clk, rst => rst, req => req, grant => grant);
 
       bad  : entity work.wait_cnt_bad
           port map (clk => clk, rst => rst, req => req, grant => grant, wait3 => wbad3);
       good : entity work.wait_cnt_good
           port map (clk => clk, rst => rst, req => req, grant => grant, wait3 => wgood3);
 
       clk <= not clk after 5 ns;
 
       stim : process
       begin
           rst <= '1'; req <= (others => '0');
           wait until rising_edge(clk); wait for 1 ns; rst <= '0';
           for c in 0 to 59 loop
               req(0) <= '1'; req(1) <= '1'; req(2) <= '0';
               if (c mod 5) = 0 then req(3) <= '0'; else req(3) <= '1'; end if;  -- blink
               wait until rising_edge(clk); wait for 1 ns;
           end loop;
           -- The correct counter must show req(3) starving; the broken one stays small.
           assert wgood3 > N-1
               report "correct continuous-wait counter should show req 3 starving" severity error;
           assert wbad3 <= N-1
               report "note: bursty stimulus did not exercise the reset-on-toggle blind spot" severity note;
           report "wait_bug self-check complete: continuous-wait exposes reset-on-toggle blind spot" severity note;
           wait;
       end process;
   end architecture;

Across all three languages the lesson is one sentence: a wait counter must reset on a GRANT and nothing else — reset it on a request edge and it measures the wrong thing and lets starvation pass.

5. Verification Strategy

Fairness verification is different in kind from functional verification, and the difference is the whole methodology. A functional check evaluates a single cycle against a reference; a fairness check evaluates behaviour accumulated over time under the worst-case stimulus. The strategy has four moving parts, and they map directly onto §4's checker.

• Drive worst-case sustained contention, not random light traffic. The single most important decision is the stimulus. Random, low-duty requests hide starvation because the high-priority masters are idle often enough to let everyone through. So the fairness testbench asserts every requester continuously (req = all-ones) and holds it for many rounds — the adversarial corner the field will eventually reach. Only under this stimulus do the wait counters run long enough to expose a bound violation. A fairness suite that uses the same stimulus as the functional suite is a fairness suite in name only.
• Measure continuous wait with a self-checking counter + max-wait assertion. For each requester, a registered counter increments while it is requesting-and-ungranted and resets only on a grant; a wait_cnt[i] <= MAX_WAIT assertion fires the instant any counter exceeds the promised bound and names the starving requester. This is the liveness property made checkable: 'a continuously-asserted request is eventually granted, within MAX_WAIT cycles.' The bound is the policy's promise — N-1 for round-robin, proportional-plus-margin for weighted, and no finite bound for fixed priority, which is exactly why fixed priority fails the assertion.
• Check the throughput histogram over a long window. A per-requester grant count, compared after the run to the expected shares: within one for round-robin, proportional for weighted, and — the tell — a zero bucket for a starved requester. The window must be long: over a few cycles the counts are noise, and a short-window histogram can look 'unfair' on a perfectly fair arbiter or 'fair' on a starving one. Length is what turns the histogram from noise into a share.
• Assert work conservation continuously. The one-line invariant req != 0 implies grant != 0 (when the resource is free) runs every cycle and catches the arbiter that idles the resource while work waits — a stalled pointer, a missing wrap-around fallback, a deadlocked handshake. It is cheap, always on, and complementary: no-starvation says each requester is eventually served; work-conservation says the resource is never wasted.

Two more angles complete the picture. The same-checker-two-arbiters result is the proof. Point the §4 checker at the round-robin arbiter and every property passes (MAX_WAIT = N-1); point it, unchanged, at the fixed-priority arbiter and the max-wait assertion fires with the low-priority requester named and its histogram bucket at zero. That the identical checker distinguishes them — without inspecting their internals — is the evidence that fairness is a black-box temporal property, not an RTL-review opinion. And the formal / assertion-based angle is worth naming: bounded wait is a liveness property — 'eventually granted' — and liveness is precisely what formal property checking (a bounded-wait SVA s_eventually, or a model-checker liveness proof) verifies exhaustively, without you having to find the adversarial stimulus. Full SVA and formal are a later track; the counter-plus-assertion here is the simulation-scoped version of the same idea, and it is enough to catch the bug that ships.

6. Common Mistakes

Testing fairness with light or random traffic only. The most common and most costly mistake. Starvation only appears under sustained contention — when the high-priority master is busy enough to lock the others out. Random, low-duty stimulus leaves the resource idle often enough that even a fixed-priority arbiter serves everyone, so the wait counters stay small and the suite passes. The bug is real but latent, and it surfaces in the field under exactly the load the testbench never drove. Fairness needs adversarial stimulus: every requester asserting continuously.

A wait counter that resets on request re-assertion instead of continuous ungranted time. The signature broken checker (§7, §4b). If the counter resets whenever req[i] toggles — drops and re-asserts — rather than only when the requester is granted, it measures 'time since the last request edge,' not 'time waiting for a grant.' A bursty requester that blinks its request keeps resetting its own stopwatch and never reaches the bound, even while it is being starved. The checker gives false confidence: it passes a starving arbiter. Reset on grant, and only on grant.

Checking grant counts over too short a window. The histogram is a long-run statistic. Over a handful of cycles, grant counts are noise — a fair round-robin arbiter mid-rotation shows an uneven histogram, and a starving arbiter can briefly look balanced. Comparing shares over a short window produces both false alarms and missed bugs. Run the sustained load for many rounds (>> N grants) before reading the histogram, so the counts are shares and not sampling noise.

Confusing functional correctness with fairness. The framing error the whole page exists to correct. 'The grant is one-hot and it is the right winner' is a single-cycle property; it can be true on every cycle of a run in which a requester is never served. Passing the functional suite says nothing about fairness. They are orthogonal checks — one about this grant, one about bounded wait over time — and an arbiter must pass both. Treating a green functional suite as evidence of fairness is how starvation ships.

Asserting a bound the policy does not actually promise. The max-wait assertion is only meaningful with the right MAX_WAIT. Set it too low for round-robin (below N-1) and it false-fails on a correct arbiter; set it to some large finite number for fixed priority and you have merely deferred the failure, not characterized it (fixed priority's wait is unbounded, so any finite bound is eventually exceeded — the correct 'bound' for fixed priority is 'none exists,' which is itself the finding). Match the bound to the policy's actual guarantee.

Forgetting work conservation — a starvation-free arbiter that serves no one. An arbiter that grants nobody has no requester waiting longer than any other, so a naive per-requester wait check can pass while the resource sits idle and every requester stalls equally. The work-conservation invariant (req != 0 implies grant != 0) is what closes this hole: no-starvation and work-conservation together say both 'each requester is eventually served' and 'the resource is never wasted.' Check both.

7. DebugLab

The engineering lesson: fairness is a temporal, liveness property — you must measure continuous ungranted wait under adversarial sustained load, because a functionally-correct arbiter can still starve a requester and a sloppy fairness checker gives false confidence. Two failures compounded here: a checker that reset its stopwatch on the wrong event (a request edge, not a grant) so it measured the wrong quantity, and a stimulus that never created contention so the quantity never grew. Either alone hides starvation; together they produce the worst outcome in verification — a green check on a broken behaviour. The habits that make it impossible are identical across SystemVerilog, Verilog, and VHDL: reset the wait counter only on a grant so it measures continuous ungranted time, and drive every requester continuously so the counter has the contention it needs to expose the bound — then the same check that passed round-robin fails fixed priority, and the starvation shows up on the bench instead of in the field.

8. Interview Q&A

9. Exercises

Design and reasoning exercises — no syntax drills. Each rehearses the 'measure the temporal property under adversarial load' habit.

Exercise 1 — Classify the property

For each check, say whether it is a functional (single-cycle) property or a fairness (temporal) property, and if fairness, which of the three (bounded wait / work conservation / throughput share): (a) grant is always one-hot; (b) a continuously-asserted req[i] is granted within N-1 cycles; (c) whenever req != 0 the arbiter asserts some grant; (d) over 10,000 cycles each requester wins within one grant of the others; (e) the granted master is the one the policy names. Then state which of (a)–(e) a fixed-priority arbiter passes and which it fails under sustained all-active load.

Exercise 2 — Break the checker on paper

The continuous-wait counter must reset only on a grant. Describe precisely what quantity the counter measures if you instead reset it (i) on any req[i] toggle, (ii) on req[i] going low, and (iii) never (only ever incrementing). For each, give a stimulus under which a genuinely starving requester's counter fails to cross MAX_WAIT — i.e. the broken checker reports a false pass — and explain why the grant-reset version does not have that blind spot.

Exercise 3 — Pick the bound

You are writing the max-wait assertion for three arbiters under N = 8 requesters, all asserting continuously: a round-robin arbiter, a weighted arbiter with weights [4,2,1,1,1,1,1,1], and a fixed-priority arbiter. State the correct MAX_WAIT for each (or 'none exists,' with justification). For the weighted case, reason about the worst-case wait of the lowest-weight requester in one full round, and explain why a single scalar bound is a coarser check for weighted than for round-robin.

Exercise 4 — Design the fairness regression

You must sign off fairness on a 4-master arbiter. Design the regression: (i) the stimulus phase(s) that create genuine contention (and why random per-master traffic is insufficient); (ii) the exact reset/increment rule for the wait counters and the bound you assert; (iii) how long you run before reading the grant histogram and what balance criterion you apply; (iv) the work-conservation invariant; and (v) how you would run the same regression against both a round-robin and a fixed-priority implementation to demonstrate the checker distinguishes them. State the expected PASS/FAIL for each implementation.

10. Related Tutorials

Continue in RTL Design Patterns (sibling links unlock as they ship):

• Round-Robin Arbiters — Chapter 10.2; the arbiter this checker passes — its rotating pointer gives the bounded wait <= N-1 the max-wait assertion confirms.
• Fixed-Priority Arbiters — Chapter 10.1; the arbiter this checker fails — functionally correct, one-hot, and yet unbounded wait under contention.
• Weighted & LRU Arbiters — Chapter 10.3; where throughput fairness becomes proportional shares, and the histogram check is compared to weights instead of an equal split.
• Request/Grant Handshake — Chapter 10.4 (sibling, this batch); the transaction-level protocol whose fairness this page's checker measures.

Backward / method:

• FIFO Verification — Chapter 7; the sibling verification-methodology page — a self-checking monitor (a shadow queue) that catches what directed tests miss, exactly as the fairness monitor here does.
• valid/ready Handshake — Chapter 9.1; the handshake whose liveness ('valid must eventually be accepted') is the same kind of temporal property as bounded wait.
• Handshake Bugs — Chapter 9; deadlock and stall — the liveness failures a handshake's own version of this checker must catch.
• The RTL Design Mindset — Chapter 0.2; the Verification lens applied here to a property no single-cycle model can express.
• What Is an RTL Design Pattern? — Chapter 0.1; why a pattern includes its signature failure — here, the starvation a broken check lets pass.

Verilog v1 prerequisites (the grammar the checker transcribes into):

• Testbench Creation Techniques — the self-checking clocked testbench discipline the fairness monitor is built on.
• Blocking and Non-Blocking Assignments — why the registered wait counters and histogram use <= on the clock, and the grant/req comparisons use =.
• If-Else Statements — the priority of the reset/grant/request branches in the wait-counter update.
• Case Statements — the construct behind per-requester bookkeeping and the arbiter policies this checker measures.

11. Summary

• Functional correctness is single-cycle; fairness is temporal. An arbiter can grant one-hot, name the right winner, and pass every functional assertion forever while a requester waits indefinitely. Fairness asks 'will every requester eventually be served, and its share?' — a property of behaviour over time that no snapshot can see. Passing the functional suite says nothing about fairness; they are orthogonal checks and an arbiter must pass both.
• Three properties define fairness. No starvation / bounded wait — a continuously-asserted request is granted within MAX_WAIT cycles (N-1 for round-robin, unbounded for fixed priority); a liveness property. Work conservation — req != 0 implies grant != 0; never idle the resource while work waits. Throughput share — grant counts match intended shares over a long run (equal for round-robin, proportional for weighted).
• Measure each with a reusable checker. A per-requester continuous-wait counter that increments while requesting-and-ungranted and resets only on a grant, guarded by a max-wait assertion; a grant-count histogram read over a long window; and a one-line work-conservation invariant — a passive monitor wrapped around the arbiter.
• Drive adversarial sustained load, or you see nothing. Starvation is latent under light random traffic; it appears only when every requester asserts continuously and the high-priority master locks the others out. The fairness testbench drives req = all-ones for many rounds — the worst case the field will reach.
• The same checker passes round-robin and fails fixed-priority. Unchanged, it confirms round-robin's bounded wait and fires on fixed-priority's unbounded wait, naming the starving requester — black-box proof that a functionally-correct arbiter can still starve. And the signature verification bug is a checker bug: a wait counter that resets on a request edge instead of on a grant, under stimulus that never creates contention, gives a green fairness check on a hanging chip. Reset on grant, drive contention, and the starvation shows up on the bench — self-checking testbenches shown here in SystemVerilog, Verilog, and VHDL.