Step 5 of 6

Deadlock and lock ordering

Mutexes fix data races, but they bring their own failure: deadlock. Moving money between two accounts needs both accounts' locks. Watch what happens if each thread locks "from" first, then "to":

void transfer(Account& from, Account& to, long long amount) {
    std::lock_guard<std::mutex> a(from.m);   // lock the first account
    std::lock_guard<std::mutex> b(to.m);     // then the second
    from.balance -= amount;
    to.balance += amount;
}
// thread 1: transfer(alice, bob, 10)
// thread 2: transfer(bob, alice, 5)

Thread 1 locks Alice's account and reaches for Bob's. At the same moment, thread 2 locks Bob's and reaches for Alice's. Each holds what the other needs, and each waits for the other forever. Nothing crashes and no error appears: the program just stops making progress. That is a deadlock, and like a race it depends on timing, so it can pass every test and then freeze a server at 3 a.m.

A deadlock needs a cycle: thread 1 holds A and waits for B, while thread 2 holds B and waits for A. Break the cycle and deadlock is impossible.

Fix 1: lock them together

std::scoped_lock (C++17) takes several mutexes and locks all of them using a deadlock-avoidance algorithm, whatever order you list them in:

#include <iostream>
#include <mutex>
#include <thread>

struct Account {
    std::mutex m;
    long long balance = 0;
};

void transfer(Account& from, Account& to, long long amount) {
    std::scoped_lock lock(from.m, to.m);   // both at once, no deadlock
    from.balance -= amount;
    to.balance += amount;
}

int main() {
    Account alice, bob;
    alice.balance = 1000;
    bob.balance = 1000;
    std::thread t1([&] { for (int i = 0; i < 100000; i++) transfer(alice, bob, 1); });
    std::thread t2([&] { for (int i = 0; i < 100000; i++) transfer(bob, alice, 1); });
    t1.join();
    t2.join();
    std::cout << alice.balance << " " << bob.balance << "\n";
}

1000 1000

With two lock_guards in "from, to" order instead, this same program froze in all five test runs on a real machine: each thread sat holding one account's lock, waiting for the other's.

Fix 2: one global order

When locks are taken in different places (a lock here, a function call that locks something else there), the rule is: every thread takes locks in the same order. If everyone who needs both A and B takes A first, no cycle can form. Teams write the order down ("always lock the account with the smaller id first") and tools like ThreadSanitizer report "lock-order-inversion" when two code paths disagree, even on runs that didn't actually deadlock.

Two more ways to get stuck

• Locking a std::mutex you already hold is undefined behavior (in practice, the thread usually deadlocks on itself). Don't call a locking member function from another one that already holds the lock.
• Holding a lock while calling code you don't control (a callback, a virtual function) invites someone else's lock into your ordering. Keep critical sections short.

Finding inversions

That lock-order check is what you'll write. Each thread is described by the locks it takes, in order, each while still holding the earlier ones: "AB" means lock A, then lock B while holding A. Two threads can deadlock if one takes some lock X before Y and another takes Y before X. A thread that takes the same lock twice can deadlock on its own.

Your turn: write may_deadlock(threads). Return true if any thread takes the same lock twice, or if two different threads take some pair of locks in opposite orders.

Previous: Atomics Next: Condition variables and producer/consumer