Free lesson · Operating Systems

BROKEN: Check-then-act race condition

Easy16 min readoperating-systemsosconcurrency

The Bug That Only Happens Sometimes

In Topic 1 you learned why the critical section problem exists and what properties a correct solution must have. Now we are going to zoom in on the specific failure mode that makes concurrency bugs so dangerous: the race condition.

A race condition is a bug where the correctness of a program depends on the relative timing of events - specifically, on which thread reaches a particular point in the code first. The program works correctly under some thread interleavings and produces wrong results under others. The outcome is a race between threads, and whoever gets there first determines whether the result is correct or corrupted.

What makes race conditions uniquely dangerous compared to other bugs is their non-determinism. A null pointer exception happens every time you run the code with a null input. A race condition might happen once in a thousand runs - or once in a million. It might happen in production under heavy load but never in your test suite. It might happen on a 16-core server but not on your 4-core laptop. The bug is real, but it hides.

This topic covers the common patterns where race conditions appear, shows you how to identify them in code, and gives you the vocabulary to discuss them precisely in interviews. Every synchronization mechanism in the rest of this module exists to eliminate race conditions.

Anatomy of a Race Condition

Every race condition has the same underlying structure. There are three ingredients, and if any one of them is missing, the race condition does not exist:

Shared state. At least two threads must access the same memory location - a variable, a data structure, a file, a database row. If threads operate on completely independent data, there is no race.

At least one writer. At least one thread must be modifying the shared state. If all threads are only reading, there is no race - reads do not conflict with other reads. The race exists because a write by one thread can interfere with a read or write by another.

No synchronization. The threads access the shared state without any mechanism to ensure that their accesses do not interleave. No lock, no atomic operation, no ordered communication channel. If proper synchronization is in place, the race is eliminated.

Remove any one of these three ingredients and the race condition disappears. This is why there are exactly three categories of solutions to race conditions: eliminate shared state (use message passing instead), make the data read-only (use immutable data structures), or add synchronization (use locks, atomics, or transactions). Every concurrency design decision is choosing among these three options.

The Five Classic Race Condition Patterns

Race conditions appear in many forms, but they cluster around five patterns that cover the vast majority of bugs you will encounter or be asked about in interviews.

Pattern 1: Check-Then-Act

The thread checks a condition, then acts on the assumption that the condition is still true. Between the check and the act, another thread changes the condition.

# BROKEN: Check-then-act race condition
if username not in user_database:        # CHECK
    user_database[username] = new_user   # ACT - but someone else might have
                                         # inserted the same username between
                                         # the check and the act

# BROKEN: File existence check
import os
if not os.path.exists(filename):         # CHECK
    create_file(filename)                # ACT - another process might have
                                         # created the file between check and act

The check-then-act pattern is the most common source of race conditions in application code. It appears in user registration (check if username exists, then create it), file operations (check if file exists, then create it), caching (check if key is cached, then fetch and store it), and inventory systems (check if item is available, then reserve it).

The fix is to make the check and the act a single atomic operation. Databases provide INSERT ... ON CONFLICT (PostgreSQL) or INSERT IGNORE (MySQL) for this. File systems provide O_CREAT | O_EXCL flags for atomic file creation. Application code uses locks to make the check-and-act sequence indivisible.

Pattern 2: Read-Modify-Write

The thread reads a value, computes a new value based on it, and writes the new value back. Between the read and the write, another thread modifies the original value.

This is the counter example from Topic 1 - counter += 1 is a read-modify-write operation that compiles to three separate instructions. But the pattern is broader than counters:

# BROKEN: Read-modify-write on a bank balance
balance = get_balance(account_id)           # READ
new_balance = balance - withdrawal_amount   # MODIFY
set_balance(account_id, new_balance)        # WRITE
# Another thread might have changed the balance between READ and WRITE

# BROKEN: Read-modify-write on a list
items = get_list(key)                       # READ
items.append(new_item)                      # MODIFY
set_list(key, items)                        # WRITE
# Another thread might have appended to the same list

