Deadlock

Definition: A state where a set of concurrent processes or threads are permanently blocked because each holds a resource needed by another, forming a cycle of unresolvable waiting.

How It Works

Requires all four Coffman conditions simultaneously: Mutual Exclusion (resources can’t be shared concurrently), Hold and Wait (a process holds one resource while waiting for another), No Preemption (resources can’t be forcibly taken away), and Circular Wait (a closed chain of processes each waiting on the next).
Detection uses a Resource Allocation Graph or wait-for graph: nodes are processes and resources, edges show “holds” and “waits for.” A cycle in this graph indicates deadlock, found with a cycle-detection traversal similar to Depth-First Search (DFS).
Deadlock Prevention breaks one of the four Coffman conditions structurally. Requesting all needed resources at once eliminates Hold and Wait; imposing a global lock ordering eliminates Circular Wait; allowing forced resource reclamation eliminates No Preemption.
Deadlock Avoidance (Banker’s Algorithm) simulates a resource request before granting it, checking whether the system stays in a “safe state,” one where some ordering of remaining process completions is still guaranteed possible, and only grants the request if so.
Deadlock Detection and Recovery lets deadlocks happen, periodically scans for wait-for cycles, then recovers by preempting a resource, rolling back a process to a safe checkpoint, or killing one process in the cycle (the “victim”) to break it.
Distributed transaction systems also use timestamp-based schemes to prevent circular wait without a global graph: Wait-Die (an older transaction may wait for a younger one, but a younger one requesting a resource held by an older one is aborted and restarted) and Wound-Wait (an older transaction preempts, “wounds,” a younger one holding a needed resource, while a younger one just waits for an older one), both guaranteeing no cycle can form since waits only ever flow in one direction relative to transaction age.

Under the Hood

The Banker’s Algorithm formalizes “safe state” with matrices: Allocation (resources currently held per process), Max (maximum resources each process may ever request), and Available (free resources). A request is granted only if, after tentatively granting it, there still exists some sequence of processes that can each finish using only their already-held resources plus what’s currently available, releasing their resources back into the pool as they finish, allowing the next process in the sequence to complete. If no such sequence exists, the state is unsafe and the request is denied or deferred, even if the resources are technically free right now. This is provably conservative: it can reject some requests that would never actually deadlock, in exchange for guaranteeing none of the ones it grants ever do.

Detection-and-recovery is the more common real-world choice, especially in databases, because prevention/avoidance requires knowing resource needs in advance (rarely true for ad hoc SQL transactions) and avoidance’s bookkeeping overhead scales poorly. A database engine instead lets transactions block on row/table locks, runs a background wait-for graph check on a timer or on each new block, and when it finds a cycle, picks a victim, usually the transaction with the least work invested (fewest log records, most recently started) to minimize wasted rollback, and aborts it, releasing its locks so the rest of the cycle can proceed.

At the OS level, the kernel itself generally does not run deadlock detection across arbitrary user-space mutexes, it has no visibility into what a pthread_mutex_t “means” to the application. What the kernel does track is which thread is blocked in a futex() wait and, for PTHREAD_MUTEX_ROBUST mutexes, whether the owning thread died while holding the lock, letting a new owner recover instead of blocking forever. General-purpose deadlock detection is left to the application layer (databases) or to external tooling that walks thread stacks and lock state after the fact.

Debugging Workflow

A hung multi-threaded process is the classic deadlock symptom: it’s still running (not crashed) but stops making progress and CPU usage drops near zero. The standard first step is a thread dump, a snapshot of every thread’s stack and blocking state:

$ gdb -p <pid>
(gdb) thread apply all bt
Thread 3: #0 futex_wait () #1 pthread_mutex_lock () #2 lock_b_then_a () ...
Thread 2: #0 futex_wait () #1 pthread_mutex_lock () #2 lock_a_then_b () ...

Two threads each blocked inside pthread_mutex_lock, each holding the lock the other is waiting for, is the signature to look for: read each thread’s stack to see which lock-acquiring function it’s stuck in, then cross-reference which lock each already holds. For Java, jstack <pid> does the same thing and explicitly prints Found one Java-level deadlock with the exact thread/lock cycle when it detects one. For a database, SHOW ENGINE INNODB STATUS (MySQL) or pg_locks/pg_stat_activity (PostgreSQL) surface the blocking transaction chain directly instead of requiring a manual stack-trace correlation.

Why It Matters

