Deadlock¶

What a deadlock is¶

A deadlock is a set of threads (or processes, or transactions), each waiting for a resource held by another member of the set, so that none can ever proceed. Nothing crashes and nothing is logged: the program simply stops making progress, with its threads asleep and CPU usage at zero.

The four necessary conditions¶

Coffman et al. (1971) showed a deadlock can occur only if all four hold at once:

Every deadlock-prevention technique breaks one of these. The most practical one, by far, is breaking circular wait.

Prevention 1: a global lock order¶

If every thread acquires locks in the same global order, no cycle can form: a thread holding a lock can only wait for a lock that comes later in the order, and the last lock in any chain waits for nothing.

// Transfer between two accounts: lock in a canonical order, not "from, then to".
func Transfer(from, to *Account, amount int64) {
    first, second := from, to
    if to.ID < from.ID {
        first, second = to, from
    }
    first.mu.Lock()
    defer first.mu.Unlock()
    second.mu.Lock()
    defer second.mu.Unlock()
    from.Balance -= amount
    to.Balance += amount
}

Without the ordering, Transfer(a, b) and Transfer(b, a) running concurrently deadlock: each takes its from lock and waits for the other's. Ordering by ID makes both take min(a,b) first. A real goroutine dump of the unordered version — two goroutines in [sync.Mutex.Lock] with their account arguments swapped — is in Panics, Stack Dumps, and Delve.

In larger systems, the order is a documented hierarchy of lock levels: "the DB mutex before any cache shard lock; a cache shard lock before nothing." Debug builds can enforce it: each thread records the levels it holds, and acquiring a lock with a level lower than one already held aborts with both stacks. Some lock libraries detect potential lock-order inversions dynamically, even if no deadlock actually occurred in that run (Abseil's Mutex does; in Go, wrappers such as github.com/sasha-s/go-deadlock record lock order in tests).

When no order can be imposed, a goroutine can take the first lock and TryLock the second, releasing both and retrying (with backoff) if the second is busy — sync.Mutex.TryLock exists for such rare cases.

Prevention 2: don't hold locks across unknown code¶

Most real deadlocks are not two locks taken in visibly opposite order in one file. They involve a lock taken indirectly:

• calling a callback, a virtual function, or a user-supplied comparator while holding a lock — the callee takes another lock, or calls back into the object;
• logging while holding a lock, when the logger has its own lock and some other thread logs while holding yours;
• a destructor run under a lock that acquires a different lock.

The rule: hold a lock only around code you control and can see. Copy what you need, release the lock, then call out. LevelDB's DBImpl releases its mutex before doing I/O or calling into code that might block for exactly this reason.

Self-deadlock¶

Go's sync.Mutex is not reentrant: a goroutine that locks a mutex it already holds waits for itself forever. It happens when a method that takes the lock calls another method that also takes it. The usual fix is a private fooLocked() variant whose name documents that the caller must hold the lock, called by both. Go deliberately has no recursive mutex: needing one usually means the invariants the lock protects may be temporarily broken when the inner call runs.

Condition variables are another source: waiting on a condition that only this goroutine could ever make true, or a Signal sent before the waiter began waiting without a condition to re-check (a lost wakeup, prevented by always calling Wait in a for !condition loop). With channels, the equivalent is a send that no receiver will ever take, or a receive on a channel nobody will close.

Deadlocks beyond mutexes¶

The four conditions apply to any resource:

The thread-pool case is the most common in storage engines: never block a pool thread waiting for work queued on the same pool. Give dependent work its own pool (RocksDB separates flush and compaction pools), or make the waiting step asynchronous.

Avoidance: Banker's algorithm¶

Avoidance grants a request only if the system stays in a "safe state" — one where some order exists in which every thread can finish given its declared maximum needs. Dijkstra's Banker's algorithm checks this before each allocation. It requires knowing every thread's maximum resource needs in advance, so it is a textbook concept rather than something general-purpose software uses; resource admission control (refusing a query that might exceed memory) is its practical cousin.

Detection and recovery¶

When prevention is impractical, detect deadlocks and break them. This is what databases do, because transactions lock rows in an order determined by user queries.

• Build the wait-for graph: an edge T1 → T2 when T1 waits for a lock T2 holds. A cycle is a deadlock.
• PostgreSQL checks for cycles only after a lock wait exceeds deadlock_timeout (default 1 s) — most waits resolve on their own, and graph search is costly — then aborts one transaction with ERROR: deadlock detected.
• InnoDB checks immediately on each lock wait (configurable with innodb_deadlock_detect) and rolls back the transaction with the fewest changes.
• Many systems instead use lock timeouts: give up after N ms and abort (RocksDB TransactionDB defaults to timeouts; its cycle detection is optional). Simpler, but a timeout cannot distinguish a deadlock from a slow holder.

Recovery means aborting a victim and having the client retry. Applications using database transactions must therefore treat deadlock/serialization errors as retriable. See Locking and Concurrency.

Diagnosing a hung process¶

A deadlock looks like a hang with zero CPU. Capture every thread's stack:

gdb -p <pid> -batch -ex "thread apply all bt" > stacks.txt    # Linux
lldb -p <pid> --batch -o "bt all" > stacks.txt                # macOS
kill -QUIT <pid>        # Go: dumps all goroutine stacks to stderr
jstack <pid>            # Java: prints stacks and reports found deadlocks

Look for threads blocked in pthread_mutex_lock / __lll_lock_wait / futex_wait, note which lock (the mutex address argument) each waits for and which locks each holds (from the frames above), and draw the cycle. Go's runtime detects the special case where all goroutines are blocked and crashes with fatal error: all goroutines are asleep - deadlock!. ThreadSanitizer reports lock-order inversions — potential deadlocks — even in runs that happened not to hang.

Livelock and starvation¶

Common pitfall¶

Only ordering the locks a developer remembers exist. A third, less-obvious lock — a mutex inside a library call, a lock in the logging framework, a database row lock acquired indirectly through an ORM — can participate in the same cycle and still deadlock. Global lock ordering works only if it is genuinely global, covering every lock a code path can acquire. That is why the database version of this problem recommends sorting IDs before locking rather than "remembering the right order," and why systems that take lock ordering seriously enforce it mechanically (lock levels checked in debug builds, Clang thread-safety annotations, TSan's inversion detector) rather than by convention.