Deadlock and Lock Ordering

Part I · Module 26 · Chapter 26.5 · Deadlock and Lock Ordering

1. Two Correct Functions That Stop the Program

Here is the entire bug. Two accounts, each with its own mutex, and two transfer functions:

static std::mutex mA, mB;

static void transferAB()
{
    std::lock_guard<std::mutex> a{mA};
    std::this_thread::sleep_for(std::chrono::milliseconds(5));
    std::lock_guard<std::mutex> b{mB};
    ++progress;
}

static void transferBA()
{
    std::lock_guard<std::mutex> b{mB};
    std::this_thread::sleep_for(std::chrono::milliseconds(5));
    std::lock_guard<std::mutex> a{mA};
    ++progress;
}

Read either function in isolation and there is nothing to criticise. Both use lock_guard, exactly as Chapter 26.4 §1 insists. Both release on every exit path. Both protect their data. Neither contains a mistake.

Run them at the same time and the program stops. Thread one holds mA and wants mB; thread two holds mB and wants mA. Each is waiting for a mutex the other will not release until it gets the one the first is holding. Neither will ever make progress, and neither will ever time out, because lock() has no timeout.

The defect does not live in either function. It lives in the pair — in the fact that one of them believes mA comes first and the other believes mB does. That is what makes deadlock different from every bug class in Module 25: there is no line you can point at and call wrong.

The sleep_for is not part of the bug. It is there to make the bug reliable, and §3 measures exactly how much difference it makes.

2. The Measurement

The harness starts one thread for each function, waits half a second for both to finish, and reports how many got through. Then it runs the same work using std::scoped_lock instead:

A. two lock orders, one thread each
  lock_guard mA then mB / mB then mA     progress 0 of 2 after 500 ms -> *** DEADLOCKED ***

B. the same work with std::scoped_lock (any argument order)
  scoped_lock{sA,sB} / scoped_lock{sB,sA} progress 2 of 2 after 500 ms -> completed

Five runs each way: the lock_guard version deadlocked all five times, and the scoped_lock version completed all five times. Part B's two call sites still name the mutexes in opposite orders — {sA, sB} in one and {sB, sA} in the other — which is the point of §4.

Two details of the harness worth stealing.

It has a timeout. A test that calls join() on a deadlocked thread deadlocks the test runner, and your CI job hangs until something kills it an hour later. Waiting on an atomic counter with a deadline turns "the program stopped" into a printable result, which is the only way a deadlock becomes a test.

It detaches the stuck threads rather than joining them. std::thread's destructor calls std::terminate on a joinable thread — Chapter 26.2 §2 measured the libc++abi: terminating and the exit code 134 — so a harness that wants to survive its own failed experiment must either join (impossible; they are stuck) or detach. Detaching leaks two threads that are blocked forever, and that leak has a consequence serious enough to have broken this very experiment once, which is the callout below.

3. How Often Does It Actually Fire?

This is the measurement that matters, and the one almost nobody makes. The defect in §1 is fixed; the timing is the variable. Four configurations, 100 independent trials each, fresh mutexes per trial, over nine runs:

  no sleep, no barrier           deadlocked   0 of 100 trials
  no sleep, started together     deadlocked  …  of 100 trials
  1 ms sleep between locks       deadlocked 100 of 100 trials
  1 ms sleep + started together  deadlocked 100 of 100 trials

Row one is why deadlocks reach production. The code is defective — provably, since rows three and four are the same code — and it deadlocked zero times in a hundred trials, in eight of the nine runs, with one lone failure in the ninth. Write that test, run it a hundred times, watch it pass, ship it.

Row two is why they are miserable to reproduce. Make the two threads wait for each other before they start, which is all the barrier does, and the failure rate jumps to a median of 39 in 100 — but across runs it was anywhere from 5 to 54. The same binary, the same machine, the same afternoon. There is no "the failure rate is X%" to put in a bug report.

Rows three and four are what a debugger does to you. One millisecond of delay between acquiring the first lock and asking for the second — which is all that a log line, a slow allocation, a page fault, or a loaded machine amounts to — takes the failure from never to always. This is the opposite of a heisenbug: adding delay here does not hide the problem, it guarantees it. And it is the reason a deadlock that has never once appeared in testing can be completely reliable in production, where the machine is busy and the critical sections are not empty.