Unresolved deadlocks cause application freezes, thread pool exhaustion, database transaction hangs, and full system hangs that need manual intervention or a restart to clear.
Distributed systems must detect deadlocks across network boundaries, which is much harder than the single-machine case because no single node holds the complete global wait-for graph; algorithms like Chandy-Misra-Haas propagate probe messages between nodes to reconstruct it.
Database engines almost universally choose detection-and-recovery over prevention, since real workloads can’t declare their full resource needs upfront the way the Banker’s Algorithm requires.

Common Pitfalls

Acquiring multiple locks in different orders on different code paths (Thread A locks X then Y; Thread B locks Y then X) is the single most common real-world cause. Fixed by enforcing a global, consistent lock acquisition order across the whole codebase.
Holding a lock while making a blocking call, network request, disk I/O, or calling into unknown third-party code, dramatically widens the window during which a deadlock can form, since the lock stays held for an unpredictably long time.
Confusing deadlock with livelock: in a livelock, threads actively change state in response to each other (both repeatedly backing off and retrying) but still make zero real progress. It won’t show up as a static cycle in a wait-for graph because nothing is actually blocked.
Relying solely on lock timeouts as a fix, without addressing the root cause. Timeouts convert a deadlock into a livelock-like retry storm under contention instead of eliminating the underlying ordering problem.
Nested locking inside callback-based or event-driven code, where it’s easy to lose track of which locks are already held when a callback fires, reintroducing inconsistent lock order without it being visible in any single function.
Self-deadlock: a thread calling a function that tries to reacquire a non-reentrant lock the thread already holds, blocking on itself. Easy to introduce accidentally when a public API function and a private helper it calls both lock the same non-recursive mutex.

History

Edsger Dijkstra formulated the Banker’s Algorithm in 1965 as part of early work on the THE multiprogramming system, framing safe resource allocation as a banker deciding whether to extend a loan without risking insolvency.
The four Coffman conditions are named after Edward G. Coffman Jr., who co-authored the 1971 survey paper that formalized deadlock’s necessary conditions and the prevention/avoidance/detection taxonomy still taught today.
Database systems moved decisively toward detection-and-recovery through the 1970s-80s as transaction workloads grew too dynamic for avoidance-style upfront resource declarations to be practical.

FAQ

Can a deadlock resolve itself without intervention? No. By definition, every process in the cycle is permanently blocked; none of them can take the action needed to break the cycle on their own. Something external, a timeout, a detector, an operator, must intervene.

Is a deadlock the same as an infinite loop? No. An infinite loop keeps consuming CPU while making no useful progress; a deadlocked thread is blocked and consumes no CPU at all, just sits waiting on a lock or resource that will never become available.

Do all four Coffman conditions really need to hold? Yes, simultaneously. Breaking any single one of them, even while the other three remain true, is sufficient to make deadlock impossible for that specific resource-allocation pattern, which is exactly why prevention strategies each target just one condition.

Comparison

	Prevention	Avoidance (Banker’s)	Detection & Recovery
When it acts	Design time, structural	Before granting each request	After the fact, periodically
Needs advance resource knowledge	No	Yes (Max claims)	No
Runtime overhead	Low	High (safety check per request)	Moderate (periodic graph scan)
Can still deadlock	No	No	Yes, briefly, until detected
Typical use	Lock ordering conventions	Rare, real-time/embedded systems	Databases, OS kernels
Recovery cost	None (never happens)	None (never happens)	Rollback/kill of a victim process
Implementation complexity	Low to moderate	High (safety-state bookkeeping)	Moderate (periodic graph scan)

Real-World Example

A common production incident: a web application’s connection pool has a fixed size, and two request handlers each need two connections to complete a cross-table operation. Handler A grabs connection 1, then blocks waiting for connection 2 because the pool is exhausted; Handler B grabs connection 2, then blocks waiting for connection 1. Every other request queues up behind them since the pool never frees a connection. The fix mirrors the lock-ordering fix below: acquire all connections a transaction needs in one batch, or always request them in a fixed order, rather than acquiring them one at a time as the code happens to need them.

Example

Thread 1 holds Lock A and waits for Lock B; Thread 2 holds Lock B and waits for Lock A. Both freeze forever:

Thread 1: lock(A) -> [preempted] -> lock(B)   # blocks: B held by Thread 2
Thread 2: lock(B) -> [preempted] -> lock(A)   # blocks: A held by Thread 1

Enforcing a global rule, “always acquire locks in alphabetical/address order,” eliminates this specific deadlock by removing the possibility of Circular Wait entirely. In practice, tools like SHOW ENGINE INNODB STATUS in MySQL or Java’s jstack thread dumps surface the exact wait-for cycle (which thread holds what, which thread is blocked on what) so the offending lock order can be found and fixed.

Referenced by

Dig deeper

Spot an error in this note?