Deadlock & Starvation

A mutex that is never released is not a performance bug—it is a correctness bug. When two threads each hold a lock that the other needs, neither can proceed. The system does not crash, the process does not exit. Threads simply wait for each other, forever. This is deadlock, and it is one of the most feared failure modes in concurrent systems because it is so difficult to detect in testing, so subtle in production, and so catastrophic when it occurs.

Beyond deadlock lies starvation: a thread that is never given CPU time or resource access because other threads perpetually ahead of it claim the resources it needs. Deadlock freezes a set of threads; starvation leaves a thread permanently behind. Both violate the fundamental promise of a multi-tasking operating system: that every runnable thread will eventually make progress.

Overview

Deadlock occurs when a set of threads are all blocked, each waiting for a lock held by another thread in the set. The threads cannot unblock themselves because the holder of each needed lock is itself blocked waiting for another lock.

The condition for deadlock was formally described by Edward Coffman in 1971, and the four Coffman conditions remain the canonical characterization:

1. Mutual exclusion: At least one resource must be non-shareable (only one thread can use it at a time)
2. Hold and wait: A thread holds a resource while waiting for another resource held by another thread
3. No preemption: Resources cannot be forcibly taken from a holding thread; they must be released voluntarily
4. Circular wait: There exists a circular chain of threads, each waiting for a resource held by the next

All four conditions must hold simultaneously for deadlock to occur. Remove any one, and deadlock is impossible. This gives us four categories of prevention strategies, and two strategies for handling existing deadlock: detection and recovery.

When to Use / When Not to Use

Design for deadlock prevention from the start. Deadlock is not an edge case to handle later—it is a fundamental property of any system with multiple locks and multiple threads. Your architectural decisions about lock ordering, lock granularity, and which resources are exclusive determine whether your system can deadlock. Address this upfront.

When to use lock ordering: If your system must acquire multiple locks, define a global partial order and ensure every thread acquires locks in that order. This eliminates circular wait and prevents deadlock by construction. The cost: you may need to acquire locks in a non-intuitive order that complicates your call graph.

When to use trylock with backoff: pthread_mutex_trylock() attempts to acquire a lock without blocking. If it fails (returns EBUSY), you can release your held locks, do something else, and retry. This breaks the hold-and-wait condition but at the cost of more complex retry logic and potential livelock if two threads continuously retry in lock-step.

When to accept deadlock risk: In short-lived programs (scripts, one-shot tools), deadlock may never manifest because the program exits before the deadlock scenario arises. For long-running servers and embedded systems, deadlock prevention is mandatory.

Architecture or Flow Diagram

graph TD
    A[Thread A] --> B[Acquires Lock 1]
    B --> C[Thread B] --> D[Acquires Lock 2]
    D --> E[Thread A tries Lock 2<br/>BLOCKED - held by B]
    E --> F[Thread B tries Lock 1<br/>BLOCKED - held by A]
    F --> G[DEADLOCK]
    style G color:#fff

The circular wait: Thread A holds Lock 1 and needs Lock 2; Thread B holds Lock 2 and needs Lock 1. Neither can proceed. No external entity can break this cycle.

Core Concepts

The Four Coffman Conditions

Understanding deadlock requires understanding exactly why it happens. The four conditions are both necessary and sufficient:

• Mutual exclusion: If any number of threads could simultaneously hold a resource, there would be no contention. But mutexes, file handles, and other exclusive resources are inherently non-shareable. This condition cannot be removed without changing the nature of the resource.

• Hold and wait: If threads never held a resource while waiting for another, deadlock couldn’t happen because a thread would either have no resources (free to acquire) or have all resources it needs (never blocked waiting). Breaking this condition requires either acquiring all locks at once (atomically) or never holding a lock while waiting for another (acquire/release per lock).

• No preemption: If the OS could forcibly take a lock from a thread, circular wait would be broken—the cycle would be cut by preemption. But mutexes are designed to be released voluntarily. Some systems support lock priority inheritance to address this indirectly (not true preemption but prevents low-priority threads from blocking high-priority ones indefinitely).

• Circular wait: The final ingredient. Even with all three conditions above, if the wait graph is acyclic, some thread will eventually acquire what it needs. Circular wait is what happens when each thread in a set waits for a resource held by the next in a closed chain.

