Deadlocks

Overview

When you protect shared data with locks, you trade one problem for another. In Mutexes — pthread_mutex_t you saw that a mutex (mutual-exclusion lock) lets only one thread into a critical section at a time, which fixes data races. But the moment a thread needs more than one lock at a time, a new failure becomes possible: two threads can end up each holding a lock the other one is waiting for. Neither can continue, and neither will ever give up its lock. The program does not crash, it does not print an error — it simply freezes forever. That is a deadlock.

Deadlocks matter because they are silent and intermittent. A deadlock usually depends on exact timing: the two threads have to interleave in just the wrong way. So a program can run correctly thousands of times in testing and then hang in production under load. The good news is that deadlocks are one of the few concurrency bugs with a clean, complete prevention strategy — if you follow one rule consistently, deadlock between locks becomes structurally impossible.

This lesson builds directly on mutex basics. There we used a single mutex. Here we deal with the harder case: a thread holding one mutex while it asks for a second one. We will name the conditions that make deadlock possible (the Coffman conditions), look at the circular wait at the heart of every deadlock, and then learn the standard cure — a consistent global lock order — and how to express it in real pthread code.

Why it matters

Real systems lock many things: a bank transfer locks two accounts, a file system locks two directories during a rename, a database locks two rows. Any time code holds one lock and reaches for a second, deadlock is on the table.

A deadlock is worse than a crash in several ways. A crash gives you a stack trace and a core dump; a deadlock gives you a process that is alive but does nothing — it still holds its file handles, sockets, and memory, so connected clients hang and time out. In a server, one deadlocked request handler can tie up a worker thread permanently; enough of them and the whole service stops accepting work even though the process never died. Because the trigger is a timing window, the bug often escapes testing and surfaces only at scale, which makes it expensive to reproduce and diagnose.

Understanding the four conditions turns deadlock from a mysterious freeze into something you can reason about and prevent by design. The most common professional rule — "always acquire locks in the same order" — comes straight from this analysis, and it is something reviewers actively look for in concurrent code.

Core concepts

Concept 1 — What a deadlock actually is

A deadlock is a state in which a set of threads are all blocked, each waiting for a resource (here, a lock) that another thread in the set is holding. Because no thread in the set can proceed, none of them ever releases anything, so the wait is permanent.

The key insight: a blocked thread holding a lock cannot release that lock, because releasing happens after it wakes up — and it will never wake up. The wait feeds itself. This is why a deadlock is forever, not just "slow."

A single mutex used by itself can never deadlock against another lock, because a thread holding one lock and asking for nothing else will always finish and release. Deadlock needs at least two locks and at least two threads (or one thread that locks the same non-recursive mutex twice — a self-deadlock).

Knowledge check: A program prints nothing and uses 0% CPU but does not exit. Is this more consistent with an infinite loop or a deadlock? (Hint: think about what the CPU is doing in each case.)

Concept 2 — The circular wait (AB-BA)

The classic deadlock comes from two threads taking two locks in opposite orders.

         Thread A                 Thread B
         --------                 --------
  t1   lock(m1)  ........ OK
  t2                              lock(m2)  ........ OK
  t3   lock(m2)  ...... BLOCKS (B holds m2)
  t4                              lock(m1)  ...... BLOCKS (A holds m1)

  Wait graph (who waits for whom):

        +-------- holds m1 --------+
        |                          v
     Thread A                  Thread B
        ^                          |
        +-------- holds m2 --------+

  A -> waits for m2 -> held by B -> waits for m1 -> held by A   (a cycle)

The arrows form a cycle. That cycle is the deadlock. Both threads are now parked in pthread_mutex_lock, and neither call will ever return.

Notice it does not always happen — if Thread A finishes both locks before Thread B starts, everything is fine. The deadlock needs the unlucky interleaving where each thread grabs its first lock before either grabs its second. That is why deadlocks are intermittent.

