Synchronization I: race conditions, locks and atomic operations

Threads share memory, and Lesson 3 showed how useful that is. This lesson faces the cost. When two threads read and write the same data without coordination, the result can depend on the exact order in which their instructions happen to run, an order that changes from run to run with scheduling, caching and processor speed. Bugs of this kind, race conditions, are among the hardest in computing to find, because a program can pass every test and then fail once a month in production. This lesson defines races precisely, shows how hardware and operating systems provide mutual exclusion, and looks at locks and atomic operations in C.

CMPUT-274 demonstrated a lost update in Python and fixed it with a lock. Here we go below the language: what the processor actually executes, why the hardware needs special instructions, how a mutex is built, and what it costs. Lesson 6 continues with semaphores, condition variables and classic coordination problems, and Lesson 7 with deadlock.

Why counter++ is not one step

In C, counter++ looks like a single operation, but the processor executes it as three: load the value from memory into a register, add one, and store the register back to memory. If two threads each perform these three steps and their steps interleave, both may load the same old value, both add one, and both store the same new value. One increment disappears. The code is correct for one thread and wrong for two.

# counter += 1 is really three steps: load, add, store. Replay two interleavings of two threads.
def run(schedule):
    mem = {"counter": 0}
    regs = {"T1": None, "T2": None}
    for thread, step in schedule:
        if step == "load":  regs[thread] = mem["counter"]
        if step == "add":   regs[thread] += 1
        if step == "store": mem["counter"] = regs[thread]
        print(f"  {thread} {step:<5} reg={regs[thread]}  counter={mem['counter']}")
    return mem["counter"]
safe = [("T1", "load"), ("T1", "add"), ("T1", "store"), ("T2", "load"), ("T2", "add"), ("T2", "store")]
racy = [("T1", "load"), ("T2", "load"), ("T1", "add"), ("T2", "add"), ("T1", "store"), ("T2", "store")]
print("serial order:"); print("  result =", run(safe))
print("interleaved order:"); print("  result =", run(racy), "(one update lost)")

serial order:
  T1 load  reg=0  counter=0
  T1 add   reg=1  counter=0
  T1 store reg=1  counter=1
  T2 load  reg=1  counter=1
  T2 add   reg=2  counter=1
  T2 store reg=2  counter=2
  result = 2
interleaved order:
  T1 load  reg=0  counter=0
  T2 load  reg=0  counter=0
  T1 add   reg=1  counter=0
  T2 add   reg=1  counter=0
  T1 store reg=1  counter=1
  T2 store reg=1  counter=1
  result = 1 (one update lost)

A race condition occurs when the correctness of a program depends on the relative timing of threads. A data race, the narrower technical term used by the C and C++ standards, is two threads accessing the same memory location concurrently, at least one of them writing, without synchronization. In C and C++, a program with a data race has undefined behaviour: the compiler is allowed to assume races do not exist, so it may keep a shared variable in a register or reorder accesses, and the results can be stranger than a simple lost update.

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

#define ITERS 1000000
static long counter = 0;               /* shared, unprotected */

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

int main(void) {
    pthread_t t[4];
    for (int i = 0; i < 4; i++) pthread_create(&t[i], NULL, work, NULL);
    for (int i = 0; i < 4; i++) pthread_join(t[i], NULL);
    printf("counter = %ld, expected %d\n", counter, 4 * ITERS);
    printf("updates lost: %s\n", counter < 4L * ITERS ? "yes" : "none this time");
    return 0;
}

$ gcc -O0 -Wall -pthread toy.c -o toy
$ ./toy
counter = 2631767, expected 4000000
updates lost: yes

On a multicore machine, this program loses many updates on almost every run, and the total changes each time. With fewer cores or fewer iterations the bug may hide completely, which is exactly what makes races dangerous. Testing alone cannot prove a concurrent program correct; you need tools and disciplined design.

Finding races with ThreadSanitizer

