Starvation

Chapters 10.5–10.6 covered the arbitration policies (fixed-priority, round-robin). This chapter examines the problem those policies manage: starvation. A master is starved when it requests the bus but never gets granted — it makes no progress, potentially hanging its function. Starvation is a fairness failure (not a protocol error): one master monopolizes the bus, so another is never served. Its causes: fixed-priority with a continuously-requesting high-priority master (which starves lower ones); a master holding HLOCK too long (blocking others); a master holding the bus with very long bursts. The fixes are arbitration-policy choices: a fair policy (round-robin guarantees every master a turn), bounded locks and bursts (limit how long any master holds the bus), hybrid policies (prioritize a critical master while round-robining the rest), and anti-starvation features like priority aging (temporarily raise a long-waiting master's priority). Starvation is prevented by ensuring every master eventually gets a bounded-latency turn.

1. What Is It?

Starvation is the condition where a master requests the bus (asserts HBUSREQ) but never gets granted — it waits indefinitely, making no progress.

The main causes:

• Fixed-priority + a busy high master: a high-priority master requests continuously, so lower-priority masters never win (chapter 10.5).
• HLOCK held too long: a master locks the bus (chapter 10.4) and doesn't release it, so others can't get the bus.
• Very long bursts: a master holds the bus for a very long burst, so others wait excessively.

So starvation is fundamentally one master monopolizing the bus at another's expense. The starved master isn't broken — it's correctly requesting the bus — but the arbitration never grants it, because some other master is always being served. This is a fairness failure: the arbitration isn't sharing the bus fairly. It's not a protocol error (no rule is violated — the arbiter is just always granting someone else); it's a fairness problem the arbitration policy must prevent. A starved master makes no progress, which can hang its function (a starved DMA never completes, a starved processor stalls). So starvation is a serious system problem, prevented by the choice of arbitration policy and the discipline of bounded bus-holding.

2. Why Does It Exist?

Starvation exists because arbitration must choose one master at a time, and a poorly-chosen policy (or unbounded bus-holding) can choose the same master(s) forever, never serving another — leaving it starved.

The root is that the bus is a shared resource served one master at a time (chapter 10.1). So the arbiter must pick — and if its policy always picks the same master(s) when contention exists, the others are never picked. Fixed-priority is the classic case: it always grants the highest-priority requester, so if a high-priority master requests continuously, the lower ones are never the highest requester — never granted, starved (chapter 10.5). So starvation arises from a policy that can perpetually favor some masters over others. It exists because arbitration involves choosing, and an unfair choice (always the same masters) starves the rest.

The bus-holding causes (locks, bursts) are the other root: even a fair policy can't help if a master holds the bus for a very long time (a long lock or burst), because the arbiter can only change ownership between transactions (chapter 10.1) — so while a master holds the bus (locked or in a long burst), others can't be granted. So if a master holds the bus excessively, it starves others regardless of the policy. So starvation also exists from unbounded bus-holding — a master keeping the bus too long. This is why bounded locks (chapter 10.4) and bounded bursts matter: they limit how long any master monopolizes the bus, giving others a chance.

The reason starvation must be prevented is that a starved master makes no progress — it can't do its job. A starved DMA never completes its transfer; a starved processor stalls (can't fetch/execute); a starved real-time master misses its deadline. So starvation isn't a minor inefficiency — it can break a master's function or violate a real-time requirement. So preventing starvation is a correctness/liveness requirement for many systems (every master must make progress), not just a performance nicety. This is why arbitration policies are designed with fairness/anti-starvation in mind: the system needs every master to eventually get the bus. So starvation exists as a liveness hazard of shared-bus arbitration, prevented by fair policies and bounded bus-holding — ensuring every master makes progress.

3. Mental Model

Model starvation as a busy shared printer where some print jobs never get printed — because either the policy always favors others' jobs, or one user sends an enormous job that hogs the printer for hours.

