Deadlocks

A deadlock is when two or more threads each wait for something another one holds, so none of them can ever proceed. Unlike a crash, nothing fails loudly: the threads are alive, CPU usage drops to zero, and the system just hangs. Understanding the four conditions behind deadlock tells you exactly how to design it out.

The simplest example#

Two threads each need two locks, and they take them in opposite order:

Thread 1 holds A and needs B; Thread 2 holds B and needs A. Neither can release what it holds, because it is stuck waiting, and neither can get what it needs.

Everyday versions: two people at opposite ends of a narrow hallway, each saying "I'll move when you move." Or you hold a file open and need the printer, while your roommate has reserved the printer and needs the same file.

Why deadlocks are nasty#

Compare how three kinds of concurrency bug show themselves:

No exception, no log line. Users just see a frozen app.

Where they show up:

The four conditions (Coffman conditions)#

All four must hold at the same time. Remove any one and deadlock is impossible.

Mapped onto the example:

All four hold, so the threads deadlock.

Without a cycle, say T1 waits for T2 but T2 waits for nothing, T2 eventually finishes and releases, and T1 continues.

Prevention: break one condition#

Since all four conditions are required, you prevent deadlock by designing out any one of them.

Break circular wait: lock ordering#

Give every lock a global order and always acquire in that order (for example, by ID ascending).

With the rule "always acquire A before B", the same two threads now take turns:

There is no cycle, so there is no deadlock.

The original deadlock happened because Thread 1 went A → B and Thread 2 went B → A. A single order removes the cycle. This is the most common real-world fix: simple and easy to check in code review.

import threading
from dataclasses import dataclass, field

@dataclass
class Account:
    id: int
    balance: int
    lock: threading.Lock = field(default_factory=threading.Lock)

def transfer(src: Account, dst: Account, amount: int) -> None:
    # Transfer between two accounts without deadlock:
    # always lock the account with the smaller ID first.
    first, second = sorted((src, dst), key=lambda a: a.id)
    with first.lock, second.lock:
        src.balance -= amount
        dst.balance += amount

Break hold and wait: all or nothing#

Acquire every lock you need in one step, or none.

If you can't get them all, release everything and retry:

1. lock(A).
2. tryLock(B) fails.
3. unlock(A).
4. Wait a random time.
5. Retry.

Downsides: you may not know every lock upfront, releasing throws away work, and if threads keep retrying in lockstep you get livelock: everyone is busy, nobody progresses. The fix is random backoff. See Starvation vs Deadlock vs Livelock.

Break no preemption: force a release#

If a thread can't get what it needs, it gives up what it holds. In Python, this is acquire() with a timeout:

import threading

a = threading.Lock()
b = threading.Lock()

with a:
    if b.acquire(timeout=0.1):
        try:
            do_work()
        finally:
            b.release()
    else:
        # Couldn't get B in 100 ms: fall through, release A, retry later
        pass

Downside: the thread may have half-modified shared data when it gives up. Releasing then exposes an inconsistent state, so you need to roll back partial work first.

Databases work this way: they detect the deadlock, pick a victim transaction, roll it back, and let the other proceed. The application (or driver) retries the aborted transaction.

Break mutual exclusion: share where possible#

Make resources sharable so several threads can hold them. Read-write locks are the practical form: many readers or one writer.

This helps a lot when 90% of operations are reads and barely at all when most are writes, so mutual exclusion is usually impossible to remove completely.

Key takeaways#

• Deadlock needs all four: mutual exclusion, hold and wait, no preemption, circular wait.
• Global lock ordering (break circular wait) is the simplest and most common prevention.
• All-or-nothing acquisition and tryLock-with-timeout work too, but bring livelock and rollback concerns; add random backoff.
• Databases detect deadlocks and abort one transaction, so your code should be ready to retry.
• A deadlocked system hangs silently; thread dumps showing threads blocked on each other's locks are the giveaway.