Knowledge check (predict the outcome): Thread A does lock(m1); lock(m2) and Thread B does lock(m1); lock(m2) — the same order. Can these two deadlock against each other on m1/m2? Why or why not?

Concept 3 — The four Coffman conditions

Deadlock is possible only when all four of these hold at the same time. Removing any one makes it impossible.

In practice, the cheapest condition to break is circular wait, by always locking in the same order. That is the strategy the rest of this lesson focuses on.

Concept 4 — Global lock ordering

Definition: assign every lock a position in one global, total order, and require that any thread acquiring multiple locks acquires them in increasing order — never the reverse.

Why it works: a cycle in the wait-for graph requires some thread to wait "backwards" (it holds a higher-ordered lock and asks for a lower-ordered one) while another waits "forwards." If everyone only ever moves forward in the order, you cannot close the loop. No cycle means condition 4 is broken, so no deadlock.

When locks have obvious names (accounts, then audit_log), you can document the order by name. When you do not know which two of many objects you will lock — for example, transferring between two Account structs chosen at runtime — you order them by a stable, comparable key. The memory address of the mutex works: it is unique and the comparison is the same for every thread.

  Two accounts, chosen at runtime. Order by address of their mutex:

    if (&a->lock < &b->lock)  lock a->lock, then b->lock
    else                      lock b->lock, then a->lock

  Every thread that touches the same pair compares the same two
  addresses and reaches the same order  =>  no AB-BA cycle.

When NOT to use it / pitfalls: address ordering only works for locks whose addresses are stable for the lifetime of the operation (do not order by address if objects can be freed/moved underneath you). And it only prevents deadlock if every code path obeys the order — one stray function that locks in the opposite order reintroduces the bug.

Concept 5 — Back-off with trylock (breaking "no preemption")

When a clean global order is impractical, an alternative is pthread_mutex_trylock, which returns immediately (with EBUSY) instead of blocking. The pattern: lock the first mutex normally, then trylock the second; if it fails, release the first one too and retry from the start. By giving up the lock it already holds, the thread refuses to "hold and wait," so no cycle forms.

The danger is forgetting the release. If trylock fails and you keep the first lock, you have just leaked a held lock — the most common trylock bug.

Knowledge check (find the bug): A function does lock(m1); if (trylock(m2) != 0) return -1; and otherwise does its work and unlocks both. What is wrong with the return -1 path?

Syntax notes

The relevant pthread calls and their return-value contract:

#include <pthread.h>

int pthread_mutex_lock(pthread_mutex_t *m);     // blocks until owned; 0 on success
int pthread_mutex_trylock(pthread_mutex_t *m);  // 0 if locked now, EBUSY if already held
int pthread_mutex_unlock(pthread_mutex_t *m);   // 0 on success

A helper that always locks two mutexes in address order, so every caller agrees on the order:

static void lock_ordered(pthread_mutex_t *a, pthread_mutex_t *b) {
    /* Compare the addresses to pick a single global order. */
    if (a < b) {                 /* a comes first in the order */
        pthread_mutex_lock(a);
        pthread_mutex_lock(b);
    } else {                     /* b comes first (or a == b, handle separately) */
        pthread_mutex_lock(b);
        pthread_mutex_lock(a);
    }
}

static void unlock_both(pthread_mutex_t *a, pthread_mutex_t *b) {
    pthread_mutex_unlock(a);     /* unlock order does not matter for correctness */
    pthread_mutex_unlock(b);
}

Note: if a == b (the same mutex passed twice) this helper would lock it twice and self-deadlock on a normal mutex. Real code should guard against that or use the same single-lock path when the two objects are identical.

Lesson

What Is a Deadlock?

A deadlock happens when two or more threads wait forever for each other to release locks. None of them can move forward, so the program freezes.

A mutex (mutual-exclusion lock) is a lock that only one thread can hold at a time. Threads use mutexes to protect shared data.

