Deadlock & Race Conditions

A race condition occurs when the correctness of a program depends on the relative timing or interleaving of operations by multiple threads or processes. The program's output is non-deterministic: run it ten times, get ten different answers — or nine correct answers and one catastrophic one.

The classic example is a shared counter. Two threads each want to increment a variable x from 0 to 1. In C, x++ looks atomic — but it compiles to three machine instructions: LOAD x into a register, ADD 1, STORE back. If both threads execute LOAD before either executes STORE, they both read 0, both compute 1, and both write 1. The counter ends up at 1 instead of 2. You've lost an increment.

This is called a lost update — one of the most common manifestations of a race condition.

The window of time during which a race can occur is called the critical section. The goal of synchronization primitives (mutexes, semaphores, spinlocks) is to ensure that critical sections execute atomically — as if they were a single indivisible operation, even though they are not.

Key insight: a race condition is a bug in the happens-before relationship. If operation A must always complete before operation B observes its effects, but the language/hardware/compiler does not enforce that ordering, you have a race.

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

static int counter = 0;

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        counter++;  // NOT atomic: load, add, store
    }
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    // Expected: 2000000. Actual: varies — often ~1100000
    printf("counter = %d\n", counter);
    return 0;
}
// Compile: gcc -O0 -pthread race.c -o race && ./race

These terms are often used interchangeably, but experts distinguish them:

• A data race (the C11/C++11 formal definition) is when two threads access the same memory location, at least one access is a write, and the accesses are not ordered by synchronization. A data race is undefined behavior in C/C++. The compiler and CPU are allowed to do anything — reorder, cache, invent values.

• A race condition is a broader, semantic concept: the program's behavior depends on thread interleaving in a way the programmer didn't intend. You can have a race condition without a data race (e.g., using atomic operations but still having a TOCTOU bug — see below), and in theory you could have a data race that doesn't manifest as a bug (though relying on this is catastrophic practice).

TOCTOU (Time-Of-Check to Time-Of-Use) is a classic race condition without a data race. A program checks if (file_exists(path)) then opens the file. Between the check and the open, another process deletes the file and replaces it with a symlink. The individual memory accesses are fine — the race is in the semantic gap between two operations.

In the Linux kernel, KCSAN catches data races. Logical race conditions require code review and formal reasoning. This distinction matters: fixing a data race (add atomics or a lock) does not necessarily fix a semantic race condition.

// TOCTOU race — no data race, but definitely a bug
#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>

int safe_open(const char *path) {
    // BAD: check then use — window exists between the two syscalls
    if (access(path, R_OK) == 0) {   // <-- check
        // attacker swaps path to /etc/shadow HERE
        return open(path, O_RDONLY); // <-- use
    }
    return -1;
}

// GOOD: open first, then check permissions via the fd
int safer_open(const char *path) {
    int fd = open(path, O_RDONLY | O_NOFOLLOW);
    // O_NOFOLLOW prevents symlink swap attacks
    return fd;
}

A critical section is a segment of code that accesses a shared resource and must not be executed by more than one thread at a time. Mutual exclusion (mutex) is the property that guarantees this — at most one thread is inside the critical section at any moment.

Any correct mutual exclusion solution must satisfy three properties (Dijkstra, 1965):

1. Mutual exclusion: No two processes execute their critical sections simultaneously.
2. Progress: If no process is in its critical section and some processes wish to enter, the decision about who enters next cannot be postponed indefinitely.
3. Bounded waiting: There exists a bound on how many times other processes can enter their critical sections after a process has made a request and before that request is granted (no starvation).

In modern systems, we use OS-provided primitives (mutexes, semaphores, spinlocks) rather than implementing these from scratch. But the properties matter: a bad lock implementation might satisfy mutual exclusion but violate bounded waiting, causing starvation.

