12.1 Why Deadlocks Occur

Two locks individually are harmless, yet together, they can bring an entire program to a halt:

Thread A: holds orders, waits for inventory
Thread B: holds inventory, waits for orders

The CPU continues running, and no threads crash, but each thread needs the other to release its lock before either can proceed. This is a deadlock. The real danger isn't in "having many locks"; it's when resource dependencies form a cycle.

This chapter establishes a model for analyzing such situations and introduces preventive strategies. The next section, Live Diagnosis, will show how to use thread stacks and wait relationships to detect the cycle.

1. Deadlock Is Not "The Program Is Slow"

Several similar phenomena must be distinguished:

Phenomenon	Does state change?	Can it resolve on its own?
Deadlock	Execution units are all waiting on each other	No, without external intervention
Livelock	Continuously retries, yields, or aborts	Theoretically possible, but in practice may result in no progress
Starvation	A particular execution unit never acquires resources	Other work may still proceed
Long blocking	Currently waiting for I/O, a condition, or a locked resource	Can resume once the condition is met
Performance congestion	Work is progressing, but throughput has dropped	Will eventually complete, just very slowly

A "no response after 5 seconds" alert should only serve as a warning, not as proof of deadlock. Diagnosis requires knowing exactly which threads hold locks, what they are waiting for, and whether the waiting chain forms a closed loop.

2. Four Necessary Conditions

Coffman's conditions describe the four things that must simultaneously hold true when a deadlock occurs:

1. Mutual exclusion: A resource can be used by only one execution unit at a time;
2. Hold and wait: An execution unit holds at least one resource while waiting for additional resources;
3. No preemption: The system cannot forcibly take a resource away from a currently holding unit;
4. Circular wait: There exists a circular dependency where each unit is waiting for a resource held by the next unit in the chain.

Using the initial example of two locks, mutex can be held by only one thread at a time; thread A holds lock A and waits for lock B, while thread B holds lock B and waits for lock A; the locks cannot be forcibly transferred; the waiting relationship forms a cycle: A → B → A. All four conditions must be met simultaneously.

These conditions are necessary, not sufficient for deadlock detection. The presence of mutual exclusion, hold-and-wait, and no preemption does not guarantee a current deadlock, there must also be an actual circular wait.

pthread_mutex_trylock does not mean "preemption." It simply means that if a resource is not available, the operation returns immediately without taking the resource or releasing any locks already held by the caller. Only when the caller voluntarily releases its held resources, re-attempts the operation, and breaks the hold-and-wait state can the cycle be broken.

3. Using a Wait Graph to Diagnose Problems

Represent threads as nodes. If thread A is waiting for a resource held by thread B, draw a directed edge from A to B:

A ──waits for B's L2──> B
▲                         │
└──waits for A's L1───────┘

When each resource has only one instance, a cycle in the wait graph indicates a deadlock. If there are multiple instances of the same resource type, observing a cycle is not sufficient on its own, additional analysis is needed to consider the available and held quantities of each resource class.

In engineering practice, a "global locking order" structurally prevents such cycles. If all threads are restricted to acquiring only lower-level locks before higher-level ones, wait edges cannot form a loop back to their origin.

4. The Most Practical Prevention: Fixed Lock Ordering

Suppose a transfer requires locking both the sender and receiver accounts. If we consistently follow the pattern of "lock sender first, then receiver," two transfers in opposite directions could form a deadlock cycle. Save the following as ordered-transfer.c. It locks by stable, unique account ID. Account pointers must be valid, IDs immutable during concurrent use, and initial balances nonnegative. Amounts are integer units: negative amounts, duplicate IDs, insufficient funds, and destination overflow return 0. A nonnegative self-transfer is a successful no-op. Pthread errors terminate this demo process instead of allowing unprotected access:

#include <limits.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    unsigned id;
    long balance;
    pthread_mutex_t mutex;
} account_t;

typedef struct {
    account_t *from;
    account_t *to;
    int rounds;
} transfer_job_t;

static void check_pthread(int error, const char *operation) {
    if (error != 0) {
        fprintf(stderr, "%s: %s\n", operation, strerror(error));
        exit(EXIT_FAILURE);
    }
}

static int transfer(account_t *from, account_t *to, long amount) {
    if (amount < 0) {
        return 0;
    }
    if (from == to) {
        return 1;
    }

    if (from->id == to->id) {
        return 0;
    }

    account_t *first = from->id < to->id ? from : to;
    account_t *second = from->id < to->id ? to : from;

    check_pthread(pthread_mutex_lock(&first->mutex), "lock first");
    check_pthread(pthread_mutex_lock(&second->mutex), "lock second");

    int completed = 0;
    if (from->balance >= amount && to->balance <= LONG_MAX - amount) {
        from->balance -= amount;
        to->balance += amount;
        completed = 1;
    }

    check_pthread(pthread_mutex_unlock(&second->mutex), "unlock second");
    check_pthread(pthread_mutex_unlock(&first->mutex), "unlock first");
    return completed;
}

