12.2 Deadlock Incident Diagnosis

The central control console suddenly goes silent, no errors, no new output. Two maintenance threads each hold a lock and are now waiting for the other to release it. The most tempting action at this point is to restart the system; however, doing so would erase the most valuable piece of information: who is waiting for whom.

12.1 Why Deadlocks Occur introduced the wait graph and Coffman conditions. This lesson brings that abstract wait diagram to life in a real-world scenario: which threads are waiting, where they entered the waiting state, and which threads currently hold the relevant resources. We first construct a reproducible two-lock deadlock scenario, then examine what diagnostic evidence each language (C, Java, and Python) can provide. The experiment must run in an isolated environment and terminate with a timeout.

1. Construct a Deterministic Waiting Loop

Relying solely on sleep to adjust scheduling timing is unreliable. Below, we use a barrier to ensure that both threads acquire the first lock before attempting to obtain the second:

#define _XOPEN_SOURCE 700

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

static pthread_mutex_t first = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t second = PTHREAD_MUTEX_INITIALIZER;
static pthread_barrier_t gate;

static void *lock_first_then_second(void *unused) {
    (void)unused;
    pthread_mutex_lock(&first);
    puts("A holds first");
    pthread_barrier_wait(&gate);
    pthread_mutex_lock(&second);
    return NULL;
}

static void *lock_second_then_first(void *unused) {
    (void)unused;
    pthread_mutex_lock(&second);
    puts("B holds second");
    pthread_barrier_wait(&gate);
    pthread_mutex_lock(&first);
    return NULL;
}

int main(void) {
    pthread_t a;
    pthread_t b;
    setvbuf(stdout, NULL, _IONBF, 0);

    if (pthread_barrier_init(&gate, NULL, 2) != 0) {
        return EXIT_FAILURE;
    }
    if (pthread_create(&a, NULL, lock_first_then_second, NULL) != 0
            || pthread_create(&b, NULL, lock_second_then_first, NULL) != 0) {
        return EXIT_FAILURE;
    }

    pthread_join(a, NULL);
    pthread_join(b, NULL);
    return EXIT_SUCCESS;
}

Compile this in an environment that supports POSIX barriers and provide it with an external deadline:

cc -std=c17 -g -O0 -Wall -Wextra -pthread deadlock.c
timeout 2 ./a.out
# A holds first
# B holds second
# timeout Terminate process with exit code 124

The barrier only enforces a fixed sequence of events. After passing the barrier, thread A holds first waiting for second, and thread B holds second waiting for first. As a result, neither pthread_join can complete.

The fix isn't simply "sleep a bit longer"; it's to ensure both functions acquire the lock according to first → second. If this is a minimal reproduction case, we must return to the actual code and verify whether the same set of locks has additional third or fourth acquisition paths.

2. C/C++: Freeze the Scene First, Then Capture the Full Thread Stack

Two threads have been halted. At this point, what's needed isn't just a CPU usage reading of zero, instead, we need the full stack trace for each thread. Stack frames can reveal exactly where a thread is stuck in a lock acquisition call. Combined with the lock address and the state of other threads, this allows us to reconstruct the waiting dependency.

With debugging symbols preserved, you can attach GDB to a running process:

gdb -p PID

Once inside GDB, first capture all threads:

(gdb) set pagination off
(gdb) info threads
(gdb) thread apply all bt

A common pattern is that multiple threads are stalled inside the low-level mutex wait function, with higher-level call stacks showing their respective business logic calls to pthread_mutex_lock. The main thread might simply be waiting at pthread_join, a task queue, or a request queue, typically, it's not the root of the deadlock.

Do not rely on private fields of pthread_mutex_t to write diagnostic logic. These are internal implementation details of the runtime, and their structure and meaning can vary across libc versions, architectures, and mutex types. More reliable evidence comes from:

• The full call stack of each thread;
• The lock acquisition path visible in source code;
• Application-level logging of lock names, holders, and the time when waiting began;
• Concurrent logs of scheduling, requests, and resource access.

If long-term process suspension isn't feasible, generate core dumps or thread dumps during approved operations, then analyze them offline. Attaching a debugger itself can suspend threads and potentially alter time-sensitive behaviors. Therefore, always assess the impact on the service before proceeding.

Reconstructing the Waiting Graph from the Stack

For each blocked thread, record a row:

Thread	Currently Holding	Currently Waiting	Acquisition Location
A	first	second	lock_first_then_second
B	second	first	lock_second_then_first

Then point the "lock being waited on" to the thread that currently holds it. Simply observing two threads is often insufficient: a holder might be waiting on a condition variable, I/O, another process, or a remote response. The waiting chain must be expanded further until a forwardable endpoint is found, or a cycle is detected.

3. Java: Thread Dumps Provide More Lock Information

A HotSpot process can typically obtain a thread dump using JDK tools, such as:

jcmd PID Thread.print -l
# or
jstack -l PID

The dump lists Java thread states, call stacks, and information about monitors or java.util.concurrent synchronizers. If a monitor cycle is detected at the Java level, the tool may directly identify the threads involved in a deadlock.

Programs can also use management interfaces internally:

ThreadMXBean bean = ManagementFactory.getThreadMXBean();
long[] ids = bean.findDeadlockedThreads();
if (ids != null) {
    ThreadInfo[] infos = bean.getThreadInfo(ids, true, true);
    for (ThreadInfo info : infos) {
        System.err.println(info);
    }
}

findDeadlockedThreads can detect some Java monitor and ownable synchronizer deadlocks, but it cannot prove that the entire system is free of deadlocks. For example, if a Java thread holds a lock while waiting for local code, a file lock, a database transaction, or a network service, the lock graph within the JVM remains incomplete.

4. Python: Thread Stacks Are Not Ownership Graphs

