Introduction

Synchronization protects shared state, but incorrect synchronization can prevent a concurrent application from making progress.

A deadlock occurs when a group of threads, processes or transactions waits indefinitely because each participant requires a resource or action that another blocked participant must provide.

Deadlocks can involve:

• Mutexes and read-write locks
• Semaphores and resource permits
• Database row or table locks
• File locks
• Connection pools
• Thread-pool tasks
• Message exchanges
• Distributed services
• Administrative or deployment operations

In your System Design curriculum, Deadlocks is Topic 2.5 under Computer Systems, Linux and Concurrency. It follows synchronization and race conditions, and prepares learners to reason about files, sockets and Linux diagnostic tools.

Prerequisites

What Is a Deadlock?

A deadlock is a state in which a set of participants cannot continue because each participant is waiting for a resource or event that another participant in the same blocked set must release or produce.

Two-thread Example

Thread A                    Thread B
--------                    --------

Acquire Lock A              Acquire Lock B

Wait for Lock B             Wait for Lock A
     |                           |
     +-------------+-------------+
                   |
                   v
                Deadlock

Neither thread can acquire its second lock. Neither thread reaches the code that releases its first lock.

Deadlock vs Other Concurrency Problems

Four Necessary Deadlock Conditions

Four conditions must hold simultaneously for a classic resource deadlock to occur:

1. Mutual exclusion
2. Hold and wait
3. No preemption
4. Circular wait

Mutual Exclusion

Mutual exclusion exists when a resource can be held by only one participant at a time.

Lock A
  |
  +--> Owned by Thread A

Thread B requests Lock A
  |
  +--> Thread B must wait

Many resources require exclusive access while being modified. Therefore, eliminating mutual exclusion is not always possible.

Mutual exclusion can sometimes be reduced through:

• Immutable data
• Read-only sharing
• Per-thread state
• Partitioned resources
• Message passing
• Concurrent read access through an appropriate read-write design

Hold and Wait

Hold and wait occurs when a participant retains one resource while waiting to acquire another.

Thread A:

Hold Lock A
     |
     v
Wait for Lock B

Possible prevention strategies include:

• Acquire all required resources together when practical.
• Release currently held resources before requesting additional ones.
• Redesign the operation to require fewer simultaneous resources.
• Copy required state and release the first lock before performing other work.

Acquiring every possible resource in advance can reduce concurrency and may be impractical when required resources are discovered dynamically.

No Preemption

No preemption means a resource is not forcibly removed from its owner. The owner must release it according to the resource protocol.

Thread A owns Lock A.

Thread B cannot forcibly take Lock A.

Thread B waits until Thread A releases it.

Mutex ownership normally follows this model. Some other resources can support cancellation, rollback, lease expiry or transaction termination, which can provide a form of recovery.

Circular Wait

Circular wait occurs when each participant waits for a resource held by the next participant in a cycle.

Thread A waits for Lock B
    ^                 |
    |                 v
Lock A held by A   Lock B held by B
    |                 ^
    v                 |
Thread B waits for Lock A

A consistent global resource-acquisition order is one of the most practical ways to prevent circular wait.

Classic POSIX Mutex Deadlock

The following program intentionally demonstrates an unsafe lock-ordering design. It must not be used as a correct concurrency pattern.

#define _POSIX_C_SOURCE 200809L

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

static pthread_mutex_t first_mutex =
    PTHREAD_MUTEX_INITIALIZER;

static pthread_mutex_t second_mutex =
    PTHREAD_MUTEX_INITIALIZER;

static void short_delay(
    void)
{
    struct timespec duration = {
        .tv_sec = 0,
        .tv_nsec = 100000000L
    };

    nanosleep(
        &duration,
        NULL
    );
}

static void *first_worker(
    void *argument)
{
    (void)argument;

    pthread_mutex_lock(
        &first_mutex
    );

    puts(
        "First worker acquired first mutex."
    );

    short_delay();

    puts(
        "First worker is waiting "
        "for second mutex."
    );

    pthread_mutex_lock(
        &second_mutex
    );

    pthread_mutex_unlock(
        &second_mutex
    );

    pthread_mutex_unlock(
        &first_mutex
    );

    return NULL;
}