In the Linux kernel, the workhorse is struct mutex for process context and spinlock_t for interrupt context. The rule is: never hold a sleeping lock (mutex) from interrupt context — because interrupt handlers cannot sleep, and a deadlock would result.

The size of the critical section matters enormously for performance: a smaller critical section means less contention and more parallelism. This is the fundamental tension in concurrent programming: safety vs. scalability.

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

static int counter = 0;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&lock);   // enter critical section
        counter++;                    // exactly one thread here at a time
        pthread_mutex_unlock(&lock); // leave critical section
    }
    return NULL;
}

// Now counter is always exactly 2000000.
// Cost: ~10x slower — locking has overhead.
// Solution: batch updates, use __atomic_add_fetch, or per-thread counters.

A deadlock is a situation where a set of processes are each waiting for a resource held by another process in the set — and none can ever make progress. Deadlocks are insidious because they can be extremely rare, only occurring under specific timing that might never appear in testing but reliably appears in production under load.

In 1971, E. G. Coffman Jr., M. Elphick, and A. Shoshani identified the four necessary and sufficient conditions for deadlock. All four must hold simultaneously for deadlock to occur. If you can break any one of them, you prevent deadlock.

1. Mutual Exclusion: Resources cannot be shared — only one process can use a resource at a time. (Locks, by definition, provide mutual exclusion.)

2. Hold and Wait: A process holds at least one resource while waiting to acquire additional resources held by other processes. This is the "greedy" behavior: I have lock A and I'm waiting for lock B.

3. No Preemption: Resources cannot be forcibly taken away from a process. A lock cannot be "stolen" — you must wait for the holder to release it voluntarily.

4. Circular Wait: There exists a circular chain of two or more processes, each waiting for a resource held by the next in the chain. P1 waits for P2's resource, P2 waits for P3's resource, ..., Pn waits for P1's resource.

Analogy: Four cars approach a 4-way stop simultaneously, each nose-to-tail in a circle. Each car holds the segment in front of it (Hold and Wait) and needs the segment occupied by the car ahead (Circular Wait). Nobody will back up (No Preemption). And a road segment can only hold one car (Mutual Exclusion). Gridlock — a physical deadlock.

// Classic two-thread deadlock demonstrating all 4 Coffman conditions
#include <pthread.h>
#include <stdio.h>

pthread_mutex_t lock_A = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_B = PTHREAD_MUTEX_INITIALIZER;

void *thread1(void *arg) {
    pthread_mutex_lock(&lock_A);   // holds A
    printf("T1: acquired A, waiting for B\n");
    // --- T2 may acquire B here ---
    pthread_mutex_lock(&lock_B);   // waits for B (held by T2)
    pthread_mutex_unlock(&lock_B);
    pthread_mutex_unlock(&lock_A);
    return NULL;
}

void *thread2(void *arg) {
    pthread_mutex_lock(&lock_B);   // holds B
    printf("T2: acquired B, waiting for A\n");
    pthread_mutex_lock(&lock_A);   // waits for A (held by T1)
    pthread_mutex_unlock(&lock_A);
    pthread_mutex_unlock(&lock_B);
    return NULL;
}
// Mutual exclusion: locks are exclusive
// Hold & Wait: each thread holds one, waits for the other
// No preemption: neither can steal the other's lock
// Circular wait: T1->B->T2->A->T1

Deadlock is not the only way a system can fail to make progress. Two related failure modes are just as important:

Livelock is like deadlock, except the processes are active — they keep changing state, keep doing work — but they make no useful progress. The classic human analogy: two people approaching each other in a narrow hallway. Each steps aside politely to let the other pass. They both step in the same direction. They both step back. They dance forever, both moving, neither progressing.

In systems: two processes each detect a conflict and "back off" to retry. If they back off by the same amount and retry at the same time, they conflict again forever. The fix is randomized exponential backoff — Ethernet's CSMA/CD protocol uses this. Without the randomization, you have livelock.