The Classic Example

Suppose two threads each need two mutexes, m1 and m2, but they take them in opposite orders:

Thread A holds m1 and waits for m2. Thread B holds m2 and waits for m1.

Each thread is waiting for a lock the other one holds. Neither can proceed. That is a deadlock.

The Four Coffman Conditions

A deadlock can only occur when all four of these conditions hold at once:

1. Mutual exclusion — a lock can be held by only one thread at a time.
2. Hold and wait — a thread holds one lock while requesting another.
3. No preemption — locks cannot be forcibly taken away from a thread.
4. Circular wait — there is a cycle in the lock dependency graph (A waits for B, B waits for A).

Break any one of these conditions and deadlock becomes impossible.

The Simplest Fix: Global Lock Ordering

The easiest cure is to enforce a global lock ordering.

The rule: every code path that needs both m1 and m2 must always take them in the same order — for example, m1 first, then m2. If no thread ever takes them in the opposite order, a circular wait cannot form.

When you don't know the lock names ahead of time, you can order locks by their memory address:

if (&m1 < &m2) lock(&m1);
lock(&m2);

Since every thread compares addresses the same way, they all agree on the order.

Code examples

/* deadlock_fix.c
 * Two threads each transfer money between the SAME two accounts, in
 * opposite "directions." Locking each account's mutex in ADDRESS ORDER
 * guarantees no AB-BA circular wait, so the program always finishes.
 *
 * Build:  cc -std=c11 -pthread -Wall -Wextra -o deadlock_fix deadlock_fix.c
 */
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    pthread_mutex_t lock;
    long balance;
} Account;

/* Lock both account mutexes in a single global order (by address). */
static void lock_pair(Account *x, Account *y) {
    if (&x->lock < &y->lock) {        /* x's lock comes first globally */
        pthread_mutex_lock(&x->lock);
        pthread_mutex_lock(&y->lock);
    } else {                          /* y's lock comes first globally */
        pthread_mutex_lock(&y->lock);
        pthread_mutex_lock(&x->lock);
    }
}

static void unlock_pair(Account *x, Account *y) {
    pthread_mutex_unlock(&x->lock);
    pthread_mutex_unlock(&y->lock);
}

/* Move `amount` from `from` to `to`, holding both locks. */
static void transfer(Account *from, Account *to, long amount) {
    if (from == to) return;           /* never lock the same mutex twice */
    lock_pair(from, to);
    from->balance -= amount;
    to->balance   += amount;
    unlock_pair(from, to);
}

static Account a, b;

/* Thread 1 sends a -> b; thread 2 sends b -> a (opposite directions). */
static void *worker_ab(void *arg) {
    (void)arg;
    for (int i = 0; i < 100000; i++) transfer(&a, &b, 1);
    return NULL;
}
static void *worker_ba(void *arg) {
    (void)arg;
    for (int i = 0; i < 100000; i++) transfer(&b, &a, 1);
    return NULL;
}

int main(void) {
    a.balance = 1000000;
    b.balance = 1000000;
    if (pthread_mutex_init(&a.lock, NULL) != 0 ||
        pthread_mutex_init(&b.lock, NULL) != 0) {
        perror("pthread_mutex_init");
        return 1;
    }

    pthread_t t1, t2;
    if (pthread_create(&t1, NULL, worker_ab, NULL) != 0 ||
        pthread_create(&t2, NULL, worker_ba, NULL) != 0) {
        perror("pthread_create");
        return 1;
    }

    pthread_join(t1, NULL);           /* wait for both to finish */
    pthread_join(t2, NULL);

    /* Each direction moved the same total, so balances net out. */
    printf("a = %ld, b = %ld, sum = %ld\n", a.balance, b.balance,
           a.balance + b.balance);

    pthread_mutex_destroy(&a.lock);   /* release lock resources */
    pthread_mutex_destroy(&b.lock);
    return 0;
}