static void *second_worker(
    void *argument)
{
    (void)argument;

    pthread_mutex_lock(
        &second_mutex
    );

    puts(
        "Second worker acquired second mutex."
    );

    short_delay();

    puts(
        "Second worker is waiting "
        "for first mutex."
    );

    pthread_mutex_lock(
        &first_mutex
    );

    pthread_mutex_unlock(
        &first_mutex
    );

    pthread_mutex_unlock(
        &second_mutex
    );

    return NULL;
}

int main(void)
{
    pthread_t first_thread;
    pthread_t second_thread;

    if (pthread_create(
            &first_thread,
            NULL,
            first_worker,
            NULL) != 0) {

        return EXIT_FAILURE;
    }

    if (pthread_create(
            &second_thread,
            NULL,
            second_worker,
            NULL) != 0) {

        pthread_join(
            first_thread,
            NULL
        );

        return EXIT_FAILURE;
    }

    pthread_join(
        first_thread,
        NULL
    );

    pthread_join(
        second_thread,
        NULL
    );

    return EXIT_SUCCESS;
}

Compile

cc -std=c17 -Wall -Wextra -Wpedantic -pthread deadlock_example.c -o deadlock_example

Why Deadlock Can Occur

1. The first worker acquires the first mutex.
2. The second worker acquires the second mutex.
3. The first worker waits for the second mutex.
4. The second worker waits for the first mutex.
5. Neither worker can reach its unlock operations.
6. The main thread waits indefinitely while joining the workers.

Prevent Deadlock with Lock Ordering

Define one global order for lock acquisition and require every code path to follow it.

Approved order:

1. Account mutex
2. Ledger mutex
3. Audit mutex

Every operation acquires locks only
from lower order to higher order.

Corrected Pattern

static int lock_both(
    pthread_mutex_t *first,
    pthread_mutex_t *second)
{
    if (pthread_mutex_lock(
            first) != 0) {

        return 0;
    }

    if (pthread_mutex_lock(
            second) != 0) {

        pthread_mutex_unlock(
            first
        );

        return 0;
    }

    return 1;
}

static void unlock_both(
    pthread_mutex_t *first,
    pthread_mutex_t *second)
{
    pthread_mutex_unlock(
        second
    );

    pthread_mutex_unlock(
        first
    );
}

Every caller must pass the locks in the approved order. A stronger design can encode resource ranking so callers do not choose the order manually.

Consistent Worker Pattern

static void *worker(
    void *argument)
{
    (void)argument;

    if (!lock_both(
            &first_mutex,
            &second_mutex)) {

        return NULL;
    }

    /*
     * Protected operation using
     * both related resources.
     */

    unlock_both(
        &first_mutex,
        &second_mutex
    );

    return NULL;
}

Circular wait cannot form between these two mutexes when every participating path follows the same order.

Resource Hierarchy

A resource hierarchy assigns every lock or resource class a rank.

Valid acquisition:

Customer -> Order -> Payment -> Audit

Invalid acquisition:

Payment -> Customer

Lock-order documentation should be maintained near synchronization interfaces and validated through code review or diagnostic assertions where practical.

Dynamic Resource Ordering

Sometimes a program must lock several resources of the same type, such as two bank accounts. Use a stable key to determine the order.

static int lock_accounts(
    struct Account *first,
    struct Account *second)
{
    if (first == NULL ||
        second == NULL ||
        first == second) {

        return 0;
    }

    struct Account *lower =
        first->id < second->id
            ? first
            : second;

    struct Account *higher =
        first->id < second->id
            ? second
            : first;

    if (pthread_mutex_lock(
            &lower->mutex) != 0) {

        return 0;
    }

    if (pthread_mutex_lock(
            &higher->mutex) != 0) {

        pthread_mutex_unlock(
            &lower->mutex
        );

        return 0;
    }

    return 1;
}

The corresponding unlock operation should follow the documented reverse order. The design must handle the case where both arguments refer to the same account according to the operation contract.

Bank Transfer Example

A transfer between two accounts frequently requires coordinated updates to both account records.

pthread_mutex_lock(
    &source->mutex
);

pthread_mutex_lock(
    &destination->mutex
);

A simultaneous transfer in the opposite direction can reverse the acquisition order.

Transfer 1:
Lock Account A
Wait for Account B

Transfer 2:
Lock Account B
Wait for Account A