The actionable conclusion is that you cannot test your way to confidence about deadlock. A hundred green runs is consistent with a defect that fires every time under load. The only durable protection is structural: make the opposite order impossible to write, which is §4 and §5.

4. The Fix the Library Gives You

std::scoped_lock takes any number of mutexes and acquires all of them without deadlocking, whatever order you name them in:

static void safeAB() { std::scoped_lock lk{sA, sB}; ++progress; }
static void safeBA() { std::scoped_lock lk{sB, sA}; ++progress; }

That is §2's part B, and it completed 5 of 5 runs with the two call sites disagreeing about the order. Compare it with the lock_guard version, which is the same disagreement and deadlocked 5 of 5.

How it manages that: it does not simply lock them left to right. It uses the algorithm behind std::lock — take one, then try the others, and if any try_lock fails, release everything and start again from the one that refused. No thread ever sits holding one mutex while blocking on another, so the circular wait in §7 cannot form. The cost is that a contended acquisition may retry; the benefit is that it cannot hang.

Three practical notes.

Use std::scoped_lock whenever you take more than one mutex — always, with no judgement call. It is C++17, it deduces its types (std::scoped_lock lk{a, b} needs no template arguments), and for a single mutex it behaves like lock_guard. Chapter 26.4 §5's table lists it as the default for the multi-mutex case for exactly this reason.

std::lock(a, b) is the same algorithm without the RAII, and so it needs guards adopted afterwards:

std::lock(a, b);                                            // deadlock-free acquisition
std::lock_guard<std::mutex> ga{a, std::adopt_lock};         // ...and now make the release safe
std::lock_guard<std::mutex> gb{b, std::adopt_lock};

Three lines where scoped_lock is one, and if you forget the guards you are back to Chapter 26.4 §2's leaked lock. It exists because it predates scoped_lock; prefer scoped_lock in new code.

It only helps when one piece of code takes both locks at once. If function f locks a and then calls function g, which locks b, no scoped_lock can see both — the acquisition is spread across two stack frames and two source files. That case needs §5.

5. The Fix You Have to Impose Yourself

When the two locks are not acquired in one place, the only remedy is a single global order in which every thread acquires mutexes, enforced by convention and documented where the mutexes are declared.

The order itself is arbitrary. All that matters is that it is total and that everyone obeys it. Common choices:

Address order is what std::scoped_lock relieves you of for the single-site case, and it is exactly what you need for the transfer(from, to) problem, where you cannot know statically which account is which:

void transfer(Account& from, Account& to, long amount)
{
    std::scoped_lock lk{from.mutex, to.mutex};   // handles transfer(a,b) AND transfer(b,a)
    from.balance -= amount;
    to.balance   += amount;
}

Without scoped_lock this function deadlocks against itself the moment two threads run transfer(a, b) and transfer(b, a) — the §1 bug, with one function instead of two.

The discipline that makes a global order survive contact with a real codebase is to write the order down next to the mutex. A comment on the declaration — // level 2: never lock while holding a level-1 mutex — is enforced by nothing, but it converts a question that requires reading the whole program into one a reviewer can answer from the diff. Chapter 26.4 §6's callout made the same move for which data a mutex guards; this is the same remedy applied to when it may be taken.

6. A Hierarchy the Code Can Check

If the ordering rule is a number, it can be enforced at runtime rather than hoped for. Give every mutex a level, keep each thread's current level in a thread_local, and refuse a lock that is not strictly downward:

class LeveledMutex {
public:
    explicit LeveledMutex(int level) : level_{level} {}

    void lock()
    {
        if (level_ >= current())                 // must go strictly DOWN
            throw std::logic_error("lock order violation");
        previous_ = current();
        current() = level_;
        mutex_.lock();
    }
    void unlock() { current() = previous_; mutex_.unlock(); }

private:
    static int& current() { thread_local int lvl = INT_MAX; return lvl; }
    std::mutex mutex_;
    int level_;
    int previous_ = INT_MAX;
};

It satisfies the Lockable requirements, so std::lock_guard<LeveledMutex> and std::scoped_lock work with it unchanged.

What this buys you is the thing §3 proved you cannot get from testing: the violation is reported by the thread that commits it, at the moment it commits it, whether or not a second thread was there to deadlock with. Row one of §3's table — defective code, 0 of 100 failures — becomes an immediate exception on the first trial. You trade a little overhead and some ceremony for turning a timing-dependent hang into a deterministic, attributable error, which is the same trade Chapter 25.6 §6 measured for memory bugs, where a 6.4× slowdown bought deterministic reports.

