Debugging Deadlocks: Common Scenarios

Part 1: What is a Deadlock?

A deadlock occurs when two or more threads are blocked forever, each waiting for a resource held by another thread in the group. This creates a circular dependency that prevents any of the threads from making progress.

Imagine a city intersection with no traffic lights where two cars arrive at the same time, each wanting to turn left. Car A enters the intersection and waits for Car B to move. Car B also enters and waits for Car A to move. Neither can proceed, and they are deadlocked.

In programming, the "cars" are threads and the "lanes in the intersection" are resources, most commonly mutexes.

This resource allocation graph perfectly illustrates a deadlock. Process P1 holds Resource R1 and is waiting for Resource R2. At the same time, Process P2 holds Resource R2 and is waiting for Resource R1. This circular wait ensures that neither process can ever proceed.

For a deadlock to occur, four conditions—often called the Coffman conditions—must be met simultaneously:

1. Mutual Exclusion: At least one resource must be held in a non-shareable mode. (A std::mutex can only be locked by one thread at a time).
2. Hold and Wait: A thread is holding at least one resource and is waiting to acquire additional resources held by other threads.
3. No Preemption: A resource can only be released voluntarily by the thread holding it.
4. Circular Wait: A set of threads {T₀, T₁, ..., Tₙ} exists such that T₀ is waiting for a resource held by T₁, T₁ is waiting for a resource held by T₂, ..., and Tₙ is waiting for a resource held by T₀.

While these conditions are the formal definition, in practice, you'll most often encounter deadlock as a simple two-thread circular dependency.

Part 2: The Classic AB-BA Locking Scenario

The most common cause of deadlock is inconsistent lock ordering. Let's consider two threads that need to lock the same two mutexes, but they do so in a different order.

Thread 1 (Function transfer_A_to_B)

void transfer_A_to_B(Account& A, Account& B, double amount) {
    std::lock_guard<std::mutex> lock_a(A.m); // Locks mutex A
    // some work...
    std::lock_guard<std::mutex> lock_b(B.m); // Tries to lock mutex B
    A.balance -= amount;
    B.balance += amount;
}

Thread 2 (Function transfer_B_to_A)

void transfer_B_to_A(Account& B, Account& A, double amount) {
    std::lock_guard<std::mutex> lock_b(B.m); // Locks mutex B
    // some work...
    std::lock_guard<std::mutex> lock_a(A.m); // Tries to lock mutex A
    B.balance -= amount;
    A.balance += amount;
}

Now, imagine the following sequence of events:

1. Thread 1 calls transfer_A_to_B and successfully locks mutex A.m.
2. The OS scheduler preempts Thread 1 and runs Thread 2.
3. Thread 2 calls transfer_B_to_A and successfully locks mutex B.m.
4. Thread 2 now tries to lock A.m, but it's held by Thread 1, so Thread 2 blocks.
5. Thread 1 resumes and tries to lock B.m, but it's held by Thread 2, so Thread 1 blocks.

Both threads are now blocked indefinitely. Deadlock.

Part 3: Debugging a Deadlock with GDB

When your program hangs, your first task is to confirm if it's a deadlock and identify the culprits. Since you're interested in the low-level details, we'll use the GNU Debugger (GDB) to see what's happening under the hood.

Let's use the following code, which is a C++ adaptation of the example from the article we'll reference.

// deadlock.cpp
#include <iostream>
#include <thread>
#include <mutex>

void worker_1(std::mutex& m1, std::mutex& m2) {
    std::lock_guard<std::mutex> lock1(m1);
    std::this_thread::sleep_for(std::chrono::milliseconds(10)); // Encourage deadlock
    std::lock_guard<std::mutex> lock2(m2);
    std::cout << "Thread 1 finished.\n";
}

void worker_2(std::mutex& m1, std::mutex& m2) {
    std::lock_guard<std::mutex> lock2(m2);
    std::this_thread::sleep_for(std::chrono::milliseconds(10)); // Encourage deadlock
    std::lock_guard<std::mutex> lock1(m1);
    std::cout << "Thread 2 finished.\n";
}

int main() {
    std::mutex m1, m2;
    std::thread t1(worker_1, std::ref(m1), std::ref(m2));
    std::thread t2(worker_2, std::ref(m1), std::ref(m2));
    t1.join();
    t2.join();
    return 0;
}

Your Turn: A Guided Debugging Session

1. Compile with Debug Symbols:

   g++ -g -o deadlock deadlock.cpp -lpthread
   

2. Run until it Deadlocks: The program will sometimes run to completion and sometimes hang. Run it in a loop to catch it when it deadlocks.

   while true; do ./deadlock; done
   

   When it hangs, press Ctrl+C to stop the loop, but the deadlock process will still be running.

3. Find the Process ID (PID) and Attach GDB:

   ps aux | grep ./deadlock
   # Look for the PID of your process
   gdb -p <PID>
   

4. Inspect All Threads: Once in GDB, the most important command is thread apply all bt (backtrace). This shows the call stack for every thread.

   (gdb) thread apply all bt
   

   You will see output where your worker threads are stuck deep inside the threading library. Look for functions like __lll_lock_wait. This is the low-level Linux function that puts a thread to sleep when it fails to acquire a mutex. It operates on a futex (Fast Userspace Mutex), which is the underlying OS primitive that std::mutex uses on Linux.