struct Account *lower =
    source->id < destination->id
        ? source
        : destination;

struct Account *higher =
    source->id < destination->id
        ? destination
        : source;

pthread_mutex_lock(
    &lower->mutex
);

pthread_mutex_lock(
    &higher->mutex
);

/*
 * Validate and apply the complete
 * transfer while both accounts
 * are protected.
 */

pthread_mutex_unlock(
    &higher->mutex
);

pthread_mutex_unlock(
    &lower->mutex
);

Reduce Simultaneous Lock Ownership

Deadlock risk can be reduced when operations do not hold several resources simultaneously.

lock(
    &cache_mutex
);

lock(
    &database_mutex
);

update_cache_and_database();

unlock(
    &database_mutex
);

unlock(
    &cache_mutex
);

struct Record snapshot;

lock(
    &database_mutex
);

snapshot =
    update_database();

unlock(
    &database_mutex
);

lock(
    &cache_mutex
);

update_cache(
    &snapshot
);

unlock(
    &cache_mutex
);

Separating the operations is valid only when temporary divergence and failure between phases are handled according to the consistency contract.

Timed Lock Acquisition

A timed lock attempt prevents one participant from waiting indefinitely. It can detect a possible progress problem, but it does not automatically make the overall operation correct.

Attempt to acquire Lock B
        |
        +--> Acquired: continue
        |
        +--> Deadline reached:
                 release held resources
                 return controlled failure
                 retry only according to policy

POSIX Timed-lock Pattern

#define _POSIX_C_SOURCE 200809L

#include <errno.h>
#include <pthread.h>
#include <time.h>

static int add_milliseconds(
    struct timespec *deadline,
    long milliseconds)
{
    if (deadline == NULL ||
        milliseconds < 0) {

        return 0;
    }

    deadline->tv_sec +=
        milliseconds / 1000;

    deadline->tv_nsec +=
        (milliseconds % 1000)
        * 1000000L;

    if (deadline->tv_nsec >=
        1000000000L) {

        ++deadline->tv_sec;
        deadline->tv_nsec -=
            1000000000L;
    }

    return 1;
}

static int lock_with_timeout(
    pthread_mutex_t *mutex,
    long timeout_milliseconds)
{
    if (mutex == NULL) {
        return 0;
    }

    struct timespec deadline;

    if (clock_gettime(
            CLOCK_REALTIME,
            &deadline) != 0 ||
        !add_milliseconds(
            &deadline,
            timeout_milliseconds)) {

        return 0;
    }

    int status =
        pthread_mutex_timedlock(
            mutex,
            &deadline
        );

    if (status == 0) {
        return 1;
    }

    if (status == ETIMEDOUT) {
        return 0;
    }

    return 0;
}

Availability of timed mutex operations and clock behaviour depend on the target POSIX implementation. A timeout can also occur because of ordinary contention, not only deadlock.

Try-lock and Retry

A try-lock operation attempts acquisition without indefinite blocking.

Acquire Lock A
      |
      v
Try Lock B
      |
      +--> Success:
      |      complete operation
      |
      +--> Busy:
             release Lock A
             wait according to policy
             retry

This can break hold-and-wait, but careless retry loops can create livelock or high CPU consumption.

for (;;) {
    if (try_operation()) {
        break;
    }
}

Maximum attempts:
Defined by policy

Delay:
Backoff with controlled randomness

Deadline:
Stop after the operation deadline

Failure:
Return a controlled retryable result

Observability:
Record contention and retry exhaustion

Livelock

Livelock occurs when participants remain active and repeatedly change their behaviour in response to one another, but useful work does not complete.

Thread A detects conflict and releases.
Thread B detects conflict and releases.

Thread A retries immediately.
Thread B retries immediately.

Both conflict again.

The cycle repeats.

Possible controls include:

• Randomized backoff
• Priority rules
• Bounded retries
• Single ownership
• Queue-based serialization

Starvation

Starvation occurs when one participant repeatedly fails to obtain the resources needed to progress, even though the system as a whole continues processing other work.

Thread A repeatedly acquires the lock.
Thread B waits.
Thread C repeatedly acquires the lock.
Thread B continues waiting.

Starvation can result from:

• Unfair resource admission
• Reader-preferred locking
• High-priority work arriving continuously
• Unbounded retries by competing tasks
• Resource limits that never favor an older waiter

Wait-for Graph

A wait-for graph represents participants and waiting dependencies.

Thread A ---> Thread B
   ^              |
   |              v
Thread D <--- Thread C

An arrow from Thread A to Thread B means Thread A waits for a resource held by Thread B.

A cycle in a single-instance resource wait-for graph indicates a deadlock. More complex resource models can require additional analysis.

Deadlock Detection

Detection allows deadlocks to occur and then identifies blocked dependency cycles.

A detection system can use:

• Wait-for graph analysis
• Database deadlock detection
• Thread dumps
• Lock-owner diagnostics
• Watchdogs
• Timeout monitoring
• Stalled-progress metrics

A timeout can identify unusually long waiting, but long waiting alone does not prove a deadlock.

Deadlock Recovery

Recovery breaks a detected cycle by forcing one or more participants to release resources or terminate.

Recovery options include:

• Abort one transaction
• Roll back one operation
• Terminate and restart one worker
• Cancel selected requests
• Revoke a lease when its protocol permits expiry
• Restart the affected process as a last-resort operational action

A recovery policy should define:

• How the victim is selected
• Which work can be safely rolled back
• Whether retries are safe
• How partial external effects are reconciled
• How repeated deadlocks are detected and escalated

Prevention vs Avoidance vs Detection

Database Deadlocks

Database transactions can deadlock when they acquire row, page, table or other database locks in conflicting orders.

Transaction A:
Lock Row 1
Wait for Row 2

Transaction B:
Lock Row 2
Wait for Row 1

A database engine can detect the cycle and abort one transaction so the other can continue.

Application responsibilities include:

• Keeping transactions focused
• Accessing records in a consistent order
• Avoiding unnecessary user or network waiting inside transactions
• Handling deadlock-victim errors
• Retrying only when the operation is safe
• Applying a bounded retry policy
• Recording repeated deadlock patterns

Consistent Record Order

Unsafe:

Transaction A updates Customer 10, then Customer 20.
Transaction B updates Customer 20, then Customer 10.


Safer ordering:

Every transaction updates lower customer ID first,
then higher customer ID.

Thread-pool Deadlock

Deadlocks can occur without explicit mutex cycles. A task can wait for another task that cannot run because all worker threads are occupied.

Thread pool capacity: 2

Worker 1:
Runs Task A.
Task A submits Task C.
Task A waits for Task C.

Worker 2:
Runs Task B.
Task B submits Task D.
Task B waits for Task D.

Task C and Task D:
Queued, but no worker is available.

Possible design corrections include:

• Do not wait synchronously for work submitted to the same saturated pool.
• Use asynchronous composition.
• Separate dependent workloads into appropriate executors.
• Execute small child tasks directly when the design permits.
• Use bounded waiting and overload controls.

Connection-pool Deadlock

A resource pool can participate in deadlock when operations retain one resource while waiting for another resource from a fully utilized pool.

Pool contains two connections.

Thread A holds Connection 1.
Thread A waits for another connection.

Thread B holds Connection 2.
Thread B waits for another connection.

No connection can become free.

The operation should avoid requesting more pooled resources than its contract allows while retaining existing resources.

Distributed Deadlocks

A distributed deadlock can form across service or machine boundaries.

Service A holds Resource A
and synchronously calls Service B.

Service B holds Resource B
and synchronously calls Service A.

Both calls wait for the other service.

Distributed deadlocks are harder to diagnose because:

• Wait relationships cross process and machine boundaries.
• There may be no single global lock manager.
• Network failure and delay can resemble blocking.
• Timeouts can trigger retries and duplicate work.
• Partial external effects may not be automatically reversible.

Useful controls include:

• Request deadlines
• Acyclic service-call design
• Asynchronous workflows
• Single ownership of state
• Transactional coordination where required
• Tracing of cross-service dependencies

Nested Callback Deadlock

A component can deadlock when it calls external or reentrant code while holding a lock.

Component A acquires Lock A.
Component A invokes callback in Component B.

Component B invokes Component A again.
Component A tries to acquire Lock A.

The same logical operation blocks itself.

Avoid invoking unknown callbacks, extension code, event handlers or remote services while holding internal locks unless the contract explicitly supports reentrancy.