Two honest limits. It only covers mutexes you have wrapped, so a std::mutex inside a third-party library is invisible to it. And previous_ is stored in the mutex rather than per thread, which is fine for the strictly nested use that a guard enforces and wrong if you ever unlock out of order — another reason the guard discipline is not optional.

7. The Four Conditions, and Which One You Break

The classical account requires all four of these to hold at once, and seeing which ones you can actually attack is clarifying:

Two of the four are fixed by the language, so every real fix attacks either hold-and-wait or circular wait. std::scoped_lock attacks hold-and-wait: it never blocks on a second mutex while holding a first. A global lock order attacks circular wait: if every thread acquires in increasing order, a cycle would require some thread to acquire downward, which no thread does. The lock hierarchy in §6 is the same attack, made checkable.

It is worth naming the "waits for" graph directly, because it is how you will reason about a real hang. Draw a node per thread, and an arrow from each thread to the thread that holds the mutex it is blocked on. A deadlock is exactly a cycle in that graph. Two threads is the common case; three mutexes in a ring is the case that survives code review, because no pair of functions in that ring disagrees — only the ring as a whole does.

8. Deadlocks You Did Not Write

Most real deadlocks are not two visibly adjacent lock_guards. They come from a lock held across a call to something that locks.

Calling unknown code while holding a lock. A callback, a virtual function, an observer notification, an allocator hook. You do not know what it locks, and neither does its author know what you hold. Chapter 26.4 §6 lists this among the three things never to do inside a critical section; this is the failure it leads to. The rule that scales is: drop the lock, then call out. Build the result inside the critical section, release, then notify.

A lock around a join() or a future::get(). You are now holding a mutex while waiting for a thread that may need that mutex. One mutex, one deadlock.

Re-entering your own class. A public function takes the lock and calls another public function, which takes the same lock. std::mutex is not recursive, so this deadlocks a single thread against itself — the cleanest deadlock there is, and the reason Chapter 26.4 §7 recommends the locking-wrapper-plus-_locked-worker split over std::recursive_mutex.

A lock held across I/O. Not a deadlock on its own, but it widens the window in §3's rows three and four from microseconds to milliseconds, which is the difference between 0 of 100 and 100 of 100.

Two mutexes acquired through a container. map1 then map2 in one function, map2 then map1 in another, a hundred lines apart in different files. This is the one that std::scoped_lock cannot see and §5 must handle.

And a liveness failure that is not a deadlock at all: the lost wake-up, where a thread waits for a notification that was already sent. No cycle exists, every lock is free, and the program still stops. Chapter 26.6 §3 measures it, and the fix is unrelated to anything in this chapter.

9. try_lock, Timeouts, and Why They Are Last Resorts

try_lock returns immediately rather than blocking, so a thread can decline to wait and give up what it holds:

std::unique_lock<std::mutex> a{mA};
std::unique_lock<std::mutex> b{mB, std::try_to_lock};
if (!b.owns_lock()) { a.unlock(); /* back off, retry later */ }

This does break hold-and-wait, and it is the core of what std::scoped_lock does internally. Written by hand it has two problems.

Livelock. Two threads that back off and retry in lockstep can repeat that forever: both acquire, both fail, both release, both retry. No thread is blocked — the program is busy and making no progress, which is worse than a deadlock because it does not even look stuck. Real backoff needs randomised delay, and at that point you have reimplemented std::lock less well.

Starvation. A thread that always loses the retry race never progresses, while the system as a whole looks healthy.

std::timed_mutex with try_lock_for is the same tool with a clock. It is right in a watchdog, a diagnostic path, or a shutdown sequence that must not hang — and it is a smell in ordinary code, because a timeout on a lock is a prediction that the lock will not be available, which is a design problem you have chosen to live with.

The honest ranking: scoped_lock first, a global order second, a checked hierarchy third, and hand-rolled try_lock only when none of those apply.

10. Finding One, and What the Tools Here Actually Did

A deadlocked program has a very recognisable signature: CPU usage drops to zero and it does not exit. A livelock looks the opposite — CPU pinned, no progress. That distinction is the first thing to establish, and it costs nothing.

