Brayden Zhang

Deadlock

4 min read

Deadlock is a state where a set of threads are all blocked forever, each waiting for a resource another holds. It is a systemic failure of concurrent Synchronization rather than a bug in any single line of code.

The Four Coffman Conditions

Deadlock can arise only if all four hold at once. Break any one and deadlock is impossible.

  1. Mutual exclusion: at least one resource is held in a non-shareable mode.
  2. Hold and wait: a thread holds a resource while waiting to acquire another.
  3. No preemption: a resource can be released only voluntarily by its holder.
  4. Circular wait: there is a cycle of threads, each waiting for a resource the next holds.

The Classic Example

// Thread 1                 // Thread 2
lock(&A);                   lock(&B);
lock(&B);   // waits <----- lock(&A);   // waits
// ... work ...             // ... work ...
unlock(&B); unlock(&A);     unlock(&A); unlock(&B);

If Thread 1 holds A and Thread 2 holds B, each waits on the other forever. All four conditions are present.

Resource Allocation Graphs

Model resources and threads as a directed graph:

  • Request edge: thread → resource (waiting for it).
  • Assignment edge: resource → thread (currently held).
   T1 ---request---> R2 ---assigned---> T2
   ^                                     |
   |                                     v
   R1 <--assigned-- T1     T2 --request--> R1
   (cycle T1 -> R2 -> T2 -> R1 -> T1)

With one instance per resource type, a cycle means deadlock. With multiple instances per type, a cycle is necessary but not sufficient; you must check for an actual unsafe allocation.

Strategy 1: Prevention

Statically deny one Coffman condition:

Condition brokenTechniqueCost
Mutual exclusionmake resources shareable (read-only, lock-free)not always possible
Hold and waitacquire all resources at once, or nonepoor utilization, starvation
No preemptionforcibly reclaim (roll back and retry)lost work, only for savable state
Circular waitimpose a global lock orderingmust know all locks in advance

Lock ordering is the practical winner

The most usable prevention is to eliminate circular wait: assign every lock a number and always acquire in increasing order. In the example above, both threads acquiring A before B removes the cycle. This is the standard discipline in real kernels and servers.

Strategy 2: Avoidance (Banker’s Algorithm)

Grant a request only if the resulting state is safe, meaning some ordering of threads can finish. Each thread declares its maximum need up front.

State: Available[], Max[t][r], Allocation[t][r]
Need[t][r] = Max[t][r] - Allocation[t][r]
 
safe():
  Work = Available;  Finish[t] = false for all t
  repeat:
    find a thread t with Finish[t]==false and Need[t] <= Work
    if none found: break
    Work += Allocation[t]   // pretend t finishes and releases
    Finish[t] = true
  return (all Finish[t] == true)   // safe if every thread can complete

A request is granted tentatively, then safe() is checked; if unsafe, the request is denied and the thread waits.

Avoidance is often impractical

The Banker’s algorithm requires each thread to declare its maximum resource claim in advance and runs in O(threads x resources) per request. Real programs rarely know their maximum needs, so avoidance is mostly a teaching tool; prevention (lock ordering) and detection dominate in practice.

Strategy 3: Detection and Recovery

Allow deadlock to occur, then find and break it:

  • Detection: periodically run a cycle-detection (or the Banker-style reducibility) check on the resource allocation graph. Frequent checks cost CPU; rare checks let deadlocks linger.
  • Recovery options:
    • Kill one or more threads in the cycle (choose by low priority or least work lost).
    • Preempt and roll back a thread to a checkpoint, then retry.

Databases take this route: they detect deadlocks among transactions and abort a victim, which then retries.

  • Livelock: threads keep reacting to each other and changing state but make no progress (two people stepping aside in a hallway). Add randomized backoff.
  • Starvation: a thread waits indefinitely though the system is not deadlocked; addressed by aging in CPU Scheduling.

The Ostrich Algorithm

Many general-purpose systems simply ignore deadlock, reasoning that it is rare and that a reboot is cheaper than the overhead of prevention or detection. This is a deliberate engineering trade-off, not an oversight.

Graph View