The fix is either an atomic operation (CAS loop, atomic increment) or a lock that wraps the entire read-modify-write sequence.

Pattern 3: Write-Write (Lost Update)

Two threads both write to the same location, and one write overwrites the other without incorporating it.

# BROKEN: Two threads updating user profile
# Thread A: User changed their email
user.email = new_email_a
save(user)

# Thread B: User changed their name (at the same time)
user.name = new_name_b
save(user)

# If both threads read the original user object, then save:
# Thread A saves email=new_email_a, name=original_name
# Thread B saves email=original_email, name=new_name_b
# Thread B's save overwrites Thread A's email change!

This is the classic lost update problem. It is extremely common in web applications where two HTTP requests modify the same database record simultaneously. ORMs that load an entire object, modify one field, and save the entire object back are especially vulnerable.

The fix at the database level is optimistic locking (add a version number to each record; the update fails if the version has changed since the read) or pessimistic locking (lock the row before reading, hold it until the write is complete).

Pattern 4: Compound Action on Multiple Variables

The thread needs to update multiple related variables atomically, but the updates happen one variable at a time. Between updates, another thread sees an inconsistent state.

# BROKEN: Transferring money between accounts
account_a.balance -= 100   # First update
# If another thread reads here, it sees money has vanished
# (debited from A but not yet credited to B)
account_b.balance += 100   # Second update

# BROKEN: Resizing a hash map
new_table = allocate_bigger_table()
# Copy entries from old table to new table...
# If another thread reads the hash map during the copy,
# it might miss entries (they've been moved to the new table
# but the map still points to the old one) or find duplicates
# (entries that exist in both tables during the copy)
hash_map.table = new_table   # Swap pointer

The fix is a lock or transaction that wraps all the related updates into a single atomic unit. This is exactly why database transactions exist - they turn a sequence of reads and writes into a single all-or-nothing operation.

Pattern 5: Publication Without Synchronization

A thread constructs an object and makes it visible to other threads before the object is fully initialized.

// BROKEN: Double-checked locking (pre-Java 5)
public class Singleton {
    private static Singleton instance;
    
    public static Singleton getInstance() {
        if (instance == null) {                    // First check (no lock)
            synchronized (Singleton.class) {
                if (instance == null) {             // Second check (with lock)
                    instance = new Singleton();     // PROBLEM: another thread
                    // might see a non-null 'instance' that is not yet
                    // fully constructed due to instruction reordering
                }
            }
        }
        return instance;
    }
}

The CPU or compiler may reorder instructions such that the reference to the new object is published (written to the instance field) before the constructor finishes executing. Another thread checking instance == null sees a non-null reference and uses the partially constructed object. The fix in Java is to declare instance as volatile, which prevents the reordering.

This pattern extends beyond singletons to any situation where one thread publishes data (writes it to a location visible to other threads) without a memory barrier or synchronization point that guarantees all prior writes are visible.

graph TD
    subgraph PATTERNS["Five Race Condition Patterns"]
        CTA["Check-Then-Act<br/>Check a condition, then act on it<br/>Gap between check and act"]
        RMW["Read-Modify-Write<br/>Read a value, compute, write back<br/>Gap between read and write"]
        WW["Write-Write (Lost Update)<br/>Two writers overwrite each other<br/>Last write wins, first is lost"]
        CA["Compound Action<br/>Multiple related updates<br/>Inconsistent intermediate state"]
        PUB["Publication<br/>Object visible before ready<br/>Partially constructed state"]
    end
    
    CTA --- FIX1["Fix: Atomic check-and-act<br/>(CAS, INSERT ON CONFLICT)"]
    RMW --- FIX2["Fix: Atomic RMW instruction<br/>(fetch-and-add, CAS loop)"]
    WW --- FIX3["Fix: Optimistic or<br/>pessimistic locking"]
    CA --- FIX4["Fix: Transaction or<br/>lock wrapping all updates"]
    PUB --- FIX5["Fix: Memory barrier,<br/>volatile, or synchronization"]

