Shared State, Race Conditions and Atomicity

Learning Objectives

Define shared mutable state, race conditions and data races — and distinguish them.

Explain read-modify-write, atomicity, lost updates, check-then-act and TOCTOU bugs, non-atomic counters and critical sections.

State invariants and the idea of linearizability.

Reproduce races, recognise nondeterministic interleavings, explain why "it worked on my machine" proves nothing, and why data races are undefined behavior in C/C++.

Use race detectors and know their limits; design away shared state.

Plain-Language Explanation

Two bank tellers serve the same account. Each looks up the balance (100), checks there is enough for a withdrawal of 80, and writes down the new balance (20). Both approve; the customer walked away with 160 from an account holding 100. Nothing was "broken" in either teller's steps — the problem was that their steps interleaved. That is a race condition: a result that depends on the timing of concurrent operations.

Precise Technical Explanation

Shared mutable state Data that more than one thread can access, at least one of them writing. Immutable shared data and unshared mutable data are both safe; the combination is where bugs live.

A race condition is a correctness bug where the outcome depends on the relative timing or interleaving of operations. Races can happen even when every individual memory access is synchronised (check-then-act with atomic reads), between processes, or across machines.

A data race is a narrower, language-defined term: two accesses to the same memory location from different threads, at least one a write, not ordered by happens-before, and not both atomic. In C and C++ a data race is undefined behavior; in Java and Go it yields unspecified but bounded results; safe Rust forbids it at compile time.

language memory model Possible with locks/atomics?

yes (logic still wrong) no (synchronised accesses are not data races) two withdrawals both pass the balance check unsynchronised counter++ from two threads

counter += 1 is three steps: *read* the value, *modify* it, *write* it back. Another thread can act between them.

An operation is atomic if no other thread can observe it half-done or act in the middle of it. Atomicity is relative to a set of operations: a single aligned 64-bit store may be atomic on hardware, but counter += 1 is not.

Two read-modify-write sequences interleave and one overwrites the other's result:

The final value can be 1, not 2. The source-level counter += 1 may compile to several machine operations and is not automatically atomic.

if (!map.containsKey(k)) map.put(k, v);, if balance >= amount: balance -= amount, if (instance == null) instance = new … — the check is stale by the time of the act. Fix by making check and act one atomic step (a lock around both, putIfAbsent, compare-and-swap).

Time-of-check/time-of-use races The same pattern with external resources: checking a file's permissions, then opening it, while another process swaps it (Module 25). Fix by operating on handles and using atomic system calls.

The classic demonstration below: four threads each increment a plain counter a million times, and the total comes out short — differently on each run.

A critical section is code that accesses shared state and must not be executed by more than one thread at a time (or more precisely, must appear atomic to others). Locks, atomics and confinement implement critical sections (Module 4).

An invariant is a property that must always hold when no operation is in progress: "sum of all account balances is constant", "size equals the number of nodes". A critical section may temporarily break an invariant; no other thread may observe that intermediate state.

A concurrent object is linearizable if every operation appears to take effect instantaneously at some point between its start and its end, consistent with a sequential specification. It is the gold-standard correctness condition for concurrent data structures (Module 19).

Reproducible race examples Races are timing-dependent, so demonstrations widen the window: many iterations, deliberate yields (time.sleep(0)), or a barrier that releases threads together. The examples below use each technique.

Two threads of *n* atomic steps each have C(2n, n) possible interleavings — 184,756 for n = 10. Testing samples a tiny fraction; correctness must hold for all.

Why "it worked on my machine" is not proof A race may need a particular core count, CPU model, load level, compiler version or optimization level to appear. Passing tests show that the bug did not occur in those runs, not that it cannot.

Language-level undefined behavior (C/C++ data races) Because data races are UB in C and C++, the compiler may assume none exist: it can keep a shared variable in a register (an infinite loop on a flag), merge or split stores, or tear a 64-bit write into two halves. The program's behavior is then unconstrained.