static void *run_transfers(void *argument) {
    transfer_job_t *job = argument;
    for (int i = 0; i < job->rounds; ++i) {
        transfer(job->from, job->to, 1);
    }
    return NULL;
}

int main(void) {
    account_t a = { 10, 100000, PTHREAD_MUTEX_INITIALIZER };
    account_t b = { 20, 100000, PTHREAD_MUTEX_INITIALIZER };
    transfer_job_t ab = { &a, &b, 50000 };
    transfer_job_t ba = { &b, &a, 50000 };
    pthread_t first;
    pthread_t second;

    if (pthread_create(&first, NULL, run_transfers, &ab) != 0
            || pthread_create(&second, NULL, run_transfers, &ba) != 0) {
        return EXIT_FAILURE;
    }
    if (pthread_join(first, NULL) != 0
            || pthread_join(second, NULL) != 0) {
        return EXIT_FAILURE;
    }

    check_pthread(pthread_mutex_destroy(&a.mutex), "destroy a");
    check_pthread(pthread_mutex_destroy(&b.mutex), "destroy b");
    printf("a=%ld b=%ld total=%ld\n",
           a.balance, b.balance, a.balance + b.balance);
    return a.balance == 100000 && b.balance == 100000
        ? EXIT_SUCCESS : EXIT_FAILURE;
}

cc -std=c17 -O2 -Wall -Wextra -Werror -pthread ordered-transfer.c
./a.out
# a=100000 b=100000 total=200000

The key isn't that "unlock order must be reversed" (a common heuristic) but that all paths acquiring multiple locks follow the same partial ordering. Reversing unlock sequences often makes nested dependencies clearer, but deadlock prevention relies entirely on the consistency of lock acquisition order.

Lock levels must be stable and unique. If two objects have the same level, a deterministic tiebreaker rule must be defined. Object address sorting may not be reliable or portable across languages or runtimes.

When Order Is Hard to Agree Upon

Callbacks, plugins, and cross-module calls often hide lock dependencies. Design can still be improved by:

• Acquire the full set through an all-or-nothing or try-lock rollback protocol; on partial failure, release everything already acquired before waiting or retrying;
• Narrowing the scope of locks, releasing internal locks before calling into unknown code;
• Using message passing to centralize ownership of resources within a single execution unit;
• When splitting large locks, define lock levels simultaneously with the partitioning, rather than for parallelism alone;
• Implement timeouts or try-lock with fallbacks, but ensure backoff strategies are designed to avoid livelock;
• Allow database transactions to deadlock, then detect and roll back the affected transaction.

Adding a global big lock does eliminate lock cycles across multiple resources, but it sacrifices parallelism. Moreover, if a caller holds this global lock while waiting for external resources, it can still form cycles with other parts of the system.

5. What the Philosophers' Dining Problem Actually Teaches

Five philosophers sit around a table, each needing two chopsticks to eat. If everyone first takes the left chopstick and then waits for the right, a five-node cycle can form. This model isn't teaching chopstick APIs; it's illustrating several structural solutions to resource contention:

Resource ordering. Assign numbers to chopsticks, and each philosopher always picks up the lower-numbered one first, then the higher-numbered one. The last philosopher's acquisition direction contradicts intuition, breaking the cycle and preventing deadlock.

Limiting concurrent applicants. Only allow up to four philosophers to attempt grabbing chopsticks at once, ensuring at least one valid path to completion. However, "a completion path exists" does not guarantee fairness, starvation remains a concern.

Centralized arbitration. A waiter grants permission to pick up a pair of chopsticks at a time. This eliminates distributed holding and waiting, but shifts throughput and availability into the hands of the arbiter.

Failure recovery. When a second chopstick isn't available, release the first and retry after a randomized or bounded backoff. If all philosophers strictly synchronize their pickup and release actions, deadlock becomes livelock.

Thus, the same example simultaneously addresses both safety and liveness: avoiding deadlock only means the system won’t get stuck in a resource cycle, it does not guarantee bounded waiting or eventual success for every participant.

6. Four Strategies for Handling Deadlocks

Textbooks typically categorize methods into four classes:

Strategy	Timing	Typical Techniques
Prevention	Disrupts necessary conditions during design	Lock ordering, single-phase resource allocation, reducing mutual exclusion
Avoidance	Checks safety before each resource allocation	Banker's algorithm
Detection	Allows deadlock entry and then identifies waiting cycles	Database wait graphs, thread dump analysis
Recovery	Breaks cycles after detection	Roll back transactions, terminate tasks, restart components

