Deadlocks

1What a Deadlock Is

A deadlock is a state where a set of tasks each wait for a resource held by another task in the set — forever. Nothing crashes; nothing progresses. Requests hang until timeouts fire, thread pools fill up, and the system degrades without an obvious error.

Task A holds lock X, waits for lock Y
Task B holds lock Y, waits for lock X        → neither can ever continue

Related failure modes:

• Livelock: tasks keep changing state in response to each other (both back off and retry in lockstep) but make no progress.
• Starvation: a task never gets the resource because others keep winning.

2The Four Coffman Conditions

A deadlock requires all four at once — so preventing any one prevents deadlock:

3Lock Ordering

Assign every lock a rank and always acquire in ascending order:

// transfer between two accounts: lock the lower id first, regardless of direction
async function transfer(a: Account, b: Account, amount: number) {
  const [first, second] = a.id < b.id ? [a, b] : [b, a];
  await first.lock.acquire();
  try {
    await second.lock.acquire();
    try { a.balance -= amount; b.balance += amount; }
    finally { second.lock.release(); }
  } finally { first.lock.release(); }
}

Without ordering, transfer(A→B) and transfer(B→A) running together is the textbook deadlock.

4Deadlocks Beyond Mutexes

• Databases: two transactions update the same rows in opposite order (UPDATE accounts SET … WHERE id = 1 then id = 2, vs 2 then 1). PostgreSQL/MySQL detect the cycle and abort one transaction with a deadlock error → the application must retry it. Mitigate by touching rows in a consistent order (ORDER BY id … FOR UPDATE), keeping transactions short, and avoiding user interaction or network calls inside transactions.
• Connection pools: a request holds connection #1 and, inside the same request, asks the pool for connection #2 while every connection is held by requests doing the same thing → pool exhaustion deadlock. Never acquire a second connection while holding one (pass the transaction/connection down).
• Async code: awaiting a promise that can only resolve after the current task finishes (e.g. a task that waits on a queue it alone feeds); in .NET, blocking .Result on async code under a synchronization context (languages/csharp/06-async_await).
• Distributed locks: service A holds a Redis lock and calls service B, which waits for a lock A holds in another store. Use lease timeouts and avoid nested distributed locks.
• Thread pool starvation: all pool threads block waiting for work that needs a pool thread to run.

5Detection and Recovery

• Timeouts on every lock and wait (tryAcquire(timeout), lock_timeout, statement_timeout), turning a hang into an error you can retry or alert on.
• Wait-for graph cycle detection (databases do this; you can for in-process lock managers).
• Thread dumps (jstack, dotnet-dump, py-spy dump) show which thread holds what and waits on what; databases expose lock views (pg_locks, pg_stat_activity, deadlock logs).
• Recovery: abort one participant (the "victim"), release its resources, retry with backoff + jitter (to avoid livelock).

Under the HoodHow PostgreSQL Detects Deadlocks▾

When a backend waits for a lock longer than deadlock_timeout (default 1 s), it runs a deadlock check: it builds the wait-for graph from the shared lock table — an edge from each waiting transaction to every transaction holding (or queued ahead for) a conflicting lock — and searches for a cycle that includes itself. If it finds one, it aborts its own transaction with ERROR: deadlock detected (SQLSTATE 40P01), logging both statements. The check is deferred by deadlock_timeout because it's relatively expensive and most lock waits resolve quickly on their own. The cost of a deadlock is therefore at least ~1 s of blocking plus a failed transaction — which is why ordering row locks consistently is far better than relying on detection.

⚠️ Common Pitfalls

1. Inconsistent lock order across code paths.
2. Calling out (network, user callbacks, other locks) while holding a lock.
3. Long transactions that hold row locks across slow operations.
4. No timeouts — deadlocks look like mysterious hangs.
5. Not retrying database deadlock errors.
6. Retry without jitter — two victims retry in lockstep → livelock.

📋 Quick Reference

deadlock needs: mutual exclusion + hold-and-wait + no preemption + circular wait
fix: global lock ordering · acquire all at once · timeouts/tryLock · short critical sections
DB: consistent row order (ORDER BY id FOR UPDATE) · short txns · retry 40P01 with jitter
diagnose: thread dumps · pg_locks / deadlock logs · wait-for graph

🎤 Interview Q&A

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

✅ Check yourself

Source: adv_deadlocks_theory.md · generated by tools/build_lessons.py