Concurrency and Race Condition
Concurrency and Race Condition
Definition: Concurrency is the execution of multiple instruction sequences simultaneously or interleaved; a race condition occurs when program output depends on the non-deterministic timing of concurrent threads accessing shared state.
How It Works
- A race condition needs shared mutable data accessed by two or more threads, with at least one access being a write. A strict “data race” requires both unsynchronized access and at least one writer; two threads only reading shared data concurrently is safe.
- Interleaving can produce lost updates (two writes overlap and one is silently discarded), stale reads (a thread reads data mid-update, seeing a partially consistent value), or structural corruption (concurrent modification of a non-thread-safe collection while another thread iterates it).
- The classic example,
counter++, isn’t atomic. It compiles to at least three machine steps: load the value into a register, increment the register, store it back. Two threads interleaving those steps can both load the same starting value before either stores its result. - Prevented with synchronization primitives (Mutex and Semaphore), atomic variables (CPU-level compare-and-swap or fetch-and-add instructions that make a read-modify-write a single indivisible step), or higher-level constructs like monitors, condition variables, and channels.
- Concurrency is distinct from parallelism: concurrency is a program structure that can handle multiple tasks, possibly interleaved on one core; parallelism is literally executing multiple tasks at the same instant on multiple cores. A single-core system can be concurrent without ever being parallel.
Under the Hood
Whether an interleaving is even possible traces back to the memory model of the language and hardware. Modern CPUs and compilers reorder instructions and cache writes in per-core buffers for performance, so without an explicit memory barrier, a write one thread performs may not be visible to another thread in program order at all, not just possibly delayed. A mutex lock/unlock, or an atomic operation with the right memory ordering (e.g., std::memory_order_seq_cst in C++, volatile/AtomicInteger in Java), inserts the fence that forces visibility and ordering guarantees other threads can rely on.
Hardware-level atomicity comes from instructions like LOCK CMPXCHG on x86 or LDXR/STXR (load-exclusive/store-exclusive) on ARM. These let the CPU guarantee a read-modify-write completes as a single step relative to other cores, by asserting a cache-line lock or exclusive monitor for the duration. Every higher-level synchronization primitive, mutexes, semaphores, atomics, is ultimately built from one of these hardware primitives plus a way to park/wake blocked threads (a futex on Linux).
A data race is technically undefined behavior in languages like C, C++, and Rust’s unsafe code: the compiler is permitted to assume no data races exist and optimize accordingly, which means a racy program’s behavior isn’t just “unpredictable timing,” it can be arbitrarily wrong, including code that appears to vanish or duplicate under optimization.
Race detectors like ThreadSanitizer work by tracking a “happens-before” relation rather than just watching raw memory addresses. Every synchronization operation, a mutex unlock, a channel send, establishes a happens-before edge to the corresponding lock/receive on another thread. TSan instruments every memory access and every synchronization event at compile time, then at runtime checks whether two conflicting accesses (at least one a write) to the same location are connected by a happens-before edge. If they aren’t, in other words, nothing guarantees one happened before the other, it’s flagged as a race, even if that particular run happened not to actually corrupt anything.
Debugging Workflow
Race conditions rarely announce themselves cleanly, they show up as “this fails maybe 1 in 500 CI runs” or as data that’s occasionally just wrong. The practical approach is to reproduce under an instrumented build rather than stare at the racy code and reason it out by hand:
$ gcc -fsanitize=thread -g -o app app.c && ./app
==================
WARNING: ThreadSanitizer: data race (pid=48213)
Write of size 4 at 0x7b0400000000 by thread T2:
#0 increment_counter app.c:14
Previous read of size 4 at 0x7b0400000000 by thread T1:
#0 increment_counter app.c:14
==================TSan points at the exact line and both threads involved, including a stack trace for each side of the race, which is usually enough to spot the missing lock. When a compiled-in sanitizer isn’t an option (production, an interpreted language), the fallback is narrowing by inspection: add logging around every access to the suspect shared variable, force the interleaving with an artificial sleep() at the suspected window to make the race reproduce reliably, then confirm the fix removes it by running the stress test hundreds of times rather than once, since a single clean run proves very little for a timing-dependent bug.
Why It Matters
- A foundational reliability and security issue in multi-threaded software. Many high-severity CVEs (use-after-free, double-free, TOCTOU bugs) trace back to unsynchronized concurrent access.
- Race conditions are notoriously hard to debug because they’re timing-dependent. A bug that reproduces reliably under a debugger (which changes timing) may vanish there and only appear in production under real load, sometimes after thousands of clean test runs.
- Understanding races is a prerequisite for understanding Deadlock, livelock, and starvation, the broader family of concurrency correctness failures that show up once naive locking gets introduced to fix races.
Common Pitfalls
- Assuming a specific thread execution order or instruction atomicity without explicit synchronization. “It works on my machine” often just means the race window is too small to trigger under light load.
- Check-then-act (TOCTOU, Time-Of-Check to Time-Of-Use) bugs: checking a condition and acting on it as two separate, unsynchronized steps, letting another thread act in between. Classic example: checking a file doesn’t exist, then creating it.
- Locking a write path but forgetting to guard the corresponding read path, leaving half the access pattern unsynchronized and just as racy as no locking at all.
- Reaching for one coarse-grained global lock to “fix” a race, which serializes unrelated work and eliminates the throughput benefit concurrency was meant to provide.
- Double-checked locking done wrong: checking a flag outside a lock, then again inside, without the flag being atomic or volatile, which the compiler/CPU can reorder in ways that break the intended safety.
Detection Tools Quick Reference
| Tool | Approach | Catches |
|---|---|---|
| ThreadSanitizer (TSan) | Runtime instrumentation, happens-before tracking | Actual data races observed during a run |
| Helgrind (Valgrind) | Runtime instrumentation, lock-order analysis | Data races and lock-order inversions |
| Go race detector | Same TSan-derived technique, built into go test -race | Data races in Go goroutines |
| Static analyzers (Coverity, clang analyzer) | Code analysis without running it | Some races via pattern matching, no runtime coverage needed |
History
- The term “race condition” predates software: it originates in digital logic design, where two signals racing to a gate could produce a glitch depending on which arrived first.
- Early multi-threaded software mostly ran on single-core machines, where races still occurred (via preemptive context switches) but were rarer and often masked by coarse OS-level scheduling granularity.
- Multi-core CPUs becoming the default in consumer hardware during the mid-2000s made race conditions dramatically more common and more severe in practice, since genuinely simultaneous execution replaced merely interleaved execution, motivating the modern generation of race detectors like ThreadSanitizer (introduced publicly around 2011).
FAQ
Is a race condition always a bug? Not automatically by definition, but in practice, yes. A small number of “benign” races exist (e.g., two threads writing the same value to a flag), but relying on this is fragile and compilers/hardware make no promise to preserve that behavior, so it’s treated as a bug in virtually all real code.
Can a race condition happen with only one CPU core? Yes. Preemptive context switches between threads on a single core create the same interleaving opportunities as true parallel execution on multiple cores; the OS can suspend a thread mid-operation regardless of core count.
Does using a high-level language like Python or JavaScript make races impossible? No, though a Global Interpreter Lock (Python’s GIL) or a single-threaded event loop (JavaScript) narrows the window significantly for pure in-language operations. Races still occur across async callbacks, multiple processes, or when native extensions release the GIL.
Comparison
| Race Condition | Deadlock | Livelock | |
|---|---|---|---|
| Threads make progress | Yes, but result is wrong/nondeterministic | No, all blocked forever | Yes, but no useful work happens |
| Root cause | Missing/incorrect synchronization | Circular resource wait | Threads repeatedly yielding/retrying to each other |
| Detectable statically | Sometimes (race detectors) | Yes, via wait-for graph cycle | Hard, no fixed blocking state to find |
| Typical fix | Add correct locking/atomics | Break one Coffman condition | Add randomized backoff or a tie-breaker |
| Reproducibility | Timing-dependent, often intermittent | Often deterministic once triggered | Timing-dependent, intermittent |
| CPU usage while stuck | Normal (threads still run) | Zero (threads fully blocked) | High (threads busy retrying) |
Real-World Example
A common production pattern: a web server caches a computed value (“lazy initialization”) the first time it’s requested, checking if (cache == null) { cache = computeExpensiveValue(); }. Under concurrent requests, two threads can both see a null cache, both compute the value, and one write overwrites the other, wasted work at best, and if computeExpensiveValue() has side effects (writing a file, incrementing a counter), a correctness bug at worst. The standard fix is either a mutex around the whole check-and-set, or an atomic compare-and-swap that only lets the first successful writer’s result stick.
Example
Two threads concurrently performing counter++ without locking can lose one increment:
Initial counter = 0
Thread A: load counter (0) -> increment to 1 -> [context switch before store]
Thread B: load counter (0) -> increment to 1 -> store 1
Thread A: store 1
Final counter = 1 (expected 2 after two increments — one update was lost)Wrapping the increment in a mutex, or using an atomic fetch_add, forces the load-increment-store sequence to complete as one indivisible unit per thread. Tools like ThreadSanitizer (-fsanitize=thread in Clang/GCC) instrument memory accesses at compile time and flag exactly this kind of unsynchronized concurrent access at runtime, without needing the race to actually corrupt data to be caught.
Related Terms
Referenced by