# Race Conditions

## 1. Definition — A Property of Timing, Not of Code Reading Wrong

A **race condition** is a bug where the correctness of a result depends on the relative **timing or interleaving** of operations that access shared, mutable state — not on any operation individually being wrong. Every step in the buggy execution is individually correct; the bug only appears from a specific *ordering* of otherwise-correct steps happening across concurrent tasks.

This makes race conditions uniquely nasty: they are non-deterministic (the same code can run correctly a thousand times and fail on the thousand-and-first, depending on scheduling), they often disappear under a debugger (adding a breakpoint changes timing enough to hide the interleaving that triggers the bug), and they require genuine concurrent execution — a topic this stack now assumes from Concurrency vs Parallelism — over shared mutable state to exist at all.

## 2. The Classic Example: `counter++` Is Three Operations, Not One

`counter++` looks like a single atomic step in source code. It is not — it compiles to (at least) three distinct machine-level operations: **read** the current value, **modify** it (add 1), **write** the new value back. Any of those three steps can be interrupted by another thread doing the same three steps on the same memory location.

```
Thread A: local_A = counter        // read:  local_A = 0
Thread B:                          local_B = counter        // read:  local_B = 0  (BEFORE A writes back!)
Thread A: local_A = local_A + 1    // modify: local_A = 1
Thread A: counter = local_A        // write: counter = 1
Thread B:                          local_B = local_B + 1    // modify: local_B = 1  (using the STALE 0 it read)
Thread B:                          counter = local_B        // write: counter = 1  (clobbers A's update!)

Two increments happened. counter ends at 1, not 2. One update is LOST.
```