What it does: two threads pound on the same pair of accounts in opposite directions, exactly the AB-BA scenario that normally deadlocks. Because lock_pair always orders the two mutexes by address, both threads agree on which mutex to take first, so a circular wait can never form and both loops run to completion.

Expected output: the sum is conserved (no money created or destroyed):

a = 1000000, b = 1000000, sum = 2000000

The individual balances of a and b come back to their starting values here only because each direction transferred the same amount the same number of times; the sum is always 2000000 regardless of timing, which is the real correctness property. Edge cases: the from == to guard prevents locking one mutex twice (self-deadlock); a real transfer would also check for sufficient funds before debiting.

Line by line

Walkthrough of the dangerous moment — two threads racing into transfer at the same time.

1. main initializes both accounts to 1,000,000 and creates the mutexes with pthread_mutex_init. It checks the return values, because a failed init would leave you locking an uninitialized mutex (undefined behavior).
2. pthread_create starts worker_ab (transfers a -> b) and worker_ba (transfers b -> a). Now two threads run transfer concurrently with the arguments swapped: thread 1 calls transfer(&a, &b, ...), thread 2 calls transfer(&b, &a, ...).
3. Inside transfer, both call lock_pair, but with x and y in opposite roles. This is exactly where naive code would deadlock.
4. lock_pair ignores the roles and compares the addresses &x->lock and &y->lock. Suppose &a.lock < &b.lock. Then:
   • Thread 1 (x=&a, y=&b): the if is true, so it locks a then b.
   • Thread 2 (x=&b, y=&a): the if (&b.lock < &a.lock) is false, so it locks a then b too.
5. Both threads therefore try to acquire a.lock first. Whichever wins proceeds to b.lock; the loser simply waits for a.lock. There is no "each holds what the other wants" — the loser holds nothing yet, so no cycle.

Trace of one collision (assume &a.lock < &b.lock):

Thread 2 only ever waits for a.lock, which it does not yet hold — so it cannot be part of a cycle. Compare this with the broken version where thread 2 would lock b first: then in step 2 it would hold b and wait for a while thread 1 holds a and waits for b → cycle → deadlock.

6. After both loops finish, pthread_join blocks main until each thread returns, guaranteeing the prints happen after all transfers.
7. pthread_mutex_destroy frees any resources the mutexes hold. main returns 0.

Common mistakes

Mistake 1 — Inconsistent lock order across functions

Wrong:

void f(void){ lock(&m1); lock(&m2); /* ... */ unlock(&m2); unlock(&m1); }
void g(void){ lock(&m2); lock(&m1); /* ... */ unlock(&m1); unlock(&m2); }

f takes m1→m2, g takes m2→m1. Run them on two threads and they can form the AB-BA cycle. Why it is wrong: the two functions disagree on the global order, which is the one thing the prevention rule requires them to share. It "works" in light testing because the bad interleaving is rare.

Corrected: pick one order (say m1 before m2) and use it everywhere, or route all double-locking through one lock_pair-style helper so there is a single place that decides the order.

How to catch it: grep for every place two locks are taken together and confirm the order matches; tools like ThreadSanitizer's deadlock detector and helgrind flag inconsistent orders.

Mistake 2 — Leaking a lock after a failed trylock

Wrong:

pthread_mutex_lock(&m1);
if (pthread_mutex_trylock(&m2) != 0)
    return -1;            /* BUG: still holding m1! */
/* ... work ... */
pthread_mutex_unlock(&m2);
pthread_mutex_unlock(&m1);

Why it is wrong: on the failure path you return while still holding m1. The next thread that needs m1 blocks forever — you turned a back-off into a permanent stall.

Corrected: always release what you already hold before backing off, then retry:

for (;;) {
    pthread_mutex_lock(&m1);
    if (pthread_mutex_trylock(&m2) == 0) break;   /* got both */
    pthread_mutex_unlock(&m1);                     /* drop m1, then retry */
    /* optionally sched_yield() to let the other thread progress */
}