Prevention: Lock Ordering

The most effective and practical prevention strategy. Assign each lock a unique rank in a total ordering (e.g., by memory address, by ID). Every thread must acquire locks in increasing order and release them in decreasing order.

// Global ordering: LOCK_A < LOCK_B < LOCK_C
// All threads must acquire in this order

void operationAB(shared_state_t *s) {
    pthread_mutex_t *first = &s->lock_a;  // Lower address
    pthread_mutex_t *second = &s->lock_b; // Higher address

    pthread_mutex_lock(first);   // Always acquire lower-ranked first
    pthread_mutex_lock(second);  // Always acquire higher-ranked second

    // Critical section using both locks

    pthread_mutex_unlock(second); // Release higher-ranked first
    pthread_mutex_unlock(first);  // Release lower-ranked second
}

The key insight: if every thread acquires locks in the same order, a cycle in the wait graph is impossible. Thread A acquires L1 before L2; Thread B also acquires L1 before L2. Thread B cannot be waiting for L1 while holding L2 if Thread A is ahead of it in the acquisition order—Thread A already holds L1. The chain is broken.

Prevention: Trylock with Backoff

#define MAX_RETRIES 5

int acquire_multiple_with_retry(pthread_mutex_t *a, pthread_mutex_t *b) {
    for (int i = 0; i < MAX_RETRIES; ++i) {
        if (pthread_mutex_trylock(a) == 0) {
            if (pthread_mutex_trylock(b) == 0) {
                return 0;  // Both acquired
            }
            pthread_mutex_unlock(a);  // Release a, will retry
        }
        // Back off — sleep, yield, or do other work
        struct timespec t = {0, 1000000 << i};  // Exponential backoff
        nanosleep(&t, NULL);
    }
    return EBUSY;  // Failed after retries
}

This approach breaks hold-and-wait: instead of holding Lock A while waiting for Lock B, you either acquire both or release any acquired locks and try again. The cost is potential livelock (both threads retry forever) if the backoff is not sufficient, and wasted work on retries.

Detection: Wait-for Graph

The OS can model deadlock by constructing a wait-for graph—a directed graph where nodes are threads and an edge from T1 to T2 means “T1 is waiting for a lock held by T2.” A cycle in this graph indicates deadlock.

graph LR
    TA[Thread A] -->|waiting for L2| TB[Thread B]
    TB -->|waiting for L1| TA
    style TA stroke:#00fff9
    style TB stroke:#ff00ff

The kernel can run a cycle detection algorithm periodically (e.g., every 30 seconds). If a cycle is found, the system can log an alert, terminate one of the deadlocked threads (victim selection via age, priority, or resource usage), or release locks on behalf of a thread. Many production systems disable this because the detection cost is non-trivial and the recovery options are all destructive.

Starvation vs. Deadlock

Deadlock: A set of threads are all blocked forever, each waiting for a resource held by another in the set. All are frozen.

Starvation: A thread is permanently denied resources because other threads perpetually consume them or have higher priority. The thread is technically runnable (not blocked) but makes no progress.

Starvation can occur without deadlock: imagine a priority-scheduling system where a low-priority thread is perpetually preempted by medium-priority threads. The low-priority thread never gets CPU time—not because it’s blocked on a lock, but because it is never scheduled. In priority-based mutex implementations, priority inheritance can also starve intermediate priorities. Fair mutex implementations that use simple FIFO queuing can starve writers if readers continuously arrive.

Production Failure Scenarios + Mitigations

The /etc/passwd Chown Bug (Linux Security Flaw, 2003)

An ancient but instructive bug: under certain configurations, a process would open /etc/passwd for writing (acquiring a lock on the file), then fork. The child inherited the open file descriptor and the lock. If the parent tried to acquire an exclusive lock on the file and blocked, and the child was terminated by a signal, the kernel would release the lock—but the parent’s blocking lock acquisition had already consumed the file descriptor from the descriptor table, leading to a use-after-free when the parent eventually acquired the lock and wrote. The root cause involved lock ordering across process hierarchies and the difficulty of managing locks across fork/exec boundaries.

Mitigation: Never hold locks across fork(). Use pthread_atfork() to register handlers that release or re-acquire locks in child processes. Better: use file locks (flock(), fcntl()) that are automatically released on close(), not on thread termination.