Race detectors and limitations ThreadSanitizer (C/C++, Go -race, Rust nightly), Helgrind/DRD (Valgrind), Java's JCStress (stress testing),.NET's Concurrency Visualizer. Dynamic detectors only see races in executions that actually happen; they slow programs 5–15×; they do not find higher-level race conditions such as check-then-act on properly synchronised data.

Designing away shared state The best race fix is having nothing to race on: give each thread its own data and combine results at the end (map/reduce), pass ownership through queues (message passing), use immutable data, or confine state to one thread.

pseudocode
shared counter = 0

Thread A:                  Thread B:
read counter -> 0          read counter -> 0
calculate 0 + 1            calculate 0 + 1
write counter = 1          write counter = 1

Why It Matters in Real Systems

Race conditions have caused double spending in payment systems, oversold inventory, corrupted caches, security bypasses (TOCTOU), and the Therac-25 radiation overdoses. They are expensive precisely because they are rare and hard to reproduce.

Key Terms

Outcome depends on interleaving Unsynchronised conflicting accesses (language-defined)

Indivisible with respect to other threads One write silently overwrites another

Acting on a condition that may have changed Code requiring mutual exclusion

Property that must hold between operations Operations appear instantaneous within their duration

Syntax and API Overview

This is a concurrency concept, not a language construct. Every language's x += 1 on shared memory is a read-modify-write unless an atomic API is used.

Complete Code Example

A non-atomic counter in C (GCC 11.2, -O1 -pthread), run five times. The variable is volatile only to stop the optimizer from collapsing the loop into one addition; volatile does not make the increments atomic, and this program has a data race (undefined behavior) on purpose, to show the symptom:

Output (five real runs):

A check-then-act race in CPython 3.13.1. time.sleep(0) between the check and the act gives the scheduler a chance to switch threads — widening a window that exists in every unsynchronised version:

#include <pthread.h>
#include <stdio.h>

#define THREADS 4
#define ITERS 1000000

static volatile long counter;                 /* shared, unsynchronised: a data race */

static void *work(void *arg)
{
    (void)arg;
    for (int i = 0; i < ITERS; ++i) {
        counter = counter + 1;                /* read, add, write — not atomic */
    }
    return NULL;
}

int main(void)
{
    pthread_t t[THREADS];
    for (int i = 0; i < THREADS; ++i) pthread_create(&t[i], NULL, work, NULL);
    for (int i = 0; i < THREADS; ++i) pthread_join(t[i], NULL);
    printf("expected %d, got %ld (lost %ld updates)\n", THREADS * ITERS, counter, THREADS * ITERS - counter);
    return 0;
}

run 1: expected 4000000, got 2010156 (lost 1989844 updates)
run 2: expected 4000000, got 2131076 (lost 1868924 updates)
run 3: expected 4000000, got 2040725 (lost 1959275 updates)
run 4: expected 4000000, got 1606135 (lost 2393865 updates)
run 5: expected 4000000, got 3072571 (lost 927429 updates)

import threading
import time


class Account:
    def __init__(self, balance):
        self.balance = balance
        self.lock = threading.Lock()

    def withdraw_unsafe(self, amount):
        if self.balance >= amount:          # check
            time.sleep(0)                   # another thread may run here
            self.balance -= amount          # act on a stale check
            return True
        return False

    def withdraw_safe(self, amount):
        with self.lock:                     # check and act are one critical section
            if self.balance >= amount:
                time.sleep(0)
                self.balance -= amount
                return True
            return False


def run(method_name):
    acct = Account(100)
    start = threading.Barrier(2)            # release both threads at the same moment
    approved = []
    def customer():
        start.wait()
        approved.append(getattr(acct, method_name)(80))
    threads = [threading.Thread(target=customer) for _ in range(2)]
    for t in threads:
        t.start()
    for t in threads:
        t.join()
    return approved.count(True), acct.balance


