Race Conditions

01 Introduction

Unit 4 introduced threads and showed why they are useful: they share an address space, so they can communicate through ordinary memory accesses without the cost of message passing; and they can run in parallel on multiple cores, so a program can use more than one processor at once. Both of these advantages come from the same property — the shared address space — and both come with the same hazard. When two threads access the same memory and at least one of them writes, the outcome can depend on the precise order in which their operations are interleaved. That order is determined by the scheduler, not by the programmer.

This is the race condition, and it is the central problem of concurrent programming. A race condition is not a syntax error, not a type error, and not a logic error in the usual sense: the program is correct as written, and it produces the right answer most of the time. It fails only when the scheduler happens to interleave the threads in a particular way — a way that may occur once in a million runs, or never on the developer's machine and always on the customer's. Race conditions are the reason concurrent programming has a reputation for being difficult, and they are the reason this unit exists.

This lesson defines the problem before presenting any solution. It introduces shared state, interleaving, and atomicity; it works through the classic lost-update example at the level of individual machine instructions; it distinguishes data races from the broader category of race conditions; and it explains why concurrency bugs are qualitatively harder to reproduce and diagnose than sequential bugs. The remaining six lessons of the unit present the mechanisms — critical sections, locks, semaphores, monitors, condition variables — that make concurrent programs correct. Understanding the problem in this lesson is the prerequisite for understanding why those mechanisms are designed as they are.

02 Learning objectives

This lesson contributes to U6.1 and U6.2, and to course learning outcomes CLO2, CLO3, and CLO8.

03 Required reading

• OSTEP — Chapter 26, Concurrency: An Introduction, through the section on the Race Condition and the counter example. This is the single most important reading for this lesson: the chapter develops the problem from the ground up and shows the assembly-level interleaving that produces the lost update.
• Operating System Concepts — Chapter 6, Sections 6.1–6.3, Background, The Critical- Section Problem, and Peterson's Solution. The formal definition of the race condition and the critical-section problem.
• Tanenbaum & Bos — Modern Operating Systems, Chapter 2, Section 2.3, Interprocess Communication, through the subsection on race conditions. A complementary treatment that places the problem in the context of interprocess communication more broadly.
• Love, R. — Linux System Programming, Chapter 10, Concurrency. A practical view of the problem from a systems-programming perspective, with examples in C on Linux.
• Linux man pages: man 7 pthreads, man 7 attributes (for the volatile and restrict qualifiers), man 3 pthread_create.

04 Core content

4.1 Concurrency and shared state

A concurrent program is one in which two or more execution contexts — threads, processes, or signal handlers — can be in progress at the same time. If the contexts do not share any state, they are independent: each can be reasoned about in isolation, and concurrency introduces no new correctness problems. This is the case for processes that communicate only through pipes or sockets, or for threads that operate on entirely disjoint data.

The difficulties begin when contexts share state. In a threaded program, all threads share the global variables, the heap, and the file descriptor table. When two threads access the same memory location and at least one of them writes, the outcome of the program depends on the order in which the accesses occur. That order is called the interleaving, and it is chosen by the scheduler — which may switch threads at almost any point, including in the middle of a high-level statement.

A race condition is a situation in which the correctness of a program depends on the interleaving of operations on shared state. The program is written correctly: each thread performs a meaningful sequence of operations, and the intended result is unambiguous. But the operations are not atomic — they can be interrupted partway through — and if they are interrupted in the wrong place, the result is wrong.

4.2 The lost-update problem

The classic illustration is a shared counter incremented by two threads. The code looks harmless:

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

int counter = 0;

void *worker(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        counter++;              /* not atomic */
    }
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, worker, NULL);
    pthread_create(&t2, NULL, worker, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("counter = %d (expected 2000000)\n", counter);
    return 0;
}

Each thread increments the counter one million times, so the expected final value is 2,000,000. On a real system, the program usually prints something smaller — often much smaller, and different on every run. The discrepancy is not caused by a bug in the increment operation; it is caused by the fact that counter++ is not a single operation.

On a typical machine, counter++ compiles to three instructions:

movl   counter(%rip), %eax    ; load counter into register
addl   $1, %eax               ; add 1 to the register
movl   %eax, counter(%rip)    ; store the register back

The scheduler may preempt a thread between any two of these instructions. If it does, another thread may execute its own load–add–store sequence on the same variable, and the two sequences can interleave in a way that loses one of the increments.

4.3 Why the high-level statement is not atomic

The lost-update problem arises because counter++ — a single statement in C — is not a single operation at the machine level. A statement is atomic if it executes as an indivisible unit: no other thread can observe an intermediate state, and no interleaving can split it. Most high-level statements in C and similar languages are not atomic, and the compiler is not required to make them so.

