Lesson 1 · Synchronization and deadlocks

Race Conditions and Critical Sections

A race condition is a bug whose outcome depends on timing you do not control. The fix is never to make the code faster or add a delay — it is to identify the critical section and make it indivisible.

The Lost Update

counter++ looks atomic in source and is not. It compiles to three separate instructions: load the value into a register, add one, store it back. Between any two of those the scheduler may preempt, and on a multicore machine another thread may be executing the same three instructions simultaneously.

The failure is the lost update. Thread A loads 0. Thread B loads 0 before A has stored. Both add one, both store 1. Two increments occurred and the counter reads 1. No error is raised, nothing crashes, and the number is simply wrong.

What makes this class of bug hard is that it is timing-dependent. The interleaving that loses an update might occur once in ten million iterations, so the code passes every test, works in development, and corrupts data in production under load. It also disappears when you add logging, because the timing shifts.

A race condition is any situation where the result depends on the relative ordering of concurrent operations. The lost update is the canonical instance, but check-then-act patterns are just as common: if (!exists(f)) create(f) races because something can create the file between the check and the create.

counter++ is load, add, store — three preemption points
The lost update corrupts silently, raising no error
Rare interleavings pass tests and fail under production load
Check-then-act races the same way as read-modify-write

The Critical Section Problem

A critical section is the region of code that accesses shared state in a way that must not overlap with another thread's access. Solving the critical section problem means ensuring at most one thread is inside at a time — and any correct solution must satisfy three requirements, not just the first.

Mutual exclusion: if one thread is executing in its critical section, no other may be. This is the obvious one, and it alone is not enough — a lock that is never released provides perfect mutual exclusion and a dead program.

Progress: if no thread is in its critical section and some want to enter, the selection cannot be postponed indefinitely, and threads not trying to enter must not participate in the decision. This rules out schemes where an uninterested thread can block an interested one.

Bounded waiting: there must be a limit on how many times other threads can enter ahead of a thread already waiting. Without it, a thread can be starved forever while others cycle through. Any solution missing one of the three is broken, and the missing one is usually bounded waiting.

The three requirements — an answer naming only mutual exclusion is incomplete
Requirement	States that	Violated when
Mutual exclusion	At most one thread is inside its critical section	Two threads update shared state at once
Progress	Only threads wanting to enter decide who enters, and not indefinitely	An uninterested thread blocks an interested one
Bounded waiting	A limit exists on how often others enter ahead of a waiting thread	One thread is overtaken forever — starvation

Mutual exclusion — at most one thread inside
Progress — the choice cannot be deferred forever
Bounded waiting — no thread is overtaken indefinitely
Two out of three is not a solution

Key reference

Terms, operations, and practical uses

The bug

Lost updateTwo threads read the same value, both add one, one write survives.
Read-modify-writecounter++ is three instructions with two preemption points.
Check-then-actState changes between the test and the action.

Correctness requirements

Mutual exclusionAt most one thread inside the critical section.
ProgressThe choice of who enters cannot be deferred forever.
Bounded waitingNo thread is overtaken an unlimited number of times.

Hardware support

Test-and-setWrites 1 and returns the old value, indivisibly.
Compare-and-swapWrites only if the value still matches the expected one.
ABA problemA changed to B and back to A makes CAS wrongly succeed.
volatileA visibility hint — never a substitute for atomicity.

Code example

Force the lost update, then prevent it

# The lost update, forced deterministically: two threads that both read
# before either writes. No sleep, no luck -- the interleaving is explicit.
shared = 0

def unlocked_increment_twice():
    global shared
    shared = 0
    a = shared            # thread A loads 0
    b = shared            # thread B loads 0 -- before A stored
    shared = a + 1        # A stores 1
    shared = b + 1        # B stores 1, overwriting A's increment
    return shared

def locked_increment_twice():
    global shared
    shared = 0
    for _ in range(2):    # the lock makes load-add-store indivisible
        current = shared  # nobody can observe or interleave here
        shared = current + 1
    return shared

lost = unlocked_increment_twice()
safe = locked_increment_twice()
print(f"unlocked: {lost} (lost update) | locked: {safe} | expected 2")