*This backtrace from GDB shows a thread blocked on a futex wait. When you see your threads in a similar state, it's a strong indication they are waiting on a lock.*

5. Find the Culprits: By examining the backtraces, you can see which lines in your code are causing the block. Now, let's confirm the circular dependency.

Following the guide, you can switch to one of the blocked threads in GDB, move up the stack frame to where the mutex variable is in scope, and print its internal state. On Linux with glibc, you can often inspect a std::mutex by casting its native handle to a pthread_mutex_t*.

For example, for Thread 1 (in worker_1), which is blocked trying to lock m2:

(gdb) thread 2  # Assuming Thread 2 is running worker_1
(gdb) frame 2   # Go to the stack frame for worker_1
(gdb) p m2
$1 = {<std::mutex>} = {_M_mutex = {__data = {__lock = 2, __count = 0, ...}, ...}}

You can inspect _M_mutex to see the owner ID. Following the technique in the article, you'll find that m2 is owned by Thread 3 (running worker_2), and m1 (which Thread 3 is waiting on) is owned by Thread 2. You've just diagnosed a deadlock at the OS level!

Part 4: Deadlock Prevention

Debugging deadlocks is a useful skill, but preventing them is far better.

Strategy 1: Strict Lock Ordering

The simplest and most robust way to prevent the AB-BA deadlock is to establish a global order for acquiring locks. If all threads always lock mutex A before mutex B, the circular wait condition becomes impossible.

You can enforce this by ordering locks based on their memory addresses.

void safe_transfer(Account& from, Account& to, double amount) {
    // Lock the mutex with the smaller address first
    if (&from.m < &to.m) {
        std::lock_guard<std::mutex> lock_from(from.m);
        std::lock_guard<std::mutex> lock_to(to.m);
        // ... do transfer ...
    } else {
        std::lock_guard<std::mutex> lock_to(to.m);
        std::lock_guard<std::mutex> lock_from(from.m);
        // ... do transfer ...
    }
}

This works, but it's manual and error-prone.

Strategy 2: std::lock and std::scoped_lock

Modern C++ gives us a much better tool. The function std::lock can lock multiple mutexes at once using a deadlock-avoidance algorithm internally. The RAII wrapper std::scoped_lock (C++17) makes this incredibly simple.

void safe_transfer_modern(Account& from, Account& to, double amount) {
    std::scoped_lock lock(from.m, to.m); // Acquires both locks without deadlock
    from.balance -= amount;
    to.balance += amount;
} // Both mutexes are automatically released here

std::scoped_lock guarantees that it will acquire all locks without causing a deadlock. Under the hood, it may use an algorithm similar to our manual address-ordering, or a more complex try-and-back-off strategy. This should always be your default choice when you need to lock more than one mutex.

Let's return to the video to see this solution in action.

Part 5: Case Study: The Dining Philosophers Problem

The AB-BA scenario involves two resources. What happens with more? The Dining Philosophers is a classic computer science problem that illustrates the complexities of deadlock and starvation with multiple resources and threads.

The setup:

• Five philosophers sit at a round table.
• Between each pair of adjacent philosophers is a single fork.
• To eat, a philosopher must pick up both the fork to their left and the fork to their right.
• The philosophers only think or eat. When they are hungry, they try to pick up the forks, eat for a while, and then put them down.

The problem is to design a protocol that allows the philosophers to eat without deadlocking (where all philosophers pick up one fork and wait forever for the other) or starving (where a philosopher is perpetually unable to get both forks).

The key insight from that paper is that simply avoiding deadlock isn't enough; a good algorithm also maximizes concurrency. The std::lock function is specified to use such a deadlock-avoidance algorithm, often a "smart" try-and-back-off strategy similar to the ones analyzed in the paper. This ensures both safety and performance. I highly recommend browsing the source code in Appendix A of that article to see a high-quality implementation of these concepts.

Conclusion

You have now confronted deadlock, one of the most classic problems in concurrent programming. You've learned not only what it is, but also how to dissect it with a debugger and, most importantly, how to architect your code to prevent it from ever happening.

Key Takeaways:

• Deadlock is a circular dependency where multiple threads are blocked forever waiting on resources held by each other.
• The most common pattern is AB-BA locking, where two threads acquire the same two mutexes in opposite orders.
• You can debug a deadlock using GDB by getting backtraces of all threads (thread apply all bt) and inspecting the low-level state of the mutexes to find the ownership cycle.
• The fundamental prevention strategy is lock ordering: always acquire locks in a consistent, globally defined order.
• The modern C++ solution is to use std::scoped_lock (or std::lock), which handles deadlock avoidance for you automatically.

What's Next?

We've spent a lot of time learning how to manage shared data with locks (std::mutex). But locks have costs: they can be slow, and as we've just seen, they can lead to deadlocks. This begs the question: is it possible to coordinate threads and share data without using locks at all?

In the next module, we will begin our journey into advanced C++ concurrency. We'll start by exploring lock-free programming, where we use std::atomic operations and careful memory ordering to build concurrent data structures that are immune to deadlock.