Deadlock Detection: Wait-for Graphs, Cycles and Victims

Preventing deadlock means designing it out, usually with a global lock order. Detecting it means letting it happen and noticing. Databases do the second constantly, because transactions lock rows in whatever order queries touch them. The tool is a small graph and a cycle search; the hard part is deciding what to do once you find one.

The problem it solves

A service hangs. The thread dump shows threads "waiting for lock", but waiting is normal in a busy program. What you need to know:

• Is anyone permanently stuck, or just slow?
• Which threads are in the deadlock, and which are only queued behind it?
• What is the smallest thing to undo so everyone can move again?

A stack trace shows one thread in isolation; the answer lives in the relationships between threads.

The intuition

Build a wait-for graph: one node per thread, and an arrow from each waiting thread to the thread holding the lock it wants. It comes from two tables a lock manager already keeps: who holds each lock, and what each blocked thread waits on.

Then follow the arrows. From any thread, the walk either ends at a thread that is not waiting, which can run and eventually release what it holds, or it comes back around. In a ring where every member waits on the next, nobody can move first. With exclusive locks, that cycle is both necessary and sufficient for deadlock.

Two refinements matter in practice:

• Members and bystanders. A thread whose walk falls into a ring is stuck too, but it is not part of the cause. Aborting it changes nothing. Only aborting a member breaks the ring, after which the bystanders drain on their own.
• One arrow or many. With exclusive locks and one pending request per thread, each node has at most one outgoing arrow, and following pointers is enough. With shared (read) locks, a waiter can be blocked by several holders at once, so the graph has several arrows per node and you need a general cycle search, the colouring depth-first search from cycle detection in directed graphs.

Detection only tells you a deadlock happened; resolution means choosing a victim, rolling it back so it releases its locks, and letting it retry. Systems pick the victim to minimise wasted work: the transaction that has done the least, or the youngest. As of October 2026, MySQL's InnoDB documents that it tries to roll back small transactions, measured by rows changed, while PostgreSQL waits a deadlock_timeout (one second by default) before checking and documents that which transaction it aborts is hard to predict. Whichever is chosen, the application must be ready to retry.

Watch it run

The animation starts with four threads, all stuck: a stack trace tells you each one is waiting, never why nobody moves. So it draws one arrow per thread, from the waiter to whoever holds what it wants. t1 waits on t2. t2 is waiting too, on a lock t3 is holding. And t3 is waiting on t1: the chain has closed, and the readout spells out t1 → t2 → t3 → t1. That ring is the whole definition; a cycle is a deadlock. t4 is also stuck, but it is queued behind the ring, not in it: 3 of 4 are in the cycle. Walking from t4 still finds the ring, because the walk falls into it and revisits t2. Detection alone changes nothing, so somebody is chosen and aborted, usually whoever did least work, here t3. With the ring broken, the whole chain drains, t4 included. The last frame shows the cheaper option: take the locks in one agreed order and no ring can form.

The code

A lock table with a deadlock, a bystander (t4) and an ordinary waiter (t6, blocked on t5, which is running). The detector follows the arrows, marking threads as it goes so each is visited once, and separates ring members from everything stuck behind them:

def wait_for_graph(holder, waiting):
    """holder: lock -> thread holding it. waiting: thread -> lock it is blocked on."""
    return {t: holder[lock] for t, lock in waiting.items() if lock in holder}

holder = {"A": "t2", "B": "t3", "C": "t1", "D": "t5"}
waiting = {"t1": "A", "t2": "B", "t3": "C", "t4": "A", "t6": "D"}
graph = wait_for_graph(holder, waiting)
print(graph)
# {'t1': 't2', 't2': 't3', 't3': 't1', 't4': 't2', 't6': 't5'}

def find_deadlocks(graph):
    """Each thread waits on at most one other, so follow the arrows, marking as you go."""
    state, cycles, stuck = {}, [], set()
    for start in graph:
        path, at = [], start
        while at in graph and at not in state:
            state[at] = "on this walk"
            path.append(at)
            at = graph[at]
        if state.get(at) == "on this walk":       # came back to this walk: a new ring
            cycles.append(path[path.index(at):])
            doomed = True
        else:                                     # a running thread, or an older walk
            doomed = at in stuck
        for t in path:
            state[t] = "done"
            if doomed:
                stuck.add(t)
    return cycles, stuck

cycles, stuck = find_deadlocks(graph)
print(cycles, sorted(stuck))
# [['t1', 't2', 't3']] ['t1', 't2', 't3', 't4']