Several things can make a statement non-atomic:

• Multiple machine instructions. As in the counter example, a read-modify-write sequence requires several instructions, and the scheduler can preempt between them.
• Compiler reordering. The compiler may reorder memory accesses for optimisation, and the processor may execute them out of order. Even if the source code looks sequential, the machine instructions may not be.
• Non-atomic data types. On many architectures, a 64-bit value on a 32-bit machine is loaded in two 32-bit halves. Another thread can observe the value between the two loads — a so-called torn read.
• Function calls that hide multiple operations. A function such as list_insert() may perform several pointer updates, each of which is a potential preemption point.

4.4 The three conditions for a race

A race condition can occur when three conditions hold simultaneously. Removing any one of them eliminates the race.

Most of this unit is concerned with the third condition. The mechanisms we will study — locks, semaphores, monitors, condition variables — all work by making a sequence of operations appear atomic to other threads. But it is worth keeping the first two conditions in mind, because they sometimes offer a simpler fix. If two threads do not need to share state, giving each its own copy is cheaper and less error-prone than adding a lock.

4.5 Data races versus race conditions

In the literature, the terms data race and race condition are often used interchangeably, but they refer to related yet distinct phenomena.

Data race

A data race is a specific, well-defined property of a program's memory accesses. Two memory accesses form a data race if they are to the same location, at least one is a write, and they are not ordered by any synchronization operation. A data race is a property of the program text and the language's memory model; it can be detected statically by tools such as ThreadSanitizer.

Race condition

A race condition is a broader and more semantic notion: the correctness of the program depends on the interleaving of operations that are not properly synchronized. A race condition can exist even in a program with no data races, if a thread makes a decision based on a value that another thread has changed between the decision and its use.

The distinction matters for two reasons. First, eliminating data races does not automatically eliminate race conditions: a program can be data-race-free and still have a logical race. Second, data races are easier to detect: tools like ThreadSanitizer can flag them at runtime, but they cannot detect a logical race that is not a data race, because detecting it requires understanding the program's intent.

The classic example of a race condition that is not a data race is the check-then-act pattern:

if (list->head != NULL) {           /* check */
    struct node *n = list->head;    /* act */
    use(n);
}

If another thread removes the head node between the check and the act, the program uses a freed or stale pointer. Each individual access is atomic; there is no data race in the formal sense. But the composition of the two accesses is not atomic, and the program is incorrect. The fix is not to make each access atomic but to make the pair atomic — which is exactly what a lock or a critical section does.

4.6 A second example: the bank transfer

The counter is the simplest race condition, but it is not the most illustrative of real-world consequences. Consider a bank account with two operations: deposit and withdraw.

struct account {
    long balance;
};

void deposit(struct account *a, long amount) {
    a->balance += amount;
}

void withdraw(struct account *a, long amount) {
    if (a->balance >= amount) {
        a->balance -= amount;
        return 1;
    }
    return 0;
}

The withdraw operation checks the balance and then decrements it. If two threads withdraw from the same account concurrently, both may see a sufficient balance, both may proceed, and the account may be overdrawn. This is the same check-then-act pattern as the list example. The consequences are more serious — money is lost — but the structure of the bug is identical.

The check-then-act pattern is the most common form of race condition in practice, because it appears in every place where a program asks a question about shared state and then acts on the answer. The window between the question and the action is the vulnerability, and making the question and the action atomic is the fix. This is the subject of Lesson 6.2, which introduces the critical-section abstraction.

4.7 Why race conditions are hard to find

Race conditions are qualitatively harder to diagnose than ordinary bugs. Several factors contribute.

• Non-determinism. The outcome depends on the interleaving, which depends on the scheduler. The same program on the same input can produce different results on different runs, or on the same run at different times.
• Rare occurrence. Many races require a preemption at a precise point. On a lightly loaded system the scheduler may never preempt at that point; on a heavily loaded one it may do so frequently. The bug may appear only under load, or only on a machine with many cores.
• Hardware and compiler dependence. The same source code may be correct on one architecture and incorrect on another, because the memory model and the instruction set differ. Compiler optimisations can also expose or hide races in ways that are not obvious from the source.
• Delayed symptoms. A race may corrupt a data structure silently and cause a crash thousands of instructions later, in a completely unrelated part of the program. The stack trace points to the symptom, not the cause.
• Heisenbug behaviour. Adding debugging output, running under a debugger, or enabling an analyser can change the timing enough to make the race disappear. The act of observing the bug changes whether it occurs.
• Test difficulty. A test that runs the program once proves nothing about a race: the race may not manifest on that run. Only running under a race detector or under a scheduling stress tool gives meaningful evidence.