Starvation is when a process is perpetually denied access to a resource it needs, even though the resource is repeatedly available to other processes. No cycle is required. A low-priority thread may never get the lock because high-priority threads always grab it first. The lock is always available in principle — just never available to that thread.

Starvation violates the bounded waiting property of mutual exclusion. Solutions include fair locks (FIFO queues — whoever waited longest goes next), priority aging (gradually increase the priority of waiting processes), or priority-inheritance protocols (used in real-time Linux via pthread_mutexattr_setprotocol).

The distinction matters: deadlock is guaranteed failure for everyone. Livelock is busy failure for everyone. Starvation is failure for the unlucky few while others proceed normally.

// Livelock sketch — two threads back off identically
// In real code, replace fixed sleep with randomized backoff
#include <pthread.h>
#include <unistd.h>
#include <stdbool.h>

static bool resource_available = false;

void *worker(void *id) {
    int tid = *(int *)id;
    while (true) {
        if (resource_available) {
            // "acquire" resource
            resource_available = false;
            // do work...
            resource_available = true;
        } else {
            // Both back off for the same fixed time -> livelock
            usleep(1000); // FIX: usleep(rand() % 2000)
        }
    }
    return NULL;
}

Prevention means structuring the system so that at least one of the four Coffman conditions can never hold. This is the most rigorous approach.

Breaking Mutual Exclusion: Make resources shareable. Read-only data can be shared by many readers simultaneously (read-write locks, pthread_rwlock_t). But for truly exclusive resources (writes, hardware ports), you cannot eliminate mutual exclusion — it's inherent.

Breaking Hold and Wait: Two strategies:

• Request all resources at once: A process must declare all resources it needs upfront and acquire them atomically. Drawback: processes often don't know in advance what they need, and holding all resources for the duration wastes them.
• Release before requesting: If a process needs a new resource, it releases all currently held resources, then re-requests everything. Drawback: work may need to be undone; prone to starvation.

Breaking No Preemption: Allow resources to be taken away. In databases, this is deadlock victim selection: when a deadlock is detected, one transaction is killed (preempted) and rolled back. Its locks are released, breaking the cycle. Works well when operations are transactional (can be retried). Terrible for arbitrary kernel code where you can't "undo" a hardware operation.

Breaking Circular Wait (Lock Ordering): Assign a global total order to all locks (e.g., by memory address, or by an assigned integer ID). Require that every thread acquires locks in strictly increasing order. Now circular wait is impossible: if T1 holds lock #3 and waits for lock #5, T2 can't hold #5 and wait for #3 — it would have had to acquire #3 before #5, but #3 is held by T1.

Lock ordering is the most widely used prevention strategy in the Linux kernel. Documentation/locking/lockdep-design.rst describes how lockdep enforces this at runtime.

// Lock ordering: always acquire locks in address order
// This breaks circular wait
#include <pthread.h>
#include <stdint.h>

void lock_pair(pthread_mutex_t *a, pthread_mutex_t *b) {
    // Impose total order by pointer value
    if ((uintptr_t)a < (uintptr_t)b) {
        pthread_mutex_lock(a);
        pthread_mutex_lock(b);
    } else {
        pthread_mutex_lock(b);
        pthread_mutex_lock(a);
    }
}

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

// Now thread1 and thread2 both call lock_pair(&lock_A, &lock_B)
// They will always acquire in the same order: no deadlock possible.

Avoidance takes a different approach: don't statically forbid configurations, but dynamically refuse resource allocations that could lead to deadlock. The system stays in a safe state — one from which every process can eventually complete, in some order.

A state is safe if there exists a safe sequence: an ordering P1, P2, ..., Pn such that each Pi's remaining resource needs can be satisfied by the currently available resources plus the resources held by all Pj where j < i.