![Two threads interleave read-modify-write steps on a shared counter; Thread B reads the stale pre-A value, so its write clobbers Thread A's increment, losing one update](diagrams/01-lost-update-interleaving.svg)

This is called a **lost update**, and it is the canonical race condition: nothing crashed, no exception was thrown, every individual line executed exactly as written — the bug exists purely in the *interleaving* of steps 2 and 3 above. Note this requires genuine simultaneity or preemption between the read and write of at least one thread — exactly the parallel or preemptively-scheduled execution described in the previous topic's Under the Hood section.

## 3. Data Race vs. Race Condition — Related but Distinct

These terms are often used interchangeably but mean different things:

- A **data race** is a specific, narrower condition: two or more threads access the **same memory location** concurrently, **at least one access is a write**, and there is no synchronization ordering the accesses. In languages with a formal memory model (C++, Rust, Java), an unsynchronized data race is technically **undefined behavior** — the compiler and CPU are allowed to reorder, cache, or tear the access in ways that produce results stranger than "just" a lost update.
- A **race condition** is the broader, higher-level bug: the *outcome* depends on timing. A race condition can exist **without** a technical data race — the classic example is a **TOCTOU (time-of-check to time-of-use)** bug, where a check and a later action are individually safe and even properly synchronized in isolation, but another process can act in the gap between them:

```js
// TOCTOU race — no shared-memory data race, still a race condition:
if (!fileExists(path)) {   // CHECK: file doesn't exist
  // <-- another process creates the file HERE, in the gap -->
  createFile(path);          // USE: overwrites the file that now exists
}
```

Every concurrency-safety technique in section 5 addresses race conditions in general; only some of them (locks, atomics) specifically target true data races on shared memory.

## 4. Where Race Conditions Hide in Real Systems

- **Check-then-act**: checking a condition, then acting on it, with a gap where another task can invalidate the check (the TOCTOU pattern above; also "check if a row exists, then insert it" without a unique constraint).
- **Read-modify-write on shared counters/balances**: the `counter++` pattern generalized — account balance updates, inventory decrements, rate-limit counters.
- **Double-submit / duplicate processing**: a user double-clicks "Pay," or a network retry resends a request, and two concurrent handlers both act on it before either has recorded that it happened (this is exactly what idempotency, covered in the Failure Handling topic, is designed to prevent).
- **Cache stampede / thundering herd on cache-miss**: many concurrent requests all miss a cold cache simultaneously, all check "is it cached?", all get "no," and all proceed to regenerate the same expensive result at once.
- **Lazy initialization without guarding**: two threads both check "has the singleton been created?", both see "no," and both construct it — producing two instances where the code assumed exactly one.

## 5. Fixing Race Conditions

| Technique | How it works | Trade-off |
|---|---|---|
| **Mutual exclusion (locks/mutexes)** | Only one thread may hold the lock and execute the guarded section at a time. | Simple to reason about; risks deadlock (next topic) and serializes contended code, hurting throughput. |
| **Atomic operations** | Hardware-guaranteed indivisible read-modify-write (e.g. atomic increment, compare-and-swap). | Fast, no blocking; only covers single-variable updates, not multi-step invariants. |
| **Immutability** | Never mutate shared state; produce new values instead. | Eliminates the *possibility* of a write-write or read-write race entirely — the strongest fix, where applicable. |
| **Message passing / actor model** | Threads never share memory directly; they communicate by sending messages to a single owner of the state, which processes them one at a time. | No shared-memory race by construction; adds messaging overhead and different failure modes. |
| **Unique constraints / conditional writes at the data layer** | Push the check-then-act atomicity down into the database (`INSERT ... ON CONFLICT`, a unique index, an optimistic-concurrency version column). | Turns an application-level race into a single atomic operation the datastore guarantees; requires the datastore to support it. |

## 6. Race Conditions Still Happen in Single-Threaded Runtimes

A common misconception is that a single-threaded model (like JavaScript's — see `languages/javascript/34-concurrency`) is immune to race conditions because "only one thing runs at a time." That protects against races **within** a single synchronous block of code (nothing can interrupt you mid-expression), but it does **not** protect against races **across** `await` boundaries, because control genuinely returns to the event loop at each `await` and another task can run — including one that mutates the same state:

```js
// Async TOCTOU race — single thread, still racy:
async function reserveSeat(seatId) {
  const seat = await db.getSeat(seatId);   // CHECK — control yields here; another
                                            // call to reserveSeat can now run fully
  if (seat.available) {
    await db.markReserved(seatId);           // USE — may double-book if two calls
  }                                             // both passed the check before either wrote
}
```

Two concurrent calls to `reserveSeat` can both read `available: true` before either writes `reserved`, double-booking the seat — on a single thread, with no true data race, purely because of `await`-boundary interleaving (see `languages/javascript/29-promises` and `27-event_loop` for exactly how the event loop schedules the resumption of each `await`).

## 7. Under the Hood: What "Atomic" Actually Guarantees at the Hardware Level

### The CPU-level primitive: compare-and-swap

Fixing a race condition on a single value ultimately relies on a hardware instruction that performs read-modify-write as one indivisible step the CPU guarantees cannot be interrupted or interleaved with another core's access to the same memory location. The most common such primitive is **compare-and-swap (CAS)**:

```
CAS(address, expected, new_value):
  atomically:
    if *address == expected:
        *address = new_value
        return true   // success — no one else touched it in between
    else:
        return false   // someone else changed it first — caller must retry
```

On x86, this is implemented via the `LOCK CMPXCHG` instruction — the `LOCK` prefix asserts exclusive ownership of that memory location's cache line for the duration of the operation, blocking other cores from accessing it mid-instruction. On ARM, the equivalent is a **load-linked/store-conditional (LL/SC)** pair: load the value and "mark" the address, then attempt to store only if nothing else wrote to that address since the load, retrying otherwise. Both approaches guarantee the same property: no other core can observe or produce an intermediate state partway through the read-modify-write.

### Building an atomic increment from CAS

A correctly atomic increment (unlike the buggy `counter++` in section 2) is built as a **CAS retry loop**:

```
atomicIncrement(address):
  loop:
    old = *address                       // read current value
    new = old + 1
    if CAS(address, old, new): return new  // succeeds only if nothing changed it since the read
    // else: someone else updated it between our read and our CAS — retry with the fresh value
```

This is the crucial difference from section 2's broken version: the *write* is conditional on the value being unchanged since the read. If another thread interleaves an update in between, the CAS fails, and the loop retries against the new value instead of blindly overwriting it — the update is never silently lost.

### Mutexes are built on top of this, not the other way around

A mutex (mutual exclusion lock) is a higher-level construct implemented using CAS: acquiring the lock is typically a CAS from "unlocked" to "locked," retried (optionally spinning briefly, then yielding) until it succeeds; releasing is a plain write back to "unlocked," possibly waking a waiting thread. Modern OS mutex implementations (Linux **futex**, "fast userspace mutex") optimize the common uncontended case entirely in userspace with a single CAS and only fall into a genuine kernel-level sleep/wake syscall when there's actual contention — because kernel transitions are far more expensive than a single CAS instruction.

### A semaphore generalizes this to N permits

Where a mutex allows exactly one holder, a **semaphore** maintains an integer count of available "permits" and allows up to that many concurrent holders; acquiring atomically decrements the count (blocking if it would go below zero), releasing atomically increments it. A mutex is a semaphore with a maximum count of 1. Semaphores are the natural fit for **bounding concurrency** to a resource limit (e.g., "at most 10 concurrent connections to this database"), which reappears as the **bulkhead** pattern in the Resilience Patterns topic.

### What atomic does NOT guarantee

Atomicity guarantees a *single* memory location's read-modify-write is indivisible. It says nothing about **ordering guarantees for other, unrelated memory locations** around it — that requires a separate concept, **memory barriers/fences**, which control how a CPU and compiler may reorder reads and writes relative to each other across cores (this is why languages with a memory model define "happens-before" relationships explicitly, rather than assuming atomic operations alone make multi-variable invariants safe). Protecting an invariant that spans **multiple** variables (e.g., "debit account A and credit account B must both happen or neither") needs a lock or transaction around the whole sequence — no single atomic instruction covers it.

## 8. Common Pitfalls

1. **Assuming an operation is atomic because it looks like one line** — `counter++`, `x += 1`, and even some higher-level "atomic-looking" library calls can hide multiple steps; verify explicitly rather than assuming.
2. **Believing single-threaded (JS-style) code can't have race conditions** — true within one synchronous block, false across `await`/callback boundaries where another task can interleave (section 6).
3. **Fixing the symptom by adding a delay ("it works if I `sleep` here")** — this doesn't fix the race, it only makes the buggy interleaving less *likely*, which reappears under different load, hardware, or timing (and is famously hard to reproduce and debug once it does).
4. **Locking too narrowly, protecting only part of a multi-step invariant** — e.g., locking around the read and separately around the write of a check-then-act sequence, leaving the gap between them unprotected; the lock must span the entire read-decide-write sequence.
5. **Using a data race fix (an atomic/lock) for a problem that isn't a data race** — a TOCTOU race across separate systems (e.g., two microservices) can't be fixed with a local mutex; it needs a distributed coordination mechanism (a unique constraint, distributed lock, or idempotency key — see Failure Handling and Resilience topics).

## 9. Quick Reference

```
Race condition: outcome depends on TIMING of access to shared mutable state
Data race: race condition ON THE SAME MEMORY LOCATION, unsynchronized, ≥1 write — undefined behavior in most memory models
Lost update: classic race — read-modify-write interleaves, one update silently overwritten

Fixes: mutex (mutual exclusion) | atomics/CAS (single-variable) | immutability (eliminates it) | message passing | DB unique constraint

CAS(address, expected, new): atomically swap only if unchanged since read — retry loop if it fails
Mutex ⊂ built on CAS; futex = fast path in userspace, kernel only on real contention
Semaphore = mutex generalized to N permits (bulkhead pattern uses this)
Atomicity ≠ ordering guarantee for OTHER variables — that needs memory barriers / a lock spanning the whole invariant
```