The reliable technique is to get a stack trace of every thread while it is stuck, from a debugger attached to the live process or from a core dump, and look for two threads blocked inside a lock acquisition. The cycle is usually obvious once you can see all the stacks at once.

Now the honest part, because this module has to report what actually happened on this machine.

ThreadSanitizer, which found the data race in Chapter 26.3 §7 immediately, reported nothing at all here. It has a deadlock detector; TSAN_OPTIONS=help=1 lists detect_deadlocks with Current Value: false. Enabling it explicitly with detect_deadlocks=1 produced output byte-identical to the un-sanitized run — the program still deadlocked, and TSan said nothing about it. So on this macOS/arm64 build, TSan did not detect the lock-order inversion, and I am reporting that as an observation about this toolchain rather than as a claim about TSan on other platforms, where the detector is documented to work and where it is worth trying.

Chapter 25.7 §1 and Chapter 25.8 §1 record the rest of the toolbox on this machine: lldb is present, so the stack-trace route above is genuinely available; valgrind is absent; and sample attaches but reports an empty call graph. That is a real limitation of the environment and not a reason to pretend a tool produced output.

Which leaves the thing that did work, and that is §6. A checked hierarchy does not need to observe the deadlock; it reports the violation from the single thread that commits it, on the first trial, including the 0-of-100 configuration that no amount of testing would have flagged. When the dynamic tools are unavailable, making the invariant checkable in your own code is not a consolation prize — it is the stronger technique.

11. The Table

12. What to Actually Do

• Never hold one mutex while asking for another. If you must, take them together with std::scoped_lock.
• Use std::scoped_lock for every multi-mutex acquisition, including transfer(from, to) where you cannot know the order statically.
• Prefer it to std::lock plus adopt_lock guards — one line instead of three, and nothing to forget.
• Where the locks are taken in different places, define one global order and write it on the declaration. A reviewer must be able to check it from the diff.
• Consider a levelled mutex when the system is large enough that convention will not hold. It turns §3's 0-of-100 into an exception on the first run.
• Drop the lock before calling anything you do not own — callbacks, virtuals, allocator hooks, notifications.
• Never hold a lock across join(), future::get(), or I/O.
• Split public functions into a locking wrapper and a _locked worker rather than reaching for recursive_mutex.
• Give every concurrency test a deadline instead of a bare join(), so a hang becomes a failed assertion rather than a hung CI job.
• Treat a process that has deadlocked once as contaminated — its mutexes are gone for good.
• Do not conclude from green tests that there is no deadlock. Conclude it from the structure of the acquisition order.

13. Mistakes Worth Making Once

Two functions, two orders. Each reviewed and approved separately. §1.

transfer(a, b) and transfer(b, a). One function, deadlocking against itself.

Shipping it because the test passed a hundred times. §3 row one: 0 of 100, and the code is provably broken.

Reporting "it fails about 40% of the time". §3 row two ranged from 5 to 54 in nine runs.

Adding a log line inside the critical section and watching the deadlock become permanent. §3 rows three and four.

Joining a deadlocked thread in a test. The test runner hangs too.

Reusing one mutex pair across two experiments. The §3 callout — it told me the standard library was broken.

Calling a user callback with the lock held. Their code locks something; now the order is theirs to decide.

Hand-rolled try_lock retry loops. Livelock: full CPU, zero progress, and it does not even look stuck.

Assuming the sanitizer will catch it. On this machine, with the flag on, it did not. §10.

14. Interview Relevance

The frozen curriculum marks this High, and the question is almost always the same: what is a deadlock and how do you prevent it? The mechanism answer — two threads, two mutexes, opposite orders, a cycle in the waits-for graph — is table stakes. Two additions separate a good answer.

The fixes, in order of preference. std::scoped_lock when one piece of code takes both locks, because it acquires them with the std::lock algorithm and therefore never holds one while blocking on another, whatever order the call site names them in. A documented global lock order when the acquisitions are in different places and no single site can see both. A levelled mutex checked against a thread_local when the codebase is too large for convention. And try_lock backoff last, because by hand it buys livelock.

The frequency, which is the part that shows experience. Say that the identical defect deadlocked 0 of 100 trials when the threads started whenever they liked, a median 39 of 100 when they were released together, and 100 of 100 with a single millisecond between the two acquisitions. Then draw the conclusion out loud: a deadlock that never appears in testing can be completely deterministic in production, where machines are loaded and critical sections are not empty, so the protection has to be structural rather than empirical.

