Fix a test plan that should show client 0 starving, but stops one edge before the deadline.
Hardware context: Round-robin arbiter with accepted-grant priority updates. Construct a finite service-bound witness for a requester skipped at priority wrap.
An arbiter has a pointer bug: it wraps to client 1 instead of client 0. A good bug report shows client 0 waiting past its deadline. This plan builder stops one edge too early, so its report never shows the starvation.
The class fairness_witness builds a list of edges for an arbiter with N clients. Every client asks on every edge. The receiver stalls for H edges, then takes one transfer, and repeats. The plan also gives two bounds: grant_bound = N transfers and cycle_bound = N × (H + 1) edges.
The tests replay the plan on a correct arbiter and on the faulty one. A fairness checker watches both. On the correct arbiter, client 0 must be served on the very last edge. On the faulty one, the checker must flag client 0 on that edge.
Find the bug and fix it.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
clients | 4 | input of each check |
maximum_hold | 2 | input of each check |
Full specification
class arbitration_offer; // given
bit [7:0] requests;
bit ready, reset;
function new(input bit [7:0] req = 0, input bit permit = 0, rst = 0);
endclass
class fairness_witness; // yours
arbitration_offer items[$];
int cycle_bound, grant_bound;
function new(input int clients, max_hold);
endclass
| Plan rule | Meaning |
|---|---|
| Clients | N is 2, 3, 5 or 8. H = max_hold is 0 to 3. |
| Requests | Every edge asks for all N clients: requests = (1 << N) - 1. |
| ready | Edge c has ready = 1 when c mod (H + 1) = H. Otherwise ready = 0. |
| reset | Always 0. |
| Length | Exactly cycle_bound edges, each a new object. No entry is null. |
| Bounds | grant_bound = N and cycle_bound = N × (H + 1). |
| Run | What happens |
|---|---|
| Start | Both arbiters start with priority 1. They keep a stalled offer, so each ready edge transfers one client. |
| Correct arbiter | It serves 1, 2, up to N - 1, then 0. Client 0 transfers on edge cycle_bound - 1, counting from 0. |
| Faulty arbiter | After N - 1 it wraps to 1, so client 0 is never served. On the last edge client 0 has seen N transfers to others. |
| Checker | It flags GRANT when a waiting client sees N transfers to others. It flags CYCLE when it waits N × G edges. Here G = H + 1. |
| After the plan | The remaining edges up to 32 are idle and not checked. |
SIZE=<items>|CYCLE_BOUND=<n>|GRANT_BOUND=<n>|SHAPE=<bad entries>|GOOD_FIRST=<edge>|FAULT_FIRST=<edge>|GOOD{<checker report and trace>}|FAULT{<checker report and trace>}
SHAPE counts null and repeated entries, plus 1 for a plan over 32 edges. GOOD_FIRST and FAULT_FIRST give the first edge where client 0 is served, or 255 if never. A correct plan gives GOOD_FIRST = cycle_bound - 1 and FAULT_FIRST = 255.
The result compares this line with the expected text, character by character. It shows both lengths and whether the two lines match. On a mismatch the log prints your line.
Examples
Example 1
The Third Transfer Meets the Deadline- Input
N = 3, H = 1
- Output
your_line_length = 859, expected_line_length = 859, lines_match = yes
The plan has 6 edges and ready is 0, 1, 0, 1, 0, 1. The correct arbiter serves 1, 2 and 0 on edges 1, 3 and 5. The faulty one serves 1, 2, 1, so the checker reports GRANT and CYCLE for client 0 on edge 5.
Example 2
Eight Clients, Three Stalls Each- Input
N = 8, H = 3
- Output
your_line_length = 3369, expected_line_length = 3369, lines_match = yes
Eight transfers need 32 edges. The correct arbiter serves client 0 on edge 31. The faulty one serves client 1 again on that edge, and the checker flags client 0 there.
Example 3
No Stalls Still Need a Full Round- Input
N = 2, H = 0
- Output
your_line_length = 479, expected_line_length = 479, lines_match = yes
ready is always 1. The correct arbiter serves 1, then 0, on edges 0 and 1. The faulty one serves 1 twice, so the second transfer shows client 0 starving.
Constraints and Contract
- Allocate a new arbitration_offer for every edge.
- N = 1 is not tested, because there is no other client to serve instead of client 0.
- Keep the class names, the members and the constructor arguments.
Hints
Hint 1
Work out N = 3 and H = 1 by hand. Ready is 0, 1, 0, 1, 0, 1. On which edge does the correct arbiter serve client 0?
Hint 2
Edges count from 0. A plan that must include edge k needs k + 1 entries.
Hint 3
Look at cycle_bound. It should be N × (H + 1), with nothing taken away, so the last ready edge is in the plan.
What the grader checks: The plan runs on a real correct arbiter and a real one that skips client 0. A fairness checker watches both runs. This shows the bound for steady requests, stalls of at most H and no withdrawal. It does not cover unbounded stalls.
19 checks on Verilator · server. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.
See all 8 steps and the final capstone