Mutex Deadlock Simulator: two threads, two locks, one cycle.

Coffman's conditions — all four must hold

Break any one and deadlock is impossible.

Deadlock requires four simultaneous conditions, identified by E. G. Coffman in 1971. Memorise them; every deadlock-prevention strategy works by violating at least one.

1. Mutual exclusion

At least one resource is held in non-shareable mode. If the resource could be shared, no deadlock — every reader gets it. Reader-writer locks, immutable data, copy-on-write data structures all eliminate deadlock for read-only access.

2. Hold and wait

A thread holds at least one resource and is waiting for another. If threads acquire all resources at once (or none), they can't deadlock. This is the basis of "two-phase locking" in databases: acquire everything in phase 1, run in phase 2, release in phase 3.

3. No preemption

Resources can't be forcibly taken; they must be released by the holder. If the OS or runtime can preempt a lock (steal it from a thread), the cycle breaks. Java's Thread.interrupt(), Rust's poison-on-panic, and Go's context-cancellation provide forms of preemption.

4. Circular wait

A cycle exists in the wait-for graph: T1 waits for T2, T2 for T3, ..., Tn for T1. If the graph is acyclic (e.g., by enforcing a global lock order), no deadlock is possible.

The simulator above breaks circular wait when you switch to "A→B / A→B" mode. It breaks hold-and-wait when you switch to try-lock (the thread releases locks instead of holding while waiting). Real production systems usually attack circular wait — it's the most amenable to code review and static analysis.

The graph that exposes the problem

The wait-for graph is the single most useful abstraction for reasoning about deadlock. Nodes are threads; an edge from T1 to T2 means "T1 is waiting for a resource held by T2." A cycle in the graph means deadlock.