4.8 The scheduler's role

It is important to be precise about the relationship between the scheduler and a race condition. The scheduler does not create the race: the race is a property of the program's use of shared state. The scheduler only chooses whether the race manifests on a given run. On a single-threaded program there is no race, because there is no other thread to interleave with. On a multi-threaded program the race exists in the code, and the scheduler determines whether the particular interleaving that triggers it occurs.

This has a practical consequence: a race cannot be "fixed" by changing the scheduler. A program with a race is incorrect, and it will fail eventually — perhaps on a different machine, perhaps under a different load, perhaps only after a software update changes the timing. The only reliable fix is to eliminate the race from the code by making the access to shared state atomic.

4.9 Common misconceptions

05 Worked example

The following example traces the lost-update problem at the instruction level, computes the expected and observed results, and shows how the outcome depends on the interleaving.

for (int i = 0; i < N; i++)
    counter++;

L:  movl  counter(%rip), %eax
A:  addl  $1, %eax
S:  movl  %eax, counter(%rip)

Time   T1            counter    T2
0      L (0)         0          —
1      A (1)         0          —
2      S (1)         1          —
3      —             1          L (1)
4      —             1          A (2)
5      —             1          S (2)
...

Time   T1            counter    T2
0      L (0)         0          —
1      —             0          L (0)
2      —             0          A (1)
3      —             1          S (1)
4      A (1)         1          —
5      S (1)         1          —
...

Time   T1            counter    T2
0      L (0)         0          —
1      A (1)         0          —
2      —             0          L (0)
3      —             0          A (1)
4      —             1          S (1)
5      S (1)         1          —
...

Time   T1                              T2
0      check balance (100 ≥ 80) → yes  —
1      —                               check balance (100 ≥ 80) → yes
2      balance = 100 − 80 = 20         —
3      —                               balance = 100 − 80 = 20

#include <stdatomic.h>

atomic_int counter = 0;

void *worker(void *arg) {
    for (int i = 0; i < 1000000; i++)
        atomic_fetch_add(&counter, 1);
    return NULL;
}

06 Interactive activity

07 Knowledge check

if (a->balance >= amount) {
    a->balance -= amount;
    return 1;
}
return 0;

08 Unit discussion

09 Practice exercise

10 Summary

• A race condition is a situation in which the correctness of a program depends on the interleaving of operations on shared state. The scheduler chooses the interleaving; the programmer does not control it.
• A race condition can occur when three conditions hold: shared state, at least one write, and non-atomic access. Removing any one condition eliminates the race.
• The classic example is the lost update: two threads increment a shared counter, both load the same original value, and both store the same incremented value, so one increment is lost.
• counter++ is not atomic: it compiles to a load, an add, and a store, and the scheduler can preempt between them. Most high-level statements in C are not atomic.
• volatile does not fix a race. It prevents some compiler optimisations but does not make a read-modify-write sequence atomic.
• A data race is a specific property of memory accesses: two accesses to the same location, at least one a write, without synchronization ordering them. A race condition is a broader correctness property. Every data race is a race condition, but not every race condition is a data race.
• The check-then-act pattern is the most common form of race condition in practice: a thread asks a question about shared state and then acts on the answer, and another thread modifies the state in between. Making the check and the act atomic is the fix.
• Race conditions are hard to find because they are non-deterministic, may occur rarely, may have delayed symptoms, and may disappear under observation. A test that runs once proves nothing.
• Tools such as ThreadSanitizer detect data races at runtime, but they cannot detect logical race conditions that are not data races.
• The general fix for a race condition is to make the sequence of operations atomic with respect to other threads. The mechanisms for doing this — critical sections, locks, semaphores, monitors, condition variables — are the subject of the rest of this unit.

11 References

• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 26. Available online at ostep.org.
• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 6, Sections 6.1–6.3.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2, Section 2.3.
• Love, R. Linux System Programming, 2nd ed., Chapter 10.
• ISO/IEC 9899:2011, Programming Languages — C, Section 5.1.2.4 (the memory model) and Section 7.17 (atomics).
• Serebryany, K., & Iskhodzhanov, T. ThreadSanitizer — Data Race Detection in Practice. Proceedings of the Workshop on Binary Instrumentation and Applications, 2009.
• Linux man-pages: man 7 pthreads, man 7 attributes, man 3 pthread_create.
• Leveson, N. G., & Turner, C. S. An Investigation of the Therac-25 Accidents. IEEE Computer, 1993. The authoritative account of the Therac-25 incidents, including the role of race conditions.