Symptoms of Deadlock

Common symptoms include:

• Requests never complete
• Worker utilization appears low while queues increase
• Several threads remain blocked on locks
• Application shutdown never finishes
• Thread joins wait indefinitely
• No progress occurs despite an active process
• Database transactions are selected as deadlock victims
• Watchdogs report stalled work
• Connection or thread pools remain exhausted

These symptoms can also result from remote hangs, slow I/O or starvation. Diagnosis must inspect the actual waiting dependencies.

Linux Deadlock Investigation

Inspect Threads

ps -T -p PROCESS_ID

Observe Thread States

top -H -p PROCESS_ID

Inspect Process Status

cat /proc/PROCESS_ID/status

Attach a Debugger

gdb -p PROCESS_ID

Inside an applicable GDB session:

info threads
thread apply all backtrace

Thread backtraces can show several threads blocked inside lock-acquisition calls and help identify the resource cycle.

Trace System Calls

strace -f -p PROCESS_ID

Tool availability, output and permissions vary by Linux environment. Attaching diagnostic tools can affect timing and performance, so follow the approved operational process.

Deadlock Investigation Process

1. Identify the user-visible operation that stopped progressing.
2. Capture thread dumps before restarting the process.
3. Identify threads blocked on synchronization or resource acquisition.
4. Determine which participant owns each requested resource.
5. Construct a wait-for graph.
6. Check for a dependency cycle.
7. Identify which necessary conditions were allowed.
8. Choose a prevention, avoidance, detection or recovery strategy.
9. Add a regression test that recreates the hazardous ordering.
10. Measure contention after applying the correction.

Deadlock Testing

Deadlock testing should deliberately create overlapping resource acquisition rather than waiting for a rare production ordering.

Deadlock Review Checklist

Common Deadlock Mistakes

Deadlock Prevention Best Practices

Practice Exercise

Analyze and correct a deadlock in a two-account transfer operation.

Defective Logic

static int transfer(
    struct Account *source,
    struct Account *destination,
    long long amount)
{
    pthread_mutex_lock(
        &source->mutex
    );

    pthread_mutex_lock(
        &destination->mutex
    );

    if (amount > 0 &&
        source->balance >=
            amount) {

        source->balance -=
            amount;

        destination->balance +=
            amount;
    }

    pthread_mutex_unlock(
        &destination->mutex
    );

    pthread_mutex_unlock(
        &source->mutex
    );

    return 1;
}

Tasks

1. Identify the two exclusive resources.
2. Write a circular-wait scenario involving opposite transfers.
3. Define a stable account-lock ordering rule.
4. Handle transfers where source and destination are the same account.
5. Validate the amount before changing balances.
6. Check arithmetic overflow before increasing the destination balance.
7. Release partially acquired resources when acquisition fails.
8. Write a concurrent transfer stress test.
9. Verify that total money remains unchanged.
10. Verify that every test completes within the defined deadline.

Model Lock-order Correction

static int transfer(
    struct Account *source,
    struct Account *destination,
    long long amount)
{
    if (source == NULL ||
        destination == NULL ||
        source == destination ||
        amount <= 0) {

        return 0;
    }

    struct Account *lower =
        source->id <
            destination->id
            ? source
            : destination;

    struct Account *higher =
        source->id <
            destination->id
            ? destination
            : source;

    if (pthread_mutex_lock(
            &lower->mutex) != 0) {

        return 0;
    }

    if (pthread_mutex_lock(
            &higher->mutex) != 0) {

        pthread_mutex_unlock(
            &lower->mutex
        );

        return 0;
    }

    int succeeded = 0;

    if (source->balance >=
        amount) {

        source->balance -=
            amount;

        destination->balance +=
            amount;

        succeeded = 1;
    }

    pthread_mutex_unlock(
        &higher->mutex
    );

    pthread_mutex_unlock(
        &lower->mutex
    );

    return succeeded;
}

A complete financial implementation must additionally check destination overflow, define monetary representation and preserve transactional and audit requirements. This example focuses on lock ordering.

Transfer Invariant

For a successful transfer:

source balance decreases by amount
destination balance increases by amount

Combined balance remains unchanged

No account balance becomes invalid

Both account updates are observed as one
protected logical operation

Frequently Asked Questions