Concurrency Bugs
Advanced Concurrency · VR Foundations track
7 min read
In this module
A Taxonomy of Concurrency Bugs
Concurrency bugs are among the hardest defects to find, reproduce, and fix. They depend on timing, thread scheduling, and the specific hardware underneath. A program can pass millions of test runs and still harbour a bug that fires exactly once in production, under conditions you'll struggle to reconstruct. Knowing the categories doesn't prevent them — but it makes you faster at recognising what you're looking at.
Data Races vs Race Conditions
These terms are often confused, but they have distinct meanings. A data race is a precisely defined condition: two or more threads access the same memory location concurrently, at least one access is a write, and there is no synchronisation (such as a lock or atomic operation) ordering the accesses. In C and C++, a data race is undefined behaviour - the compiler is allowed to assume it never happens, which means it can optimise in ways that make the bug even worse.
A race condition is broader: any situation where the correctness of a program depends on the relative timing of events. You can have race conditions without data races. The classic TOCTOU (Time of Check, Time of Use) bug is a race condition that operates on files through system calls - all accesses are individually atomic, so there is no data race, but the file can change between the check and the use.
// TOCTOU race - no data race, but still a race conditionif (access("/tmp/file", W_OK) == 0) { // check // attacker replaces /tmp/file with symlink here fd = open("/tmp/file", O_WRONLY); // use write(fd, data, len); // writes to wrong file!}Deadlocks
A deadlock occurs when two or more threads are each waiting for a resource held by another, forming a circular dependency that can never be resolved. The classic scenario involves two locks:
Thread 1: lock(A), lock(B) - holds A, waits for BThread 2: lock(B), lock(A) - holds B, waits for ABoth threads are permanently stuck. The four necessary conditions for deadlock (the Coffman conditions) are: mutual exclusion, hold and wait, no preemption, and circular wait. Breaking any one of these prevents deadlock. The most practical approach is to prevent circular wait by establishing a lock ordering - all threads must acquire locks in the same global order.
Step through it yourself. In the first stepper the two threads take the locks in opposite orders: give Thread 1 its lock A, then Thread 2 its lock B, and neither thread can move. The second runs the same work with both threads taking A before B. Ask it to enumerate every schedule and the deadlock count drops to zero.
Opposite lock orders
Pick which thread runs next and watch shared memory and registers change.
- 0lock(&A);
- 1lock(&B);
- 2fetch_add(&transfers, 1);
- 3unlock(&B);
- 4unlock(&A);
- 0lock(&B);
- 1lock(&A);
- 2fetch_add(&transfers, 1);
- 3unlock(&A);
- 4unlock(&B);
- transfers = 0
- A: free
- B: free
Every possible schedule
2 of 6 possible schedules end with an unexpected result.
| Final result | Schedules |
|---|---|
| transfers = 2 | 4 |
| deadlock | 2 |
Same lock order: A before B
Pick which thread runs next and watch shared memory and registers change.
- 0lock(&A);
- 1lock(&B);
- 2fetch_add(&transfers, 1);
- 3unlock(&B);
- 4unlock(&A);
- 0lock(&A);
- 1lock(&B);
- 2fetch_add(&transfers, 1);
- 3unlock(&B);
- 4unlock(&A);
- transfers = 0
- A: free
- B: free
Every possible schedule
0 of 2 possible schedules end with an unexpected result.
| Final result | Schedules |
|---|---|
| transfers = 2 | 2 |
Assign each lock a numeric rank. Every thread must acquire locks in increasing rank order. If Thread 1 needs locks A (rank 1) and B (rank 2), it always acquires A first. Thread 2 must also acquire A before B. This eliminates circular wait and prevents deadlock. The Linux kernel uses lockdep, a runtime tool that detects lock ordering violations dynamically.
Livelocks
A livelock is similar to a deadlock, but the threads are spinning, not blocked — actively executing, making zero progress. Two threads detect a conflict, back off, retry, and immediately conflict again, forever.
The hallway analogy: two people step aside in the same direction, step back, step aside again, indefinitely polite and completely stuck. Livelocks are insidious because monitoring shows the threads as active and consuming CPU — no stuck-thread alerts, no obvious signal, just wasted cycles.
Solutions include adding randomized backoff (each thread waits a random duration before retrying) or using asymmetric retry strategies.
Priority Inversion
Priority inversion occurs when a high-priority thread is indirectly blocked by a low-priority thread. Thread H (high priority) needs a lock held by Thread L (low priority). While L holds the lock, Thread M (medium priority) preempts L because M has higher priority than L. Now H is effectively blocked by M, which has lower priority than H - the priorities are inverted.
This bug nearly doomed the Mars Pathfinder mission in 1997. The solution deployed via a remote patch was priority inheritance: when Thread H blocks on a lock held by Thread L, L temporarily inherits H's priority, preventing M from preempting it. Once L releases the lock, its priority returns to normal.
On Pathfinder the three roles were real VxWorks tasks. A low-priority meteorological task held a mutex guarding the shared information bus; a long-running, medium-priority communications task kept preempting it; and the high-priority bus management task sat blocked on that mutex. A watchdog noticed the bus task had missed its deadline and reset the whole spacecraft, several times over. Engineers reproduced it on a ground replica, then uploaded a patch that flipped the mutex's priority-inheritance option on.
Thundering Herd
The thundering herd problem occurs when many threads (or processes) are waiting on the same event. When the event occurs, all of them wake up simultaneously, but only one can make progress (e.g., only one can acquire the lock or accept the connection). The rest immediately go back to sleep, having wasted CPU time and generated a burst of cache contention.
This pattern appears in web servers where many worker threads wait on accept() for new connections, or in applications where many threads wait on a condition variable. Solutions include adding the listening socket to each thread's epoll instance with EPOLLEXCLUSIVE (Linux 4.5 and later), so an event wakes one or a few waiters rather than all of them; giving each thread its own listening socket with SO_REUSEPORT (Linux 3.9 and later), so the kernel spreads connections across them; or a single acceptor thread, or a leader-follower pattern, where only one thread waits at a time and hands the work on.
Starvation and Fairness
Starvation occurs when a thread cannot make progress because other threads perpetually acquire the resources it needs. This is different from deadlock (where no thread makes progress) - in starvation, some threads make progress while others do not.
Unfair locks can cause starvation. A simple test-and-set spinlock lets the fastest responder win, and on a NUMA machine that tends to be a thread close to wherever the lock's cache line currently lives, so remote threads can lose again and again. Ticket locks and MCS locks provide FIFO fairness, ensuring that threads acquire the lock in the order they requested it.
Debugging Concurrency Bugs
Traditional debugging techniques struggle with concurrency bugs because the act of debugging changes timing. Adding print statements slows execution and may prevent the bug from manifesting. Single-stepping a thread in a debugger holds it in place while other threads continue, completely altering the interleaving.
Specialised tools include:
- ThreadSanitizer (TSan): instruments memory accesses at compile time and detects data races dynamically. It maintains a "happens-before" graph and flags accesses that are not ordered.
- Helgrind (Valgrind tool): detects lock ordering violations and data races by monitoring all synchronisation operations.
- rr (record-and-replay debugger): records the exact execution of a program, including all thread interleavings, and allows deterministic replay. This lets you reproduce a concurrency bug consistently and step through it.
The most effective strategy is designing for correctness from the start: minimise shared mutable state, use well-tested synchronisation primitives, and prefer message-passing architectures. Threads that communicate by exchanging immutable messages are dramatically easier to reason about than threads that share a heap.