This diagram shows the five classic race condition patterns and their fixes. Check-Then-Act is fixed with atomic check-and-act operations. Read-Modify-Write is fixed with atomic instructions like fetch-and-add or CAS loops. Write-Write or Lost Update is fixed with optimistic or pessimistic locking. Compound Action on multiple variables is fixed with transactions or locks that wrap all updates. Publication without synchronization is fixed with memory barriers, volatile declarations, or explicit synchronization.

Spotting Race Conditions in Code

When reviewing code for race conditions - whether in an interview whiteboard session or in a production code review - there is a systematic approach that catches most bugs.

Step 1: Identify the shared state. What variables, data structures, files, or database rows are accessed by more than one thread or process? List them. Every item on this list is a candidate for a race condition.

Step 2: For each shared item, identify the accessors. Which threads read it? Which threads write it? If all accessors are readers, there is no race. If at least one is a writer, continue to Step 3.

Step 3: Check for synchronization. Is every access to this shared item protected by the same lock, wrapped in the same transaction, or mediated by the same atomic operation? If yes, the access is safe. If any access is unprotected - even a single read without the lock - there is a potential race condition.

Step 4: Check for compound operations. Even if individual accesses are protected, are there sequences of accesses that need to be atomic together? The check-then-act and read-modify-write patterns involve multiple accesses that are each individually atomic but together are not. The lock must wrap the entire sequence, not just each individual access.

# This code looks safe but is NOT

lock = threading.Lock()
shared_list = []

# Thread A
with lock:
    length = len(shared_list)       # Protected read
with lock:
    shared_list.append(item)        # Protected write

# RACE: Between the two lock acquisitions, another thread
# might have modified shared_list. The 'length' variable
# is stale by the time we append.

# FIXED version:
with lock:
    length = len(shared_list)       # Read
    shared_list.append(item)        # Write
    # Both operations under the SAME lock acquisition

Warning: The most dangerous race conditions are the ones that look safe. A function that acquires a lock for every individual operation can still have races between those operations. The granularity of locking must match the granularity of the logical operation, not the granularity of the individual memory accesses.

The Time-of-Check-to-Time-of-Use (TOCTOU) Problem

TOCTOU is a special case of the check-then-act pattern that appears in operating systems and file system security. It is common enough (and important enough for interviews) to deserve its own section.

The pattern is: a program checks a property of a file (permissions, existence, size), and then uses the file based on that check. Between the check and the use, an attacker replaces the file.

# TOCTOU vulnerability in a setuid program
# Step 1: Program checks if the user has permission to read the file
if access("/tmp/userfile", R_OK) == 0:
    # Step 2: Program opens and reads the file with elevated privileges
    fd = open("/tmp/userfile", O_RDONLY)
    # BETWEEN steps 1 and 2, an attacker replaces /tmp/userfile
    # with a symlink to /etc/shadow. The access() check passed
    # for the original file, but open() follows the symlink and
    # opens /etc/shadow with the program's elevated privileges.

sequenceDiagram
    participant PROG as Setuid Program
    participant FS as File System
    participant ATK as Attacker
    
    PROG->>FS: access("/tmp/userfile") - check permissions
    FS-->>PROG: OK - user has read permission
    
    Note over ATK: Window of vulnerability
    ATK->>FS: Replace /tmp/userfile<br/>with symlink to /etc/shadow
    
    PROG->>FS: open("/tmp/userfile") - read with elevated privileges
    Note over FS: Follows symlink → opens /etc/shadow
    FS-->>PROG: Returns file descriptor to /etc/shadow
    
    Note over PROG: Program reads /etc/shadow<br/>thinking it is /tmp/userfile

