# Deadlocks: The Four Conditions and the One Fix That Works

> Every deadlock requires four conditions to hold simultaneously, and every practical cure breaks exactly one of them. Why lock ordering is the fix that survives contact with real codebases, and how to find the cycle when it happens anyway.

URL: https://harshith.in/blog/deadlocks-in-practice/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: concurrency, systems, fundamentals

A deadlock is the politest catastrophe in systems programming: nothing crashes,
nothing errors, CPU drops to zero, and your service simply stops — threads
frozen mid-sentence, each holding something another needs. The theory here is
genuinely useful in a way theory sometimes isn't, because it's exhaustive: a
deadlock *cannot exist* unless four specific conditions hold at once, so every
cure you'll ever see is just a choice of which condition to assassinate.

## The Four Conditions

Coffman et al. (1971) nailed the requirements. All four, simultaneously:

1. **Mutual exclusion** — the resources can't be shared (a mutex, by contract).
2. **Hold and wait** — threads hold one resource while waiting for another.
3. **No preemption** — you can't forcibly take a mutex from its holder.
4. **Circular wait** — a cycle: T1 waits on what T2 holds, T2 on what T1 holds.

```text
   T1: lock(A) ──── waiting for B ────▶ held by T2
   T2: lock(B) ──── waiting for A ────▶ held by T1     ← cycle = deadlock
```

The textbook two-lock example looks contrived until you meet its production
costumes: two threads transferring money between accounts X→Y and Y→X, each
locking source-then-destination; a callback invoked under lock A that acquires
lock B while another path takes them B-then-A; two database transactions
updating the same rows in opposite orders (databases *detect* this and kill one
— your mutexes won't); a signal handler or destructor taking a lock the
interrupted code already holds — a one-thread deadlock.

## Breaking Condition Four: Lock Ordering

The fix that scales is a **global lock order**: assign every lock a rank and
acquire strictly ascending. Circular wait becomes impossible — a cycle would
require someone to acquire downward. When there's no natural rank
(account-transfer case), manufacture one from addresses or IDs:

```c
void transfer(Account *a, Account *b, int amt) {
    Account *first = a < b ? a : b;     /* order by address */
    Account *second = a < b ? b : a;
    pthread_mutex_lock(&first->m);
    pthread_mutex_lock(&second->m);
    ...
}
```

The Linux kernel takes this seriously enough to enforce it at runtime:
**lockdep** records every acquisition order ever observed and warns the moment
two locks are seen in both orders — *even if no deadlock happened*, because the
interleaving that triggers it is a matter of timing, not possibility. That's
the crucial mental shift: a deadlock isn't a bug that occurs, it's a bug that
*exists* in the ordering graph, waiting for a scheduler coin-flip. Testing
rarely finds it; analysis does. (Userspace equivalents:
`clang -fsanitize=thread` reports lock-order inversions; so does helgrind.)

## Breaking the Others

Each remaining condition has a niche cure. **Hold-and-wait**: acquire
everything atomically up front (`std::scoped_lock(m1, m2)` deadlock-free
multi-lock), or drop lock A before taking B — correct only if the protected
invariant tolerates the gap. **No preemption**: `trylock` with backoff —
acquire A, *try* B, and on failure release A and retry — turning a deadlock
into livelock-with-jitter, which is at least a fixable performance bug (this is
essentially what databases do with wait-die/wound-wait). **Mutual exclusion**
itself: the radical option — lock-free structures, per-thread sharding, or a
single-writer message-passing design where the cycle can't form because nobody
holds two things. Notice what's *not* on the list: timeouts on every lock as a
strategy. A timeout doesn't fix the ordering bug; it converts a clean hang into
an intermittent mystery failure that fires under load.

## When It Happens Anyway

A wedged process is actually one of the friendlier debugging scenarios, because
the evidence is still alive:

```bash
gdb -p <pid>
(gdb) thread apply all bt
```

Find threads parked in `__lll_lock_wait`; a pthread mutex stores its owner TID
right in the struct (`p *(pthread_mutex_t*)addr` — the `__owner` field), so you
can walk the wait chain by hand: T7 wants the mutex T12 owns, T12 wants T7's.
Cycle found, bug identified — the fix is deciding whose acquisition order is
wrong. `pstack` works when gdb is too heavy; on the kernel side, hung-task
warnings and `echo w > /proc/sysrq-trigger` dump the same story for kernel
locks.

## Takeaways

- Four conditions, all required: mutual exclusion, hold-and-wait, no
  preemption, circular wait. Every fix targets one.
- Global lock ordering (rank by design, or by address when symmetric) is the
  fix that survives large codebases; enforce it with lockdep/TSan, don't hope.
- A deadlock exists the moment two locks are ever taken in both orders — timing
  only decides when you pay.
- trylock+backoff and scoped multi-lock are the honest fallbacks; blanket
  timeouts just launder a hang into flakiness.
- Debugging a live one: `thread apply all bt`, read mutex owners, walk the
  cycle.