for name in ["withdraw_unsafe", "withdraw_safe"
…

Line-by-Line Explanation

C: each thread does counter = counter + 1 a million times; the load and store of different threads interleave, so increments are lost. Every run loses a different number.

Python: Barrier(2) makes both customers start together. In withdraw_unsafe, both can pass the balance >= 80 check before either subtracts, producing two approvals and a balance of −60. The lock in withdraw_safe makes check and act atomic with respect to other withdrawals.

The Python program counts outcomes over 200 runs, so the result shows the *distribution* rather than one lucky run.

Output

Output (one real run of 200 trials each — the counts vary):

The unsafe version produced overdrafts in some trials and correct results in others — exactly why testing a race once proves nothing. The safe version never approved twice.

withdraw_unsafe  1 approved -> balance 20: 170 runs, 2 approved -> balance -60: 30 runs
withdraw_safe    1 approved -> balance 20: 200 runs

Interleaving or State Trace

The overdraft interleaving:

check 100 ≥ 80 ✓ sleep(0) → switch balance = 100 − 80 balance = 20 − 80

Correctness and Safety Analysis

Invariant: *balance ≥ 0*. The unsafe method breaks it because the invariant depends on two steps (check, act) that are not atomic together. The safe method holds the lock across both, so every withdrawal sees and updates the balance as one step. Note that the race in the Python version is a *race condition*, not a data race: CPython's GIL makes each bytecode atomic, yet the logic is still wrong.

Common Mistakes and Misconceptions

"The GIL makes Python code thread-safe." It makes single bytecodes atomic; multi-step logic still races.

"volatile fixes it." Not in C/C++ (Module 7).

"I'll just add a sleep to fix the timing." Sleeps hide races, they do not fix them.

Protecting the write but not the read.

Locking each step separately (check under the lock, act under another acquisition).

Failure Modes and Debugging Steps

Reproduce under stress: many threads, many iterations, barriers, run in a loop.

Run a race detector (ThreadSanitizer, go run -race).

Identify the invariant and every code path that reads or writes the state involved.

Make the multi-step operation atomic — or remove the sharing.

ThreadSanitizer pinpoints the C data race (GCC 11 on this kernel needs ASLR disabled for the one process — setarch -R — see the Memory course, Module 14):

The same bug in Go, found by Go's race detector (Go 1.23.4, -race build for linux/amd64 run in WSL2):

Go's race detector reports the race and makes the program exit with status 66 when a race was found.

#include <pthread.h>
#include <stdio.h>

static long counter;

static void *work(void *arg)
{
    (void)arg;
    for (int i = 0; i < 1000; ++i) counter++;
    return NULL;
}

int main(void)
{
    pthread_t a, b;
    pthread_create(&a, NULL, work, NULL);
    pthread_create(&b, NULL, work, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("counter = %ld\n", counter);
    return 0;
}

gcc -std=c17 -g -O1 -fsanitize=thread -pthread m03_tsan_src.c -o m03_tsan_bin
setarch "$(uname -m)" -R ./m03_tsan_bin 2>&1 | grep -E 'WARNING|of size|#0|SUMMARY|counter =' || true

WARNING: ThreadSanitizer: data race (pid=150)
  Read of size 8 at 0x555555558018 by thread T2:
    #0 work m03_tsan_src.c:9 (m03_tsan_bin+0x1263)
  Previous write of size 8 at 0x555555558018 by thread T1:
    #0 work m03_tsan_src.c:9 (m03_tsan_bin+0x128d)
  Location is global 'counter' of size 8 at 0x555555558018 (m03_tsan_bin+0x000000004018)
    #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:969 (libtsan.so.0+0x605b8)
    #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:969 (libtsan.so.0+0x605b8)
SUMMARY: ThreadSanitizer: data race m03_tsan_src.c:9 in work
counter = 2000

package main

import (
	"fmt"
	"sync"
)

func main() {
	counter := 0
	var wg sync.WaitGroup
	for i := 0; i < 2; i++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for j := 0; j < 1000; j++ {
				counter++ // unsynchronised read-modify-write
			}
		}()
	}
	wg.Wait()
	fmt.Println("counter =", counter)
}

