What Is a Deadlock?

Classic Two-Mutex Deadlock

Here is the most common deadlock scenario: Thread A locks mutex1 then tries to lock mutex2. Thread B locks mutex2 then tries to lock mutex1.

Code Example 1: Deadlock in Action

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

pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;

/* Thread A: locks mutex1 FIRST, then mutex2 */
void *threadA(void *arg)
{
    printf("Thread A: locking mutex1\n");
    pthread_mutex_lock(&mutex1);
    printf("Thread A: locked mutex1, now trying mutex2\n");

    sleep(1); /* Give Thread B time to lock mutex2 */

    printf("Thread A: trying to lock mutex2 (will DEADLOCK)\n");
    pthread_mutex_lock(&mutex2);  /* <-- Will block here FOREVER */

    printf("Thread A: locked both (will never print)\n");
    pthread_mutex_unlock(&mutex2);
    pthread_mutex_unlock(&mutex1);
    return NULL;
}

/* Thread B: locks mutex2 FIRST, then mutex1 (opposite order!) */
void *threadB(void *arg)
{
    printf("Thread B: locking mutex2\n");
    pthread_mutex_lock(&mutex2);
    printf("Thread B: locked mutex2, now trying mutex1\n");

    sleep(1); /* Give Thread A time to lock mutex1 */

    printf("Thread B: trying to lock mutex1 (will DEADLOCK)\n");
    pthread_mutex_lock(&mutex1);  /* <-- Will block here FOREVER */

    printf("Thread B: locked both (will never print)\n");
    pthread_mutex_unlock(&mutex1);
    pthread_mutex_unlock(&mutex2);
    return NULL;
}

int main(void)
{
    pthread_t tA, tB;
    pthread_create(&tA, NULL, threadA, NULL);
    pthread_create(&tB, NULL, threadB, NULL);

    pthread_join(tA, NULL);  /* Will wait forever */
    pthread_join(tB, NULL);  /* Will wait forever */

    printf("Done (will never print)\n");
    return 0;
}

/*
 * Compile: gcc -o deadlock deadlock.c -lpthread
 * Run: ./deadlock
 * The program will hang — press Ctrl+C to kill it.
 *
 * Output before hanging:
 *   Thread A: locking mutex1
 *   Thread B: locking mutex2
 *   Thread A: locked mutex1, now trying mutex2
 *   Thread B: locked mutex2, now trying mutex1
 *   Thread A: trying to lock mutex2 (will DEADLOCK)
 *   Thread B: trying to lock mutex1 (will DEADLOCK)
 *   [Program hangs here]
 */

Solution 1: Lock Hierarchy (Recommended)

The simplest and most reliable way to prevent deadlock is the mutex hierarchy rule:

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

pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;

/* FIXED Thread A: locks mutex1 FIRST, then mutex2 */
void *threadA_fixed(void *arg)
{
    pthread_mutex_lock(&mutex1);   /* Always lock mutex1 first */
    printf("Thread A: locked mutex1\n");
    sleep(1);
    pthread_mutex_lock(&mutex2);   /* Then mutex2 */
    printf("Thread A: locked mutex2\n");

    /* Critical work */
    printf("Thread A: doing work with both mutexes\n");

    pthread_mutex_unlock(&mutex2); /* Unlock in reverse order */
    pthread_mutex_unlock(&mutex1);
    printf("Thread A: done\n");
    return NULL;
}

/* FIXED Thread B: ALSO locks mutex1 FIRST, then mutex2 (same order!) */
void *threadB_fixed(void *arg)
{
    pthread_mutex_lock(&mutex1);   /* Same order as Thread A */
    printf("Thread B: locked mutex1\n");
    sleep(1);
    pthread_mutex_lock(&mutex2);
    printf("Thread B: locked mutex2\n");

    printf("Thread B: doing work with both mutexes\n");

    pthread_mutex_unlock(&mutex2);
    pthread_mutex_unlock(&mutex1);
    printf("Thread B: done\n");
    return NULL;
}

int main(void)
{
    pthread_t tA, tB;
    pthread_create(&tA, NULL, threadA_fixed, NULL);
    pthread_create(&tB, NULL, threadB_fixed, NULL);
    pthread_join(tA, NULL);
    pthread_join(tB, NULL);
    printf("Both threads completed successfully — no deadlock!\n");
    return 0;
}

/*
 * One thread will block waiting for mutex1 while the other
 * holds it and acquires mutex2. But since BOTH want mutex1 first,
 * there is no circular wait. Eventually Thread A gets both, finishes,
 * and releases — then Thread B gets both. No deadlock.
 */

Solution 2: Try-and-Back-Off

An alternative strategy: lock the first mutex with pthread_mutex_lock(), then try the remaining ones with pthread_mutex_trylock(). If any trylock fails, release all locks and retry after a delay.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>

pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;

/* Try to acquire both mutexes; back off and retry if we can't */
int acquire_both(pthread_mutex_t *m1, pthread_mutex_t *m2)
{
    while (1) {
        /* Lock the first one (blocking is OK) */
        pthread_mutex_lock(m1);

        /* Try the second without blocking */
        if (pthread_mutex_trylock(m2) == 0) {
            return 1;  /* Got both! */
        }

        /* Couldn't get m2 — release m1 and back off */
        pthread_mutex_unlock(m1);

        /* Small random delay to reduce livelock */
        struct timespec ts = {0, (rand() % 10 + 1) * 1000000};
        nanosleep(&ts, NULL);
        printf("Backing off, retrying...\n");
    }
}

void *threadA(void *arg)
{
    acquire_both(&mutex1, &mutex2);
    printf("Thread A: has both locks\n");
    /* do work */
    pthread_mutex_unlock(&mutex2);
    pthread_mutex_unlock(&mutex1);
    return NULL;
}

void *threadB(void *arg)
{
    /* Thread B tries in a different order — would cause deadlock
     * with straight locking, but try-and-backoff prevents it */
    acquire_both(&mutex2, &mutex1);
    printf("Thread B: has both locks\n");
    /* do work */
    pthread_mutex_unlock(&mutex1);
    pthread_mutex_unlock(&mutex2);
    return NULL;
}

int main(void)
{
    pthread_t tA, tB;
    pthread_create(&tA, NULL, threadA, NULL);
    pthread_create(&tB, NULL, threadB, NULL);
    pthread_join(tA, NULL);
    pthread_join(tB, NULL);
    printf("Both done — no deadlock\n");
    return 0;
}