Synchronisation: critical section, Peterson, semaphores and monitors
Race conditions, critical section requirements, Peterson's mutual exclusion proved, test-and-set and CAS, semaphores, producer and consumer, monitors.
When several threads or processes access the same data, the result can depend on the unpredictable order in which their instructions interleave. These are the hardest bugs to find: they appear once in a million runs and disappear when a debug print is added. In this lesson we look at race conditions, the requirements of a critical section, Peterson’s algorithm with the proof of mutual exclusion, atomic instructions, semaphores with the producer-consumer problem, and monitors.
The race condition
The C statement counter++ looks indivisible, but the processor executes it in three steps: it reads the value from memory into a register, increments it, writes it back. If two threads execute it together starting from 5:
| Thread A | Thread B | counter |
|---|---|---|
| reads 5 | 5 | |
| reads 5 | 5 | |
| writes 6 | 6 | |
| writes 6 | 6 |
Two increments, but the counter is 6: one has been lost. This is a race condition. Two threads each performing a million increments on a multicore almost always end with less than two million, and with a different value on every run.
The critical section
The code that accesses shared data is a critical section. A correct solution must guarantee:
- mutual exclusion: at most one thread at a time in the critical section;
- progress: if nobody is in the critical section and someone wants to enter, the decision cannot be postponed forever;
- bounded waiting: a thread asking to enter succeeds after a bounded number of entries by the others.
Peterson’s algorithm
For two threads, 0 and 1, two shared variables suffice: flag[i] is true when thread i wants to enter, turn indicates who must give way.
/* code of thread i; j = 1 - i is the other */
flag[i] = true; /* I want to enter */
turn = j; /* but I give way to the other */
while (flag[j] && turn == j)
; /* wait */
/* critical section */
flag[i] = false; /* leave */Theorem. Peterson’s algorithm guarantees mutual exclusion.
Proof. Suppose, for contradiction, that both threads are in the critical section. Then flag[0] and flag[1] are both true, because each set it to true before entering and resets it to false only on leaving. Consider the last thread that wrote turn, for example thread 1, which wrote turn = 0. From that moment turn is 0 and flag[0] is true, so the loop condition of thread 1, flag[0] && turn == 0, is true: thread 1 cannot have passed the loop after its write. But the loop comes after the write in its code: contradiction. The same holds with the roles swapped. ∎
Progress and bounded waiting can also be proved. On modern processors, however, the algorithm works only with memory barriers, because the processor and the compiler may reorder reads and writes to different addresses (lesson on multicore systems): it is a teaching idea, not a practical tool.
Atomic instructions
Processors offer instructions that read and modify a memory word indivisibly:
- test-and-set: writes true and returns the previous value;
- compare-and-swap (CAS): writes a new value only if the current one equals an expected value, and reports whether it succeeded.
With these a spinlock is built: a thread repeats test-and-set until it gets the value false. It is fine for very short critical sections on multicore; otherwise it wastes CPU, and it is better for the thread to block and yield the processor.
Semaphores
A semaphore (Dijkstra, 1965) is an integer with two atomic operations:
- wait (or P): if the value is positive it decrements it, otherwise it blocks the thread until it becomes positive;
- signal (or V): increments the value and wakes a waiting thread, if any.
A semaphore initialised to 1 is a mutex: wait before the critical section, signal after. A semaphore initialised to 
counts available resources.
Producer and consumer. A producer puts items into a circular buffer of slots, a consumer takes them out. Three semaphores are needed: e counts empty slots (initially ), f full slots (initially 0), m protects the indices (initially 1).
/* producer */ /* consumer */
wait(e); wait(f);
wait(m); wait(m);
buf[i] = x; i = (i+1) % N; y = buf[j]; j = (j+1) % N;
signal(m); signal(m);
signal(f); signal(e);The producer blocks on e when the buffer is full, the consumer on f when it is empty. The order of the waits matters: if the producer did wait(m) before wait(e) and found the buffer full, it would block while holding m, and the consumer could no longer enter to free a slot. This is a deadlock (lesson on deadlock).
Monitors
Semaphores are powerful but easy to get wrong: a forgotten or swapped wait breaks everything. Modern languages offer higher-level constructs. A monitor groups shared data and procedures, with the guarantee that only one thread at a time executes a procedure; to wait for a condition inside the monitor, condition variables are used, with the operations wait (which releases the monitor while waiting) and signal. In Java every object is a monitor (synchronized, wait, notify); in C and C++ the mutexes and condition variables of the thread library are used.
An alternative is to avoid sharing: lock-free data structures based on compare-and-swap, or threads that share nothing and communicate only by messages, as in the Go and Erlang languages.