counter = 2000
==================
WARNING: DATA RACE
Read at 0x00c00011e078 by goroutine 8:
  main.main.func1()
      m03_go_race/main.go:16 +0x99

Previous write at 0x00c00011e078 by goroutine 7:
  main.main.func1()
      m03_go_race/main.go:16 +0xab

Goroutine 8 (running) created at:
  main.main()
      m03_go_race/main.go:13 +0x78

Goroutine 7 (finished) created at:
  main.main()
      m03_go_race/main.go:13 +0x78
==================
Found 1 data race(s)
[exit status 66]

Performance and Scalability Implications

Removing races by adding locks serialises work; removing them by removing sharing (per-thread accumulation) keeps parallelism. The fastest correct counter is usually one counter per thread summed at the end.

Security Considerations

Race conditions in authorization ("check permission, then act"), file handling (TOCTOU) and balance checks are exploitable — attackers can repeat requests to win the race. Treat any shared check-then-act on security-relevant state as a vulnerability until it is atomic.

Platform and Runtime Caveats

C/C++: data races are UB. Java: racy reads return some previously written value (no "out-of-thin-air" values for most types; long/double may tear on 32-bit JVMs without volatile). Go: racy programs have undefined-but-limited behavior per the Go memory model; maps may panic with "concurrent map writes". Safe Rust: compile-time error.

How often a race shows up depends on core count, load and CPU — on a single-core VM some races may never appear.

Real-World Applications

Inventory reservation, seat booking, rate counters, caches, session stores, "create if not exists" in databases (use unique constraints or INSERT … ON CONFLICT).

Best Practices

Identify all shared mutable state and its invariants.

Make compound operations atomic as a unit.

Prefer confinement, immutability and message passing.

Run race detectors in CI.

Test with stress and many repetitions; never trust a single run.

Exercises

E1 · Beginner. Is x = x * 2 on a shared integer safe without synchronization if two threads run it once each, starting from 3? List all possible results.

Answer: Not safe. Possible results: 12 (no interleaving) or 6 (both read 3 and write 6). In C/C++ it is a data race and therefore undefined behavior.

E2 · Intermediate. Rewrite if key not in cache: cache[key] = compute(key) for concurrent use so compute runs at most once per key.

Answer: Hold a lock across check and insert; to avoid holding the lock during a slow compute, store a future/placeholder under the lock, compute outside it, and have other threads wait on the placeholder (the "in-flight request deduplication" pattern, Module 18).

E3 · Advanced challenge. How many interleavings exist for two threads each executing the three steps read/add/write once? How many lose an update?

Answer: C(6, 3) = 20 interleavings. The update survives only when one thread's read comes after the other's write: 2 of them (A entirely before B, or B before A). The other 18 lose an update.

Quiz

? Which is a data race in C?
+ Two threads increment a plain int without synchronization. :: Conflicting unsynchronised accesses.
- Two threads increment an _Atomic int. :: Atomic accesses do not form data races.
- Two threads read a const global. :: No writes, no race.
- A check-then-act on a mutex-protected map with separate lock acquisitions. :: That is a race condition, not a data race.

? A test ran 10,000 times without losing an update. What can you conclude?
- The code is race-free. :: Rare interleavings may not have occurred.
+ Only that the race did not manifest in those runs. :: Testing samples a few schedules.
- The GIL protected it. :: That depends on the language and the code.
- The CPU has no reordering. :: Unrelated.

? Which fix a check-then-act bug? (select all that apply)
+ Holding one lock across both the check and the act :: They become one atomic step.
+ Using an atomic compare-and-swap or putIfAbsent :: Check and act in one operation.
- Adding sleep() before the act :: That only changes timing.
- Making the variable volatile in C :: volatile gives no atomicity.

Summary

Shared mutable state plus interleaving yields race conditions; unsynchronised conflicting accesses are data races, which are undefined behavior in C/C++. Read-modify-write and check-then-act sequences need atomicity as a unit. Races are nondeterministic, so single test runs prove nothing — use invariants, reasoning, stress tests and race detectors, and above all design away the sharing.