Two DMA engines each copy between two buffers. Engine A locks buffer 1 and then asks for buffer 2. Engine B locks buffer 2 and then asks for buffer 1. Each waits for the other to let go, and neither will, because neither has finished. The design review had checked each engine on its own. Nobody had drawn the arrows between them.
What exactly has to be true for a deadlock, and how do you find one?
The obvious defence is careful design of each block: if every agent behaves correctly, the system should too. But deadlock is not a property of any one agent. It is a property of how their waits connect. Every agent above did something reasonable; together they formed a loop. Finding deadlocks means looking at the connections, and the tool for that is a graph.
A deadlock can occur only if all four of these hold at once:
Condition | Meaning | Hardware example |
|---|---|---|
Mutual exclusion | A resource can be used by only one agent at a time | A buffer slot, a channel, a lock |
Hold and wait | An agent holds a resource while waiting for another | A packet holds a buffer at one router while waiting for the next |
No preemption | A resource cannot be taken away from its holder | A flit cannot be pulled back from a buffer |
Circular wait | There is a cycle of agents, each waiting for a resource the next holds | Four packets in a square, each waiting for the next link |
Break any one condition and deadlock becomes impossible. In hardware, the first three are usually inherent (buffers hold one thing; packets sit in them; you cannot un-send a flit), so designs break the fourth: they make sure no cycle of waits can form.
A wait-for graph makes the fourth condition visible: draw an arrow from each agent (or resource) to whatever it is waiting for. A deadlock is a cycle in this graph.
The model searches a wait-for graph for cycles with a depth-first search, on three graphs: the AXI-style hang from lesson 9.10, requests and responses sharing buffers (lesson 9.4), and the same system with responses given their own buffers.
"""Find deadlocks as cycles in a wait-for graph.
Each edge "A -> B" means agent (or resource) A is waiting for B. A deadlock is a
cycle: everyone in it waits for the next, so none can proceed. The search is a
depth-first search that reports the first cycle it finds.
"""
def find_cycle(edges):
graph = {}
for a, b in edges:
graph.setdefault(a, []).append(b)
graph.setdefault(b, [])
state, stack = {n: 0 for n in graph}, [] # 0 unvisited, 1 on the stack, 2 done
def dfs(n):
state[n] = 1
stack.append(n)
for m in graph[n]:
if state[m] == 1: # back edge: a cycle
return stack[stack.index(m):] + [m]
if state[m] == 0:
found = dfs(m)
if found:
return found
state[n] = 2
stack.pop()
return None
for n in graph:
if state[n] == 0:
found = dfs(n)
if found:
return found
return None
# The hang from lesson 9.10: a requester waits for the address to be accepted before
# sending data; the target waits for data before accepting the address.
hang = [("requester: W channel", "target: AWREADY"), ("target: AWREADY", "target: sees WVALID"),
("target: sees WVALID", "requester: W channel")]
# Requests and responses sharing one buffer in each direction (lesson 9.4)
shared = [("node A requests", "buffer A->B"), ("buffer A->B", "node B"), ("node B", "buffer B->A"),
("buffer B->A", "node A"), ("node A", "node A requests")]
# The same system with responses in their own buffers: B's responses never wait on A's requests
split = [("node A requests", "req buffer A->B"), ("req buffer A->B", "node B"), ("node B", "rsp buffer B->A"),
("rsp buffer B->A", "node A responses sink")]
for name, edges in (("dependency rule broken", hang), ("shared request/response buffers", shared), ("separate response buffers", split)):
c = find_cycle(edges)
print(f"{name:32s}: " + (" -> ".join(c) if c else "no cycle: cannot deadlock"))
assert find_cycle(hang) and find_cycle(shared) and find_cycle(split) is None
print("PASS: a deadlock is a cycle of waits; removing one edge of the cycle removes the deadlock")It prints:
dependency rule broken : requester: W channel -> target: AWREADY -> target: sees WVALID -> requester: W channel
shared request/response buffers : node A requests -> buffer A->B -> node B -> buffer B->A -> node A -> node A requests
separate response buffers : no cycle: cannot deadlock
PASS: a deadlock is a cycle of waits; removing one edge of the cycle removes the deadlockThe first two graphs contain a cycle: deadlock is possible. In the third, giving responses their own buffer removes the edge that closed the loop, and the finder reports no cycle. Every deadlock fix in this part works the same way: find the cycle, remove an edge.
Technique | Removes the cycle by |
|---|---|
Resource ordering | All agents acquire resources in one global order (buffer 1 before buffer 2); a cycle would need someone to go backwards |
Separate resources per class | Requests and responses never share a buffer, so responses never wait on requests (lesson 9.4) |
Routing restrictions | Forbid the turns that close cycles (lesson 8.9) |
Escape resources | Always keep one path that cannot be part of a cycle (lesson 9.6) |
Pre-allocation | Reserve everything needed before starting, so no one holds while waiting (lesson 9.7) |
The opening DMA engines (illustrative) were fixed by resource ordering: both engines were changed to lock the lower-numbered buffer first. Engine B now waits for buffer 1 before it takes buffer 2, so it can never hold buffer 2 while waiting for buffer 1, and the cycle cannot close.
A → lock 2 (held by B) → lock 3 (held by C) → lock 1 (held by A). Fix: acquire locks in a fixed global order, so the engine holding lock 3 never waits for lock 1.
The response's wait on the shared buffer held by requests (node B waiting for the buffer B→A full of A's requests): responses now go to a buffer requests cannot fill.
Deadlock needs mutual exclusion, hold and wait, no preemption and circular wait, all at once.
A deadlock is a cycle in the wait-for graph; find cycles before RTL exists.
Hardware usually breaks circular wait: ordering, separate classes, routing rules, escape paths or pre-allocation.