Deadlock

Transfer money between two accounts. Lock the source, lock the destination, move the funds.

function transfer(from: Account, to: Account, amount: number) {
  from.lock();
  to.lock();
  from.balance -= amount;
  to.balance += amount;
  to.unlock();
  from.unlock();
}

Now run transfer(a, b) and transfer(b, a) at the same instant. The first thread holds a and wants b. The second holds b and wants a. Neither will ever release.

The process does not crash. It stops.

The four conditions

Deadlock requires all four of these at once — this is Coffman’s 1971 result, and it is the reason the problem is tractable:

1. Mutual exclusion — a resource can be held by one thread at a time.
2. Hold and wait — a thread holding something requests something else.
3. No preemption — a resource cannot be taken away, only released.
4. Circular wait — a cycle of threads each waiting on the next.

Attack condition 4: lock ordering

The standard fix, and almost always the right one. Give every lock a global order and always acquire in that order.

function transfer(from: Account, to: Account, amount: number) {
  const [first, second] = from.id < to.id ? [from, to] : [to, from];

  first.lock();
  second.lock();
  try {
    from.balance -= amount;
    to.balance += amount;
  } finally {
    second.unlock();
    first.unlock();
  }
}

Now transfer(a, b) and transfer(b, a) both lock a then b. One waits, the other finishes, and no cycle can form.

The ordering key must be stable and total — a database id, a memory address, anything with a consistent comparison. An address works and is what most C++ codebases use.

Attack condition 2: take everything at once

Acquire all the locks you need in one atomic step, or none:

if (!tryLockAll([from, to])) return retryLater();

No thread ever holds one while waiting for another. The cost is that you must know the full set in advance, which is not always possible, and that the retry loop can livelock if two threads keep colliding and backing off in step. Add randomised backoff.

Attack condition 3: allow timeouts

if (!to.tryLock(100)) {
  from.unlock();          // give up everything and start over
  return retry();
}

tryLock with a deadline turns a deadlock into a slow operation. Useful when ordering is impossible — locks acquired across a plugin boundary, say — but it is a mitigation: the cycle still forms, you just escape it. And without randomised backoff, two threads will retry in lockstep forever.

Attack condition 1: do not share

Lock-free structures, immutable data, actors — if there is no exclusive resource, condition 1 fails and none of the rest can happen.

Not just mutexes

Deadlock is a shape, not a mutex feature. The same cycle appears with:

• Database transactions taking row locks in different orders. Postgres and MySQL detect this and abort one transaction — which is why “deadlock detected, retry your transaction” is a normal error your application must handle rather than a bug report.
• Thread pools. A pool task that submits another task to the same pool and waits for it deadlocks when the pool is full. Every worker is waiting for work that has nowhere to run.
• async/await with a blocking wait. Calling .Result or .get() on a task that needs the thread you are blocking is the same cycle with one thread.

Finding one

A deadlocked process is easy to diagnose once you know the trick: take a thread dump. jstack on the JVM, SIGQUIT in Go, py-spy dump in Python, thread apply all bt in gdb.

Every deadlocked thread is blocked on a lock acquisition, and the stack traces show you the cycle directly. The JVM even names it for you.