Deadlocked Threads in a Wait Graph
Problem
A lock monitor takes a snapshot of a running process. holds maps each held lock to the thread holding it, and waits maps each blocked thread to the one lock it is waiting for; a thread waits for at most one lock at a time. A thread is deadlocked when following "waits for a lock held by" from it leads back to itself. Return the deadlocked threads, sorted. Threads that are merely stuck behind a deadlock, without being on the cycle themselves, are not part of the answer.
Examples
Input: holds = {"a": "T1", "b": "T2"}, waits = {"T1": "b", "T2": "a"}
Output: ['T1', 'T2']
Why: T1 waits for T2 and T2 waits for T1Input: holds = {"a": "T1", "b": "T2", "c": "T3"}, waits = {"T1": "b", "T2": "c", "T3": "a", "T4": "a"}
Output: ['T1', 'T2', 'T3']
Why: T4 is blocked behind the cycle but not on itInput: holds = {"a": "T1"}, waits = {"T2": "a", "T3": "a"}
Output: []
Why: edge case, T1 is running, so the waiters will get their turnHints
0 / 3
Turn the snapshot into a graph of threads: an edge from each waiting thread to the thread that holds the lock it wants.
Each thread waits for at most one lock, so every node has at most one outgoing edge. From any start there is only one path to follow, and it either ends or loops.
Follow the path from each thread not yet visited, marking threads on the current path. If the walk reaches a thread already on the current path, everything from that thread onwards is a cycle. Mark the whole path finished afterwards so no thread is walked twice.
Solution
Replacing each "waits for lock" with "waits for the thread that holds it" turns the snapshot into a wait-for graph, and a deadlock is exactly a cycle in that graph. Because a thread waits for one lock at most, each node has one outgoing edge at most, so a walk from any thread has no choices: it stops at a running thread, reaches a thread finished earlier, or steps back onto its own path. Only the last case is a new cycle, and the cycle is the part of the path from the repeated thread onwards, which leaves waiters like T4 outside it. Marking every walked thread finished means each thread is visited once, so time is O(t + l) for t threads and l locks, and space is O(t).
def deadlocked(holds, waits):
# wait-for edge: a waiting thread points at the thread holding its lock
nxt = {t: holds[lock] for t, lock in waits.items() if lock in holds}
state, stuck = {}, set() # 1 = on the current path, 2 = done
for start in nxt:
path, t = [], start
while t in nxt and t not in state:
state[t] = 1
path.append(t)
t = nxt[t]
if state.get(t) == 1: # walked back onto this path: a cycle
stuck.update(path[path.index(t):])
for p in path:
state[p] = 2
return sorted(stuck)
print(deadlocked({"a": "T1", "b": "T2"}, {"T1": "b", "T2": "a"})) # -> ['T1', 'T2']
print(deadlocked({"a": "T1", "b": "T2", "c": "T3"}, {"T1": "b", "T2": "c", "T3": "a", "T4": "a"})) # -> ['T1', 'T2', 'T3']
print(deadlocked({"a": "T1"}, {"T2": "a", "T3": "a"})) # -> []Stuck on the idea rather than the code? Detecting Deadlock covers it.