Three bug reports arrive on the same day, all titled "system hangs". In the first simulation, every valid signal is high, every ready is low, and nothing has changed for a million cycles. In the second, the bus is busy every single cycle, with retries and NAKs flying, yet no transaction finishes. In the third, everything runs normally, except that one DMA engine has been waiting for its first grant for 40,000 cycles. Three different diseases, one symptom.
What are the different ways a system can stop making progress, and how do you tell them apart?
The obvious diagnosis for "it hangs" is deadlock, and the obvious fix is to look for the cycle of waits. But only one of the three reports above is a deadlock. Chasing a cycle in the second (where nothing waits for long, everything retries) or the third (where most of the system is fine) wastes days. Liveness has three failure modes, and each has its own signature and its own causes.
Failure | What happens | On a waveform | Typical cause |
|---|---|---|---|
Deadlock | A set of agents each wait for another in the set; none can move | Everything frozen: valids high, readies low, no handshakes, no state changes | A cycle of dependencies: shared buffers, forbidden channel waits, cyclic routes |
Livelock | Agents keep acting, but no one completes useful work | Busy: handshakes, retries, NAKs every cycle, but completion counters stop rising | Retry without reservation, symmetric back-off, repeated collisions |
Starvation | Most of the system progresses; one agent never does | Normal traffic everywhere; one requester's valid high for ever, never granted | Unfair arbitration, priority without limits, lost wake-ups |
A useful question splits them quickly: is anything completing? Nothing completes and nothing moves: deadlock. Nothing completes but things move: livelock. Things complete, but not for one agent: starvation.
Count completions (responses, retired transactions) over time, per agent. Flat for everyone: deadlock or livelock. Flat for one: starvation.
Count handshakes, including retries and rejections. Zero: deadlock. Busy: livelock.
For deadlock, build the wait-for graph: who holds what, who waits for what (lessons 9.2 and 9.10).
For livelock, look at the retry path: what is rejected, why, and whether anything guarantees the retry will succeed (lesson 9.8).
For starvation, look at the arbiter on the starved agent's path and its fairness bound (lesson 8.3).
A team (illustrative) spent a week looking for a dependency cycle in a "hang" that turned out to be livelock: two requesters kept colliding on a shared resource, each backing off by exactly the same fixed delay, and colliding again. Completion counters had stopped, but the bus was 100% busy, the signature of livelock, not deadlock. Randomising the back-off fixed it in an hour once the right question was asked.
Livelock: things move, nothing completes.
Starvation; look at the arbiter on its path and its fairness bound.
Deadlock: frozen in a cycle of waits. Livelock: busy, no completions. Starvation: everyone progresses but one.
Ask first: is anything completing, and is anything moving?
Instrument completions, retries and a state-dumping watchdog from the start.