Deadlocks and consistent lock ordering

Understanding Deadlocks and consistent lock ordering

A deadlock is neither a crash nor a slow path: it is two threads parked forever, burning no CPU. Thread 1 runs transfer(a, b) and locks a.m, thread 2 runs transfer(b, a) and locks b.m, and then each blocks on the mutex the other is holding. std::mutex::lock has no timeout and no way to give up, so both wait for a release that can never come. Four conditions have to hold at once (exclusive ownership, holding one lock while asking for another, no forcible take-back, and a cycle among the waiters), and the only one you can realistically design away is the cycle.

The mental model is a graph: one node per mutex, and an arrow from A to B every time any thread anywhere holds A while acquiring B. Deadlock is possible exactly when that graph contains a cycle, and the naive transfer draws both a.m to b.m and b.m to a.m, a cycle of length two. A consistent lock order is a rank on the nodes such that every arrow points strictly downhill, which makes a cycle impossible by construction. The order must be global: it is a property of the whole program, not something one function may decide from its own argument list.

Two mutexes at the same level, like the two accounts inside one transfer, have no natural rank, so you either invent one (compare their addresses with std::less) or let the library sidestep the question. std::scoped_lock over two or more mutexes locks them as if by std::lock, which try_locks and drops what it already holds when an attempt fails, so hold-and-wait never occurs. That covers only the mutexes named in that one constructor; a lock taken later, deeper in the call stack, or inside a callback invoked while holding a lock, is back under the ordering rules. Because the failure is timing dependent and may hide for months, prefer a rule you can verify by reading the code over a test run that happened to pass.

Deadlock avoidance is cheaper than deadlock recovery, so bake the ordering into the API where possible: a function that needs both accounts should take both and lock them once, rather than exposing lock() and unlock() to callers who will nest them in whatever order suits them.

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

struct Account {
    std::mutex m;
    int balance;
    explicit Account(int b) : balance(b) {}
};

// The version that deadlocks:
//     std::lock_guard<std::mutex> g1(from.m);
//     std::lock_guard<std::mutex> g2(to.m);
// It takes the mutexes in argument order, so transfer(a, b) on one thread and
// transfer(b, a) on another can each hold one and block on the other forever.
void transfer(Account& from, Account& to, int amount) {
    if (&from == &to) return;              // locking one mutex twice is UB
    std::scoped_lock guard(from.m, to.m);  // both, or neither, in one step
    from.balance -= amount;
    to.balance   += amount;
}

int main() {
    Account a{1000}, b{1000};

    std::thread t1([&] { for (int i = 0; i < 100000; ++i) transfer(a, b, 1); });
    std::thread t2([&] { for (int i = 0; i < 100000; ++i) transfer(b, a, 1); });
    t1.join();
    t2.join();

    std::cout << "a     = " << a.balance << '\n';
    std::cout << "b     = " << b.balance << '\n';
    std::cout << "total = " << a.balance + b.balance << '\n';
}

Worked examples

#include <functional>
#include <iostream>
#include <mutex>
#include <thread>
#include <utility>

struct Node {
    std::mutex m;
    int value = 0;
};

void swap_values(Node& x, Node& y) {
    Node* first  = &x;
    Node* second = &y;
    if (std::less<Node*>{}(second, first)) std::swap(first, second);

    std::lock_guard<std::mutex> g1(first->m);
    std::lock_guard<std::mutex> g2(second->m);
    std::swap(x.value, y.value);
}

int main() {
    Node p, q;
    p.value = 1;
    q.value = 2;

    std::thread t1([&] { for (int i = 0; i < 100000; ++i) swap_values(p, q); });
    std::thread t2([&] { for (int i = 0; i < 100000; ++i) swap_values(q, p); });
    t1.join();
    t2.join();

    std::cout << p.value << " " << q.value << '\n';
}

#include <iostream>
#include <limits>
#include <mutex>
#include <stdexcept>

class RankedMutex {
public:
    explicit RankedMutex(int rank) : rank_(rank) {}

    void lock() {
        if (rank_ >= held_rank())
            throw std::logic_error("lock order violation");
        m_.lock();
        previous_ = held_rank();
        held_rank() = rank_;
    }

    void unlock() {
        held_rank() = previous_;
        m_.unlock();
    }

private:
    static int& held_rank() {
        static thread_local int rank = std::numeric_limits<int>::max();
        return rank;
    }

    std::mutex m_;
    int rank_;
    int previous_ = 0;
};

int main() {
    RankedMutex outer(100), inner(50);

    {
        std::lock_guard<RankedMutex> a(outer);
        std::lock_guard<RankedMutex> b(inner);
        std::cout << "outer then inner: ok\n";
    }

    try {
        std::lock_guard<RankedMutex> a(inner);
        std::lock_guard<RankedMutex> b(outer);
        std::cout << "unreachable\n";
    } catch (const std::logic_error& e) {
        std::cout << "inner then outer: " << e.what() << '\n';
    }
}

Important notes

Common mistakes

Try it yourself