Dijkstra's Banker's Algorithm (1965) is the canonical avoidance algorithm. The name comes from a bank: a banker (the OS) has a fixed amount of capital (resources). Customers (processes) declare their maximum claim upfront. The banker only lends if the resulting state is safe — if every loan can theoretically be repaid without triggering a cascade where no one can repay.

The algorithm:

1. Before granting a request, tentatively grant it.
2. Run the safety check: can all processes still complete in some order with remaining resources?
3. If yes (safe state), grant permanently. If no (unsafe), block the requester.

Why it's rarely used in practice: It requires each process to declare its maximum resource needs in advance (often impossible), assumes a fixed number of processes and resource types (both change dynamically in a real OS), and the safety check is O(n² * m) where n = processes, m = resource types — too slow for a kernel hot path.

The Banker's Algorithm is crucial to understand because it crystallizes the concept of safe vs. unsafe states, and many real-world techniques (timeout-based deadlock detection, two-phase locking in databases) are practical approximations of its core insight.

/* Simplified Banker's safety check in C.
   n processes, m resource types.
   available[j] = currently free units of resource j
   need[i][j]   = max additional units process i may request
   alloc[i][j]  = units currently allocated to process i      */
#include <stdbool.h>
#define N 5
#define M 3

bool is_safe(int available[M], int need[N][M], int alloc[N][M]) {
    int work[M];
    bool finish[N] = {false};
    for (int j = 0; j < M; j++) work[j] = available[j];

    int count = 0;
    while (count < N) {
        bool found = false;
        for (int i = 0; i < N; i++) {
            if (finish[i]) continue;
            // Can process i's remaining needs be met?
            bool can = true;
            for (int j = 0; j < M; j++)
                if (need[i][j] > work[j]) { can = false; break; }
            if (can) {
                for (int j = 0; j < M; j++)
                    work[j] += alloc[i][j]; // process finishes, returns resources
                finish[i] = true;
                found = true;
                count++;
            }
        }
        if (!found) return false; // unsafe: no process can proceed
    }
    return true; // safe sequence found
}

When prevention and avoidance are too costly, a third strategy is to let deadlocks happen, detect them, and recover. This is the approach taken by most database systems (PostgreSQL, MySQL InnoDB) and by the Linux kernel's optional lockdep in debug mode.

Detection works by building a Resource Allocation Graph (RAG):

• Nodes: processes (circles) and resource instances (squares).
• Edges: P → R (request edge: process P is waiting for resource R) and R → P (assignment edge: resource R is held by process P).
• Deadlock exists if and only if the RAG contains a cycle (when each resource has only one instance; for multiple instances, a more complex reduction algorithm is needed).

For the multi-instance case, the detection algorithm is essentially the Banker's safety check run after the fact.

Recovery options (from least to most disruptive):

1. Process termination: Kill one or more processes in the deadlock cycle. Selection criteria: minimum cost — prefer killing the youngest process, the one with least work done, the one holding fewest resources.
2. Resource preemption: Take a resource away from a process, roll that process back to an earlier checkpoint, and give the resource to another. Requires checkpoint/rollback infrastructure.
3. Rollback: Roll one process back to a safe state before it acquired the conflicting locks (database transactions are built for this).

Detection frequency trades off overhead vs. recovery cost. Detect too rarely: deadlocks linger, users suffer. Detect too often: CPU cycles wasted checking. A practical middle ground: run detection when CPU utilization drops unexpectedly (a hint that something is stuck).

/* Resource Allocation Graph cycle detection
   Adjacency list representation, DFS-based            */
#include <stdbool.h>
#include <string.h>
#define MAX 16

typedef struct { int adj[MAX]; int n; } Node;
Node graph[MAX];
int  total_nodes;

bool dfs(int v, bool *visited, bool *rec_stack) {
    visited[v] = rec_stack[v] = true;
    for (int i = 0; i < graph[v].n; i++) {
        int u = graph[v].adj[i];
        if (!visited[u] && dfs(u, visited, rec_stack))
            return true;
        if (rec_stack[u])
            return true; // back edge -> cycle -> deadlock
    }
    rec_stack[v] = false;
    return false;
}

