Think of a single-seat washroom on a train. Many passengers may want it, but only one can be inside at a time. There is a simple rule that everyone follows: check the indicator, go in, lock the door, come out, unlock. Nobody has to know who else is on the train, and nobody gets stuck outside forever.
In the previous chapter, Process Synchronization & Race Conditions, we saw that a piece of code that touches shared data, the critical section, must be executed by only one thread at a time, or we get lost updates and other bugs. In this chapter we turn that into a precise problem, list the three rules any correct solution must follow, try some "obvious" solutions and watch them fail, and then study Peterson's solution, the classic correct software answer. We end with the hardware instructions that real systems use instead.
The Critical Section Problem
The critical section problem is to design a protocol that cooperating processes can use so that when one process is executing in its critical section, no other process is executing in its critical section for the same shared data, while also guaranteeing progress and bounded waiting.
Every process that uses the shared data is written in this general shape:
while (true) {
/* ENTRY SECTION : ask for permission to enter */
/* CRITICAL SECTION : touch the shared data */
/* EXIT SECTION : announce that we have left */
/* REMAINDER SECTION: everything else the process does */
}Entry section – the code that requests permission. This is where a process may have to wait.
Critical section (CS) – the code that accesses shared variables, files, buffers and so on.
Exit section – the code that releases permission so others can enter.
Remainder section – the rest of the program, which does not touch the shared data.
Solving the problem means designing the entry and exit sections.
The Three Requirements
A correct solution must satisfy all three of these:
1. Mutual Exclusion
If a process is executing in its critical section, no other process can be executing in its critical section.
This is the main goal: one person in the washroom at a time.
2. Progress
If no process is in its critical section and some processes want to enter, then only processes that are not in their remainder sections can take part in deciding who enters next, and this decision cannot be postponed forever.
In plain words: if the critical section is free and somebody wants it, somebody must get in. A process that is busy elsewhere (in its remainder section) must not be able to block others. And the processes must not get stuck waiting for each other forever (deadlock).
3. Bounded Waiting
There is a limit on the number of times other processes can enter their critical sections after a process has requested entry and before that request is granted.
In plain words: no starvation. Once you are in the queue, others cannot keep overtaking you forever.
Two more ground rules apply when we judge a solution:
We make no assumptions about the relative speed of the processes or the number of CPUs. The solution must work for every possible interleaving.
Each process runs at non-zero speed (it does not stop forever inside its critical section).
Requirement | Protects against | Question to ask |
|---|---|---|
Mutual exclusion | Race conditions | Can two processes ever be in the CS together? |
Progress | Deadlock, and blocking by uninterested processes | If the CS is empty and someone wants it, is entry guaranteed? |
Bounded waiting | Starvation | Can a waiting process be overtaken an unlimited number of times? |
Mutual exclusion is a safety property (something bad never happens). Progress and bounded waiting are liveness properties (something good eventually happens). A solution that never lets anybody in is perfectly "safe" and completely useless, which is why we need all three.
Wrong Attempts (and Why They Fail)
The best way to appreciate Peterson's solution is to try simpler ideas first. All attempts below are for two processes, P0 and P1. In the code, i is the current process and j = 1 - i is the other one. For each attempt we explored every possible interleaving with a small Python state-space search to confirm the verdict.
Attempt 1: A Simple Lock Variable
int lock = 0; /* 0 = free, 1 = taken */
while (lock == 1) /* entry: wait while taken */
;
lock = 1; /* entry: take it */
/* critical section */
lock = 0; /* exit */This is exactly the check-then-act bug from the last chapter. The check (lock == 1) and the act (lock = 1) are two separate steps:
lock = 0
P0: reads lock → 0, leaves the while loop
P1: reads lock → 0, leaves the while loop
P0: lock = 1
P1: lock = 1
P0: enters critical section
P1: enters critical section ← BOTH INSIDEVerdict: mutual exclusion fails.
Attempt 2: Strict Alternation (Taking Turns)
int turn = 0; /* whose turn is it? */
while (turn != i) /* entry: wait for my turn */
;
/* critical section */
turn = j; /* exit: give the turn away */Only the process whose number equals turn can enter, and turn has one value at a time, so mutual exclusion holds. But look at this:
turn = 0
P0: enters CS, leaves, sets turn = 1
P0: goes to its remainder section and stays there a long time
P1: enters CS, leaves, sets turn = 0
P1: wants to enter again → waits for turn == 1
... but P0 is busy elsewhere and does not want the CS.
P1 is blocked even though the CS is EMPTY.The processes are forced to alternate P0, P1, P0, P1 ... If one is much slower, or does not want to enter again, the other is stuck. A process in its remainder section is blocking another one, which is exactly what progress forbids.
Verdict: mutual exclusion holds, bounded waiting holds, progress fails.
Attempt 3: Flags ("I Want to Enter")
Instead of turns, each process announces its interest:
bool flag[2] = {false, false}; /* flag[i] = true means "Pi wants in" */
flag[i] = true; /* entry: I want to enter */
while (flag[j]) /* entry: wait while you want */
;
/* critical section */
flag[i] = false; /* exit */Mutual exclusion holds now, but:
P0: flag[0] = true
P1: flag[1] = true
P0: while (flag[1]) → true, waits ...
P1: while (flag[0]) → true, waits ...
Both wait for each other FOREVER.Both are too polite: each waits for the other to go first. This is a deadlock. If we swap the two lines (check the other's flag first, then set our own), the deadlock goes away but mutual exclusion breaks, because both can check before either sets its flag.
Attempt | Mutual exclusion | Progress | Bounded waiting |
|---|---|---|---|
Lock variable | No | Yes | No |
Strict alternation ( | Yes | No | Yes |
Flags, set then check | Yes | No (deadlock) | – |
Flags, check then set | No | Yes | No |
The flags solve the "uninterested process blocks me" problem; the turn variable solves the "both too polite" problem. Peterson's insight was to combine them.
Peterson's Solution
Published by Gary L. Peterson in 1981, this is a simple and elegant software solution for two processes. It uses two shared variables:
bool flag[2]–flag[i] == truemeans process Pi wants to enter.int turn– if both want to enter, whose turn it is.
bool flag[2] = {false, false};
int turn;
/* code for process Pi (j = 1 - i) */
while (true) {
flag[i] = true; /* 1. I want to enter */
turn = j; /* 2. but you can go first */
while (flag[j] && turn == j) /* 3. wait only if you want in */
; /* AND it is your turn */
/* critical section */
flag[i] = false; /* 4. I am done */
/* remainder section */
}Read the entry section like a polite conversation: "I would like to go in (flag[i] = true), but please, you go first (turn = j)." Then a process waits only if the other one also wants to go in and the other one has the turn.
Case 1: Only P0 wants to enter
P0: flag[0] = true
P0: turn = 1
P0: check (flag[1] && turn == 1) → flag[1] is false → condition false
P0: enters CS immediatelyNo waiting when there is no competition. This is what strict alternation could not do.
Case 2: Both want to enter at the same time
P0: flag[0] = true
P1: flag[1] = true
P0: turn = 1
P1: turn = 0 ← the LAST write to turn wins
P0: check (flag[1] && turn == 1) → turn is 0 → false → P0 ENTERS
P1: check (flag[0] && turn == 0) → true → P1 WAITS
P0: leaves, flag[0] = false
P1: check → flag[0] is false → P1 ENTERSBoth processes write to turn, but a variable holds only one value, so one write overwrites the other. Each process "gives the turn away", and the one who gives it away last is the one who waits. Whoever was more polite last, loses. That breaks the tie without deadlock.
Why Peterson's solution is correct
Mutual exclusion. Suppose both P0 and P1 are in the CS at the same time. Then both flags are true. Both processes wrote to turn before checking it; look at the one that wrote last, say P0, which wrote turn = 1. P1 had already set flag[1] = true before its own write to turn, which came earlier. So when P0 checked its loop condition after its write, it saw flag[1] == true and turn == 1 (nobody changes turn again until someone re-enters), and it must have kept waiting. That contradicts P0 being in the CS. The same argument works if P1 wrote last. So mutual exclusion holds.
Progress. A process waits only while the other has flag true and has the turn. If the other is in its remainder section, its flag is false, so it cannot block anyone. If both are waiting, turn is either 0 or 1, so one of the two loop conditions is false and that process enters. No deadlock.
Bounded waiting. Suppose P1 is waiting and P0 is in the CS. When P0 leaves, it sets flag[0] = false. If P0 immediately tries again, it first sets turn = 1, handing the turn to P1, and now P0 must wait. So P1 waits for at most one entry by P0. The bound is 1.
Our exhaustive state search agrees: in every reachable state of the two-process model, the two processes are never both in the critical section and there is no state where both are stuck.
A famous mistake: the order of the two lines matters
What if you write turn = j; before flag[i] = true;? It looks harmless. The state search found a schedule that breaks mutual exclusion:
P0: turn = 1
P1: turn = 0
P1: flag[1] = true
P1: check (flag[0] && turn == 0) → flag[0] false → P1 ENTERS
P0: flag[0] = true
P0: check (flag[1] && turn == 1) → turn is 0 → false → P0 ENTERS ← BOTH INSIDEA process must first announce its interest, and only then give the turn away.
Peterson's Solution on a Modern Computer
Here is the surprising part. Let's run Peterson's algorithm in C with two threads, using it to protect the same counter++ from the last chapter. This first version declares the shared variables volatile so the compiler does not keep them in registers:
#include <stdio.h>
#include <stdbool.h>
#include <pthread.h>
#define N 1000000
volatile bool flag[2] = {false, false};
volatile int turn = 0;
long counter = 0;
void *worker(void *arg)
{
int i = *(int *)arg; /* my id: 0 or 1 */
int j = 1 - i; /* the other thread */
for (int k = 0; k < N; k++) {
flag[i] = true; /* entry section */
turn = j;
while (flag[j] && turn == j)
; /* busy wait */
counter++; /* critical section */
flag[i] = false; /* exit section */
}
return NULL;
}
int main(void)
{
pthread_t t[2];
int id[2] = {0, 1};
for (int i = 0; i < 2; i++)
pthread_create(&t[i], NULL, worker, &id[i]);
for (int i = 0; i < 2; i++)
pthread_join(t[i], NULL);
printf("Expected: %d, Actual: %ld\n", 2 * N, counter);
return 0;
}$ gcc -std=c17 -Wall -pthread peterson_broken.c -o peterson_broken
$ ./peterson_broken
Expected: 2000000, Actual: 1984666
$ ./peterson_broken
Expected: 2000000, Actual: 1985029
$ ./peterson_broken
Expected: 2000000, Actual: 1996893It still loses updates, fewer than before but on every run (the exact numbers depend on timing and will differ on your machine). The algorithm is correct, so what went wrong?
The proof above assumed that each process's reads and writes happen in program order and are seen by the other process immediately. Modern CPUs do not promise that. To run fast, each core writes into a private store buffer first, and a later load of a different variable is allowed to complete before that store becomes visible to other cores. x86 permits exactly this "store followed by load" reordering; ARM permits even more. So this can happen:
Core 0: flag[0] = true (sits in core 0's store buffer, not yet visible)
Core 1: flag[1] = true (sits in core 1's store buffer, not yet visible)
Core 0: reads flag[1] → still sees false in memory → enters CS
Core 1: reads flag[0] → still sees false in memory → enters CS ← BOTH INSIDEvolatile stops the compiler from reordering or caching, but it does nothing about the CPU. The fix is to use C11 atomic variables. By default, atomic_store and atomic_load are sequentially consistent: the compiler inserts the needed memory barriers so that all threads see the operations in one agreed order.
#include <stdio.h>
#include <stdbool.h>
#include <stdatomic.h>
#include <pthread.h>
#define N 1000000
atomic_bool flag[2]; /* both start false */
atomic_int turn;
long counter = 0;
void *worker(void *arg)
{
int i = *(int *)arg;
int j = 1 - i;
for (int k = 0; k < N; k++) {
atomic_store(&flag[i], true); /* I want to enter */
atomic_store(&turn, j); /* but you go first */
while (atomic_load(&flag[j]) && atomic_load(&turn) == j)
; /* busy wait */
counter++; /* critical section */
atomic_store(&flag[i], false); /* I am done */
}
return NULL;
}
int main(void)
{
pthread_t t[2];
int id[2] = {0, 1};
for (int i = 0; i < 2; i++)
pthread_create(&t[i], NULL, worker, &id[i]);
for (int i = 0; i < 2; i++)
pthread_join(t[i], NULL);
printf("Expected: %d, Actual: %ld\n", 2 * N, counter);
return 0;
}$ gcc -std=c17 -Wall -pthread peterson.c -o peterson
$ ./peterson
Expected: 2000000, Actual: 2000000
$ ./peterson
Expected: 2000000, Actual: 2000000Now it is correct every time. The lesson: Peterson's solution is correct in theory, but on real hardware it needs memory barriers. That, plus the fact that it only works for two processes and wastes CPU time spinning, is why real systems use hardware-supported locks instead. Peterson's solution is still very important to learn, because it shows clearly what mutual exclusion, progress and bounded waiting mean, and it is a favourite exam and interview topic.
Other software solutions you may see in textbooks:
Dekker's algorithm (1960s) – the first known correct software solution for two processes; more complicated than Peterson's.
Lamport's Bakery algorithm – for n processes. Like a bakery token system: each process takes a number one larger than any number it sees, and the smallest number goes first (ties broken by process ID).
Hardware Support for Synchronization
All the software attempts failed or became complicated for one root reason: reading a value and then writing it are two separate steps, and another process can sneak in between. Hardware designers fixed this directly by adding instructions that read and write a memory word as one atomic (indivisible) step.
Option 0: Disabling Interrupts
On a single-CPU system, a running process can only lose the CPU because of an interrupt. So the kernel can disable interrupts before the critical section and enable them after. Nothing can preempt it in between.
This does not work in general:
On a multiprocessor, disabling interrupts on one CPU does not stop other CPUs from running and touching the same data.
It is a privileged operation; user programs are not allowed to do it (imagine a program disabling interrupts and never enabling them again).
While interrupts are off, the system cannot respond to the timer, disks or network, so it must be kept very short.
Kernels still use it for very short sections on the local CPU, usually together with other locks.
Option 1: Test-and-Set
The test_and_set instruction sets a boolean to true and returns its old value, atomically. Its meaning, written as a C function:
/* executed ATOMICALLY by the hardware */
bool test_and_set(bool *target) {
bool old = *target;
*target = true;
return old;
}A lock using it:
bool lock = false;
while (test_and_set(&lock)) /* old value true → someone has it: keep trying */
; /* old value false → it was free and is now mine */
/* critical section */
lock = false;Compare this with Attempt 1. The check and the set are now one instruction, so two processes cannot both see false: whoever executes test_and_set first gets false, and everyone after gets true until the lock is released.
Option 2: Compare-and-Swap (CAS)
compare_and_swap changes a value only if it still equals what we expect, and returns the old value, atomically:
/* executed ATOMICALLY by the hardware */
int compare_and_swap(int *value, int expected, int new_value) {
int old = *value;
if (*value == expected)
*value = new_value;
return old;
}int lock = 0;
while (compare_and_swap(&lock, 0, 1) != 0) /* change 0 → 1, or keep trying */
;
/* critical section */
lock = 0;CAS is more general than test-and-set. It is the building block of lock-free data structures and atomic counters: read the value, compute the new one, and CAS it in; if someone changed it in the meantime, the CAS fails and you retry.
Real instruction sets: on x86, XCHG (always atomic with memory) acts like test-and-set, and LOCK CMPXCHG is compare-and-swap. ARM uses a pair of instructions, load-exclusive and store-exclusive (LDXR/STXR), and newer ARM chips also have a direct CAS instruction. In C you never write these by hand; you use <stdatomic.h>, and the compiler picks the right instruction.
Atomic variables: the one-line fix for our counter
For a simple shared counter, you do not need a lock at all. An atomic fetch-and-add does the whole load-add-store as one hardware operation:
#include <stdio.h>
#include <stdatomic.h>
#include <pthread.h>
#define N 1000000
atomic_long counter = 0;
void *work(void *arg)
{
(void)arg;
for (int i = 0; i < N; i++)
atomic_fetch_add(&counter, 1); /* one indivisible read-modify-write */
return NULL;
}
int main(void)
{
pthread_t t1, t2;
pthread_create(&t1, NULL, work, NULL);
pthread_create(&t2, NULL, work, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("Expected: %d, Actual: %ld\n", 2 * N, atomic_load(&counter));
return 0;
}$ gcc -std=c17 -Wall -pthread atomic_counter.c -o atomic_counter
$ ./atomic_counter
Expected: 2000000, Actual: 2000000Looking at GCC's assembly for this program, the increment became a single lock addq $1, counter(%rip). The lock prefix makes the CPU perform the read-modify-write so that no other core can touch that memory location in between.
Atomic variables are perfect for single counters and flags. For anything bigger (updating two variables together, or a check-then-act like the bank example) you still need a lock around the whole critical section. That is the topic of the next chapter.
Bounded waiting with test-and-set
The simple test-and-set lock gives mutual exclusion and progress, but not bounded waiting: when the lock is released, any spinning process may grab it, and an unlucky one could lose every time. A well-known fix for n processes adds an array waiting[n]. When a process leaves, instead of just releasing the lock, it scans the other processes in cyclic order (i+1, i+2, ...) and hands the critical section directly to the first one that is waiting:
bool waiting[n]; /* all false */
bool lock = false;
/* process Pi */
waiting[i] = true;
bool key = true;
while (waiting[i] && key)
key = test_and_set(&lock);
waiting[i] = false;
/* critical section */
int j = (i + 1) % n;
while (j != i && !waiting[j]) /* find the next waiting process */
j = (j + 1) % n;
if (j == i)
lock = false; /* nobody waiting: release the lock */
else
waiting[j] = false; /* pass the CS directly to Pj (lock stays true) */A process enters either because test_and_set returned false (lock was free) or because the previous holder set its waiting[i] to false. Because the leaving process scans in cyclic order, any waiting process will get its turn within n − 1 entries by others. We model-checked this algorithm for three processes over every reachable state: no two processes were ever in the critical section together, and the system never got stuck.
Comparing the Solutions
Solution | Mutual exclusion | Progress | Bounded waiting | Processes | Busy waiting? |
|---|---|---|---|---|---|
Lock variable | No | Yes | No | n | Yes |
Strict alternation | Yes | No | Yes | 2 | Yes |
Peterson's solution | Yes | Yes | Yes | 2 | Yes |
Bakery algorithm | Yes | Yes | Yes | n | Yes |
Disabling interrupts | Single CPU only | Yes | No guarantee | n | No |
Test-and-set / CAS lock | Yes | Yes | No | n | Yes |
Test-and-set with | Yes | Yes | Yes (n − 1) | n | Yes |
Notice the last column. Every solution so far makes a waiting process spin in a loop, burning CPU time while doing nothing useful. This is called busy waiting. The next chapter, Mutex Locks & Semaphores, wraps these ideas in easy-to-use locks and shows how a waiting process can sleep instead of spinning.
Common Mistakes
Forgetting progress. Strict alternation guarantees mutual exclusion, so students often call it correct. It is not: an uninterested process can block the other.
Mixing up progress and bounded waiting. Progress: if the CS is free, someone must get in soon (no deadlock). Bounded waiting: every waiting process gets in eventually (no starvation).
Swapping
flag[i] = trueandturn = jin Peterson's code. This breaks mutual exclusion, as shown above.Writing
turn = iinstead ofturn = j. The process must give the turn to the other process. Withturn = i, a process can walk in while the other is already inside (our state search found such a schedule), so mutual exclusion breaks.Using Peterson's solution with plain variables in real code. On modern CPUs, it needs atomics or memory barriers. In practice, use the locks your OS or language provides.
Thinking disabling interrupts works on multicore. It only affects the current CPU.
Interview Questions
What is the critical section problem?
Designing entry and exit code so that processes sharing data never execute their critical sections at the same time, while also guaranteeing progress and bounded waiting.
What are the three requirements of a critical section solution?
Mutual exclusion (only one process in the CS), progress (if the CS is free and someone wants it, the choice of who enters cannot be postponed forever, and processes in their remainder sections take no part), and bounded waiting (a limit on how many times others can enter before a waiting process gets its turn).
Explain Peterson's solution.
Two processes share flag[2] and turn. To enter, Pi sets flag[i] = true, sets turn = j, and waits while flag[j] && turn == j. On exit it sets flag[i] = false. The flag shows interest; turn breaks ties, and whoever writes turn last waits.
Does Peterson's solution satisfy bounded waiting? What is the bound?
Yes. A waiting process waits for at most one entry by the other process, because the other process sets turn to the waiting one when it tries to re-enter.
Why does strict alternation fail?
It violates progress. Processes must alternate, so if one process is in its remainder section and does not want to enter, the other cannot enter even though the critical section is free.
Why is Peterson's solution not used in modern systems?
It works only for two processes, uses busy waiting, and modern CPUs and compilers can reorder memory operations, which breaks it unless memory barriers or atomic operations are added. Hardware-based locks are simpler and faster.
What is test-and-set? What is compare-and-swap?
Atomic hardware instructions. Test-and-set writes true to a variable and returns the old value. Compare-and-swap writes a new value only if the current value equals an expected value, and returns the old value. Both do a read and a write as one indivisible step, which makes simple locks possible.
Why can't user programs disable interrupts to get mutual exclusion?
It is a privileged instruction (a buggy or malicious program could hang the system), and on a multiprocessor it only affects one CPU, so it does not give mutual exclusion anyway.
Does a simple test-and-set lock satisfy bounded waiting?
No. When the lock is released, any spinning process may get it next, so one process can lose repeatedly. Adding a waiting[] array and handing the lock to the next waiting process in cyclic order gives a bound of n − 1.
Summary
Each process has an entry section, a critical section, an exit section and a remainder section. The critical section problem is about designing the entry and exit sections.
A correct solution needs mutual exclusion, progress and bounded waiting, with no assumptions about speed.
A lock variable fails mutual exclusion; strict alternation fails progress; flags alone can deadlock.
Peterson's solution combines
flag[]andturnand satisfies all three requirements for two processes, with a waiting bound of 1.On real hardware, Peterson's solution needs atomic operations / memory barriers; our
volatileversion lost updates, while the C11 atomic version was correct.Hardware provides atomic instructions such as test-and-set and compare-and-swap, and atomic variables, which make locks simple. All the solutions in this chapter use busy waiting.