Deadlock

A deadlock is a set of threads each waiting for a resource held by another thread in the set — none can ever proceed.

Concept

Definition and the Four Conditions A deadlock is a set of threads each waiting for a resource held by another thread in the set — none can ever proceed. Coffman's four necessary conditions (all must hold):

Mutual exclusion — resources can't be shared.

Hold and wait — a thread holds one resource while waiting for another.

No preemption — resources can't be taken away.

Circular wait — a cycle of threads each waiting for the next.

A resource-allocation graph with single-instance resources is deadlocked exactly when it contains a cycle.

Break a condition: acquire all locks at once (no hold-and-wait), allow preemption, and most practically impose a global lock order (no circular wait)

Grant a request only if the system stays in a safe state — the Banker's algorithm (needs maximum demands in advance) Detection and recovery

Periodically look for cycles (wait-for graph); recover by killing or rolling back a victim (databases abort a transaction) Ignore ("ostrich")

Many OSes ignore application deadlocks; developers must prevent them

Livelock: threads keep changing state in response to each other without progress (two people stepping aside in a corridor). Starvation: a thread never gets a resource although the system progresses.

Banker's Algorithm With *Available*, *Max*, *Allocation* and *Need = Max − Allocation*: the state is safe if there is an order in which every process can obtain its remaining need from what is available plus what earlier processes release. A request is granted only if the resulting state is still safe.

flowchart LR
    T1["Thread 1"] -->|"holds"| A["can_bus lock"]
    T2["Thread 2"] -->|"holds"| B["log_file lock"]
    T1 -.->|"waits for"| B
    T2 -.->|"waits for"| A

Why It Matters

Deadlocks freeze servers, GUIs and embedded systems — often only under rare timing. Databases detect them and abort transactions (the MySQL course shows InnoDB's deadlock error). Lock ordering is the everyday cure.

Syntax

/* global order: always lock A before B */
pthread_mutex_lock(&A); pthread_mutex_lock(&B);
pthread_mutex_timedlock(&m, &deadline);   /* detect "waited too long" */
pthread_mutex_trylock(&m);                /* back off instead of waiting */

Example

16.1 A real deadlock (detected with a timeout) and the lock-ordering fix 16.2 Banker's algorithm

#define _GNU_SOURCE
#include <stdio.h>
#include <pthread.h>
#include <time.h>
#include <unistd.h>
#include <errno.h>

pthread_mutex_t can_bus = PTHREAD_MUTEX_INITIALIZER, log_file = PTHREAD_MUTEX_INITIALIZER;
pthread_barrier_t both_hold_one;
int ordered;                                    /* 0 = inconsistent lock order, 1 = global order */

static int lock_with_timeout(pthread_mutex_t *m)
{
    struct timespec t;
    clock_gettime(CLOCK_REALTIME, &t);
    t.tv_sec += 1;
    return pthread_mutex_timedlock(m, &t);      /* a real deadlock would wait forever; we give up after 1 s */
}

static void *task(void *arg)
{
    int id = *(int *)arg;
    pthread_mutex_t *first = &can_bus, *second = &log_file;
    if (!ordered && id == 2) { first = &log_file; second = &can_bus; }   /* thread 2 locks in reverse order */
    pthread_mutex_lock(first);
    if (!ordered) pthread_barrier_wait(&both_hold_one);                   /* make the bad interleaving certain */
    int rc = lock_with_timeout(second);
    if (rc == ETIMEDOUT) printf("  thread %d: waited 1 s for its second lock -> DEADLOCK (circular wait)\n", id);
    else { printf("  thread %d: got both locks\n", id); pthread_mutex_unlock(second)
…

"""Banker's algorithm: is the system in a safe state, and can a request be granted safely?"""

available = [3, 3, 2]                       # free instances of resources A, B, C
maximum = {"P0": [7, 5, 3], "P1": [3, 2, 2], "P2": [9, 0, 2], "P3": [2, 2, 2], "P4": [4, 3, 3]}
alloc = {"P0": [0, 1, 0], "P1": [2, 0, 0], "P2": [3, 0, 2], "P3": [2, 1, 1], "P4": [0, 0, 2]}


def need(p, al):
    return [m - a for m, a in zip(maximum[p], al[p])]


def safe_sequence(avail, al):
    work, finished, order = avail[:], set(), []
    while len(finished) < len(al):
        for p in al:
            if p not in finished and all(n <= w for n, w in zip(need(p, al), work)):
                work = [w + a for w, a in zip(work, al[p])]      # p runs to completion, releases everything
                finished.add(p); order.append(p)
                break
        else:
            return None
    return order


def request(p, req):
    if any(r > n for r, n in zip(req, need(p, alloc))):
        return "error: exceeds declared maximum"
    if any(r > a for r, a in zip(req, available)):
        return "must wait: not enough free resources"
    trial_alloc = {k: v[:] for k, v in alloc.items()}
    trial_alloc[p
…

Expected Result

With inconsistent lock order each thread held one lock and waited for the other: a circular wait. The 1-second timeout is only there to make the deadlock visible — without it, both threads would wait forever. After thread 2 gave up and released its lock, thread 1 could finish. With one global order, both threads always complete.

The initial state is safe (P1, P3, P0, P2, P4 can finish in that order). P1's request keeps the system safe and is granted; P4's request would leave too few resources for anyone to finish and is denied; P0's request is safe.

inconsistent lock order:
  thread 2: waited 1 s for its second lock -> DEADLOCK (circular wait)
  thread 1: got both locks
same global lock order (can_bus before log_file):
  thread 1: got both locks
  thread 2: got both locks

need matrix: {'P0': [7, 4, 3], 'P1': [1, 2, 2], 'P2': [6, 0, 0], 'P3': [0, 1, 1], 'P4': [4, 3, 1]}
current state safe sequence: ['P1', 'P3', 'P0', 'P2', 'P4']
P1 requests [1, 0, 2]: granted, safe sequence ['P1', 'P3', 'P0', 'P2', 'P4']
P4 requests [3, 3, 0]: denied: would lead to an unsafe state
P0 requests [0, 2, 0]: granted, safe sequence ['P3', 'P1', 'P0', 'P2', 'P4']

Common Mistakes

Acquiring locks in different orders in different code paths.

Calling unknown code (callbacks, virtual methods) while holding a lock.

"Fixing" a deadlock with sleep or retries that turn it into a livelock.

Confusing an unsafe state (deadlock *possible*) with a deadlock.

Best Practices

Define and document a global lock order; enforce it with lock hierarchies or tools (lockdep in the Linux kernel).

Hold as few locks as possible, for as short as possible.

Use trylock/timeouts to detect problems in watchdogs, not as normal control flow.

Prefer designs without shared locks (message passing, single-owner data).

Interview Relevance

Very high: "what are the four conditions for deadlock?", "how do you prevent deadlock?", "explain the Banker's algorithm", "deadlock vs livelock vs starvation?", "dining philosophers solutions?".

Practice Questions

Implement the dining philosophers with 5 threads and fix the deadlock by ordering the forks.

Run the Banker's algorithm by hand for P1's request and check the program's answer.

Write a wait-for-graph cycle detector for 5 threads.

Which deadlock condition does pthread_mutex_trylock with back-off break?

Quick Quiz

Q1. (Multiple choice) Imposing a global order on lock acquisition breaks which condition? A) Mutual exclusion B) Hold and wait C) No preemption D) Circular wait Answer: D.