bool has_deadlock(void) {
    bool visited[MAX]   = {false};
    bool rec_stack[MAX] = {false};
    for (int i = 0; i < total_nodes; i++)
        if (!visited[i] && dfs(i, visited, rec_stack))
            return true;
    return false;
}

Dijkstra's Dining Philosophers problem (1965) is the most elegant test case for concurrent resource-sharing algorithms ever devised. Here it is:

Five philosophers sit at a round table. Between each adjacent pair of philosophers lies a single chopstick (5 philosophers, 5 chopsticks). Each philosopher alternates between thinking and eating. To eat, a philosopher needs both chopsticks adjacent to them. After eating, they put both chopsticks down.

If every philosopher simultaneously picks up their left chopstick and then waits for their right chopstick — deadlock. This is a perfect concrete instance of all four Coffman conditions: mutual exclusion (a chopstick can only be held by one), hold and wait (holding left, waiting for right), no preemption (can't grab a chopstick from another), circular wait (each waits for the next's chopstick in a circle).

Solutions:

1. Allow only N-1 philosophers to sit simultaneously: If at most 4 of 5 philosophers try to eat at once, at least one chopstick is always free, preventing full circular wait. A counting semaphore initialized to 4 enforces this.

2. Lock ordering (asymmetry): Number chopsticks 0–4. All philosophers pick up the lower-numbered chopstick first. This breaks circular wait — philosopher 4 now picks up chopstick 4 before chopstick 0, same order as philosopher 0. The symmetry that creates the cycle is broken.

3. Chandy/Misra solution: Philosophers send requests for chopsticks. A holder sends the chopstick if it's clean (unused since last received) or if they're not hungry. Uses message-passing, no shared memory, fully distributed.

4. Waiter (central arbiter): A waiter controls access to the table, granting permission to pick up chopsticks only when both are free. Serializes but eliminates deadlock. Works but is a bottleneck.

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#define N 5

pthread_mutex_t chopstick[N];

void think(int id) { printf("P%d thinking\n", id); usleep(100000); }
void eat(int id)   { printf("P%d eating\n",  id); usleep(100000); }

void *philosopher(void *arg) {
    int id = *(int *)arg;
    int left  = id;
    int right = (id + 1) % N;

    // Lock-ordering fix: last philosopher picks up RIGHT first
    // This breaks the circular wait
    for (int i = 0; i < 3; i++) {
        think(id);
        if (id == N - 1) {
            pthread_mutex_lock(&chopstick[right]);
            pthread_mutex_lock(&chopstick[left]);
        } else {
            pthread_mutex_lock(&chopstick[left]);
            pthread_mutex_lock(&chopstick[right]);
        }
        eat(id);
        pthread_mutex_unlock(&chopstick[left]);
        pthread_mutex_unlock(&chopstick[right]);
    }
    return NULL;
}

int main(void) {
    pthread_t ph[N]; int ids[N];
    for (int i = 0; i < N; i++) {
        pthread_mutex_init(&chopstick[i], NULL);
        ids[i] = i;
    }
    for (int i = 0; i < N; i++)
        pthread_create(&ph[i], NULL, philosopher, &ids[i]);
    for (int i = 0; i < N; i++)
        pthread_join(ph[i], NULL);
    return 0;
}

The Linux kernel enforces lock ordering at runtime using lockdep — a dynamic lock dependency checker that ships in debug kernels (CONFIG_PROVE_LOCKING=y).

lockdep builds a directed graph of lock acquisition orders. Every time a lock is acquired while holding another, an edge is added: "lock A was held when lock B was acquired". If this graph ever develops a cycle — if the kernel ever acquires locks in an order that could lead to deadlock — lockdep fires immediately, before the actual deadlock, with a full stack trace and lock history.

