Deadlock

How a deadlock forms — Coffman's four conditions

Deadlock requires all four conditions to hold simultaneously:

1. Mutual exclusion. The resources can be held in a non-shareable mode. Two threads can't simultaneously hold the same exclusive lock.
2. Hold and wait. Threads can hold one resource while requesting another. They don't release everything to grab a single lock.
3. No preemption. Resources are released only voluntarily. The system can't yank a lock away from a thread (unlike CPU scheduling, which can preempt).
4. Circular wait. There's a cycle: thread A waits for B's resource, B waits for C's, ..., Z waits for A's.

Eliminating any single condition prevents deadlock. In practice, the easiest target is circular wait — that's why "lock ordering" is the dominant prevention strategy.

The dining philosophers problem

Five philosophers sit around a circular table. Each needs both adjacent forks to eat. There are 5 forks total — one between each pair.

// Naive — every philosopher does this:
acquire(left_fork);
acquire(right_fork);
eat();
release(right_fork);
release(left_fork);

If all five execute the first acquire simultaneously, each holds their left fork and waits for their right (which is the next philosopher's left). Circular wait. Deadlock.

Five solutions:

1. Lock ordering. Number forks 1-5; require each philosopher to acquire the lower-numbered fork first. The 5th philosopher (between fork 5 and fork 1) acquires fork 1 first — breaks the circular pattern.
2. Asymmetric philosophers. Most acquire left then right; one acquires right then left. Same effect as lock ordering.
3. Resource hierarchy. Both forks must be acquired atomically (one syscall, all-or-nothing). Eliminates hold-and-wait.
4. Referee. A waiter (semaphore initialized to 4) limits how many philosophers can try eating simultaneously. With at most 4 trying, at least one always has both forks available.
5. Optimistic with rollback. Acquire left, try acquire right. If right unavailable, release left and retry after a random delay (livelock-resistant via randomization).

Prevention strategies — break each condition

Condition broken	Strategy	Real-world example
Mutual exclusion	Use shared resources (read/write locks, lock-free data structures)	RCU in the Linux kernel; concurrent hash maps
Hold and wait	Acquire all needed locks atomically; release-and-retry on failure	Database two-phase locking with strict acquire-all-then-execute
No preemption	Allow timeouts; abort + restart on lock contention	Database deadlock detector kills victim transaction
Circular wait	Lock ordering — acquire in a globally consistent order	Linux lockdep validates this in kernel; standard practice in production code

Lock ordering is the most popular because it's verifiable statically (lockdep), preserves performance (no extra coordination), and doesn't require giving up exclusive locks.

Detecting deadlock at runtime

Build a wait-for graph — directed graph with one vertex per thread, edge from A to B if A is waiting for a lock held by B. Run cycle detection (DFS with three-color marking). Any cycle is a deadlock.

function detectDeadlock(waitForGraph) {
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Map();
  for (const t of Object.keys(waitForGraph)) color.set(t, WHITE);

  function dfs(t) {
    color.set(t, GRAY);
    for (const blocker of waitForGraph[t] || []) {
      if (color.get(blocker) === GRAY) return [t, blocker]; // cycle
      if (color.get(blocker) === WHITE) {
        const result = dfs(blocker);
        if (result) return result;
      }
    }
    color.set(t, BLACK);
    return null;
  }

  for (const t of color.keys()) {
    if (color.get(t) === WHITE) {
      const cycle = dfs(t);
      if (cycle) return cycle;
    }
  }
  return null;
}

Databases (PostgreSQL, MySQL InnoDB) run this periodically. On detection, kill the youngest or least-work-done transaction. Linux's lockdep does similar analysis in the kernel for kernel-level locks; reports any cycle as a CONFIG_PROVE_LOCKING warning at boot or runtime.

When deadlock typically strikes

• Database transactions with mixed lock orders. Two transactions update the same rows in different orders → wait-for cycle. The DB detects, kills one. Application retries. Fine in moderate doses; horrible at high contention.
• Multi-resource workflows. Code that acquires file lock, then DB lock, then network lock — versus other code path that acquires them in different order. Lock-ordering audits in code review prevent this.
• Producer-consumer with bounded buffers. Producer holds source lock waiting for buffer space; consumer holds buffer space waiting to acquire source. Use condition variables and proper signaling.
• Recursive locks held across callbacks. Thread A holds a lock and calls a function that asynchronously calls back into code that wants the same lock. Re-entrant mutexes help; better solution is to release the lock before invoking callbacks.
• Cross-process IPC with shared resources. Two processes that both lock files, message queues, semaphores. Deadlock detection often missing across process boundaries.

JavaScript: a deadlock-prone pattern (with mutex library)

// Using async-mutex library — typical deadlock scenario
const m1 = new Mutex();
const m2 = new Mutex();

// Thread A:
await m1.runExclusive(async () => {
  await m2.runExclusive(async () => { /* work */ });
});

// Thread B:
await m2.runExclusive(async () => {
  await m1.runExclusive(async () => { /* work */ });
});

// If both run simultaneously:
//   A holds m1, waits for m2
//   B holds m2, waits for m1
// Circular wait — deadlocked forever.

// Fix — establish a global order. Always acquire mutexes in (m1, m2) order:
// Thread A and Thread B both:
await m1.runExclusive(async () => {
  await m2.runExclusive(async () => { /* work */ });
});

Modern alternatives to traditional locking

• Lock-free data structures (CAS-based). No mutex; use compare-and-swap atomics for state changes. Concurrent queues, stacks, hash maps. ConcurrentLinkedQueue (Java), crossbeam (Rust). Deadlock-free by construction.
• Software transactional memory (STM). Wrap critical sections in transactions; runtime detects conflicts and rolls back losers. Clojure refs, Haskell STM. Popular in functional languages.
• Actor model. Each actor processes messages serially; no shared state means no locks. Erlang, Akka, Pony. Deadlock can still happen at the message-passing level (deadlock by waiting for a reply that depends on us replying first), but conventional locking deadlocks vanish.
• RCU (Read-Copy-Update). Readers proceed without locks; writers create a new version, atomically swap pointer. Used heavily in the Linux kernel. Super-fast reads; complex writes; relies on grace periods to free old data.

Common deadlock-related bugs

• Inconsistent lock acquisition order across the codebase. Even one path that acquires (B, A) when everyone else does (A, B) can create deadlock. Static analysis tools (Coverity, lockdep) help; manual code review is still essential.
• Holding a lock during long operations. Async I/O, network calls, slow disk reads — these increase the deadlock window dramatically. Refactor to release the lock before slow operations; re-acquire if needed.
• Calling user code under a lock. If your library holds a lock and invokes a user-supplied callback, the callback might re-enter your library and try to acquire the same lock. Either use re-entrant mutexes (and accept the complexity) or ensure callbacks are invoked outside the lock.
• Deadlock vs livelock confusion. Both block progress. Deadlock — threads stop. Livelock — they're active but spinning. Symptoms differ; diagnosis differs (live=high CPU, dead=zero CPU).
• Convoy effect — non-deadlock but related. Many threads waiting on a lock held by a slow operation. Throughput collapses even without deadlock. Often confused with deadlock; lockdep traces show what's actually held.
• Trying to detect deadlock in user code. Mostly futile in JS, Python, Java without specific runtime instrumentation. Better — use thread dumps in production (jstack, py-spy), look for threads blocked on locks held by other blocked threads.