Concurrency, Synchronization & Deadlock Questions

Starvation means a task or class of work is ready to run but is never granted the resource it needs, because other work keeps getting it first. The system is busy and not deadlocked (nobody is waiting in a cycle), yet one party makes no progress. In a livelock everyone is busy and none progresses; in starvation most work progresses and a victim does not.

A concrete service scenario

A backend worker pulls jobs from two queues: interactive API requests (high priority) and batch report exports (low priority). The rule is "always take interactive first". On a quiet day batch jobs drain in the gaps. During a busy hour interactive requests arrive as fast as the worker can serve them, the interactive queue is never empty, and the batch queue only grows. Exports time out at the client, support tickets arrive, yet CPU is high and the throughput graph looks healthy. The same shape appears with a reader-preferring reader-writer lock (readers keep entering, a writer waits forever), an unfair mutex, and a thread pool where a long job class holds every thread.

A small model

One worker, 10 ms per job, interactive arrivals every 10 ms (the worker's whole capacity), batch arrivals every 100 ms, simulated for 10 s of virtual time. The simulation is deterministic, so its output is the same on every run:

from collections import deque

def simulate(reserve=0, cap=None):
    """One worker, one job per 10 ms slot, 1000 slots (10 s).
    Interactive job arrives every 10 ms, batch job every 100 ms.
    reserve=N: every Nth slot goes to batch if a batch job is waiting.
    cap=C: refuse an interactive arrival when C interactive jobs already wait."""
    hi, lo = deque(), deque()
    hi_served = lo_served = shed = 0
    max_lo_wait = None
    for slot in range(1000):
        t = slot * 10
        if cap is not None and len(hi) >= cap:
            shed += 1
        else:
            hi.append(t)
        if t % 100 == 0:
            lo.append(t)
        if reserve and slot % reserve == reserve - 1 and lo:
            wait = t - lo.popleft()
            lo_served += 1
            max_lo_wait = wait if max_lo_wait is None else max(max_lo_wait, wait)
        elif hi:
            hi.popleft()
            hi_served += 1
        elif lo:
            wait = t - lo.popleft()
            lo_served += 1
            max_lo_wait = wait if max_lo_wait is None else max(max_lo_wait, wait)
    return hi_served, lo_served, shed, len(hi), len(lo), max_lo_wait

rows = [("strict priority", simulate()),
        ("1 slot in 5 reserved", simulate(reserve=5)),
        ("reserved + queue cap 50", simulate(reserve=5, cap=50))]
print(f"{'policy':26}{'hi served':>10}{'lo served':>10}{'shed':>6}{'hi queued':>10}{'lo queued':>10}{'max lo wait ms':>16}")
for name, (h, l, s, hq, lq, w) in rows:
    print(f"{name:26}{h:>10}{l:>10}{s:>6}{hq:>10}{lq:>10}{str(w):>16}")

Run in a python:3.12-slim container it prints:

Column key: hi served and lo served are the interactive and batch jobs finished in the 10 s; shed is jobs refused outright; hi queued and lo queued are jobs still waiting at the end; max lo wait ms is the longest a batch job waited before a worker took it (None means no batch job was ever served, so there is no wait to measure).

policy                     hi served lo served  shed hi queued lo queued  max lo wait ms
strict priority                 1000         0     0         0       100            None
1 slot in 5 reserved             900       100     0       100         0              40
reserved + queue cap 50          900       100    51        49         0              40

Strict priority served all 1000 interactive jobs and none of the 100 batch jobs. Reserving one dispatch in five for batch served every batch job (waiting at most 40 ms), at the price of 100 interactive jobs left queued: the interactive class alone needed 100% of capacity, so giving batch any slots must push a backlog somewhere. The reserve is a guarantee of up to 20% of slots, not a quota that is always spent: only 100 batch jobs arrived against 1,000 dispatch slots (10 s at 10 ms each), so batch used 10% of them and interactive got the other 900. The 100 interactive jobs left queued are exactly the 100 slots batch consumed. Capping the interactive queue at 50 turns that backlog into explicit shedding (51 jobs refused) instead of unbounded latency. The model is idealised (fixed job size, one worker), so read the pattern, not the exact counts.

How I would mitigate, in order

1. Detect it with the right metric. Throughput and CPU look fine. Alert on age of the oldest item per class and per-class completion rate; starvation is invisible in an average.
2. Guarantee a floor. Reserve a share (a slot in N, a separate small pool, or a minimum weight in a weighted fair queue, which hands each class a share of dispatches in proportion to its weight) for each class. This is the fix I would ship first, because it bounds a victim's wait regardless of load.
3. Age priorities. For many classes, raise a job's effective priority the longer it waits, so any job eventually outranks new arrivals.
4. Bound the dominant class. Cap its queue or concurrency and shed or defer its excess (as in the third row), so that high priority cannot consume 100% of a shared worker.
5. Use fair primitives. Choose a fair lock (one that hands the lock to waiters in arrival order, a FIFO hand-off lock) or a writer-preferring or fair reader-writer lock where writers must not wait indefinitely, and know its throughput cost. A reader-preferring reader-writer lock, by contrast, lets new readers in while a writer waits, which is the starvation case described earlier.
6. Fix capacity. Starvation under saturation is a capacity signal. Priorities choose who suffers; they do not create capacity.

I would recommend 2 plus 4 plus the age metric: a floor protects the low class, the cap protects the system, and the metric tells you when the real fix is more workers.

Direct answer

Take thread dumps first (three, about ten seconds apart, before restarting anything) and read the state and the CPU of each blocked thread. A deadlock is a cycle: every thread in it waits for a lock another thread in it holds, the threads use almost no CPU and the stacks are identical in every dump. A livelock is threads that keep running (high CPU) and keep changing state, each retrying or backing off in response to the others, so the stacks differ between dumps and no work completes. Priority inversion is a high-priority thread blocked on a lock held by a low-priority thread that cannot run because medium-priority threads are using the CPU; it exists only under strict-priority scheduling (the scheduler always runs the highest-priority runnable thread) and ends when the medium work finishes. Collect dumps, per-thread CPU and a core file; recover by draining (taking the instance out of load-balancer rotation so no new requests arrive) and restarting the instance (a lock cycle among monitors, the per-object locks the Java virtual machine uses for synchronized, cannot be broken from outside); prevent a repeat with a global lock order, timeouts, and a lock-order check in CI.

Ordered checks

1. Confirm the hang is real and scope it. Is any request counter still moving? Does only one instance hang? Take the instance out of the load balancer rotation (drain) before touching it, so users stop hitting it.
2. Dump three times. For a Java virtual machine (JVM): jstack PID > dump1.txt (and again after 10 s and 20 s). For native code: gdb -p PID -batch -ex "thread apply all bt" (not run in the demos here: gdb was not available in the container image used) or gcore PID to keep a core file (a snapshot of the process's memory and thread state written to disk, which you can inspect after the process is gone) for offline analysis. Capture per-thread CPU: top -H -p PID or ps -L -o tid,pcpu,stat,wchan -p PID (one line per thread: pcpu is its CPU use, stat its state, and wchan the kernel function it is sleeping in, which shows a futex wait, the kernel-assisted sleep on a lock, when it is blocked on a lock).
3. Classify with the table. A wait-for graph has one node per thread and an arrow from each thread to the thread whose lock it is waiting for; a cycle in that graph is a deadlock.

4. Find the cycle. The JDK prints it for you. Here is a program with the classic opposite-order locks:

public class Transfer {
    static final Object ACCOUNT_A = new Object(), ACCOUNT_B = new Object();

    static void move(String name, Object first, Object second) {
        synchronized (first) {
            pause(200);                       // widen the window so the demo is deterministic
            synchronized (second) { System.out.println(name + " done"); }
        }
    }
    static void pause(long ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }

    public static void main(String[] args) {
        new Thread(() -> move("a-to-b", ACCOUNT_A, ACCOUNT_B), "worker-1").start();
        new Thread(() -> move("b-to-a", ACCOUNT_B, ACCOUNT_A), "worker-2").start();
    }
}

Built with javac Transfer.java and run with java Transfer in a Linux container (JDK 21), then checked after 5 seconds with ps -o pid,pcpu,stat,comm, the process showed well under 1 percent CPU and state Sl (sleeping, multithreaded). jstack PID ended with:

Found one Java-level deadlock:
=============================
"worker-1":
  waiting to lock monitor 0x0000ffff40001d30 (object 0x00000007152139d0, a java.lang.Object),
  which is held by "worker-2"

"worker-2":
  waiting to lock monitor 0x0000ffff44000f00 (object 0x00000007152139c0, a java.lang.Object),
  which is held by "worker-1"
...
Found 1 deadlock.

(addresses differ per run; the per-thread stack sections below the cycle list the lines waiting to lock and locked for each thread.) Read each block as an arrow: worker-1 waits for a lock held by worker-2, and worker-2 waits for one held by worker-1. That is the cycle. In the ps check, near-zero CPU says nothing is running, and Sl says the process is sleeping (S) and multithreaded (l), the signature of threads that are all blocked. For native code the same information comes from the backtraces: threads parked in pthread_mutex_lock or a futex wait, and the owning thread of each mutex (not run here).

5. Priority inversion check. Is a high-priority thread blocked while a lower-priority thread holds the lock and is runnable but not running? Under real-time priorities that is the signature. The fix is a mutex with a priority-inheritance protocol: POSIX PTHREAD_PRIO_INHERIT means "when the calling thread is blocked because the mutex is owned by another thread, that owner thread shall inherit the priority level of the calling thread as long as it continues to own the mutex".
6. Livelock check. Compare two dumps: identical retry loops, rising CPU and flat progress counters. The usual cause is symmetric retry with no randomness (both back off by the same amount).
7. A long-running holder. If one thread holds the lock and is calling a remote service or waiting on a disk, it is not a deadlock: look at that holder's stack, not at the waiters.

Recover

A deadlock among JVM monitors cannot be broken without a restart: you cannot safely kill one thread. Order of actions: drain the instance, save the dumps and (for native code) a core file, restart, and shift traffic back. Two mitigations that need no restart for a service that cannot be stopped: drain traffic away from the stuck instance so the fleet keeps serving, and switch off with a feature flag (or route around) the single code path that takes both locks until the fix is deployed. Lock timeouts help only if they already exist in the code: ReentrantLock.tryLock(timeout) in Java, pthread_mutex_timedlock in POSIX.

For processes that deadlock across file locks (a second tool for a different failure; the thread dump and lock order above are the main path): POSIX fcntl locks taken with F_SETLKW are checked by the kernel and one process gets EDEADLK. In this program two processes lock two files in opposite order (compiled with gcc 14.4.0 and run in a Linux container):

#define _GNU_SOURCE
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>

static int lock_wait(int fd) {
    struct flock fl = { .l_type = F_WRLCK, .l_whence = SEEK_SET, .l_start = 0, .l_len = 1 };
    return fcntl(fd, F_SETLKW, &fl);                 // blocks until granted, or fails with EDEADLK
}
static void worker(const char* name, const char* first, const char* second) {
    int f1 = open(first, O_RDWR | O_CREAT, 0600), f2 = open(second, O_RDWR | O_CREAT, 0600);
    lock_wait(f1);
    usleep(300000);
    if (lock_wait(f2) == -1) printf("%s: second lock failed: %s\n", name, strerror(errno));
    else printf("%s: got both locks\n", name);
    fflush(stdout);
}
int main(void) {
    pid_t p1 = fork();
    if (p1 == 0) { worker("proc-1", "lockA", "lockB"); return 0; }
    pid_t p2 = fork();
    if (p2 == 0) { worker("proc-2", "lockB", "lockA"); return 0; }
    waitpid(p1, 0, 0); waitpid(p2, 0, 0);
    return 0;
}

In the program, F_WRLCK asks for an exclusive write lock, l_whence, l_start and l_len say "one byte at the start of the file", and F_SETLKW means set the lock and Wait if it is held. It printed:

proc-2: second lock failed: Resource deadlock avoided
proc-1: got both locks

Which process loses varies from run to run (either proc-1 or proc-2 can be the one refused, so the two lines above can appear with the names swapped): the one whose second request would close the wait cycle is refused, and the other then gets both locks. EDEADLK is the error number the kernel returns when granting the lock would complete a wait cycle. The man page for F_SETLKW says the error means "It was detected that the specified F_SETLKW operation would cause a deadlock" and that the kernel limits its dependency search to 10 steps, so longer cycles are not detected. To inspect held locks on a live system, /proc/locks and lslocks list them (not run here).

Prevent a repeat

1. One global lock order. Always lock the lower account id first. The fixed program ran two threads doing 1,000,000 opposite-direction transfers each, with a 30-second timeout on each result, so a deadlock would have shown as a failure:

import java.util.concurrent.*;

public class Ordered {
    record Account(int id, Object lock) { Account(int id) { this(id, new Object()); } }

    static void move(Account from, Account to) {
        Account first = from.id() < to.id() ? from : to;     // one global order: lowest account id first
        Account second = first == from ? to : from;
        synchronized (first.lock()) {
            synchronized (second.lock()) { /* debit from, credit to */ }
        }
    }

    public static void main(String[] args) throws Exception {
        Account a = new Account(1), b = new Account(2);
        ExecutorService pool = Executors.newFixedThreadPool(2);
        Future<?> f1 = pool.submit(() -> { for (int i = 0; i < 1_000_000; i++) move(a, b); });
        Future<?> f2 = pool.submit(() -> { for (int i = 0; i < 1_000_000; i++) move(b, a); });
        f1.get(30, TimeUnit.SECONDS);                         // a deadlock would surface as a TimeoutException
        f2.get(30, TimeUnit.SECONDS);
        pool.shutdown();
        System.out.println("2 x 1,000,000 opposite-direction transfers finished, no deadlock");
    }
}

javac Ordered.java && java Ordered printed: 2 x 1,000,000 opposite-direction transfers finished, no deadlock.

2. Detect order violations without waiting for a hang. ThreadSanitizer (a tool that reports data races and lock misuse at run time) finds lock-order inversions even in a run that did not deadlock. This program takes the two locks in opposite orders one after the other, so nothing can hang:

#include <mutex>
#include <thread>
std::mutex account_a, account_b;
void a_then_b() { std::lock_guard<std::mutex> x(account_a); std::lock_guard<std::mutex> y(account_b); }
void b_then_a() { std::lock_guard<std::mutex> x(account_b); std::lock_guard<std::mutex> y(account_a); }
int main() {
    a_then_b();                       // run the two paths one after the other: no deadlock can happen in this run
    std::thread t(b_then_a);
    t.join();
}

g++ -std=c++20 -O1 -g -fsanitize=thread lockorder.cpp -o lo && ./lo printed WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock) with Cycle in lock order graph: M0 => M1 => M0 and the two stacks that took the locks in opposite order. Run the test suite under TSan in continuous integration (CI). Where TSan is not available, record the order locks are acquired in a debug build and fail on a violation.
3. Never hold a lock across a call to unknown code (callbacks, remote calls); that is how long, unexplained cycles appear.
4. Timeouts with backoff on try-lock where a lock order cannot be imposed; add randomness so symmetric retries do not livelock.
5. Alert on a stuck-thread watchdog (no progress counter movement for N seconds) so the next hang is a page with dumps attached, not a customer report.

Verify the fix

Reproduce the original hang with the old code in a test (as in the first program), confirm the new code survives the same harness with a timeout, and keep the TSan job in CI.

Direct answer

Do not start by changing code. First preserve evidence from the failing production process, then narrow the bug class with the cheapest checks, then reproduce it by recreating the production concurrency in a test environment with a race detector on, and use record and replay to make one captured failure repeatable. Only then fix it, and prove the fix with the same harness that failed before. A concurrency bug is one where the result depends on the exact interleaving (the order in which the threads' steps happen), and under heavy load the number of threads, cache pressure and lock contention make the bad interleaving frequent enough to see.

Step 1: capture evidence before restarting anything

Reach first for the dump tool of your language: jstack for Java, the pprof goroutine endpoint for Go, py-spy for Python, gdb for C and C++. rr and the sanitizers come later, at reproduction.

• Take a thread dump (jstack for Java, the /debug/pprof/goroutine?debug=2 endpoint for Go (net/http/pprof), gdb -p PID -batch -ex "thread apply all bt" for C and C++, py-spy dump for Python) at the moment of failure, and again a few seconds later. If every thread is parked in the same lock wait both times: deadlock. If one thread is busy at 100% CPU in a loop: livelock or a spin.
• Save the log lines and metrics around the failure with a correlation id (one id attached to every log line of a request), and note the load level, instance, and deploy version. Check whether the bug tracks the load (concurrency) or the deploy (a code change).
• Enable a core dump (a file with the process memory and every thread's stack at the moment of a crash, which you can open in a debugger afterwards) on the next failure.

Step 2: reason in a fixed order before touching code

For a log collector that drops or duplicates events, check in this order, cheapest first:

1. Data races: two threads access the same memory, at least one writes, with no synchronization between them. An unsynchronized batch = append(batch, e) is one: two threads read the same length and one overwrites the other's element.
2. Atomicity violations: every access is locked, but a check and the action that depends on it are in different critical sections (check "is it flushed?", unlock, then flush). A race detector will not report these.
3. Ordering: a flag is set before the data it announces is visible to another core (needs acquire/release or a lock). Release on the writer and acquire on the reader are the atomic-operation modes that make everything written before the flag visible to a reader that sees the flag; a memory barrier is a point the compiler and CPU may not move memory operations across.
4. Contention: no wrong answer, but timeouts under load cause retries, and retried requests look like duplicates. Check lock wait times and queue depth.

Step 3: instrumentation that is safe in production

• Low-overhead always-on measures: a ring buffer of the last N events per thread, counters for lock wait time, per-request correlation ids, and a watchdog that takes a thread dump when a request exceeds its deadline.
• Avoid adding log lines inside the suspected critical section: they change timing and often hide the bug (a printed line usually takes a lock, which also acts as a memory barrier).

Step 4: reproduce

• Stress: replay recorded production traffic or run a load generator at the production thread count and a bit beyond, with more threads than cores. Vary the number of cores (taskset, container CPU limits), which shifts the interleavings.
• Race detectors: build with ThreadSanitizer (TSan, for C, C++ and others) or Go's -race. Both are dynamic: they observe the run and report conflicting accesses that lack a happens-before relationship (a guaranteed ordering between two operations). They only see code paths that actually execute, so the workload must be realistic. Documented overhead: TSan typically slows the program 5x to 15x and uses 5x to 10x memory; Go's race detector is documented at 2x to 20x time and 5x to 10x memory. In practice a test that takes 10 minutes normally takes 50 to 150 minutes under TSan, so you run the detector in tests, in a staging environment, or on a small slice of replayed traffic, not on the whole production fleet.
• Deterministic replay: rr (a Linux record-and-replay debugger for C and C++) records a failing run including thread scheduling, then replays it byte for byte as many times as needed, with reverse execution; its "chaos mode" randomizes scheduling decisions during recording to make intermittent failures more likely to appear. It runs the program as if on a single core, so parallel programs lose their parallelism while recording.

Step 5: worked example, a collector that loses events

package main

import (
	"fmt"
	"sync"
)

type collector struct {
	mu    sync.Mutex
	batch []int
}

func (c *collector) addRacy(e int) { c.batch = append(c.batch, e) } // unsynchronized read-modify-write of the slice header
func (c *collector) addSafe(e int) { c.mu.Lock(); c.batch = append(c.batch, e); c.mu.Unlock() }

func run(add func(*collector, int)) int {
	c := &collector{}
	var wg sync.WaitGroup
	for g := 0; g < 4; g++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for i := 0; i < 10000; i++ {
				add(c, i)
			}
		}()
	}
	wg.Wait()
	return len(c.batch)
}

func main() {
	racy := run((*collector).addRacy)
	safe := run((*collector).addSafe)
	fmt.Println("expected 40000 events")
	fmt.Println("racy collector kept all of them:", racy == 40000)
	fmt.Println("locked collector kept all of them:", safe == 40000)
}

Run with go run collector.go, then go run -race collector.go in a Linux container (Go 1.23):

expected 40000 events
racy collector kept all of them: false
locked collector kept all of them: true

With -race, the run also prints several WARNING: DATA RACE reports pointing at the append line. Four goroutines (Go's lightweight threads) each add 10,000 events. The unlocked version usually loses some, but not every run: on a multicore host it printed false in most plain runs and true in some, and with GOMAXPROCS=1 (one thread at a time) it printed true in every re-run tried, which does not prove it cannot fail, so a single clean run proves nothing, which is the same point as the pitfall below. The count varies per run, so the program prints only whether all 40,000 survived; the mutex version never loses any. The race report names the exact two source lines, which is what turns "rare data loss under load" into a one-line fix.

Step 6: fix and prove it

Make the smallest fix that removes the race (a lock or a channel, not a sleep), then rerun the same stress harness many times with the race detector on, and add an invariant check as a permanent test (events in equals events out). Keep a watchdog alert on the symptom for a few weeks, and run a soak test (a long run under steady load, hours or days) plus a canary (a new build serving a small slice of real traffic before full rollout) before declaring it fixed.

Pitfalls

Adding a sleep or retry that hides the failure; "fixing" it by increasing a timeout; turning on -race in a canary and treating a clean run as proof (it only proves those paths did not race in that run).

Direct answer

Two threads deadlock when each takes one lock and then asks for the lock the other already holds. The fix is to make every thread take the locks in the same order (or let std::scoped_lock take both without deadlock), or to use try_lock with a randomized back-off. To find it in a live system, take a thread dump (a snapshot listing every thread and the call stack it is currently stuck in) and look for two threads each blocked on a lock the other holds; to reproduce it, widen the timing window and run lock-order checking (ThreadSanitizer or the kernel's lockdep) in test builds.

The deadlock, in code

Each worker takes its first lock, sleeps 100 ms so the other thread can take its first lock, then asks for the second one. The sleep is only there to make the unlucky timing certain; in production the same interleaving happens rarely and under load, which is why these bugs are intermittent.

#include <chrono>
#include <cstdio>
#include <cstring>
#include <mutex>
#include <random>
#include <thread>

using namespace std::chrono_literals;

std::mutex lock_a, lock_b;

// Each worker takes its first lock, pauses so the other thread can take its own
// first lock, then asks for the second one.
void worker_opposite(std::mutex& first, std::mutex& second, const char* name) {
    std::lock_guard<std::mutex> g1(first);
    std::printf("%s holds its first lock\n", name);
    std::this_thread::sleep_for(100ms);
    std::lock_guard<std::mutex> g2(second);   // never returns in "bad" mode
    std::printf("%s got both\n", name);
}

// Fix 1: take both locks through std::scoped_lock, which avoids deadlock whatever order the arguments are listed in.
void worker_scoped(const char* name) {
    std::scoped_lock both(lock_a, lock_b);
    std::printf("%s got both\n", name);
}

// Fix 2: try-lock with randomized backoff. Releases what it holds on failure.
void worker_trylock(std::mutex& first, std::mutex& second, const char* name, unsigned seed) {
    std::mt19937 rng(seed);
    for (;;) {
        std::unique_lock<std::mutex> g1(first);
        std::this_thread::sleep_for(100ms);
        if (second.try_lock()) {
            std::lock_guard<std::mutex> g2(second, std::adopt_lock);
            std::printf("%s got both\n", name);
            return;
        }
        g1.unlock();                                   // give up the first lock
        std::this_thread::sleep_for(std::chrono::milliseconds(1 + rng() % 50));
    }
}

int main(int argc, char** argv) {
    std::setvbuf(stdout, nullptr, _IOLBF, 0);   // flush each line even when piped
    const char* mode = argc > 1 ? argv[1] : "bad";
    std::thread t1, t2;
    if (!std::strcmp(mode, "bad")) {
        t1 = std::thread(worker_opposite, std::ref(lock_a), std::ref(lock_b), "T1");
        t2 = std::thread(worker_opposite, std::ref(lock_b), std::ref(lock_a), "T2");
    } else if (!std::strcmp(mode, "sequential")) {
        // Opposite orders, but one after the other: cannot hang, yet a lock-order
        // checker still sees both orders and flags the potential deadlock.
        std::thread(worker_opposite, std::ref(lock_a), std::ref(lock_b), "T1").join();
        std::thread(worker_opposite, std::ref(lock_b), std::ref(lock_a), "T2").join();
        std::puts("finished");
        return 0;
    } else if (!std::strcmp(mode, "scoped")) {
        t1 = std::thread(worker_scoped, "T1");
        t2 = std::thread(worker_scoped, "T2");
    } else {
        t1 = std::thread(worker_trylock, std::ref(lock_a), std::ref(lock_b), "T1", 1u);
        t2 = std::thread(worker_trylock, std::ref(lock_b), std::ref(lock_a), "T2", 2u);
    }
    t1.join();
    t2.join();
    std::puts("finished");
}

Reading guide for the trylock worker: std::unique_lock is a lock holder that, unlike lock_guard, can be released early with unlock(); second.try_lock() attempts to take the second lock and returns false at once instead of waiting; std::lock_guard<std::mutex> g2(second, std::adopt_lock) takes over a lock that is already held so it is released automatically at the end of the scope; std::mt19937 rng(seed) is a random-number generator, given a different seed per thread so the two threads pick different delays; and std::ref passes a mutex by reference to std::thread, which would otherwise try to copy it.

Built and run in a Linux container with GCC 14 (g++ -std=c++20 -O2 -Wall -Wextra -pthread deadlock.cpp -o dl), each mode under timeout 5:

$ timeout 5 ./dl bad ; echo exit=$?
T1 holds its first lock
T2 holds its first lock
exit=124
$ timeout 5 ./dl scoped
T1 got both
T2 got both
finished
$ timeout 5 ./dl trylock
T2 got both
T1 got both
finished

In bad mode neither "got both" line ever appears, and exit code 124 is timeout killing a process that did not finish: that is the deadlock. Two lines of output followed by silence, with zero CPU use, is the classic signature (a livelock, by contrast, burns CPU while making no progress). In scoped and trylock modes the order of the two "got both" lines can differ between runs; the point is that both always appear and the program finishes.

Fixes

1. One global lock order. If every code path that needs both locks takes lock_a then lock_b, the cycle cannot form. std::scoped_lock both(lock_a, lock_b) is the library way to take both without deadlock: the C++ reference says that with several mutexes it uses a deadlock-avoidance algorithm as if by std::lock. It does not impose a rank on your locks (a common implementation tries one lock, try-locks the rest and backs off), so it protects only the code that takes all the locks through it together; a path that locks them one at a time in the opposite order can still deadlock, which is why a written global order stays the rule that covers every path. For locks chosen at run time, order by a stable key (an id or, within one process, the address).
2. try_lock with randomized back-off (trylock mode above). Take the first lock, try_lock the second, and if that fails release the first, sleep a random few milliseconds and start again. Livelock risk: if both threads back off for the same fixed time they can collide again forever, each repeatedly taking its first lock and failing on the second. The random delay (different seed per thread) breaks the symmetry. It does not guarantee progress in every execution, only that repeated collision becomes unlikely. Prefer fix 1 when you can order the locks.

Detecting it in a live system (in order)

1. Confirm the symptom. Some requests hang, the process is alive, and CPU use for those threads is near zero. High CPU with no progress points to livelock instead.
2. Capture all thread stacks. For a native process, attach gdb and run thread apply all bt (bt is short for backtrace, the list of function calls that led to where a thread is stopped; the GDB manual: thread apply all command runs the command on every thread). A deadlock shows as two or more threads parked inside pthread_mutex_lock, where each one's lock is the one the other holds. In a Java service, ThreadMXBean.findDeadlockedThreads() returns the IDs of platform threads in a cycle over monitors (Java's built-in synchronized locks) and ownable synchronizers (lock objects such as ReentrantLock) (its Javadoc warns it can be expensive, so call it from a diagnostic endpoint, not in a hot loop; it does not report cycles that include virtual threads, which are lightweight threads scheduled by the JVM rather than one-to-one by the operating system). A core file is a saved snapshot of a process's memory taken when it is killed or crashes, which gdb can open afterwards to run the same thread apply all bt.
3. Name the two locks and the two code paths, then check which one violates the order your design says it should follow.
4. Instrument for next time. Log lock acquisition with the holder when a try_lock_for (timed lock) times out, so a stuck wait becomes a log line with both thread names instead of a silent hang.

Reproducing it under load

• Widen the window. Add a short sleep or yield between acquiring the first and second lock in a test build (exactly what the sleep_for(100ms) above does), then run many threads against the same locks.
• Run a lock-order checker so the deadlock need not happen. ThreadSanitizer (TSan) builds a graph of which lock was taken while holding which, and reports a cycle as lock-order-inversion (potential deadlock). In the sequential mode, T1 finishes before T2 starts, so no hang is possible, yet it still reports (the full report also prints stack frames, trimmed here):

$ g++ -std=c++20 -O1 -g -fsanitize=thread -pthread deadlock.cpp -o dlt && ./dlt sequential
T1 holds its first lock
T1 got both
T2 holds its first lock
==================
WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock) (pid=14)
  Cycle in lock order graph: M0 (0x000000420150) => M1 (0x000000420120) => M0

  Mutex M1 acquired here while holding mutex M0 in thread T1:
    ...  worker_opposite(std::mutex&, std::mutex&, char const*) /w/deadlock.cpp:18
  Mutex M0 acquired here while holding mutex M1 in thread T2:
    ...  worker_opposite(std::mutex&, std::mutex&, char const*) /w/deadlock.cpp:18
SUMMARY: ThreadSanitizer: lock-order-inversion (potential deadlock) ...
T2 got both
finished

Reading the report: M0 and M1 are TSan's names for the two mutexes (here lock_a and lock_b, shown with their addresses); Cycle in lock order graph: M0 => M1 => M0 says some thread took M1 while holding M0 and another took M0 while holding M1, which is the circular wait; each Mutex Mx acquired here while holding mutex My in thread Tn block gives the thread and the source line of one half of the cycle.

Run on the same TSan build, ./dlt bad prints no report: TSan checks when the second lock is acquired, and in bad mode that acquisition never completes. Test with the non-overlapping sequential mode, or on code paths that sometimes run alone, and do not expect the report from a build that already hangs. The Clang documentation gives a typical slowdown of 5x-15x and memory overhead of 5x-10x, so this belongs in test and staging builds, not production.

• In kernel code the lockdep validator (the Linux kernel's built-in lock-order checker) tracks lock classes and proves from lock sequences that occurred at least once that no timing of them can deadlock, so a bad ordering is reported without the hang ever happening.

Pitfalls

• Fixing only the two code paths you found: add the rule (a comment next to the lock declarations, plus a test) so a third path does not reintroduce the inversion.
• Back-off without randomness, or without releasing the first lock, which turns a deadlock into a livelock or does nothing at all.
• Holding a lock while calling a callback, which hides the second acquisition from anyone reading the call site.

Direct answer

Run a dynamic race detector (for example ThreadSanitizer for C and C++, or Go's -race) on your tests every merge and on a realistic, replayed workload in a staging or canary environment, never on all of production, because it slows the program and only reports races that the run actually executes. Pair it with static analysis on every pull request, which is cheap, sees all code paths, and catches lock-discipline mistakes, but gives false alarms and cannot see runtime behaviour. The balance: static analysis for breadth and speed, the dynamic detector for precision on the paths your workload exercises, and a small amount of production-like traffic to extend the coverage. A dynamic detector watches a running program; a static one reads source code without running it.

How a dynamic detector works

A data race is two threads accessing the same memory, at least one writing, with no ordering guaranteed between them (no happens-before relationship, meaning no lock, atomic or channel operation that orders one access before the other). ThreadSanitizer (TSan) instruments every memory access at compile time and tracks synchronization events at run time; Go's -race does the same for goroutines (Go's lightweight threads) and channels. When it sees two conflicting accesses with no happens-before edge, it prints both stacks.

Overhead (documented figures)

• TSan: documented typical slowdown 5x to 15x and typical memory overhead 5x to 10x.
• Go -race: documented as 2x to 20x execution time and 5x to 10x memory for a typical program.

What this means for a fleet (arithmetic, assuming 20 instances each 30% busy, and that you keep the race-build instance at or under 60% CPU as headroom so latency stays tolerable; both numbers are illustrative assumptions, not measurements). In the table, "CPU needed at normal share" is the CPU the race-built instance would burn if it served its ordinary one-twentieth of the traffic: today's 30% busy times the slowdown:

False positives and false negatives

• False negatives (misses): the Go documentation states that the detector "only finds races that happen at runtime, so it can't find races in code paths that are not executed", and suggests running a -race build under a realistic workload. A clean run proves only that this workload did not race.
• False positives: the detector judges ordering only from the synchronization it models. If your code orders two accesses with something it does not model, it sees two conflicting accesses with no ordering and reports a race that is not real. Example, compiled and run with GCC 14 and -fsanitize=thread, where the C++ fences correctly order the plain payload write before its read. A standalone fence is a barrier not attached to any one variable: a release fence orders all of the thread's earlier writes before a later store, an acquire fence orders an earlier load before all later reads, and a release fence before a relaxed store pairs with a relaxed load followed by an acquire fence, which is what the two fences below do:

#include <atomic>
#include <cstdio>
#include <thread>

int payload = 0;                       // plain data, handed from producer to consumer
std::atomic<bool> ready{false};

int main() {
    std::thread producer([] {
        payload = 42;
        std::atomic_thread_fence(std::memory_order_release);
        ready.store(true, std::memory_order_relaxed);
    });
    std::thread consumer([] {
        while (!ready.load(std::memory_order_relaxed)) {}
        std::atomic_thread_fence(std::memory_order_acquire);
        std::printf("payload = %d\n", payload);   // correct under the C++ memory model: fences pair up
    });
    producer.join(); consumer.join();
}

g++ -std=c++20 -O1 -g -fsanitize=thread -pthread fence.cpp -o fence && ./fence printed:

warning: 'atomic_thread_fence' is not supported with '-fsanitize=thread' [-Wtsan]
WARNING: ThreadSanitizer: data race
payload = 42

The program is correct under the C++ memory model (a release fence before the store and an acquire fence after the load that observes it), yet TSan reports a race because it does not model standalone fences, and GCC says so at compile time. Triage rule: a report is a bug until you can name the synchronization the tool missed. Handle genuine false positives with a suppression file entry that names the owner and a review date, not a blanket disable.

Where static analysis fits (short comparison)

Start with the tool for your language: Clang thread-safety annotations for C++, go vet for Go, Error Prone for Java. They are the same idea (declare which lock guards which data and let the compiler check it) in three ecosystems.

• C and C++: Clang's thread-safety analysis (-Wthread-safety with GUARDED_BY and REQUIRES annotations) runs at compile time with no runtime overhead. Documented limits: it works one function at a time (no inlining), cannot follow aliases to the same mutex, cannot handle a lock held on only some paths, and does not check constructors and destructors.
• Go: go vet includes a copylocks check for locks passed by value; the race detector covers the rest dynamically.
• Java: Error Prone's (a Java compiler plugin for bug patterns) GuardedBy check verifies that fields annotated @GuardedBy(lock) are accessed only with that lock held.
• Common limits: annotation burden, false alarms where the tool cannot see the real locking rule, and no knowledge of how threads actually interleave. CI integration: run static checks on every pull request (seconds to minutes, fails the build), treat them as errors for annotated modules, and add a baseline file so existing warnings do not block new work.

Putting cost and coverage together

1. Every pull request: static analysis plus unit tests built with the detector (a test suite is small, so a 5x to 20x slowdown is affordable).
2. Nightly: stress and soak tests with the detector at higher thread counts and longer runs.
3. Weekly or per release: replayed production-shaped traffic in staging with the race build; a fixed small fraction on a canary if the memory and CPU budget allow.
4. Track every report to closure; a detector whose output is ignored costs the 5x to 20x and returns nothing.

Pitfalls

Running it on a trivial test workload and declaring the code race-free; turning it on in the whole production fleet; silencing noisy reports wholesale instead of triaging each; comparing static findings and dynamic findings as if they covered the same bugs (the static tool can flag a path never executed, the dynamic tool can find a race through a function pointer the static tool cannot resolve).