Arbitration, fairness and atomic access
Choose how several initiators share one target, recognise starvation in a trace, and explain the two ways a bus makes a read-modify-write safe.
- Lesson
- P1.9
- Time
- 30 min
- Runs on
- Your browser
- Check
- 5 questions
A DMA engine was given the lowest priority on a shared memory port, because its transfers were "not urgent". The core next to it issued a request three cycles out of four, and an accelerator filled most of the gaps. The DMA engine waited for 12,000 cycles without a single grant, its buffer overflowed, and the audio stream it was feeding dropped out every few seconds.
A lit req wire is a request; a lit grant wire is this cycle's winner; the pill names who owns the memory.
- Cycle 0
All three ask. The core is requester 0, so it wins.
- Cycle 3
The core pauses for a cycle. The accelerator wins; the DMA engine is still waiting.
- Cycle 4
The core is back and wins again. The DMA engine has asked every cycle and been refused every cycle.
- Cycle 7
Eight cycles, zero grants for requester 2. With these requesters it will never be served: that is starvation.
Fixed priority is simple and fast, and it promises nothing to the lowest requester.
One target, several initiators
When two initiators want the same target in the same cycle, something must choose. An arbiter takes a request from each initiator and returns one grant per cycle; the winner drives the target, the others hold their requests. The choice is the arbiter's policy, and the policy decides who waits and for how long.
Two policies cover most designs. Fixed priority picks the lowest-numbered requester that asks. Round robin starts each search just after the requester granted last time, so a requester that keeps asking is served within three grants when there are three requesters. Many arbiters mix them: a weighted round robin gives one requester two turns per round.
Round robin and fairness
The pill moves around the ring: after a grant to requester k the search starts at k+1.
- Cycle 0
The first search starts at requester 0, which asks and wins.
- Cycle 1
The search starts at requester 1, which is quiet, so requester 2 wins. The DMA engine is served on its second cycle.
- Cycle 4
While all three ask, each wins every third cycle.
- Cycle 7
Eight cycles: three, two and three grants. Nobody waits more than two cycles while asking.
Round robin bounds the wait of every requester. The price is that an urgent requester waits like everyone else.
A policy is fair when a requester that keeps asking is granted within a known number of cycles. Round robin is fair; fixed priority is fair only for the top requester. Starvation is the failure of fairness: a requester that asks forever and is never served. The bench measures it as the longest wait while asking.
Fixed priority is the right choice when one requester truly must not wait, such as a refresh controller or a real-time core, and the rest can tolerate gaps. Round robin is the right choice when every requester has a deadline. The usual mistake is the opening story: a priority list written by importance rather than by deadline.
Where the arbiter lives
| Bus | Who arbitrates | Between what |
|---|---|---|
| AHB | a central arbiter | managers sharing one address and data bus, one at a time |
| AXI | the interconnect, per target | requests from several managers to the same subordinate |
| Network-on-chip | every router | packets contending for one output link |
| PCIe | each switch port | packets, by virtual channel and traffic class |
On a shared bus the arbiter is a block of its own. On a point-to-point interconnect it sits at every meeting point.
Making a read-modify-write safe
Arbitration shares a target cycle by cycle, and that is exactly the problem for a read-modify-write. Two cores that each increment a shared counter both read 5, both compute 6, both write 6. One increment is lost, and neither core broke a rule of the bus.
The counter should end at 7. It ends at 6.
- Cycle 0
Core A reads the counter: 5.
- Cycle 1
Core B reads it too: 5. Nothing stops B, because A holds nothing.
- Cycle 3
A writes 6.
- Cycle 4
B writes 6 as well. The second increment overwrote the first instead of adding to it.
- Cycle 5
Two increments, one counted. A lock or an exclusive pair would have caught this.
Each core did a correct read and a correct write. The gap between them is the bug.
Buses offer two cures. A locked access keeps the grant with one initiator from its read to its write: the arbiter serves nobody else in between. It is simple and it stalls everyone, so AXI4 dropped it and AHB keeps it. An exclusive access leaves the bus free. The initiator marks its read as exclusive and the target records the address and the initiator. The matching exclusive write succeeds only if no other write touched that address since. If one did, the write fails with a plain response, and the initiator reads again and retries. Newer buses add atomic operations, where the target does the whole read-modify-write itself.
| Mechanism | Who guarantees it | Cost | Where |
|---|---|---|---|
| Locked access | the arbiter: no other grant until the lock is released | everybody waits | AHB, AXI3 |
| Exclusive access | the target's monitor: the write fails if the location changed | a retry when it fails | AXI4, AXI5, AHB5 |
| Atomic operation | the target performs read, modify and write in one transaction | a wider target | AXI5, TileLink, PCIe |
Three ways to keep a read-modify-write whole, from the oldest to the newest.
Asked in interviews: arbitration and atomic access
Priority or round robin, when?
Fixed priority when one requester must never wait and the others can tolerate gaps. Round robin when every requester has a deadline, because it bounds everyone's wait.
What is starvation?
A requester that keeps asking and is never granted. Fixed priority starves the lowest requester whenever the higher ones ask often enough.
What is the difference between a locked and an exclusive access?
A lock holds the bus from the read to the write, so nobody else is served. An exclusive pair leaves the bus free and lets the write fail if the location changed, so the initiator retries.
Where does arbitration happen on AXI?
Inside the interconnect, at every subordinate that several managers can reach. There is no central arbiter and no shared bus.
How do you verify fairness?
Count grants per requester under a request pattern where all keep asking, and measure the longest wait while asking. A bounded wait is fairness; an unbounded one is starvation.
Try it
The core asks three cycles in four, the accelerator two in four and the DMA engine every cycle. With fixed priority the DMA engine gets nothing in twelve cycles. Change POLICY(0) to POLICY(1) and run again: the shares become 5, 3 and 4, and nobody waits more than three cycles.
Then make the core ask every cycle with ask(3'b111) four times, and see which policy still serves the others.
grants: I0 I0 I0 I1 I0 I0 I0 I1 I0 I0 I0 I1 shares over 12 cycles: I0 9, I1 3, I2 0 longest wait while asking: I0 0, I1 2, I2 12Read included file: arbiter.sv
// arbiter.sv: one grant per cycle among three requesters (read-only in this lesson).
// grant is one-hot in the same cycle as req, or 0 when nobody asks.
// POLICY 0, fixed priority: requester 0 wins whenever it asks, then 1, then 2.
// POLICY 1, round robin: the search starts just after the requester granted last time, so a
// requester that keeps asking is served within three grants.
module arbiter #(parameter int POLICY = 0) (
input logic clk,
input logic rst_n,
input logic [2:0] req,
output logic [2:0] grant
);
logic [1:0] last; // round robin: the requester granted most recently
int i;
always_comb begin
grant = 3'b000;
if (POLICY == 0) begin
casez (req)
3'b??1: grant = 3'b001;
3'b?10: grant = 3'b010;
3'b100: grant = 3'b100;
default: grant = 3'b000;
endcase
end else begin
for (int k = 1; k <= 3; k++) begin
i = (last + k) % 3;
if (grant == 3'b000 && req[i]) grant = 3'b001 << i;
end
end
end
always_ff @(posedge clk or negedge rst_n)
if (!rst_n) last <= 2'd2; // the first round-robin search starts at requester 0
else if (grant != 3'b000) last <= grant[0] ? 2'd0 : grant[1] ? 2'd1 : 2'd2;
endmodule
Read included file: arb_tasks.svh
// arb_tasks.svh: drive the three requesters cycle by cycle and keep the score (read-only).
// `cycle` counts rising edges from 0. The grant is sampled at every edge.
int cycle = -1;
always @(posedge clk) cycle = cycle + 1;
bit quiet = 0; // 1: print only the shares line
int granted [3]; // grants per requester
int waiting [3]; // cycles spent asking since the last grant
int longest [3]; // the longest such wait
string history = "";
int cycles = 0;
initial for (int k = 0; k < 3; k++) begin granted[k] = 0; waiting[k] = 0; longest[k] = 0; end
// Hold one request pattern (bit i for requester i) for one cycle.
task automatic ask(input logic [2:0] r);
req = r;
@(posedge clk); #1;
endtask
always @(posedge clk) begin
logic [2:0] g, r; logic active;
g = grant; r = req; active = rst_n;
#1 if (active) begin
cycles++;
history = {history, " ", g[0] ? "I0" : g[1] ? "I1" : g[2] ? "I2" : "--"};
for (int k = 0; k < 3; k++) begin
if (g[k]) begin granted[k]++; waiting[k] = 0; end
else if (r[k]) begin waiting[k]++; if (waiting[k] > longest[k]) longest[k] = waiting[k]; end
end
end
end
task automatic report();
#1; // let the monitor count the last edge first
if (!quiet) $display("grants:%s", history);
$display("shares over %0d cycles: I0 %0d, I1 %0d, I2 %0d", cycles, granted[0], granted[1], granted[2]);
if (!quiet) $display("longest wait while asking: I0 %0d, I1 %0d, I2 %0d", longest[0], longest[1], longest[2]);
endtask
Check yourself
Remember
- An arbiter returns one grant per cycle among several requesters; its policy decides who waits.
- Fixed priority serves the lowest-numbered requester and can starve the rest. Round robin starts after the last winner and bounds every wait.
- Pick fixed priority for a requester that must never wait, round robin when everyone has a deadline, and measure the longest wait while asking.
- Two reads then two writes lose an update. A locked access holds the bus for the pair; an exclusive pair leaves the bus free and fails the write if the location changed.
- On AXI the arbiter is inside the interconnect at every subordinate; on AHB it is a block of its own.
Practice
- A round-robin arbiter model Implement · Medium