Detecting Deadlock
Concurrency: lesson 12 of 15
Draw who waits for whom; a closed ring is the proof.
Lesson 12 of 15 · 5 min
Detecting Deadlock
Step 1 of 10
blocked4
Four threads, all stuck. A stack trace tells you each one is waiting; it never tells you why nobody moves.
The Idea
A wait-for graph has one node per thread and an edge from a waiter to the holder it is blocked on. Following the edges from any thread either runs out — the chain ends at somebody who is running — or comes back around. That ring is the deadlock, and breaking it means aborting one member.
Real-World Example
Four people in a corridor, each waiting for the person ahead to step aside. Three of them form a circle and nobody moves. The fourth is only stuck because they queued behind the circle.
The Code
waits = {"t1": "t2", "t2": "t3", "t3": "t1", "t4": "t2"}
def stuck(graph, start):
seen, at = [], start
while at in graph: # who is this one waiting on?
if at in seen:
return seen[seen.index(at):] # a closed ring: nobody can move
seen.append(at)
at = graph[at]
return [] # chain ends at a thread still running
print(stuck(waits, "t1")) # ['t1', 't2', 't3']
print(stuck(waits, "t4")) # ['t2', 't3', 't1'] -- queued behind it
freed = {k: v for k, v in waits.items() if k != "t3"}
print(stuck(freed, "t1")) # [] -- abort one victim, ring brokenYour turn
What does this print?
def stuck(graph, start):
seen, at = [], start
while at in graph:
if at in seen:
return seen[seen.index(at):]
seen.append(at)
at = graph[at]
return []
print(stuck({"a": "b", "b": "c", "c": "b"}, "a"))Mini quiz
1 / 3