Linux System Programming · advanced · ~10 min

Deadlocks

Recognise the four conditions for deadlock and the standard fix.

Lesson

A deadlock is when threads wait forever for each other to release locks. Classic case:

Thread A Thread B
lock(m1) lock(m2)
lock(m2) blocks lock(m1) blocks

Both threads hold one mutex and wait for the other. Neither can proceed.

Four necessary conditions (Coffman conditions):

  1. Mutual exclusion — locks can only be held by one thread.
  2. Hold and wait — a thread holds one lock while requesting another.
  3. No preemption — locks aren't forcibly taken away.
  4. Circular wait — a cycle in the lock dependency graph.

The simplest cure: enforce a global lock ordering. If every code path that takes both m1 and m2 always takes them in the order m1 then m2, no circular wait is possible. Sort by address (if (&m1 < &m2) lock(&m1); lock(&m2);) when you don't have static knowledge of names.

Code examples

/* Avoiding deadlock by ordering by address. */
#include <pthread.h>

static void lock2(pthread_mutex_t *a, pthread_mutex_t *b) {
    if (a < b) { pthread_mutex_lock(a); pthread_mutex_lock(b); }
    else       { pthread_mutex_lock(b); pthread_mutex_lock(a); }
}

static void unlock2(pthread_mutex_t *a, pthread_mutex_t *b) {
    pthread_mutex_unlock(a); pthread_mutex_unlock(b);
}

Common mistakes

  • Acquiring locks in different orders in different functions. Eventually two of them collide.
  • Using pthread_mutex_trylock "to avoid blocking" then forgetting to release the one you DID get when the second fails.

Summary

Deadlock = circular wait on locks. The cheapest cure is a global lock-ordering rule (often by address).

Practice with these exercises