A shared office printer (the bus) prints one job at a time (the bus serves one master). Starvation is when your print job (a master's request) never gets printed — you submitted it (HBUSREQ asserted) but it sits in the queue forever. This happens two ways. Unfair policy: if the printer always prints the boss's jobs first (fixed-priority), and the boss is always printing, your job (low priority) never gets its turn — starved. Hogging: if someone sends a 10,000-page job (a very long burst) or locks the printer for a long session (HLOCK held too long), no one else's jobs print while theirs runs — others starve. The fix: a fair queue (round-robin — everyone's job prints in turn), job-size limits (bounded bursts — no enormous jobs monopolizing), and aging (a job waiting too long gets bumped up). So everyone's job eventually prints — no starvation.

This captures starvation: your job never printing = a master never granted; the boss always favored = fixed-priority with a busy high master; a 10,000-page job hogging = a very long burst; locking the printer = HLOCK held too long; a fair queue / job limits / aging = round-robin / bounded bursts / priority aging. The shared resource must serve everyone eventually, or some are starved.

Watch a starved master vs a fair one:

The model's lesson: starvation is the shared resource never serving a requester — prevented by fairness and bounded hogging. In the waveform, under fixed-priority the low master C is never granted (starved); under round-robin C gets turns (fair). The policy choice determines whether a master starves — fairness prevents it.

4. Real Hardware Perspective

In hardware, starvation is prevented by the arbiter's policy and the system's bus-holding limits — fair policies (round-robin) and anti-starvation features in the arbiter, plus bounded locks and burst-length limits enforced around the bus.

The arbiter's policy is the primary defense: a fair policy (round-robin, chapter 10.6) structurally prevents starvation (every master gets a turn). A fixed-priority policy (chapter 10.5) risks starvation, so if used, it needs either bounded high-priority demand or an anti-starvation feature — e.g., priority aging, where a master that's waited too long has its priority temporarily raised so it eventually wins. So the arbiter hardware may include aging logic (counters tracking how long each master has waited, boosting priority past a threshold). So in hardware, the arbiter's policy (fair, or fixed-priority-with-aging) is the main starvation prevention.

The bus-holding limits are the other defense: even with a fair policy, a master holding the bus too long (a long lock or burst) starves others while it holds. So the system limits bus-holding: bounded locks (a master must release HLOCK promptly, chapter 10.4) and bounded bursts (or the interconnect breaks/limits long bursts, chapters 8.10, 12.x). So the hardware/system enforces that no master holds the bus excessively — the arbiter can change ownership at bounded intervals. So starvation prevention is partly the arbiter (policy) and partly the bus-holding discipline (bounded locks/bursts).

The hybrid policies combine prioritization with fairness (chapter 10.6): a critical master gets priority (low latency), but the rest are round-robined (fair, no starvation among them), and the critical master's demand is bounded (so it doesn't starve the rest). So a well-designed arbiter often uses a hybrid that both serves critical masters quickly and prevents starvation of the others. So in hardware, the arbiter's policy is tuned to give the needed latency without starvation — a hybrid being the common solution. So the arbiter hardware embodies the chosen anti-starvation strategy (fair policy, aging, hybrid, or bounded demand).

A hardware note on detecting/verifying no-starvation: starvation is a liveness property (every requester is eventually granted), which is verified by checking that no master's request can be perpetually unserved. In verification, this is checked by liveness assertions ("if a master requests, it's eventually granted within N cycles") or by stress-testing with worst-case contention. So the absence of starvation is a verified property — the design must guarantee every requester is served within a bounded time. So in hardware/verification, no-starvation is a liveness guarantee that's designed in (via the policy) and verified (via liveness checks). A starvation bug (a master that can be perpetually starved) is a serious liveness failure.

5. System Architecture Perspective

At the system level, preventing starvation is a liveness requirement — every master must make progress — and it shapes the choice of arbitration policy and the discipline of bus-holding, balanced against the latency needs of critical masters.