ThreadSanitizer (TSan), built into GCC and Clang, instruments every memory access and synchronization operation and reports pairs of accesses that are not ordered by any synchronization. It finds races even when the run happens to produce the right answer. Like AddressSanitizer in CMPUT-201 and CMPUT-331, it slows the program (here by five to fifteen times), so it is used in testing and continuous integration rather than production.

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

static long counter = 0;

static void *work(void *arg) {
    (void)arg;
    for (int i = 0; i < 1000; i++) counter++;    /* data race */
    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);
    puts("finished");
    return 0;
}

$ gcc -O1 -g -pthread -fsanitize=thread toy.c -o toy
$ ./toy
finished
==================
WARNING: ThreadSanitizer: data race
  Read of size 8 by thread T2:
    #0 work toy.c:8
  Previous write of size 8 by thread T1:
    #0 work toy.c:8
  Location is global 'counter' of size 8
  Thread T2 created by main thread at:
    #0 pthread_create tsan_interceptors_posix.cpp
    #1 main toy.c:15
  Thread T1 created by main thread at:
    #0 pthread_create tsan_interceptors_posix.cpp
    #1 main toy.c:14
SUMMARY: ThreadSanitizer: data race toy.c:8 in work
==================
ThreadSanitizer: reported 1 warnings

The critical-section problem

A critical section is a piece of code that accesses shared data and must not be executed by more than one thread at a time. A correct solution to the critical-section problem must provide three properties. Mutual exclusion: at most one thread is in its critical section at once. Progress: if no thread is in its critical section and some want to enter, one of them must be able to enter without waiting forever. Bounded waiting: after a thread asks to enter, there is a limit on how many times others may enter before it does, so no thread starves. A practical solution should also be efficient and should not depend on the relative speeds of threads.

Peterson's algorithm (1981) solves the problem for two threads using only ordinary loads and stores. Each thread sets a flag announcing its interest, then politely gives the turn to the other thread, then waits while the other is interested and has the turn. Exploring every possible interleaving, as the program below does, shows that both threads can never be in the critical section together.

# Peterson's algorithm for two threads, explored exhaustively over every interleaving
from itertools import product
CODE = ["flag[me]=1", "turn=other", "wait", "CS", "flag[me]=0", "done"]
def step(state, me):
    pc, flag, turn = list(state[0]), list(state[1]), state[2]
    other = 1 - me
    op = CODE[pc[me]]
    if op == "flag[me]=1": flag[me] = 1; pc[me] += 1
    elif op == "turn=other": turn = other; pc[me] += 1
    elif op == "wait":
        if flag[other] == 0 or turn == me: pc[me] += 1      # may enter
    elif op == "CS": pc[me] += 1
    elif op == "flag[me]=0": flag[me] = 0; pc[me] += 1
    return (tuple(pc), tuple(flag), turn)
start = ((0, 0), (0, 0), 0)
seen, stack, violations = {start}, [start], 0
while stack:
    s = stack.pop()
    if CODE[s[0][0]] == "CS" and CODE[s[0][1]] == "CS":
        violations += 1
    for me in (0, 1):
        if CODE[s[0][me]] != "done":
            n = step(s, me)
            if n not in seen:
                seen.add(n); stack.append(n)
print("reachable states explored:", len(seen))
print("states with both threads in the critical section:", violations)
print("both threads can finish:", any(CODE[s[0][0]] == CODE[s[0][1]] == "done" for s in seen))

reachable states explored: 34
states with both threads in the critical section: 0
both threads can finish: True

Peterson's algorithm is beautiful but no longer correct on real hardware as written. Modern processors and compilers reorder memory operations for speed: a store may sit in a store buffer while a later load completes, so each thread may read the other's flag before its own flag becomes visible. Only memory barriers (fences) or atomic operations with sequential-consistency ordering prevent this. The lesson is general: correct synchronization requires help from the hardware and the language's memory model, not just clever code.

Hardware support: atomic instructions