Mistake 3 — Re-locking a non-recursive mutex (self-deadlock)

Wrong: a function locks m, then calls a helper that also locks m. A default (non-recursive) pthread_mutex_t will deadlock the thread against itself. Corrected: restructure so the lock is taken once, or pass a flag indicating the lock is already held; only use PTHREAD_MUTEX_RECURSIVE deliberately, knowing it can hide design problems.

Debugging tips

The symptom: the program hangs, makes no progress, and uses little or no CPU (the threads are sleeping in the kernel waiting on a lock, not spinning). An infinite loop burns 100% CPU; a deadlock burns ~0%. That difference is your first clue.

Step 1 — attach a debugger and look at the threads. With the process hung:

gdb -p <pid>
(gdb) info threads          # lists all threads and where each is
(gdb) thread apply all bt   # backtrace of every thread

Look for two (or more) threads parked inside __lll_lock_wait / pthread_mutex_lock. Read the frames just above to see which mutex each is waiting on and what each already holds. If thread 1 waits on lock X (held by thread 2) and thread 2 waits on lock Y (held by thread 1), you have found the cycle.

Step 2 — use a deadlock-aware tool during testing.

• valgrind --tool=helgrind ./prog reports lock-order inconsistencies ("lock order violated") even when the run did not actually hang.
• Compile with -fsanitize=thread (ThreadSanitizer); it detects lock-order inversions and data races.

Common errors and what they mean:

• Compiler: undefined reference to pthread_create → you forgot -pthread on the compile/link line.
• Runtime: locking an uninitialized mutex → check pthread_mutex_init return value; on some systems this is undefined behavior rather than a clean error.
• Logic: program finishes most of the time but rarely hangs → almost always an inconsistent lock order; do not "fix" it by adding sleeps, fix the order.

Questions to ask when it hangs: Which locks does each stuck thread hold, and which is it waiting for? Do all code paths take those locks in the same order? Is any thread re-locking a mutex it already holds? Did a failed trylock/early return/error path skip an unlock?

Memory safety

Deadlocks are a liveness failure, not a memory-corruption failure — but the surrounding multithreaded code raises real undefined-behavior and robustness concerns you must handle alongside lock ordering:

• Lock the mutex before every access to the data it protects. Reading or writing shared data without the lock is a data race, which is undefined behavior in C11 — even if you got the lock order right.
• Match every lock with exactly one unlock on every path, including early returns and error paths. A missed unlock is itself a permanent stall for the next thread. Keep critical sections short and structure them so there is one exit point, or use a cleanup helper.
• Do not lock by address if the object can be freed or moved while another thread might be ordering against it. Address ordering assumes the addresses are stable for the duration of the operation.
• Never re-lock a non-recursive mutex you already hold; that is a self-deadlock (a degenerate cycle of length one).
• Initialize before use, destroy after use. Use pthread_mutex_init (and check its return) or the static PTHREAD_MUTEX_INITIALIZER, and pthread_mutex_destroy when done. Locking an uninitialized or already-destroyed mutex is undefined behavior.
• Integer/state safety inside the critical section still applies: the lock makes the section atomic with respect to other threads, but it does not validate your arithmetic. In the transfer example, you still need to check for sufficient funds and avoid overflow before mutating balances.

Real-world uses

Concrete uses:

• Databases acquire row and table locks; engines like PostgreSQL and MySQL run an internal deadlock detector that aborts one transaction (the "victim") to break a cycle, returning an error you must retry. Application code that locks rows in inconsistent orders is a frequent cause.
• Operating-system kernels (Linux included) enforce documented lock-ordering hierarchies; lockdep is a kernel feature that learns lock orders at runtime and warns on any inversion, exactly the global-ordering idea from this lesson.
• Bank/ledger transfers, filesystem rename (locking two directories), and GUI frameworks (UI thread + worker thread) are textbook two-lock situations that need a consistent order.