Python can use faulthandler to print thread stacks when a signal is received or a timeout occurs:

import faulthandler
import sys

faulthandler.dump_traceback_later(
    timeout=10,
    repeat=False,
    file=sys.stderr,
)

This answers the question "where is each thread currently stalled," but does not automatically reveal the full ownership relationships described by threading.Lock. Even Python's Global Interpreter Lock (GIL) cannot eliminate application-level deadlocks: a thread might hold an application lock while waiting for another lock, condition, queue, or I/O operation; blocking operations may also release the GIL.

Therefore, Python services must also record resource semantics at a higher level, such as task IDs, lock names, queues, request deadlines, and current execution phases. Do not equate periodic stack printing from third-party tools with a deadlock detector.

5. Condition Variables Can Also Create "Looks-Like-Deadlock" Stalls

Condition variable waits atomically release the associated mutex and then reacquire it before returning. Therefore, the fact that a thread is "in pthread_cond_wait" does not imply it currently holds that mutex and is sleeping.

The real issues may include:

• Modifying a predicate without remembering to signal or broadcast;
• Waiters and notifiers protecting different predicates;
• A notification occurring, but the waiter failing to recheck the condition in a loop;
• Producers having exited, while consumers still expect future data;
• No broadcast of termination state along the shutdown path.

When diagnosing, record both predicate values and producer lifecycles. A wait graph that only shows mutexes and ignores business conditions risks misdiagnosing protocol errors as classic lock cycles.

6. lockdep: Detecting Potential Reverse Ordering During Testing

The Linux kernel's lockdep tracks observed lock classes and their acquisition dependencies during runtime. When a new dependency combines with existing ones to form a cycle, it reports a "potential cyclic lock dependency." This does not require that two threads are currently deadlocked in the system, it simply alerts developers that observed execution patterns have already formed a dangerous cycle.

Its effectiveness depends on test coverage: paths that have never been executed will not generate corresponding dependencies. Incorrect lock class annotations, disabled kernel debugging configurations, or running tests in low-coverage environments all undermine the reliability of the results.

User-space projects can adopt a similar approach:

1. Assign stable classes or levels to locks;
2. Maintain a thread-local record of currently held locks;
3. On every lock acquisition, verify that the lock level only increases, or record a dependency edge;
4. Make violations of these rules explicit failures during testing.

Dynamic checks can detect actual reverse ordering that occurs in runtime, while static analysis and code reviews can uncover paths that have never been executed. Together, they provide complementary coverage.

7. Database Deadlocks: The Failure Is the Transaction, Not Necessarily the Process

Databases maintain their own lock and wait relationships. From the operating system's perspective, two application threads may simply appear to be waiting for a database response, what's actually forming a cycle is the database's row locks, range locks, or other transactional resources.

Many databases detect such cycles and select one transaction as the victim to roll back, allowing the others to proceed. When an application receives a deadlock error, it should:

• Roll back and retry the entire transaction boundary, not resume from a single statement within it;
• Use bounded, jittered backoff strategies;
• Ensure that external side effects do not repeat during retries;
• Keep transactions short and access tables and objects in a consistent order;
• Save the database-provided deadlock report to reconstruct the cycle using the actual locked resources.

Specific error codes, victim selection logic, and diagnostic commands vary by database product and version, and should be referenced according to the current official documentation.

8. Remote Waiting Will Hide Loops Across Multiple Machines

Service A holds a local resource call to B, and B in turn holds another resource that triggers a callback back to A, this can also form a waiting loop. A single-machine thread dump can only reveal "waiting for a network call"; it cannot show which remote service is itself waiting for the original one.

Such issues require cross-service request IDs, distributed tracing, and a unified timeout to reconstruct the causal chain. Timeouts can release some resources, but if an older request might still write to shared storage after timing out, mechanisms like leases or fencing tokens are needed to reject stale holders. You cannot analogize the "forceful unlock" of a local mutex to distributed systems, resource ownership and failure models are fundamentally different.

9. An Executable On-Site Debugging Workflow

When progress stalls, follow this sequence to narrow the scope:

1. Verify the symptom: Is it throughput dropping to zero, individual requests hanging, or tail latency increasing?
2. Preserve the context: Record the timestamp, version, PID, request ID, load conditions, and the most recent changes.
3. Capture everything at once: Gather stack traces from all threads, don’t inspect them one by one, as that risks time drift.
4. Label the resources: For each blocking point, document what is being held, what is being waited for, and who might be able to advance it.
5. Trace to endpoints: Follow local locks, conditions, I/O operations, database calls, and remote service invocations to identify the root cause.
6. Identify loops or missing events: Distinguish between lock deadlocks, missed notifications, a holder blocking another, and simple congestion.
7. Restore service: Roll back, terminate, or restart according to predefined recovery strategies, and retain all diagnostic artifacts.
8. Fix the structure: Enforce consistent ordering, reduce lock holding scope, or add detection and timeout mechanisms.
9. Write regression tests: Use barriers, fault injection, or lock ordering checks to amplify and validate the original race condition.

10. Summary

The core of deadlock diagnosis lies in reconstructing resource dependencies from instantaneous stack traces, not in pausing at function names:

• C/C++ thread stacks require combining with source code and lock semantics to determine lock holders;
• Java tools provide richer synchronizer details but lack visibility into the full external loop;
• Python stack traces can pinpoint where execution stalled, but standard locks do not automatically generate ownership graphs;
• lockdep-style checks are effective for identifying dangerous ordering patterns during testing;
• Databases and remote services each require their own wait graphs, transaction reports, and trace context.

The next chapter covers File Systems and Crash Recovery. While concurrency control answers the question of "who modifies first," persistence protocols must also address "what happens if a power failure occurs mid-modification."