The Database Double-Lock Bug

A database transaction held lock A, performed some I/O, then tried to upgrade to a more exclusive lock level on the same resource. The lock upgrade failed because the transaction already held a shared lock, and exclusive upgrade required releasing the shared lock first—but releasing and re-acquiring introduced a window where another transaction could acquire the exclusive lock first. The result was a deadlock-like scenario where two transactions each waited for the other to release.

Mitigation: When upgrading lock levels, acquire the highest level first, then downgrade if needed. Or use lock upgrade primitives that are atomic (not available in all systems—SQL Server’s UpdLock hint is an example of atomic upgrade).

Starvation in Python’s GIL-Protected Code

Python’s Global Interpreter Lock (GIL) causes threads to starve each other for CPU time when running CPU-bound Python code. The GIL only allows one thread to execute Python bytecode at a time. If a thread runs a tight CPU loop, other threads are starved of CPU—they are not blocked on a lock, but they never get scheduled. This is starvation, not deadlock.

Mitigation: Use multiprocessing for CPU-bound workloads, which bypasses the GIL entirely by using separate processes. Use asyncio for I/O-bound workloads, which avoids threading overhead.

Trade-off Table

Strategy	How it breaks Coffman	Pros	Cons
Lock Ordering	Circular wait	Simple, zero runtime cost	Requires global convention across codebase
Trylock + backoff	Hold and wait	Graceful degradation under contention	Livelock risk, wasted work on retries
One-shot acquisition	Hold and wait	Atomic, no partial state	Complex if multiple lock levels needed
Deadlock detection	(Post-hoc handling)	Can recover, no prevention overhead	Cycle detection is O(n^2), recovery is destructive
Priority inheritance	(Partial preemption)	Real-time safe	Doesn’t prevent deadlock, only mitigates priority inversion
Resource pre-allocation	Mutual exclusion	Eliminates contention entirely	Underutilizes resources, poor concurrency

Implementation Snippets

C: Global Lock Ordering with Ranked Mutexes

#include <pthread.h>
#include <stdatomic.h>

typedef struct {
    pthread_mutex_t lock_user;
    pthread_mutex_t lock_account;
    pthread_mutex_t lock_session;
} ranked_locks_t;

// Initialize with consistent ordering
void init_locks(ranked_locks_t *l) {
    // Acquire in address order (lowest address = first)
    pthread_mutex_t *locks[3] = {&l->lock_user, &l->lock_account, &l->lock_session};
    for (int i = 0; i < 3; ++i) {
        pthread_mutex_init(&locks[i], NULL);
    }
}

// Always acquire in order: user -> account -> session
int get_user_session(ranked_locks_t *l, int user_id, int *session_id) {
    pthread_mutex_lock(&l->lock_user);
    pthread_mutex_lock(&l->lock_account);
    pthread_mutex_lock(&l->lock_session);  // Safe: no cycle possible

    int result = lookup_user_session(user_id, session_id);

    pthread_mutex_unlock(&l->lock_session);  // Reverse order
    pthread_mutex_unlock(&l->lock_account);
    pthread_mutex_unlock(&l->lock_user);
    return result;
}

Python: Timeout-based Deadlock Detection

import threading
import time

class TimeoutLock:
    def __init__(self, timeout=5.0):
        self._lock = threading.Lock()
        self._timeout = timeout
        self._owner = None

    def acquire(self, blocking=True):
        if not blocking:
            return self._lock.acquire(False)
        deadline = time.monotonic() + self._timeout
        while True:
            acquired = self._lock.acquire(False)
            if acquired:
                self._owner = threading.current_thread().name
                return True
            if time.monotonic() >= deadline:
                raise TimeoutError(
                    f"Lock acquisition timeout after {self._timeout}s. "
                    f"Owner: {self._owner}"
                )
            time.sleep(0.01)  # Retry interval

    def release(self):
        self._owner = None
        self._lock.release()

C: Hierarchical Lock Ordering with Compile-Time Ordering Check

#define LOCK_ORDER_INIT(locks) \
    do { for (int _i = 0; _i < sizeof(locks)/sizeof(locks[0]) - 1; _i++) \
        if (&locks[_i] >= &locks[_i + 1]) \
            __builtin_trap(); /* Die if order violated */ \
    } while(0)

