# Deadlocks

## 1. What 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.

## 2. The Four Coffman Conditions

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

| Condition | Meaning | Break it by… |
|---|---|---|
| **mutual exclusion** | a resource can be held by one task at a time | lock-free structures, immutable data, read-sharing |
| **hold and wait** | a task holds one resource while waiting for another | acquire all needed resources at once, or release before waiting |
| **no preemption** | resources can't be forcibly taken | timeouts (`tryLock(timeout)`), lock leases, transaction aborts |
| **circular wait** | a cycle in the wait-for graph | **global lock ordering** — the most practical fix |

## 3. Lock Ordering

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

```ts
// 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.

## 4. Deadlocks 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.

## 5. Detection 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 Hood: How 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.

![Transfer A to B locks X then waits for Y while transfer B to A locks Y then waits for X, forming a cycle in the wait-for graph; acquiring locks in a global order removes the cycle, and databases detect the cycle and abort one transaction](diagrams/01-wait-for-cycle.svg)

## 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
```