Processors provide instructions that read, modify and write a memory location as one indivisible step, even with many cores. Test-and-set writes a 1 and returns the old value. Compare-and-swap (CAS) compares a location with an expected value and, only if they are equal, writes a new value, reporting whether it succeeded; x86 provides it as LOCK CMPXCHG. Fetch-and-add adds to a location and returns the old value (LOCK XADD on x86). Arm and RISC-V provide load-linked and store-conditional pairs (LDXR and STXR, LR and SC) from which the others can be built, and newer Arm processors add single-instruction atomics. C11 exposes all of these portably through stdatomic.h, and C++ through std::atomic.

Locks: spinlocks and mutexes

A lock (or mutex, for mutual exclusion) has two operations: acquire (lock) before entering a critical section and release (unlock) after leaving it. The simplest implementation is a spinlock: acquire repeatedly performs test-and-set until it returns 0, meaning the lock was free; release stores 0. Spinning wastes processor time while waiting, so spinlocks suit only very short critical sections on multicore machines, especially inside the kernel where the code holding the lock cannot be descheduled. Fairness is another issue: a plain spinlock may let the same thread win repeatedly. A ticket lock fixes this using fetch-and-add to hand out numbered tickets, served in order like a bakery queue.

A user-level mutex should not spin for long, because the thread holding it may have been preempted and may not run again for milliseconds. Instead, a waiting thread asks the kernel to put it to sleep until the lock is released. Linux implements pthread mutexes with futexes (fast user-space mutexes): acquiring an uncontended lock is a single atomic instruction in user space with no system call; only when there is contention does a thread call futex to sleep, and the releasing thread calls futex to wake a waiter. Many implementations spin briefly before sleeping, betting that the holder will release the lock soon.

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

#define ITERS 1000000
static long locked = 0;                          /* protected by m */
static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static atomic_long atom = 0;                     /* updated with atomic instructions */

static void *work(void *arg) {
    (void)arg;
    for (int i = 0; i < ITERS; i++) {
        pthread_mutex_lock(&m);                  /* enter critical section */
        locked++;
        pthread_mutex_unlock(&m);                /* leave critical section */
        atomic_fetch_add(&atom, 1);              /* one indivisible read-modify-write */
    }
    return NULL;
}

int main(void) {
    pthread_t t[4];
    for (int i = 0; i < 4; i++) pthread_create(&t[i], NULL, work, NULL);
    for (int i = 0; i < 4; i++) pthread_join(t[i], NULL);
    printf("mutex-protected counter = %ld\n", locked);
    printf("atomic counter          = %ld\n", (long)atomic_load(&atom));
    printf("expected                = %d\n", 4 * ITERS);
    return 0;
}

$ gcc -O2 -g -pthread -fsanitize=thread toy.c -o toy
$ ./toy
mutex-protected counter = 4000000
atomic counter          = 4000000
expected                = 4000000

Both fixes give the right answer, and ThreadSanitizer stays silent. The atomic version is faster for a single counter because it avoids lock and unlock calls, but atomics only work when the shared update is one variable. As soon as an invariant involves several variables, for example moving money between two accounts or inserting into a linked list, a lock around the whole update is the clear and correct choice. Lock-free data structures built from CAS loops exist and are used in high-performance systems, but they are notoriously hard to get right; they also face the ABA problem, where a value changes from A to B and back to A between a thread's read and its CAS, fooling the comparison.

Using locks well

Locks are simple to call and easy to misuse. Keep critical sections short, never doing slow input and output or waiting on the network while holding a lock. Protect each shared variable with one specific lock and document which; every access to the variable, including reads, must hold that lock. Prefer coarse-grained locking (one lock for a whole structure) until profiling shows contention, then consider finer-grained locks (one per bucket of a hash table, say) or reader-writer locks, which let many readers proceed at once while writers get exclusive access. Always release locks on every path, including error paths; C++ and Rust release them automatically when a guard object goes out of scope, which prevents a whole class of bugs.

Inside the kernel, the rules are stricter. Code holding a spinlock must not sleep, and data shared with an interrupt handler requires disabling interrupts on the local core while the lock is held, or the handler could interrupt the lock holder and spin forever on the same core. Linux also uses read-copy-update (RCU), which lets readers access shared data with no locks at all, while writers publish new versions and free old ones only after every reader that might see them has finished.

Worked examples