Race conditions and the critical section problem

Difficulty: Beginner

Question

What is a race condition? Explain the critical section problem and the three requirements a solution must satisfy.

Answer

Let's take a very concrete starting point: two people share a bank account with 1000 rupees, and both walk up to different ATMs at the same instant to withdraw 800. Each machine checks the balance, sees enough money, and dispenses cash. The account ends up overdrawn. Nothing was wrong with either machine's logic in isolation; the bug is in how their operations interleaved on shared data. This is a race condition: the outcome depends on the relative timing of concurrent operations on shared state.

The textbook example is counter++. It looks like one operation but compiles to three: load the value into a register, add one, store it back. If two threads each run it 1,000,000 times without protection, the final count is often far below 2,000,000. Thread A loads 5, thread B loads 5, both add one and both store 6, so one increment is lost. This kind of bug is nasty because it depends on scheduling, may only appear under load, and disappears when you add a print statement or attach a debugger (a so-called Heisenbug).

The part of code that accesses shared resources and must not be executed by more than one thread at a time is the critical section. The structure of every synchronization solution is an entry section (request permission), the critical section itself, an exit section (release), and the remainder section. The critical section problem asks us to design the entry and exit protocol so that processes cooperate safely.

A valid solution must satisfy three requirements. First, mutual exclusion: if one process is executing in its critical section, no other process may be. Second, progress: if no process is in its critical section and some want to enter, only those not in their remainder section take part in deciding who goes next, and the decision cannot be postponed indefinitely. Third, bounded waiting: after a process has made a request, there is a limit on how many times others can enter before it does, which prevents starvation. Some books also add the assumption that no assumptions can be made about CPU speed or the number of CPUs.

Classic software solutions include Peterson's algorithm for two processes, which uses a flag array and a turn variable, and Lamport's bakery algorithm for n processes. They are elegant but rely on memory ordering assumptions that modern out-of-order CPUs violate unless you use memory barriers. Practical solutions use hardware support: atomic instructions like test-and-set and compare-and-swap, which are the building blocks for locks, and higher-level primitives built on them: mutexes, semaphores, monitors and condition variables. Disabling interrupts works on a single-core kernel but not on multiprocessors and must not be given to user code.

Also mention alternatives that avoid critical sections altogether: immutable data, thread-local storage, message passing, and lock-free structures built on atomic operations. The best way to avoid a race is often to avoid sharing.

Finally, be careful with two terms. A data race is a specific low-level race, two unsynchronized accesses to the same memory location where at least one is a write. A race condition is the broader logical bug. You can have a race condition without a data race, for instance a check-then-act sequence using individually atomic operations.

Code examples

Lost updates without a lock

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

long counter = 0;

void *inc(void *arg) {
    for (int i = 0; i < 1000000; i++)
        counter++;                 /* load, add, store: not atomic */
    return NULL;
}

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

Increments from the two threads overwrite each other, so the result is nondeterministic and usually lower than 2,000,000.

Fixed with a mutex

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

long counter = 0;
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void *inc(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&lock);     /* entry section */
        counter++;                     /* critical section */
        pthread_mutex_unlock(&lock);   /* exit section */
    }
    return NULL;
}

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

The mutex guarantees mutual exclusion, so exactly one thread modifies counter at a time.

Key points

Concepts covered

race condition, critical section, mutual exclusion, atomicity, synchronization