Real databases (Postgres, MySQL's InnoDB) build this graph periodically and run cycle detection. When a cycle is found, they pick a victim — usually the transaction with the least work done — and abort it, letting the others proceed. The victim is rolled back and can be retried by the application.

The OS doesn't usually do this. Application threads don't have transactional rollback, so if a deadlock forms the process just hangs forever (or until the watchdog times out). This is why deadlock prevention is the engineering goal for application-level locking; deadlock detection is for systems that can recover.

Hold-for graph variants

The dual is the resource-allocation graph: nodes are threads and resources; edges show which thread holds (or waits for) which resource. Cycle detection works the same way. Useful when there are many resources with different multiplicities; less common in mutex-only systems.

Drawing it for debugging

When you suspect a deadlock in production, get a thread dump (jstack for JVM, py-spy dump for Python, SIGQUIT for Go, gdb thread apply all bt for native). Each thread shows what it holds and what it's waiting on. Draw the graph by hand. The cycle pops out.

Three techniques that actually work in production

Global lock order (by address)

Every acquisition of multiple locks happens in the same sorted order, usually by memory address. Linux kernel does this; Java's lock ordering pattern does this. Code: if (&a < &b) { lock(a); lock(b) } else { lock(b); lock(a) }. The address comparison gives a total order; no cycle can form.

Limitations: requires you can sort the locks. Recursive structures (linked lists, trees) where you traverse can't sort upfront; you need to acquire as you discover. Tools like lockdep (Linux kernel) detect ordering violations at runtime.

Try-lock with backoff and jitter

Don't block on lock acquisition. If try_lock fails, release everything held and retry after a randomised delay. Postgres SAVEPOINT-and-retry, Redis WATCH, optimistic concurrency control in databases all use this pattern.

Risks: livelock if all threads always retry simultaneously. The fix is jitter — exponential backoff with random multiplier. Pattern: delay = base * 2^retries * random(0.5, 1.5).

Deadlock detection (with victim selection)

Periodically build the wait-for graph; on cycle, kill the victim. Postgres deadlock_timeout (default 1s); MySQL InnoDB deadlock detector runs every wait event. Victim picked by: least work done (Postgres), youngest transaction (some), explicit priority.

Requires the system to support transactions or some other rollback mechanism. Applications using bare mutexes don't have this — they have to prevent.

Lock-free data structures

Skip locks entirely; use compare-and-swap loops. No locks = no deadlock. Java's ConcurrentLinkedQueue, Go's sync/atomic, C++ atomics. Trade-off: complex to design correctly; ABA problem; memory ordering subtleties; harder to reason about than locks.

Coarse-grained locking + asynchrony

One global lock for shared mutable state; serialise everything through it. Then use queues and async messages between subsystems to keep latency down. The actor model (Erlang, Akka, Pony) takes this to the extreme — one mailbox per actor, no shared state, no locks, no deadlock by construction.

How real deadlocks happen

Bank transfer between two accounts

The canonical example. Two threads each transferring money between the same pair of accounts; one locks acct(A) then acct(B), the other locks acct(B) then acct(A). The fix: always lock the account with the lower id first.

UI thread + worker thread

UI thread holds the UI lock and calls into the worker; worker thread holds the worker lock and calls back into the UI. Both blocked. Classic in Java Swing and early Cocoa apps. The fix: never call cross-subsystem while holding a lock; always queue.

Logging while holding a lock

You hold lock X, log a message, the logger acquires lock Y (its mutex). Another thread holds Y, tries to log, takes X. Deadlock. The fix: log outside the critical section, or use a lock-free logger.

Reentrant lock vs recursive call

std::mutex in C++ is not reentrant — locking it twice from the same thread deadlocks instantly. Use std::recursive_mutex if you need it; better, restructure to not need it. Java's ReentrantLock is reentrant by default; Python's threading.RLock too.

Database row-locking + foreign key cascades

Two transactions update rows in tables connected by FK. The FK check may require a lock on the parent row, which is held by the other transaction. Postgres surfaces these as deadlock detected; InnoDB rolls back the victim.

Distributed deadlock

Two services holding locks in each other's databases. Hard to detect because no single wait-for graph exists. The fix is usually saga pattern: replace distributed transactions with a sequence of local transactions plus compensations on failure.

async/await + sync mutex

Modern hazard. Holding a sync mutex across an await point in async code. While suspended, another task on the same thread tries to acquire the same lock. Single-threaded deadlock. The fix: don't hold sync locks across awaits; use an async-aware Mutex (tokio::sync::Mutex in Rust, asyncio.Lock in Python).

Finding deadlocks before they hit prod

Linux kernel: lockdep

Built into the kernel (CONFIG_LOCKDEP). Records every lock acquisition and the order; detects ordering violations and reports the cycle before it deadlocks. Pioneered the at-runtime ordering checker; the model has been ported to other systems.

Java: jstack and jcmd

jstack <pid> dumps all thread stacks. The JVM annotates threads with their lock state; jstack identifies deadlocks and prints the cycle explicitly. Critical for diagnosing hung Java services in production.

Go: runtime detection

The Go runtime detects when all goroutines are blocked and panics with "all goroutines are asleep — deadlock!". Only catches the all-blocked case; doesn't catch partial deadlocks (some goroutines deadlocked, others running). Use the race detector (-race) and lock-order checkers (third-party like sasha-s/go-deadlock).

Rust: parking_lot deadlock detection

parking_lot::deadlock::check_deadlock() runs cycle detection on the global lock graph. Run periodically from a watchdog thread; logs cycles. Production-ready.

Python: faulthandler + py-spy dump

py-spy dump --pid <pid> shows current stacks of all threads. faulthandler.dump_traceback() can be triggered on SIGUSR1. Combined with threading.enumerate() showing which threads hold which locks, you can reconstruct the wait-for graph.

Postgres: pg_locks and pg_stat_activity

SELECT * FROM pg_locks WHERE NOT granted; shows blocked queries. JOIN with pg_stat_activity to see what they're trying to do. The deadlock detector logs the victim and the cycle to the server log.

Helgrind and ThreadSanitizer

Helgrind (part of Valgrind) and TSAN (in clang and gcc) detect lock ordering violations and races at runtime. Slow (3-10x); use in CI on test workloads. Catches many bugs that don't trigger in normal testing.

When the database is the one that deadlocks

Database engines have their own lock subsystem and their own deadlock detector. Application code rarely has to think about these directly, but understanding them matters because they show up as "transaction was deadlocked on lock resources" errors in production.

Row-level locking

Modern engines lock individual rows (or pages) rather than whole tables. UPDATE/DELETE acquire write locks; SELECT FOR UPDATE acquires write locks for read; SELECT acquires no locks under MVCC (it reads from snapshot). The granularity prevents most contention but allows fine-grained deadlocks.

Index locks

Updates to a row may require updates to multiple indexes — and acquiring locks on each. If two transactions update the same row and the same indexes in different orders, deadlock. Single index = no issue; multiple indexes = potential trouble.

Gap locks (InnoDB)

MySQL's InnoDB locks not just rows but gaps between rows to prevent phantom reads at the REPEATABLE READ isolation level. Gap locks cause more deadlocks than necessary; many shops drop to READ COMMITTED to avoid them.

Postgres deadlock_timeout

Postgres waits this long (default 1 second) before running the deadlock detector. Lower it for latency-sensitive workloads — but the detector itself takes some time, so don't go too low.

Application-side handling

Catch the deadlock-detected error code (SQLState 40P01 in Postgres, 1213 in MySQL) and retry the transaction. The driver may or may not do this automatically; check. If the same transaction deadlocks repeatedly, there's a logic problem that retry won't fix.

When the cycle spans network boundaries

Distributed systems can deadlock across services. Service A holds a lock in its database; calls service B; service B holds a lock in its database and calls service A. No single wait-for graph; no detector. The system hangs until timeouts fire.

Solution 1: avoid distributed transactions

Saga pattern: a long-running business transaction is a sequence of local transactions, each with a compensating action. If step 3 fails, run steps 2-comp and 1-comp. No locks held across services; no distributed deadlock. This is the dominant pattern in modern microservice architectures.

Solution 2: distributed mutexes with timeouts

Use a shared mutex (Redis Redlock, Zookeeper, etcd) with a TTL. If the holder dies or hangs, the lock expires and another acquirer succeeds. Not perfect (the holder may complete after the lock expired), but avoids permanent hang.

Solution 3: global ordering by domain key

Across services, lock resources in a deterministic global order based on a domain key (user ID, order ID). Every service acquires locks for a multi-resource operation in the same order. Hard to enforce but eliminates cycles by construction.

Solution 4: chains, not cycles

Structure the system so calls always flow in one direction (frontend → backend → database, never back). Cycles in the service-call graph are deadlock hazards. Use queues and async messages to break call-back patterns.

The lesson: distributed deadlock is a system-design problem more than a code problem. The architectural choices you make about service interaction patterns determine whether deadlocks are even possible.

The deadlock and three fixes

The bug (Python)

import threading, time

lock_a = threading.Lock()
lock_b = threading.Lock()

def t1():
    with lock_a:
        time.sleep(0.01)
        with lock_b:
            print('T1 has both')

def t2():
    with lock_b:
        time.sleep(0.01)
        with lock_a:
            print('T2 has both')

# Both threads deadlock when run concurrently.

Fix 1: global lock order (Python)

def t2_fixed():
    with lock_a:                       # same order as t1
        time.sleep(0.01)
        with lock_b:
            print('T2 has both')

Fix 2: try-lock with backoff (Go)

var mu1, mu2 sync.Mutex

func t2() {
    for {
        if mu2.TryLock() {
            if mu1.TryLock() {
                // do work
                mu1.Unlock()
                mu2.Unlock()
                return
            }
            mu2.Unlock()
        }
        time.Sleep(time.Duration(rand.Intn(10)) * time.Millisecond)
    }
}

Fix 3: lock by address (C++)

void transfer(Account& a, Account& b, int amount) {
    std::unique_lock<std::mutex> lk1, lk2;
    if (&a < &b) {
        lk1 = std::unique_lock(a.mu);
        lk2 = std::unique_lock(b.mu);
    } else {
        lk1 = std::unique_lock(b.mu);
        lk2 = std::unique_lock(a.mu);
    }
    a.balance -= amount;
    b.balance += amount;
}

Fix 4: std::scoped_lock (C++17)

void transfer(Account& a, Account& b, int amount) {
    std::scoped_lock lk(a.mu, b.mu);   // acquires both deadlock-free
    a.balance -= amount;
    b.balance += amount;
}

std::scoped_lock uses a deadlock-avoiding algorithm internally (lock once, try-lock the rest, release and retry on contention). The cleanest C++ fix.

The other things that go wrong

Livelock

Threads aren't blocked but make no progress because they keep reacting to each other. Classic: two people in a corridor each stepping aside the same way. Try-lock retry without jitter is the textbook trigger. Fix: randomised backoff.

Starvation

One thread never gets the lock because others keep getting it first. Reader-writer locks with reader priority can starve writers; LIFO scheduling can starve old jobs. Fix: fair locks (FIFO queue of waiters), aging, priority inheritance.

Priority inversion

Low-priority thread holds a lock; high-priority thread waits; medium-priority thread runs (because high is blocked). The high-priority thread is effectively running at low priority. Solution: priority inheritance (the lock holder temporarily inherits the highest waiter's priority). Famously caused the Mars Pathfinder bug in 1997.

Convoying

Multiple threads serialise on a hot lock; throughput collapses. Fix: shard the lock (one lock per partition), use lock-free structures, or reduce critical section size.

Lock contention scaling

As cores grow, a hot mutex becomes the bottleneck — CPUs spend most cycles in lock acquisition. Use sharded locks, reader-writer locks, RCU, or transition to lock-free.

False sharing

Not a deadlock but adjacent. Two variables in the same cache line, modified by different threads; each modification invalidates the line on the other core. Solution: pad the data to cache-line boundaries (typically 64 bytes).

Lost wakeup

Condition variable patterns done wrong. Thread A signals before thread B starts waiting; B never wakes. Always check the predicate in a loop and signal under the lock.

Order-of-magnitude costs

The takeaway: uncontended mutexes are nearly free. Contention is the killer. Lock-free is usually faster than contended locks but slower than uncontended ones. Profile before optimising.

Common interview prompts

"What's a deadlock and how do you prevent it?"

Define: two or more threads, each waiting for a lock the other holds, in a cycle. Mention the four Coffman conditions briefly. Prevention: global lock ordering (most common, easy to enforce), try-lock with backoff (when ordering impossible), avoid hold-and-wait by acquiring all at once, prefer immutable / lock-free structures.

"What's the difference between deadlock, livelock, and starvation?"

Deadlock: threads blocked on each other; no progress; no CPU use. Livelock: threads running but making no progress because they keep reacting to each other; high CPU. Starvation: some thread can run but never gets to (always loses the lock race). All three break liveness; only deadlock is detectable by cycle search.

"How would you implement a deadlock detector?"

Build a wait-for graph: for each blocked thread, an edge to the thread holding the resource it's blocked on. Run cycle detection (DFS with three-color marking, or Tarjan SCC). On cycle, pick a victim (least work done, or youngest, or explicit priority) and roll it back. Schedule periodically — Postgres does it on every lock acquisition after a timeout.

"Why are databases more tolerant of deadlock than OS threads?"

Databases have transactions, which provide rollback. The detector can kill a transaction without corrupting the system; the application retries. Application threads have no rollback — killing one mid-execution leaves shared state in an inconsistent state. So OS-level deadlock is fatal; DB-level deadlock is a slow path.

"How do you debug a hang in production?"

Get a thread dump (jstack, py-spy dump, SIGQUIT for Go, gdb thread apply all bt). Identify threads in WAITING / BLOCKED state. For each, see what they're waiting on. Build the wait-for graph by hand. Look for cycles. If found, you have your deadlock. If not, it might be a single hung thread (waiting on I/O, network, etc.).

"Why is std::mutex not reentrant?"

Reentrancy carries a cost (counter and owner tracking) and hides bugs (recursive code that holds a lock too long doesn't get caught). C++ design favours making the cost explicit; if you need reentrancy, use std::recursive_mutex. Most code shouldn't need reentrancy — restructure to acquire once at the top.

"What's a fair lock?"

One that grants the lock in the order threads requested it (FIFO queue of waiters). Without fairness, the same thread can repeatedly re-acquire while others starve. Java ReentrantLock(true), Linux PI futexes, pthread mutexes with PRIO_PROTECT all offer fairness. Trade-off: fair locks are slower (more bookkeeping).

Terms used above, defined

Mutex — mutual-exclusion lock. Held by at most one thread at a time.

Reader-writer lock — multiple readers OR one writer. Faster for read-heavy workloads.

Spinlock — lock implemented by busy-waiting (loop on CAS). Fast when contention is brief; wasteful otherwise.

Futex — Linux fast userspace mutex. Fast path stays in userspace (atomic ops); slow path enters kernel for waitqueue.

Atomic / CAS — single-instruction compare-and-swap. The building block of lock-free.

Reentrant lock — can be acquired multiple times by the same thread without deadlocking.

Wait-for graph — directed graph of "thread X is waiting for resource held by Y." Cycle = deadlock.

Coffman conditions — mutual exclusion, hold-and-wait, no preemption, circular wait. All four needed for deadlock.

Lock ordering — global rule that all threads acquire locks in the same sorted order. Prevents circular wait.

Try-lock — attempt to acquire; if not immediately available, return without blocking.

Deadlock detection — algorithm that builds the wait-for graph and finds cycles; usually paired with victim selection.

Victim — the thread (or transaction) chosen to abort/kill to break a deadlock cycle.

Livelock — threads running but making no progress, often from synchronised retry patterns without jitter.

Starvation — a thread is repeatedly losing the lock race and never makes progress.

Priority inversion — high-priority thread blocked behind low-priority lock holder while medium-priority threads run. Fix: priority inheritance.

Lock-free — algorithm guarantees system-wide progress even if individual threads stall. Uses CAS, not locks.

Wait-free — stronger than lock-free. Each thread makes progress in bounded steps regardless of others.

RCU — Read-Copy-Update. Linux kernel lockless read-side synchronisation; writers swap pointers, old readers retire on grace period.

MVCC — Multi-Version Concurrency Control. Database readers see a snapshot, never block writers, never deadlock with writers.

Two-phase locking — acquire all locks in phase 1, work in phase 2, release in phase 3. Prevents hold-and-wait.

Optimistic concurrency — work first, validate at commit (CAS-like). Used in some DBs and in CRDT systems.

Pessimistic locking — acquire locks upfront. The standard mutex model.

Lockdep — Linux kernel runtime checker for lock ordering violations.

ThreadSanitizer (TSAN) — Clang/GCC instrumented runtime that detects data races and lock ordering issues.

Try these on the simulator and in code

1. In the simulator, run the default "deadlock" scenario. Watch the wait-for graph form a cycle. Click "kill T2" to break it.

2. Switch to "A→B / A→B (fixed)" mode. Run. Both threads complete. The cycle never forms because the wait-for graph is acyclic by construction.

3. Switch to "try_lock" mode. Watch threads release and retry instead of blocking. No deadlock — at the cost of repeated work.

4. Write a bank-transfer function in Python. Two threads, each transferring between the same pair of accounts (one A→B, one B→A). Verify the deadlock with thread dumps. Fix using address ordering.

5. In Go, write two goroutines with sync.Mutex that deadlock. Run with go run -race. The race detector won't catch the deadlock per se but will flag the underlying ordering issue if you also have a race.

6. In C++, replace your manual lock(a); lock(b); with std::scoped_lock(a, b). Confirm no deadlock even when threads use different argument orders. Read the std::scoped_lock implementation.

7. In Postgres, create two transactions in two psql sessions; have each lock different rows then try to lock the other's. Watch the deadlock detector kill one after ~1 second. Note the error code (40P01) for application-side retry.

8. Read the lockdep documentation in the Linux kernel source. Understand how it catches ordering violations at runtime even when no deadlock actually forms. This is the gold standard of lock-debugging tooling.

9. Read the parking_lot::deadlock module in Rust. Build a tiny example that uses parking_lot with periodic deadlock checks. Watch a cycle get detected and logged.

10. Design a distributed deadlock scenario across two HTTP services. Implement a fix using saga pattern (compensating actions on failure). The system-design skill is recognising that distributed deadlock is best avoided by avoiding distributed transactions.

Sixty years of fighting deadlock

Edsger Dijkstra introduced the semaphore in 1965 and immediately ran into deadlock — the dining philosophers problem he posed in 1971 is the canonical example. His solution introduced the idea of acquiring resources in a global order (by philosopher index).

E. G. Coffman identified the four necessary conditions in 1971; this remains the framework for reasoning about deadlock prevention. Every modern technique violates one of the four.

The first deadlock detectors appeared in OS research in the late 1960s — the Banker's algorithm (Dijkstra again) for prevention via deadlock-avoidance, and graph-based detection for recovery. Production databases adopted the detection approach starting with System R.

Lockdep in the Linux kernel (Ingo Molnár, ~2006) was a breakthrough — runtime lock-ordering validation without deadlock having to actually form. The system records every lock acquisition and the order; flags violations the first time they happen. Has caught thousands of bugs.

Modern lock-free data structures (Java's java.util.concurrent, Go's sync/atomic, Rust's crossbeam) sidestep the problem entirely. The trend is to provide both: high-level locks for ease of use, lock-free primitives for hot paths.

The current frontier is async/await deadlocks — sync mutexes held across await points in async code can deadlock on a single thread. Async-aware mutexes (tokio::sync::Mutex, asyncio.Lock) and async-aware deadlock detectors (Rust's tokio-deadlock) are early-stage but maturing.

The core five

1. Deadlock = cycle in the wait-for graph. All deadlocks reduce to this.

2. Coffman's four conditions are all necessary; break any one and deadlock is impossible.

3. Global lock ordering is the most-used prevention strategy in application code.

4. Databases use detection + victim rollback; OS uses prevention because rollback isn't available.

5. Don't hold mutexes across calls that might call back, log, or await.

Internalise those and you can follow almost any concurrency bug discussion. The rest is detail.

Recommended next steps

The Little Book of Semaphores by Allen Downey. Free PDF, 300 pages. Every classic synchronization problem with solutions. The single best learning resource.

The Art of Multiprocessor Programming by Herlihy and Shavit. The textbook for lock-free data structures and concurrent algorithms. Demanding but worth it.

Java Concurrency in Practice by Brian Goetz. Pre-dates lambdas and modern Java but the concurrency principles are timeless. Read for the patterns, not the syntax.

Linux Kernel Development by Robert Love. Chapter on kernel synchronization is the clearest description of mutex/spinlock/RCU trade-offs anywhere.

Dining Philosophers (Dijkstra, 1971). Read the original problem statement. It's short.

Mars Pathfinder priority inversion postmortem. Glenn Reeves' write-up. Real-world deadlock-adjacent bug that shipped to Mars.

Bookmark this page. Return when EXPLAIN or jstack confuses you. The skill compounds.

The sim above shows the smallest possible deadlock. Real ones span more locks and more threads. But every one reduces to a wait-for cycle. Recognise the shape and the fix follows.

— end of page —

Dijkstra's parable, demystified

Five philosophers sit around a circular table. Between each pair is a single chopstick. To eat, a philosopher must hold both chopsticks adjacent to her. After eating, she puts them down and thinks until hungry again. If all five pick up the chopstick on their left at the same time, all five are blocked waiting for the chopstick on their right — classic deadlock.

The standard fixes are exactly the prevention strategies we've covered: a global order (each philosopher always picks up the lower-numbered chopstick first; one philosopher is forced to do the opposite, breaking symmetry); a waiter that arbitrates (only allows N-1 philosophers to attempt eating at once); try-lock and put-down on conflict. Each fix corresponds to violating one of Coffman's conditions.

The lesson isn't really about philosophers. It's that symmetric distributed protocols deadlock; breaking symmetry is the foundation of progress. Leader election, consistent hashing, lock-ordering by address all do the same thing in different guises.

The hidden lock acquisitions

Textbook deadlocks involve two threads explicitly grabbing two locks. Real production deadlocks rarely look like that. The locks are hidden behind library calls, garbage collection, logging, allocator pools, and condition variables. The cycle exists, but no developer wrote both halves of it.

Allocator deadlock

You hold lock X. You allocate memory inside the critical section. The allocator's per-thread cache misses; it takes the global heap lock. Another thread holds the heap lock and is now blocked trying to acquire X (perhaps via a signal handler or its own logging). Cycle. Fix: do allocations outside the critical section, or use arenas / object pools that don't share global state.

Logger deadlock

You hold X. You log a debug message. The logger acquires its mutex Y. Another thread holds Y while running a hook that calls into your subsystem and takes X. Cycle. Fix: log outside critical sections, or use a lock-free logger (atomic ring buffer with a draining thread).

Signal handler deadlock

A signal handler fires on a thread that currently holds a non-async-signal-safe lock (most locks are not async-signal-safe). The handler tries to acquire the same lock. Single-thread deadlock. Async-signal-safe functions are limited; printf is not async-signal-safe even though it usually works.

GC deadlock

Garbage collector pauses your thread mid-critical-section. Another thread runs a finalizer that takes a lock you hold. The collector waits for you to resume; you wait for the finalizer thread; the finalizer waits for the lock you hold. Cycle. Java's old finalizers were notorious for this; modern Java avoids using finalizers entirely.

Reentrant callback deadlock

You hold X, call into a callback or virtual method that user code provided. The user code takes X (it didn't know you held it). On a non-reentrant lock, instant deadlock; on a reentrant lock, you've broken invariants because the callback ran while X's data was being modified.

The pattern across all of these: lock acquisition during something that looks innocent. The fix is the same across all of them: never hold a lock across a call that could touch any other lock, allocator, logger, or callback. The discipline is harsh but the alternative is unrepeatable production hangs.

Three production deadlocks, named

The Pathfinder priority inversion (1997)

The Mars Pathfinder rover kept rebooting after landing. The cause: a high-priority data-management thread blocked on a mutex held by a low-priority meteorology thread, while medium-priority threads ran. Effectively the high-priority thread ran at low priority. The watchdog noticed missed deadlines and forced a reboot. The fix, uploaded from Earth: enable priority inheritance on the offending mutex via VxWorks parameters. The lesson — even with priority inheritance available, you have to actually turn it on, and your testing has to exercise the priority interactions.

Therac-25 (1980s)

Not strictly a mutex deadlock but a related race / timing bug. A hardware interlock that prevented the X-ray beam from being on at full intensity in setup mode was bypassed by a race in the software controller — a careful sequence of operator inputs could put the system in a state where the high-intensity beam fired without the proper attenuator in place. Multiple patients died. The case study is the most-cited example of how subtle concurrency bugs can have catastrophic consequences in safety-critical systems. Modern medical-device development is far more disciplined as a direct response.

Database transaction storms

An e-commerce backend that processed orders by acquiring row locks on the user, the product, and the inventory in inconsistent orders. Under normal load, deadlock-detector caught and rolled back perhaps one in a million. Under a flash sale, the deadlock rate climbed to dozens per second; users saw timeouts and the application thrashed retrying. The fix took two days: enforce a strict acquisition order (always lock by primary key, lowest first) across every transaction in the codebase. After the fix, deadlock rate dropped to near zero under any load.

Three different domains, same lesson: lock acquisition order matters, and the only way to enforce it consistently is to make it a code-review rule, not a hope.

Quick answers

"Can a single thread deadlock?"

Yes. Hold a non-reentrant mutex and call a function that tries to acquire it again — instant single-thread deadlock. Also: hold a mutex across an await point in async code; another task on the same thread tries to acquire it; the scheduler can't make progress.

"Does my language's runtime detect deadlocks?"

Go detects all-goroutines-blocked. Java's jstack identifies cycles when asked. Postgres / InnoDB detect cycles in their lock subsystem. Rust + parking_lot has an opt-in detector. C++/C have nothing standard — use tooling like Helgrind or TSAN. Python has no built-in detector; you read thread dumps and reason.

"Will async/await save me from deadlocks?"

No. Async code can deadlock too — most commonly when sync mutexes are held across await points. Use async-aware locks (tokio::sync::Mutex, asyncio.Lock) and the same care about lock ordering.

"Are lock-free data structures always faster?"

No. Uncontended, a mutex is ~25 ns and a CAS is ~10 ns — similar order. Lock-free wins under heavy contention because there's no thread sleeping/waking. Under low contention, the simpler mutex code is often faster overall. Profile before switching.

"Can I use timeouts instead of deadlock prevention?"

You can, but it's a worse strategy. Timeouts catch deadlocks late (after some delay) and don't fix the underlying ordering bug. They can also mask bugs that occasionally would have caused a deadlock — the system limps along until the failure conditions align and you hit a real one. Prefer prevention; use timeouts as a safety net.

"Why do databases use detection instead of prevention?"

Two reasons. First, database queries can lock arbitrary rows in arbitrary order based on user input — there's no easy way to enforce a global order across all possible queries. Second, transactions have rollback, so detection-then-victim works cleanly. Application threads without rollback can't recover from arbitrary kills, so prevention is the right strategy there.

"How do I write deadlock-free distributed systems?"

The honest answer: avoid distributed locks. Use sagas (sequence of local transactions with compensations); use single-writer designs (one service owns each piece of data; mutations go through that owner); use leases (acquire with TTL, lose if you can't refresh). Distributed mutexes are a smell; their correct use is hard and the failure modes are subtle.

"What's the simplest deadlock-free way to share data between threads?"

Don't share — communicate via channels or message queues. Go's "do not communicate by sharing memory; share memory by communicating." Actor systems take this to the extreme. When you do share, use immutable structures (no mutation = no lock) or single-writer patterns (only one thread mutates, others read).

From a hung JVM to the offending line of code

A Java service stopped serving requests. Load balancer marks it unhealthy after 30 seconds of no /health response. You SSH in, find the PID, run jstack. Output (abridged):

Found one Java-level deadlock:
=============================
"http-nio-8080-exec-3":
  waiting to lock monitor 0x00007f8a04003c28 (object 0x000000076bd5f4a0,
        a com.example.OrderService),
  which is held by "http-nio-8080-exec-7"

"http-nio-8080-exec-7":
  waiting to lock monitor 0x00007f8a04005d18 (object 0x000000076bd5f8c0,
        a com.example.InventoryService),
  which is held by "http-nio-8080-exec-3"

Java stack information for the threads listed above:
===================================================
"http-nio-8080-exec-3":
  at com.example.OrderService.updateInventory(OrderService.java:142)
  - waiting to lock <0x000000076bd5f4a0> (a com.example.OrderService)
  at com.example.InventoryService.reserveStock(InventoryService.java:78)
  - locked <0x000000076bd5f8c0> (a com.example.InventoryService)
  at com.example.CheckoutController.placeOrder(CheckoutController.java:55)

"http-nio-8080-exec-7":
  at com.example.InventoryService.releaseStock(InventoryService.java:103)
  - waiting to lock <0x000000076bd5f8c0> (a com.example.InventoryService)
  at com.example.OrderService.cancelOrder(OrderService.java:201)
  - locked <0x000000076bd5f4a0> (a com.example.OrderService)
  at com.example.RefundController.refund(RefundController.java:34)

Read the cycle: thread exec-3 holds InventoryService, wants OrderService. Thread exec-7 holds OrderService, wants InventoryService. The placeOrder path locks Inventory then Order; the refund path locks Order then Inventory. Two HTTP requests, two endpoints, opposite acquisition orders. Classic.

The fix lives in source. CheckoutController.placeOrder at line 55 calls InventoryService.reserveStock (which synchronises on InventoryService) and that method calls OrderService.updateInventory (which synchronises on OrderService). RefundController.refund does it the other way. Pick one order — say, always Order before Inventory — and refactor refund to grab the OrderService monitor first.

Better: get rid of the cross-service synchronised methods entirely. Move the shared state into a database row with a primary key; let the database row-locking and its deadlock detector handle ordering. The synchronized keyword on service classes is almost always wrong in a multi-request server — it serialises every request that touches the service through one monitor.

This is the shape of every production deadlock investigation: stack dump, identify the cycle, find the source lines, decide whether to reorder or to remove the locks entirely. Most of the work is in the last step.

What to run when a service hangs

The common workflow for any of these: take the dump while the hang is live (don't restart the process — you'll lose the evidence), identify threads in BLOCKED / WAITING state, map each thread's wait target to the holder, build the wait-for graph, look for a cycle. If you find one, the two threads at the cycle point you straight at the offending call sites.