#include <iostream>
using namespace std;
// The lost update, forced deterministically: two threads that both read
// before either writes. No sleep, no luck -- the interleaving is explicit.
int shared = 0;
int unlockedIncrementTwice() {
    shared = 0;
    int a = shared; // thread A loads 0
    int b = shared; // thread B loads 0 -- before A stored
    shared = a + 1; // A stores 1
    shared = b + 1; // B stores 1, overwriting A's increment
    return shared;
}
int lockedIncrementTwice() {
    shared = 0;
    for (int i = 0; i < 2; i++) {   // the lock makes load-add-store indivisible
        int current = shared; // nobody can interleave here
        shared = current + 1;
    }
    return shared;
}
int main() {
    int lost = unlockedIncrementTwice();
    int safe = lockedIncrementTwice();
    cout << "unlocked: " << lost << " (lost update) | locked: " << safe
    << " | expected 2\n";
}

class Main {
    // The lost update, forced deterministically: two threads that both read
    // before either writes. No sleep, no luck -- the interleaving is explicit.
    static int shared = 0;
    static int unlockedIncrementTwice() {
        shared = 0;
        int a = shared; // thread A loads 0
        int b = shared; // thread B loads 0 -- before A stored
        shared = a + 1; // A stores 1
        shared = b + 1; // B stores 1, overwriting A's increment
        return shared;
    }
    static int lockedIncrementTwice() {
        shared = 0;
        for (int i = 0; i < 2; i++) {   // lock makes load-add-store indivisible
            int current = shared; // nobody can interleave here
            shared = current + 1;
        }
        return shared;
    }
    public static void main(String[] args) {
        int lost = unlockedIncrementTwice();
        int safe = lockedIncrementTwice();
        System.out.println("unlocked: " + lost + " (lost update) | locked: "
        + safe + " | expected 2");
    }
}

Inputtwo threads each increment a shared counter once

Outputunlocked: 1 (lost update) | locked: 2 | expected 2

Example

Run the example step by step

Output

Software Solutions and Why They Are Not Enough

Peterson's solution solves the two-thread case using only ordinary loads and stores, with a flag[] array declaring intent and a turn variable breaking ties. Each thread sets its flag, yields the turn to the other, and waits while the other both wants in and holds the turn. It provably satisfies all three requirements.

It is also unusable on real hardware without help. Modern CPUs and compilers reorder memory operations for performance, and Peterson's correctness depends entirely on the write to flag becoming visible before the read of turn. Without memory barriers the reordering breaks it, which is why textbook Peterson code fails on real machines.

Disabling interrupts is the other classic approach: no interrupt means no preemption means no interleaving. It genuinely works, but only on a single core — on a multicore machine the other cores keep running and are entirely unaffected. It is also a privileged operation, so user code cannot do it, and holding interrupts off for long delays every device on the system.

The conclusion both routes reach is the same: correct mutual exclusion needs hardware support. Not because software solutions are wrong on paper, but because the memory model underneath them is weaker than the algorithms assume.

Peterson's is provably correct under sequential consistency
Real CPUs reorder, so it needs explicit memory barriers
Disabling interrupts does nothing to other cores
Correctness at speed requires hardware primitives

Atomic Hardware Instructions

Processors provide read-modify-write instructions that complete indivisibly — no other core can observe or interleave with a half-finished one. Test-and-set writes 1 and returns the previous value in one uninterruptible step; compare-and-swap writes a new value only if the current value matches an expected one, returning whether it succeeded.

A spinlock is then trivial: loop on test-and-set until it returns 0, do the critical section, store 0 to release. Spinning burns CPU while waiting, which is exactly right when the critical section is a few instructions long — spinning for 50 ns beats a 2 µs context switch — and exactly wrong when it is long, where blocking is correct. Real mutexes do both, spinning briefly before sleeping.

Compare-and-swap is the more general primitive and underpins lock-free data structures: read a value, compute a new one, and swap it in only if nothing changed meanwhile; retry if it did. Its classic trap is the ABA problem, where a value changes from A to B and back to A, so CAS succeeds even though the world moved underneath it.

In practice you use std::atomic in C++, java.util.concurrent.atomic in Java, or Python's GIL-protected operations, which compile down to exactly these instructions. The point of understanding the layer below is knowing why volatile is not a substitute — it prevents caching the value in a register, and does nothing about atomicity.

Why software-only solutions are not enough in practice
Approach	Works on multicore	Needs privilege	Fails because
Disabling interrupts	No	Yes, kernel only	Other cores keep running
Peterson's solution	In theory only	No	CPU and compiler reorder memory operations
Test-and-set	Yes	No	(works — busy-waits while spinning)
Compare-and-swap	Yes	No	(works — but see the ABA problem)

Test-and-set and compare-and-swap complete indivisibly
Spin for short critical sections, block for long ones
CAS enables lock-free structures and carries the ABA trap
volatile is a visibility hint, never a substitute for atomicity