If the conversation goes to tooling, the four conditions are a good frame — mutual exclusion and no-preemption are fixed by the language, so every fix attacks hold-and-wait or circular wait — and it is fine, and better than bluffing, to say that a sanitizer's deadlock detector is worth trying but that you have seen it report nothing on a real deadlock.

15. What You Should Be Able to Say Now

• That a deadlock needs only two mutexes and two opinions about their order, and that the defect is in the pair, not in either function.
• That it reproduced 5 of 5 with lock_guard and that std::scoped_lock completed 5 of 5 with the call sites still disagreeing about the order.
• That the same code deadlocked 0 of 100 trials with no delay, a median 39 of 100 [5–54] when the threads were started together, and 100 of 100 with 1 ms between the locks.
• Therefore testing cannot establish the absence of a deadlock, and 1 ms of delay is what a log line or a loaded machine supplies for free.
• That a deadlocked thread still owns its mutexes, nothing can take them away, and so a process that deadlocked once can no longer measure anything.
• That std::scoped_lock breaks hold-and-wait and a global order breaks circular wait — the only two of the four conditions you can attack.
• That the multi-site case needs a written-down order, and that a levelled mutex makes it checkable by the thread that violates it.
• That most real deadlocks come from calling unknown code, or waiting on a thread, while holding a lock.
• That hand-rolled try_lock loops buy livelock and starvation.
• That on this machine, TSan with detect_deadlocks=1 reported nothing for a genuine deadlock.

16. Exercises

Exercise 1 — reproduce it. Write §1's two functions and drive them from two threads with a 500 ms deadline rather than a join(). Confirm the deadlock and confirm your harness prints a result instead of hanging.

Exercise 2 — the frequency table. Reproduce §3's four configurations with 100 trials each, allocating fresh mutexes per trial. Run the whole thing nine times. Satisfy yourself that row one is 0 and row three is 100.

Exercise 3 — the contamination bug. Deliberately share one mutex pair between a deadlocking experiment and a scoped_lock experiment, and watch the correct code be reported as broken.

Exercise 4 — the fix, in both orders. Replace the guards with std::scoped_lock, keeping the two call sites naming the mutexes in opposite orders. Then write the std::lock plus adopt_lock version and count the lines.

Exercise 5 — transfer. Write transfer(Account&, Account&) and deadlock it against itself with transfer(a,b) and transfer(b,a). Fix it with one scoped_lock.

Exercise 6 — the hierarchy. Implement §6's LeveledMutex, use it with std::lock_guard, and confirm that the 0-of-100 configuration from §3 throws on the very first trial.

Exercise 7 — the tools. Run your deadlock under -fsanitize=thread with detect_deadlocks=1 and record what it reports on your platform. Then get a stack trace of both threads while stuck, and find the cycle by hand.

17. Summary

• A deadlock is two mutexes and a disagreement about which comes first. Each function is correct in isolation; the defect lives in the pair, which is why code review alone does not catch it.
• Measured: the lock_guard version deadlocked 5 of 5 runs; the std::scoped_lock version completed 5 of 5 with its two call sites still naming the mutexes in opposite orders.
• The central measurement is the frequency. The identical defect deadlocked 0 of 100 trials when the threads started independently, a median 39 of 100 (range 5–54 over nine runs) when released together, and 100 of 100 with one millisecond between the two acquisitions.
• So a hundred green test runs prove nothing, and the millisecond that makes it certain is what a log line, an allocation, or a busy machine contributes for free. Protection must be structural.
• A deadlocked thread still owns its mutexes — nothing in C++ can take them back — so a deadlocked process is contaminated, which is how a harness once told me scoped_lock was broken.
• Use std::scoped_lock for every multi-mutex acquisition; it breaks hold-and-wait by never blocking on one lock while holding another. Prefer it to std::lock with adopt_lock.
• Where two locks are taken in different places, impose one global order and document it on the declaration; make it a checked level per mutex when the codebase outgrows convention.
• Most real deadlocks are a lock held across a call you do not control — a callback, a virtual, a join(), a future::get(), or I/O.
• try_lock backoff by hand buys livelock: full CPU, no progress, and it does not look stuck.
• And on this machine TSan reported nothing, with detect_deadlocks=1 set, for a deadlock that happened every run.

Chapter 26.6 is the liveness failure that has no cycle at all: a thread waiting for a notification that has already been sent.