The Critical-Section Problem and Software/Hardware Solutions

When two threads update shared data at the same time, the result can depend on the exact order in which their machine instructions interleave. That situation is a race condition. The statement count = count + 1 looks indivisible in C, but it compiles to a load, an add and a store; if two threads interleave those steps, one update can be lost.

The cure is to make each update a critical section: a piece of code that only one thread may execute at a time. The critical-section problem is to design entry and exit code around the critical section that guarantees this, without deadlock and without making anyone wait forever. The three requirements are stated precisely and then used to check each classic attempt: two-process software solutions (strict alternation, flag-based attempts, Peterson's algorithm), disabling interrupts, and the hardware instructions TestAndSet, swap and compare-and-swap. Semaphores and monitors, which build on these, are in Semaphores, Mutexes and Monitors.

Two threads each execute x = x + 1 once, starting from x = 0, as three atomic steps: r <- x, r <- r + 1, x <- r (each thread has its own register r). If one thread finishes before the other starts, x ends at 2. If both load before either stores, both store 1 and x ends at 1. Over all interleavings the possible final values are exactly $\{1, 2\}$.

If each thread does the increment twice, the possible final values are $\{2, 3, 4\}$; three times each gives $\{2, 3, 4, 5, 6\}$. The minimum is 2, not $n$, for $n \ge 2$ increments per thread: thread A loads 0 and stalls; B does all but its last increment; A stores 1; B loads 1 for its last round and stalls; A finishes all its increments; B finally stores 2. Three threads doing one increment each can end at 1, 2 or 3.

Each process repeats:

A solution must satisfy:

Assumptions: each process runs at a non-zero speed, nothing is assumed about relative speeds, and individual loads and stores are atomic.

Progress versus bounded waiting. Progress is about the system as a whole (somebody gets in); bounded waiting is about each individual (every requester gets in after a bounded number of others). A solution can have progress and still starve one process, as a TestAndSet lock does.

The processes are $P_0$ and $P_1$; in the code, $i$ is the current process and $j = 1 - i$ the other. All variables shown are shared.

Mutual exclusion holds (only the process named by turn may enter). Progress fails: if $P_0$ leaves its critical section and stays in its remainder forever, $P_1$ can enter once more and then waits forever for a turn that never comes, although the critical section is free. Bounded waiting holds with bound 1.

Mutual exclusion holds. Progress fails through deadlock: if both set their flags before either tests, both spin forever.

Mutual exclusion fails: both can pass the while (each sees the other's flag false) and then both set their flags and enter.

flag[i] says "I want to enter"; turn <- j says "but you may go first". If both want in, turn holds whichever value was written last, and the process that wrote last waits.

The order of the two assignments matters. If a process writes turn <- j before flag[i] <- true, mutual exclusion fails: $P_0$ writes turn <- 1; $P_1$ writes turn <- 0, sets its flag and enters because flag[0] is still false; $P_0$ then sets its flag, sees turn = 0 and enters too.

Related material. On modern processors with store buffers and compilers that reorder memory operations, Peterson's algorithm as written is not guaranteed to work without memory barriers. The traces assume sequential consistency.

For $n$ processes, the bakery algorithm (each process takes a number, lowest number enters, ties broken by process ID) satisfies all three requirements in software.

On a single processor, a process can disable interrupts before its critical section and re-enable them after: in this single-CPU kernel model, masking ordinary interrupts prevents interrupt-driven preemption inside the section. Drawbacks: it is a privileged operation, so only the kernel can use it; it does not work on multiprocessors (another CPU still runs); and a long critical section delays all interrupts.

The hardware provides instructions that read and modify a memory word in one indivisible step.

Swap (exchange) is equivalent: each process sets a local key <- true and repeats SWAP(lock, key) until key comes back false.

These simple locks give mutual exclusion (only the caller that saw false enters) and progress, but not bounded waiting: a process can lose the race every time the lock is released, while others re-acquire it forever. A bounded-waiting version keeps an array waiting[0..n-1]: on exit, the releasing process scans the array cyclically from $i + 1$ and hands the lock directly to the next waiting process, so each waits at most $n - 1$ turns.

All the solutions so far busy-wait: the waiting process loops, using CPU time. Such a lock is a spinlock. Spinning is wasteful on one CPU (the lock holder cannot run while the spinner holds the CPU, until a timer interrupt) but efficient on multiprocessors when critical sections are short, because it avoids two context switches. Blocking primitives (semaphores with a waiting queue) are the alternative.

Priority inversion. Under strict priority scheduling on one CPU, a high-priority process spinning on a lock held by a low-priority process can spin forever (Tanenbaum calls this the priority inversion problem): the low-priority holder never gets the CPU to release it. With blocking locks, a medium-priority process can keep the low-priority holder off the CPU indefinitely; priority inheritance solves this by temporarily raising the holder's priority.

A protocol uses flag[i] <- true; while flag[j] do { flag[i] <- false; flag[i] <- true }. Mutual exclusion holds (a process enters only after seeing the other's flag false while its own is true). Progress is not guaranteed: both processes can keep lowering and raising their flags in lockstep and never see the other's flag false, a livelock. This is the same failure as attempt 2, made less likely but not impossible.

In Peterson's algorithm, $P_0$ has executed turn <- 1 and is spinning. $P_1$ is in its critical section. $P_1$ leaves, loops back, sets flag[1] <- true and turn <- 0, and now spins because flag[0] is true and turn = 0. So $P_1$ entered at most once while $P_0$ waited. With a TestAndSet lock, there is no such bound: $P_1$ can release and re-acquire the lock between two of $P_0$'s tests indefinitely.

A claim that a protocol fails is only as good as the interleaving that shows it. Each trace lists the steps in the order they execute; $P_0$ and $P_1$ run the same code.

A single lock variable.

Mutual exclusion fails: the test and the set are two separate steps, which is exactly the gap that TestAndSet closes. Progress holds (a free lock is always taken by some tester), and bounded waiting fails (one process can win every race).

Attempt 2 (set the flag, then check), deadlock. $P_0$ sets flag[0] <- true; $P_1$ sets flag[1] <- true; $P_0$ tests flag[1]: true, spins; $P_1$ tests flag[0]: true, spins. The critical section is free and neither will ever enter.

Attempt 3 (check, then set the flag), both inside. $P_0$ tests flag[1]: false; $P_1$ tests flag[0]: false; $P_0$ sets its flag and enters; $P_1$ sets its flag and enters.

A variant of Peterson that fails. A student writes turn <- i instead of turn <- j but keeps the loop while flag[j] and turn = j.

The last writer of turn now goes first instead of waiting, so mutual exclusion fails. If the loop is also changed to while flag[j] and turn = i, the last writer waits again and the protocol is Peterson's algorithm with the meaning of turn inverted: all three requirements hold, with bound 1.

Bounded waiting with TestAndSet. The simple TestAndSet lock gives no bound, as shown above. A standard fix hands the lock directly to a waiting process:

A process enters either because its TestAndSet returned false (the lock was free) or because the exiting process cleared its waiting entry, passing the lock on without releasing it. The exit scan visits processes in cyclic order $i + 1, i + 2, \dots$, so a waiting process is reached after at most $n - 1$ other entries. The bound is tight: if all other processes are waiting, the scan can admit each of them once first.

Common misconceptions.