Deadlock and how to avoid it

Understand what causes deadlock in multithreaded C programs and apply the design disciplines — lock ordering, timeouts, and lock hierarchies — that prevent it.

Deadlock is a situation where two or more threads are blocked permanently, each waiting for a resource held by another. No progress is possible. The program does not crash — it freezes. Deadlocks can take minutes or hours to appear in production after being latent in the code for months.

The four necessary conditions

Deadlock requires all four of these conditions simultaneously (Coffman, 1971):

Mutual exclusion: at least one resource can only be held by one thread at a time.
Hold and wait: a thread holds at least one resource while waiting to acquire another.
No preemption: resources cannot be forcibly taken — threads release them voluntarily.
Circular wait: there is a circular chain of threads where each holds a resource the next needs.

Breaking any one of the four prevents deadlock.

A minimal deadlock

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

static pthread_mutex_t A = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t B = PTHREAD_MUTEX_INITIALIZER;

void *thread1(void *arg) {
    (void)arg;
    pthread_mutex_lock(&A);
    sleep(1); /* give thread2 time to lock B */
    pthread_mutex_lock(&B); /* blocks -- B held by thread2 */
    printf("Thread 1 has both locks\n");
    pthread_mutex_unlock(&B);
    pthread_mutex_unlock(&A);
    return NULL;
}

void *thread2(void *arg) {
    (void)arg;
    pthread_mutex_lock(&B);
    sleep(1); /* give thread1 time to lock A */
    pthread_mutex_lock(&A); /* blocks -- A held by thread1 */
    printf("Thread 2 has both locks\n");
    pthread_mutex_unlock(&A);
    pthread_mutex_unlock(&B);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, thread1, NULL);
    pthread_create(&t2, NULL, thread2, NULL);
    pthread_join(t1, NULL); /* blocks forever */
    pthread_join(t2, NULL);
    return 0;
}

Thread 1 holds A and wants B. Thread 2 holds B and wants A. Neither can proceed. The sleep(1) calls make the interleaving deterministic for demonstration — in real code, a race determines whether the deadlock manifests.

Prevention: consistent lock ordering

The most reliable fix: always acquire multiple locks in the same order across all threads. If every thread always locks A before B, no circular wait can form:

void *thread1(void *arg) {
    pthread_mutex_lock(&A); /* always A before B */
    pthread_mutex_lock(&B);
    /* ... */
    pthread_mutex_unlock(&B);
    pthread_mutex_unlock(&A);
    return NULL;
}

void *thread2(void *arg) {
    pthread_mutex_lock(&A); /* same order: A before B */
    pthread_mutex_lock(&B);
    /* ... */
    pthread_mutex_unlock(&B);
    pthread_mutex_unlock(&A);
    return NULL;
}

Define a global lock ordering (by address, by a declared priority, or by a naming convention) and document it. Any code that needs multiple locks must acquire them in that order.

Prevention: trylock with backoff

pthread_mutex_trylock attempts to acquire a mutex without blocking, returning EBUSY if it cannot:

pthread_mutex_lock(&A);
if (pthread_mutex_trylock(&B) != 0) {
    /* Could not get B -- release A and try again */
    pthread_mutex_unlock(&A);
    usleep(1000); /* back off before retrying */
    /* restart from the top */
}

This breaks the "hold and wait" condition — a thread that cannot get all the locks gives up what it has. Combined with exponential backoff, this is a practical technique when lock ordering is infeasible.

Prevention: minimise the number of locks held simultaneously

The fewer locks a thread holds at once, the harder deadlock is to achieve. Design data structures so operations require at most one lock at a time. If you find yourself needing two locks, consider whether you can restructure the data.

Detecting deadlock with tools

helgrind (a valgrind tool) detects deadlocks and lock ordering violations:

valgrind --tool=helgrind ./program

It reports lock-order reversals even for deadlocks that did not actually manifest in the current run — making it a powerful preventive tool.

Condition variables and lock ordering. When using pthread_cond_wait, the mutex is released while waiting and re-acquired on wakeup. Be sure the lock ordering invariant is maintained at the point of re-acquisition — particularly if the awakened thread needs to acquire a second lock.

Where to go next

Next: the thread-safe bounded queue challenge — you will implement a complete, production-quality bounded queue using mutexes and condition variables.

Finished reading? Mark it complete to track your progress.