This sequence diagram shows a TOCTOU attack. The setuid program first calls access to check if the user has permission to read the file at /tmp/userfile. The file system confirms permission. Then, in the window between the check and the use, an attacker replaces /tmp/userfile with a symbolic link pointing to /etc/shadow. When the program calls open on the same path, the file system follows the symlink and opens /etc/shadow with the program's elevated privileges. The program reads the sensitive file thinking it is the original user file.

TOCTOU bugs are a classic operating systems security problem. The fix is to never separate the check from the use. Instead of calling access() and then open(), call open() directly and handle the error if the user does not have permission. The open() call performs the permission check and the file access atomically with respect to file system changes.

In application code, the same principle applies: never check a condition and then assume it is still true later. Check and act in the same atomic operation, or lock the resource so the condition cannot change between the check and the act.

Race Conditions in Real Production Systems

Race conditions cause some of the most expensive and dangerous bugs in production systems. Here are documented examples that illustrate the patterns above.

Therac-25 radiation therapy machine (1985-1987). A race condition between the operator interface and the beam control system allowed the machine to deliver radiation doses 100 times higher than intended. The operator could switch from X-ray mode to electron mode faster than the software could process the change, leaving the machine in a state where it used the high-energy beam with the collimator removed. Three patients died and three more were seriously injured. This is the most cited example of a race condition causing loss of life.

Northeast blackout of 2003. A race condition in the FirstEnergy alarm system software caused a failure in the alarm logging system. When multiple alarms arrived within a narrow time window, the event handler failed to process them in order, leaving operators unaware of cascading failures. Combined with other failures, this contributed to a blackout affecting 55 million people.

GitHub's early MySQL race condition. In 2012, GitHub discovered a race condition in their user session management that could allow one user to be logged in as another user under specific timing conditions. Two simultaneous requests could receive each other's session tokens if they hit the database at exactly the right millisecond.

These are not edge cases - they are the natural consequence of shared mutable state without proper synchronization. The scale of the consequences varies from a lost counter increment to lost lives, but the underlying bug is structurally identical.

Data Races vs Race Conditions

These two terms are related but not identical, and interviewers sometimes test whether you know the difference.

A data race is a specific, precisely defined condition: two threads access the same memory location concurrently, at least one of them is a write, and there is no synchronization between them. Data races are defined at the memory access level. Languages like C, C++, and Java define data races as undefined behavior - the compiler is allowed to assume they never happen and can optimize code accordingly. If your code has a data race, the compiler might transform it in ways that make the bug even worse.

A race condition is a broader concept: the correctness of the program depends on the relative timing of events. A race condition is a logical error at the algorithm level. You can have a race condition even without a data race (if all individual memory accesses are properly synchronized but the overall logic is still timing-dependent), and you can have a data race without a race condition (a data race on a variable whose value does not affect correctness - though this is rare and still technically undefined behavior).

# Race condition WITHOUT a data race:
lock = threading.Lock()

# Thread A
with lock:
    if balance >= withdrawal:
        pass
# Lock released here
# Thread B could change balance here
with lock:
    balance -= withdrawal  # Race condition: balance might have changed
# Each lock acquisition prevents data races, but the LOGIC
# has a race condition because the check and the update are
# in separate critical sections.

# Data race WITHOUT a visible race condition (still undefined behavior):
# Thread A writes to x (used only for logging, never affects program logic)
# Thread B reads from x concurrently without a lock
# The program might "work correctly" despite the data race, but
# the behavior is technically undefined and the compiler can break it.

Interview: "What is the difference between a data race and a race condition?"

"A data race is when two threads access the same memory location without synchronization, and at least one is a write. It is defined at the hardware and language level - in C and C++, it is undefined behavior. A race condition is when program correctness depends on the relative timing of operations. It is defined at the algorithm level - the logic produces wrong results under some interleavings.

You can have a race condition without a data race - for example, if two lock acquisitions protect individual reads and writes, but the program logic between them is timing-dependent. And a data race does not always produce visible incorrect behavior, but it is still undefined behavior and must be fixed.