Q2. (Predict the output) Is the example's initial state safe? Give a safe sequence.

Answer: Yes: P1, P3, P0, P2, P4 (verified).

Q3. (True/False) An unsafe state always leads to deadlock.

Answer: False. It means deadlock *may* occur; safe states guarantee it can't.

Q4. (Find the bug) transfer(a, b) locks a->lock then b->lock; two threads call transfer(x, y) and transfer(y, x) at the same time.

Answer: Opposite lock order → deadlock. Lock the two accounts in a fixed order (e.g. by account ID or address).

Coding Challenge

Write transfer(Account *from, Account *to, int amount) that is deadlock-free by always locking the account with the lower ID first; run two threads doing opposite transfers 100 000 times and print the final balances.

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

typedef struct { int id; long balance; pthread_mutex_t lock; } Account;
static Account x = {1, 1000, PTHREAD_MUTEX_INITIALIZER}, y = {2, 1000, PTHREAD_MUTEX_INITIALIZER};

static void transfer(Account *from, Account *to, int amount)
{
    Account *first = from->id < to->id ? from : to;          /* global order by id */
    Account *second = from->id < to->id ? to : from;
    pthread_mutex_lock(&first->lock);
    pthread_mutex_lock(&second->lock);
    from->balance -= amount;
    to->balance += amount;
    pthread_mutex_unlock(&second->lock);
    pthread_mutex_unlock(&first->lock);
}

static void *x_to_y(void *a) { for (int i = 0; i < 100000; i++) transfer(&x, &y, 1); return a; }
static void *y_to_x(void *a) { for (int i = 0; i < 100000; i++) transfer(&y, &x, 1); return a; }

int main(void)
{
    pthread_t a, b;
    pthread_create(&a, NULL, x_to_y, NULL);
    pthread_create(&b, NULL, y_to_x, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("x = %ld, y = %ld, total = %ld (no deadlock, money conserved)\n", x.balance, y.balance, x.balance + y.balance);
    return 0;
}