// Usage: enforce ordering at startup
pthread_mutex_t lock_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_b = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_c = PTHREAD_MUTEX_INITIALIZER;

void init() {
    pthread_mutex_t order[3] = {lock_a, lock_b, lock_c};
    LOCK_ORDER_INIT(order);  // Crashes if lock_a >= lock_b >= lock_c violated
}

Observability Checklist

• Thread state monitoring: Track threads in BLOCKED state waiting on mutexes. If blocked time exceeds threshold, alert
• Lock acquisition time histogram: Long tail (p99 >> p50) indicates contention or potential undetected deadlock
• Wait-for graph cycle detection: Periodic check in the kernel (if your OS exposes this) or manual instrumentation
• CPU utilization by thread: A thread consuming 0% CPU over a sustained period while the system has idle cycles indicates starvation
• Deadlock timeout alerts: Use pthread_mutex_timedlock() with a reasonable timeout (e.g., 10s), and alert if acquisition fails
• Thread count in blocked state: Sudden spikes in blocked thread count can indicate lock contention or early-stage deadlock

Security/Compliance Notes

Denial of service via deadlock: An attacker who can trigger a deadlock can cause a service to hang, denying availability to all users. In networked services, this can be exploited remotely by crafting requests that cause lock acquisition patterns that lead to deadlock. Mitigation: use lock timeouts to ensure bounded wait, use lock ordering to prevent deadlock structurally.

Priority inversion as security issue: In systems with security domains (e.g., SELinux enforcement threads, capability checks), priority inversion can cause a high-integrity thread to be blocked by a low-integrity thread holding a lock. Priority inheritance mitigates this but must be explicitly enabled and tested.

For compliance (SOC2, ISO 27001): document deadlock risk assessment for any multi-threaded service handling sensitive operations. Implement lock ordering discipline and verify with static analysis. Deadlock that causes service unavailability is an availability failure under most compliance frameworks.

Common Pitfalls / Anti-patterns

1. Different lock ordering across functions. If funcA() acquires Lock1 then Lock2, and funcB() acquires Lock2 then Lock1, you have a deadlock hazard if both can be called concurrently. Use a documented global ordering and a linter rule to enforce it.

2. Lock acquisition in library code without ordering guarantee. A library function that acquires locks must document its lock ordering requirements. If a caller violates the ordering, deadlock occurs even though the library code is correct. Libraries should use lock ranking within their own code and never acquire caller-owned locks.

3. Forking while holding a lock. A thread holding a lock that then forks creates a child process with a lock held by a thread that no longer exists. The lock becomes unreleasable. Use pthread_atfork() handlers or avoid holding locks across fork().

4. Acquiring a lock, then calling a blocking operation. If you hold a lock, call read() on a file descriptor that might block, and the read never returns (network failure, disk hang), you hold the lock forever. Release the lock before any potentially blocking operation.

5. Starvation from reader-writer lock favoring readers. A read-preferring RW lock can starve writers indefinitely if reads keep arriving. Use write-preferring or fair RW lock variants if writers must make progress.

Quick Recap Checklist

• Deadlock requires all four Coffman conditions simultaneously: mutual exclusion, hold-and-wait, no preemption, circular wait
• Prevention by lock ordering (global consistent order) is the most practical and zero-cost strategy
• Trylock with backoff breaks hold-and-wait but risks livelock
• Deadlock detection constructs a wait-for graph and looks for cycles; recovery is typically to kill a thread
• Starvation is a thread permanently denied CPU or resources without being blocked on a lock
• Use pthread_mutex_timedlock() to detect potential deadlock in production
• Never hold locks across fork() — use pthread_atfork() handlers
• Starvation in reader-writer locks requires choosing a fairness policy (read-preferring vs. write-preferring vs. fair)

Interview Questions

## Further Reading

• Process Scheduling — How the OS decides which process runs next
• Mutex Implementation — How synchronization primitives work
• Semaphores — Alternative synchronization primitives

Conclusion

• Process Scheduling — How the OS decides which process runs next
• Mutex Implementation — How synchronization primitives work
• Semaphores — Alternative synchronization primitives