work = {"t1": 40, "t2": 25, "t3": 5}              # e.g. rows changed so far
victims = [min(ring, key=lambda t: (work.get(t, 0), t)) for ring in cycles]
print(victims)                                     # ['t3']

def abort(holder, waiting, victim):
    """Roll the victim back: it stops waiting and releases everything it holds."""
    return ({lock: t for lock, t in holder.items() if t != victim},
            {t: lock for t, lock in waiting.items() if t != victim})

def drain(holder, waiting):
    """Brute force: whoever can run finishes and releases its locks, until nothing moves."""
    holder, waiting = dict(holder), dict(waiting)
    threads = set(holder.values()) | set(waiting)
    finished, moved = set(), True
    while moved:
        moved = False
        for t in sorted(threads - finished):
            if waiting.get(t) not in holder:       # not waiting, or its lock is free
                finished.add(t)
                moved = True
                waiting.pop(t, None)
                for lock in [l for l, h in holder.items() if h == t]:
                    del holder[lock]
    return threads - finished

print(sorted(drain(holder, waiting)))              # ['t1', 't2', 't3', 't4']
print(sorted(drain(*abort(holder, waiting, "t3"))))   # []

t6 is waiting but not reported: its chain ends at t5, which can run. drain is the brute force; it never looks for cycles, it lets every thread that can move finish and reports who is left. On 3,000 seeded random lock tables, the stuck set equals what drain leaves, ring members are exactly the threads that reach themselves, and aborting one random member per ring lets everyone else finish:

import random

rng = random.Random(33)
ok = True
for _ in range(3_000):
    threads = ["t%d" % i for i in range(rng.randint(1, 9))]
    locks = ["L%d" % i for i in range(rng.randint(1, 9))]
    holder = {l: rng.choice(threads) for l in locks if rng.random() < 0.8}
    waiting = {}
    for t in threads:
        options = [l for l in locks if holder.get(l) != t]   # never waits on its own lock
        if options and rng.random() < 0.7:
            waiting[t] = rng.choice(options)
    graph = wait_for_graph(holder, waiting)
    cycles, stuck = find_deadlocks(graph)
    ok &= stuck == drain(holder, waiting)              # brute force: run it and see
    def returns(t):                                    # brute force: does t reach itself?
        at = graph.get(t)
        for _ in range(len(graph)):
            if at == t:
                return True
            at = graph.get(at)
        return False
    ok &= sorted(t for ring in cycles for t in ring) == sorted(filter(returns, graph))
    for ring in cycles:                                # one victim per ring
        holder, waiting = abort(holder, waiting, rng.choice(ring))
    ok &= drain(holder, waiting) == set()              # everyone else now finishes
print(ok)                                              # True

The complexity

• Building the graph: O(W) for W waiting threads, from the holder and waiter tables.
• Detection: O(T) for T threads with one arrow each, since every thread is marked once; O(T + E) for a general graph with E wait edges.
• When to run it: on every block (immediate, but paid on each wait) or after a wait exceeds a threshold, which keeps the common uncontended case free.

Where it goes wrong

• Aborting a bystander. It frees nothing the ring needs; pick a ring member.
• Treating timeouts as detection. A timeout cannot tell a deadlock from a slow holder: it fires on healthy waits or leaves real deadlocks stuck until it expires.
• No retry path. The victim is rolled back; the caller must retry, with jittered backoff.
• Pointer-following with shared locks. One waiter can depend on several holders; use a full cycle search.
• Detecting what ordering would prevent. In your own code, a consistent lock order is cheaper than detection; see the four conditions and lock ordering.

When it shows up in interviews

As "how would you detect a deadlock?" after the four-conditions question, in database rounds ("what happens when two transactions deadlock?"), and as a graph problem in disguise: given lock ownership and requests, report the deadlocked threads. It pairs with race conditions and mutexes.

How to say it in an interview

"I'd build a wait-for graph: an edge from each blocked thread to the thread holding the lock it wants. A deadlock is exactly a cycle. With exclusive locks each thread has one outgoing edge, so I follow pointers and mark visited threads, which is linear; with shared locks I'd use a colouring DFS. Threads whose chain falls into a cycle are stuck but aren't the cause. To resolve it I abort one cycle member, usually the one with least work, roll it back so it releases its locks, and have the caller retry with backoff. In my own code I'd rather prevent it with a global lock order."