The liveness requirement is the core system concern: in a multi-master system, every master must eventually get the bus and make progress — a starved master is a broken master (it can't do its job). So preventing starvation is a correctness/liveness requirement, especially in real-time systems where each master has a deadline (a starved master misses its deadline — a failure). So the system must guarantee that no master starves — every master gets a bounded-latency turn. This is a fundamental requirement shaping the arbitration design: the policy must ensure liveness for all masters.

The policy-choice balance is the key trade-off (chapters 10.5–10.6): the system must balance latency for critical masters (favoring prioritization) against no-starvation for all (favoring fairness). Pure fixed-priority gives low critical latency but risks starvation; pure round-robin prevents starvation but gives no prioritization. So the system chooses a policy — often a hybrid — that gives critical masters their needed latency while guaranteeing the others don't starve. So the arbitration policy is designed to meet both the latency requirements and the liveness (no-starvation) requirement. This balance is a central system-design decision — getting both right is the goal.

The bus-holding discipline is the complementary system requirement: even a fair policy needs bounded bus-holding — bounded locks (chapter 10.4) and bounded bursts (chapters 8.10, 12.x) — so no master monopolizes the bus. So the system enforces bus-holding limits: masters release locks promptly, bursts are bounded (or the interconnect limits them), ensuring the bus is available to be re-arbitrated at bounded intervals. So at the system level, preventing starvation requires both a fair-enough policy and bounded bus-holding — together ensuring every master gets the bus within a bounded time. So starvation prevention is a system-wide concern: the arbitration policy (fair/hybrid/aging), the bus-holding discipline (bounded locks/bursts), and the verification (liveness checks) together guarantee every master makes progress. As systems grow in masters and in real-time requirements, this liveness guarantee becomes more critical — which is why modern interconnects (chapter 12.x) carefully manage arbitration and bus-holding to prevent starvation. So starvation is the liveness hazard that arbitration design exists, in large part, to prevent.

6. Engineering Tradeoffs

Starvation prevention embodies the fairness-vs-latency balance.

• Fairness (no starvation) vs prioritization (low critical latency). A fair policy (round-robin) prevents starvation but gives no prioritization; a prioritized policy (fixed-priority) gives low critical latency but risks starvation. The system needs both — usually via a hybrid (prioritize critical, round-robin the rest).
• Bounded bus-holding vs long holds. Bounded locks/bursts prevent a master from monopolizing the bus (no starvation) at the cost of limiting how much a master can do per grant (it must re-arbitrate). Long holds are more efficient per-grant but risk starving others. Bounded holding is needed for liveness.
• Anti-starvation features vs simple policy. Adding priority aging (or other anti-starvation logic) to a fixed-priority arbiter prevents starvation while keeping prioritization, at the cost of more arbiter complexity. A simple fixed-priority arbiter is simpler but risks starvation. Aging is a middle ground.
• Guaranteed bounded latency vs best-effort. Guaranteeing every master a bounded-latency turn (for real-time) requires a fair/bounded policy; best-effort (no guarantee) is simpler but unsafe for real-time. Real-time systems need the bounded-latency guarantee.

The throughline: starvation is a master never getting the bus (a liveness/fairness failure), caused by one master monopolizing it (unfair policy or unbounded bus-holding). It's prevented by a fair-enough policy (round-robin, hybrid, or fixed-priority-with-aging) and bounded bus-holding (bounded locks/bursts) — ensuring every master gets a bounded-latency turn. The central design balance is fairness/no-starvation versus latency for critical masters, usually resolved with a hybrid. Preventing starvation is a liveness requirement, critical for real-time systems and verified with liveness checks.

7. Industry Example

Trace starvation and its prevention in a system.

A system has a high-bandwidth DMA (high priority) and a CPU plus a low-priority background master, on a shared bus.

• A starvation bug under fixed-priority. The system initially uses fixed-priority with the DMA at top priority (for its bandwidth). But the DMA, doing a large sustained transfer, requests the bus continuously. So the lower-priority masters — including the CPU — are never granted: they're starved. The CPU stalls (can't fetch/execute), the system hangs. This is a starvation bug: the busy high-priority DMA monopolized the bus.
• Diagnosing it. The symptom (CPU stalled, system hung) is traced to the CPU's HBUSREQ being asserted but never granted — starved by the continuously-requesting DMA under fixed-priority. The root cause: fixed-priority + unbounded high-priority (DMA) demand.
• Fix 1 — bounded DMA bursts. One fix: bound the DMA's burst length, so it releases the bus periodically (re-arbitrating between bursts), giving the lower masters a chance. So the DMA does bounded bursts instead of one continuous transfer, leaving gaps for the CPU. The CPU now gets the bus between the DMA's bursts — no starvation. Bounded bus-holding fixed it.
• Fix 2 — hybrid policy. A better fix: use a hybrid policy. The CPU gets high priority (it's latency-critical), the DMA and background master are round-robined for the rest. So the CPU gets the bus quickly (low latency), and the DMA and background master share the rest fairly (no starvation among them). This balances the CPU's latency need with no-starvation for all. So the hybrid serves the CPU's urgency and prevents starvation.
• Fix 3 — priority aging. Alternatively, keep fixed-priority but add priority aging: a master waiting too long has its priority temporarily raised, so even the background master eventually wins. So aging guarantees every master eventually gets the bus, preventing starvation while keeping mostly-prioritized behavior. The arbiter's aging logic ensures liveness.
• Verification. After the fix, the system verifies no-starvation with a liveness check: stress-test with worst-case contention (all masters requesting continuously) and assert every master is granted within a bounded time. The check passes — no master starves. So the liveness property is verified, not just assumed.

The example shows a starvation bug (fixed-priority + continuously-busy DMA starving the CPU) and its fixes: bounded bursts (bus-holding limit), a hybrid policy (prioritize the CPU, round-robin the rest), and priority aging (boost long-waiters) — each ensuring every master eventually gets the bus. Verification confirms no-starvation. Starvation is a real, serious bug, prevented by policy choice and bounded bus-holding.

8. Common Mistakes

9. Interview Insight

Starvation is a common interview topic — its definition (a liveness failure), causes, and prevention (fairness, bounded holding, hybrids) are the signals.

The answer that lands defines starvation and covers causes and prevention: "Starvation is when a master requests the bus — it has HBUSREQ asserted — but never gets granted, so it makes no progress. It's a fairness failure, not a protocol error: no rule is broken; the arbiter just always grants someone else. The causes all come down to one master monopolizing the bus: fixed-priority where a high-priority master requests continuously, so the lower ones never win; a master holding HLOCK too long, blocking others; or a master holding the bus with very long bursts. The fixes are arbitration-policy and bus-holding choices: a fair policy like round-robin guarantees every master a turn; bounded locks and bounded bursts limit how long any master holds the bus; a hybrid policy prioritizes a critical master while round-robining the rest, so none starves; and anti-starvation features like priority aging temporarily raise a long-waiting master's priority. It's important because a starved master makes no progress — it can hang its function or miss a real-time deadline — so preventing it is a liveness requirement, verified with liveness checks." The liveness-failure definition, the monopolization causes, and the fairness/bounded-holding/hybrid prevention are the senior signals.

10. Practice Challenge

Reason from starvation.

1. Define it. Explain what starvation is and why it's a fairness/liveness failure, not a protocol error.
2. List the causes. Give the causes of starvation.
3. Read the waveform. From Figure 2, contrast the starved master under fixed-priority with the fair one under round-robin.
4. Prevention. Explain why both a fair policy and bounded bus-holding are needed.
5. Verification. Explain how no-starvation is verified as a liveness property.

11. Key Takeaways

• Starvation is a master that requests the bus but never gets granted — it makes no progress (a fairness/liveness failure, not a protocol error).
• Causes — one master monopolizing the bus: fixed-priority with a continuously-requesting high master; HLOCK held too long; very long bursts.
• It's a liveness requirement to prevent — a starved master can't do its job (a starved DMA never completes, a real-time master misses its deadline).
• Prevention needs a fair-enough policy — round-robin (fully fair), a hybrid (prioritize critical, round-robin the rest), or fixed-priority with priority aging.
• AND bounded bus-holding — bounded locks and bursts — since even a fair policy can't help while a master holds the bus too long.
• No-starvation is verified as a liveness property — every requester granted within a bounded time. The central design balance is fairness/no-starvation versus latency for critical masters (usually resolved with a hybrid).

12. What Comes Next

You now understand starvation and its prevention. The next chapters cover the timing of arbitration and handover:

• 10.8 — Arbitration Timing (coming next) — grant timing relative to the address phase and bus handover.
• 10.9 — Bus Ownership Handover (coming soon) — the clean handover of the bus between two masters.

To revisit the policies that manage starvation, see Fixed-Priority Arbitration and Round-Robin Arbitration. For the locks and bursts that can cause it, see Locked Transfers (HLOCK) and Burst Termination. For the broader protocol map, see the AMBA family overview.