Real-world systems often combine these strategies. For example, mutexes within a process use lock hierarchies for prevention, database transactions rely on detection to identify victims and roll back, and external service calls employ timeouts to prevent indefinite resource consumption.

Timeouts serve as a fail-safe mechanism, but they do not automatically prove or resolve deadlocks. If a timeout occurs and the holding resources are not released, partial work is not undone, and retries are not idempotent, the system may shift from "infinite waiting" to "continuous failure with inconsistent state."

7. A Safe State Is Stronger Than Currently Deadlock-Free

The Banker's Algorithm requires each task to declare its maximum demand for every resource type in advance. After attempting allocation, the system only approves a request if there exists at least one "safe sequence", a valid order in which all tasks can complete one after another.

Resource counts must be nonnegative integers, matrix dimensions must match, and allocations cannot exceed maximum claims. This function returns a safe sequence, or None if none exists. Save as banker.py and run with Python 3:

def safe_sequence(available, maximum, allocation):
    process_count = len(maximum)
    resource_count = len(available)

    if len(allocation) != process_count:
        raise ValueError("matrix height mismatch")

    if any(type(value) is not int or value < 0 for value in available):
        raise ValueError("available must contain nonnegative integers")

    need = []
    for maximum_row, allocated_row in zip(maximum, allocation):
        if len(maximum_row) != resource_count:
            raise ValueError("maximum width mismatch")
        if len(allocated_row) != resource_count:
            raise ValueError("allocation width mismatch")

        row = []
        for claim, held in zip(maximum_row, allocated_row):
            if (type(claim) is not int or type(held) is not int
                    or claim < 0 or held < 0):
                raise ValueError("resource counts must be nonnegative integers")
            if claim < held:
                raise ValueError("allocation exceeds maximum claim")
            row.append(claim - held)
        need.append(row)

    work = list(available)
    finished = [False] * process_count
    order = []

    while len(order) < process_count:
        progressed = False
        for process in range(process_count):
            if finished[process]:
                continue
            if all(need[process][resource] <= work[resource]
                   for resource in range(resource_count)):
                for resource in range(resource_count):
                    work[resource] += allocation[process][resource]
                finished[process] = True
                order.append(process)
                progressed = True
        if not progressed:
            return None

    return order

available = [3, 3, 2]
maximum = [
    [7, 5, 3],
    [3, 2, 2],
    [9, 0, 2],
    [2, 2, 2],
    [4, 3, 3],
]
allocation = [
    [0, 1, 0],
    [2, 0, 0],
    [3, 0, 2],
    [2, 1, 1],
    [0, 0, 2],
]

order = safe_sequence(available, maximum, allocation)
assert order is not None
print(order)

An unsafe state has no safe sequence under the declared maximum demands. It need not already be deadlocked: tasks may request less than their maximum and complete, or future requests may cause deadlock. The algorithm decides safety in this resource model; it does not replace an actual wait graph.

This approach is rarely practical in general thread locking scenarios, because programs typically cannot predict their full maximum resource demands, and both tasks and resources may appear dynamically. Its value lies in distinguishing between "resources are currently available" and "the system can still complete all tasks after this allocation."

The Banker's Algorithm is not synonymous with two-phase locking or two-phase commit. Databases generally prefer to detect deadlocks via a wait graph and roll back a transaction, rather than requiring transactions to pre-declare all their locks.

8. Design Checklist

When reviewing code paths involving locks, ask each of the following questions systematically:

1. What locks does this path hold when it enters?
2. Does it call functions that might acquire locks, block, or invoke callbacks?
3. Where is the global lock hierarchy recorded, and can automated checks cover it?
4. Do error, cancellation, and timeout paths release the same resources?
5. When a thread waits on a condition variable, is the associated mutex released according to protocol?
6. Does any lock span across network, disk, or user interaction?
7. Could retrying after failure cause all participants to enter a synchronized livelock?
8. If deadlock remains possible, how does the system detect it, select a victim, and recover to a consistent state?

9. Summary

Deadlock depends on resource relationships. Even one PTHREAD_MUTEX_NORMAL lock can produce a self-cycle when its owner tries to acquire it again. The four necessary conditions help explain why it can occur, but in practice, the most effective engineering approach is to ensure that dependency edges only flow in one direction:

• Use a stable lock hierarchy to enforce a consistent acquisition order;
• Minimize external calls and blocking during lock holding;
• When prevention is impossible, implement clear detection and recovery mechanisms;
• Treat timeouts as a safety measure, not as proof of correctness;
• Simultaneously monitor for livelock and starvation, avoiding the false assumption that only one form of stagnation can be eliminated.

The next section, Deadlock Diagnosis in the Field, will walk you through capturing the instantaneous state of all threads, then reconstructing the full cycle from questions like "what are they waiting for" and "who currently holds the lock."