Professional best practices:

Beginner rules: (1) Hold as few locks as possible, for as short a time as possible. (2) If you must hold two, define one global order and route all multi-lock acquisition through a single helper. (3) Never call unknown/foreign code (callbacks, library functions) while holding a lock — it might try to lock something and invert your order. (4) Match every lock with an unlock on every path.

Advanced habits: document your lock hierarchy in code comments; prefer designs that need only one lock at a time (e.g., copy data out, release, then process); use lock-ordering checkers (helgrind, TSan, kernel lockdep) in CI; where ordering is genuinely impossible, use trylock with disciplined back-off; and make operations idempotent/retryable so a database-style "victim, please retry" strategy is safe.

Practice tasks

Beginner 1 — Spot the inversion. Given two functions, one that locks m1 then m2 and one that locks m2 then m1, write out the AB-BA trace table (like the one in this lesson) showing the exact interleaving that deadlocks. Then rewrite the second function so both share one order. Concepts: circular wait, global ordering. Hint: the deadlock needs each thread to grab its first lock before either grabs its second.

Beginner 2 — Reproduce, then fix. Write a program with two mutexes and two threads that take them in opposite orders inside a loop. Confirm it eventually hangs (use ~0% CPU as the signal). Then apply address ordering and confirm it now always completes. Requirements: compile with -pthread; print a counter so you can see progress stop. Concepts: deadlock symptom, address ordering.

Intermediate 1 — lock_pair helper. Implement void lock_pair(pthread_mutex_t *a, pthread_mutex_t *b) and a matching unlock that always acquire in address order and correctly handle the a == b case (lock once, not twice). Write a small test that calls it from two threads with the arguments swapped and verifies no hang. Concepts: ordering by address, self-deadlock guard.

Intermediate 2 — trylock back-off. Rewrite the two-lock acquisition using pthread_mutex_lock on the first mutex and pthread_mutex_trylock on the second, releasing the first and retrying on failure. Add a counter for how many retries happened and print it. Requirements: no lock may be held across the retry boundary. Concepts: breaking "no preemption," avoiding the lock-leak bug. Hint: EBUSY is the failure return; consider sched_yield() between retries.

Challenge — N-account transfer. Extend the bank example to a function transfer_many(Account **accts, long *deltas, int n) that atomically applies deltas[i] to accts[i] while holding all relevant locks. Acquire the locks in a single consistent global order (sort the account pointers by address first, deduplicate, then lock in that order; unlock in reverse). Verify under heavy multithreaded load that the total across all accounts is conserved. Constraints: no thread may ever take two of these locks in different relative orders; handle duplicate accounts. Concepts: generalizing global ordering to N locks, sorting by address, all-or-nothing acquisition. Hint: qsort the pointer array; you do not need trylock if the order is total and consistent.

Summary

• A deadlock is a permanent circular wait: a set of threads each block holding a lock another needs, so none ever releases. It hangs the program silently at ~0% CPU rather than crashing.
• It needs at least two locks and the AB-BA pattern, where threads take the same locks in opposite orders. It is intermittent because it depends on an unlucky interleaving.
• Deadlock requires all four Coffman conditions at once: mutual exclusion, hold-and-wait, no preemption, circular wait. Break any one and it cannot happen.
• The standard cure is a global lock order — always acquire multiple locks in the same order. When names are unknown, order by mutex address so every thread agrees. Centralize this in one lock_pair-style helper.
• An alternative is trylock with back-off (release what you hold and retry), which breaks "no preemption" — but never return or retry while still holding a lock.
• Most important to remember: never hold two locks in inconsistent orders, keep critical sections short, unlock on every path, and use helgrind/ThreadSanitizer to catch order violations before they hang production.

Practice with these exercises

• Opposite lock ordering
• Consistent lock order
• Fix the race with a pthread_mutex_t