This is a profound idea: lockdep doesn't wait for the deadlock to actually happen. It detects that the acquisition pattern is potentially deadlock-inducing, and screams the moment that pattern appears. A rare deadlock that only manifests under specific timing (perhaps once a week in production) will be caught in the first second of a test run if the order is ever acquired in two different directions.

Key lockdep concepts:

• Lock classes: lockdep doesn't track individual lock instances but classes (e.g., "all spinlocks in struct inode" are one class). This keeps the graph tractable.
• Annotations: lockdep_assert_held(), lockdep_assert_not_held() — assertions you can add to document and verify locking requirements.
• lock_is_held() — query whether the current thread holds a lock.

For the kernel contributor: when you write code that acquires multiple locks, you must document and verify the lock order. The convention in the kernel source is comments like /* Must be called with foo->lock held */ and annotating which locks protect which fields.

/* Kernel-style lock ordering annotation pattern.
   Not runnable userspace code — illustrates the idiom.   */

// In a real kernel driver:
// Rule: always acquire dev->big_lock before dev->small_lock

static void do_something(struct my_device *dev)
{
    spin_lock(&dev->big_lock);   /* outer lock — acquired first */

    /* lockdep_assert_held(&dev->big_lock); */  /* document requirement */

    spin_lock(&dev->small_lock); /* inner lock — acquired second */

    /* ... critical section ... */

    spin_unlock(&dev->small_lock);
    spin_unlock(&dev->big_lock);
    /* Reverse order of release is a style convention,
       not a correctness requirement for mutexes/spinlocks,
       but it mirrors acquisition order and aids readability */
}

To truly understand race conditions at the systems level, you must understand that CPUs do not execute instructions in program order. Modern CPUs and compilers perform reordering for performance: out-of-order execution, store buffers, load forwarding, write combining. From the perspective of another CPU core, stores to memory can appear to happen in a different order than you wrote them.

This is formalized in a CPU's memory model. x86 has a relatively strong model (Total Store Order — TSO): stores are seen in program order by all cores, but loads can be reordered with respect to subsequent stores. ARM and RISC-V have weaker models: loads and stores can be reordered in almost any way unless you insert explicit barriers.

A memory barrier (fence) is an instruction that constrains reordering:

• mfence (x86): full barrier — no load or store may cross this point.
• dmb ish (ARM): data memory barrier, inner shareable domain.
• fence rw, rw (RISC-V): fence for reads and writes.

In C11/C++11, _Atomic types and atomic_thread_fence() express the required ordering portably. In the Linux kernel, smp_mb(), smp_rmb(), smp_wmb(), and READ_ONCE()/WRITE_ONCE() are the standard tools.

READ_ONCE(x) and WRITE_ONCE(x, v) prevent the compiler from optimizing away or merging accesses to shared variables, which is a separate (and equally real) source of races.

This is why volatile in C does not fix race conditions: it prevents compiler caching but provides no memory ordering guarantees across cores. volatile is for memory-mapped I/O registers, not thread synchronization.

// Correct producer-consumer with C11 atomics
// No race, correct ordering guaranteed
#include <stdatomic.h>
#include <stdbool.h>

struct {
    int data;
    atomic_bool ready;  // C11 atomic
} shared = { .data = 0, .ready = false };

void producer(void) {
    shared.data = 42;                      // write data first
    atomic_store_explicit(               // THEN signal ready
        &shared.ready, true,
        memory_order_release);           // release barrier: data write
                                         // happens-before this store
}

void consumer(void) {
    while (!atomic_load_explicit(        // spin until ready
        &shared.ready,
        memory_order_acquire))           // acquire barrier: this load
        ;                                // happens-before data read
    int val = shared.data;               // guaranteed to see 42
    (void)val;
}
// memory_order_release + memory_order_acquire form a
// synchronization pair: establishes happens-before across threads.