The fix for data races is synchronization at the memory access level - locks, atomics, or volatile. The fix for race conditions is synchronization at the logical operation level - wrapping the entire check-and-act or read-modify-write sequence in a single critical section."

How Programming Languages Handle Race Conditions

Different languages take different approaches to preventing or managing race conditions. Knowing these approaches is valuable in interviews because it shows breadth.

Java uses the synchronized keyword to create implicit mutex locks on objects, volatile for visibility guarantees on individual variables, and the java.util.concurrent package for higher-level abstractions (concurrent collections, atomic variables, explicit locks with condition variables). Java's memory model precisely defines what guarantees synchronized and volatile provide.

Go takes a different philosophy: "Do not communicate by sharing memory; instead, share memory by communicating." Go's primary concurrency primitive is the channel, which is a synchronized message-passing mechanism. Goroutines send data through channels instead of accessing shared variables. Go also provides sync.Mutex and sync.atomic for cases where shared memory is necessary, but the culture strongly favors channels.

Rust prevents data races at compile time. The ownership system ensures that mutable references are exclusive - you cannot have two mutable references to the same data, and you cannot have a mutable reference and an immutable reference to the same data simultaneously. This eliminates data races by construction. You can opt into shared mutable state using Arc<Mutex<T>>, but the type system forces you to use a lock.

Python has the Global Interpreter Lock (GIL), which prevents true parallel execution of Python bytecode by multiple threads. This eliminates most data races in pure Python code, but it does not eliminate race conditions - the GIL can be released between any two bytecodes, so check-then-act and read-modify-write patterns are still vulnerable. And the GIL does not help at all with multi-process concurrency or I/O-based concurrency.

Debugging Race Conditions

Race conditions are notoriously difficult to debug because they are non-deterministic. Here are the techniques that work in practice:

Thread sanitizers. Tools like Google's ThreadSanitizer (TSan), available in GCC and Clang via -fsanitize=thread, instrument memory accesses at compile time and detect data races at runtime. TSan slows your program by 5-15x but catches race conditions that would take months to reproduce otherwise. If you write concurrent C, C++, or Go code and you are not running TSan, you have race conditions you do not know about.

Stress testing with controlled scheduling. Run your concurrent code with many more threads than cores, under heavy load, with random delays inserted between operations. This increases the probability that threads interleave in the exact order that triggers the bug. Some testing frameworks (like Go's -race flag combined with -count=1000) automate this.

Code review with the shared-state checklist. The four-step process from earlier in this topic (identify shared state, identify accessors, check for synchronization, check for compound operations) applied systematically during code review catches most race conditions before they reach production.

Logging with timestamps. When you suspect a race condition in production, add logging with high-resolution timestamps around the suspected critical section. If the logs show two threads entering the region within microseconds of each other, that confirms the race.

Exercise: Starter: Write a Python program with two threads that both increment a shared counter using a balance = balance + 1 pattern (not +=). Introduce a small time.sleep(0.0001) between the read and write to increase the chance of interleaving. Run it and observe the lost updates. Then fix it using threading.Lock.

Intermediate: Write a program that demonstrates the check-then-act race condition: two threads each check if a key exists in a shared dictionary, and if not, insert it with an initial value. Without locking, both threads can pass the check and both insert, with one overwriting the other. Add proper locking to fix it. Then research Python's dict.setdefault() - does it solve the race? Why or why not?

Advanced: Write a concurrent bank transfer simulation in Python. Create 10 accounts with initial balances. Spawn 20 threads that each perform 1,000 random transfers between random accounts. Verify that the total balance across all accounts is conserved (the invariant). First implement it without locking and show that the invariant is violated. Then implement it with per-account locks (not a single global lock). Be careful about deadlock - if Thread A locks account 1 then account 2, and Thread B locks account 2 then account 1, they deadlock. Use lock ordering (always lock the lower-numbered account first) to prevent it.

Back to Operating Systems