Peterson's Solution to Race Conditions
Table of Contents
In the last couple of posts, I’ve discussed race conditions and what causes them, in pursuit of understanding multithreading.
Today, I want to look at an old solution to this problem: Peterson’s Algorithm. But first, let’s understand why our “obvious” solutions don’t actually work.
What’s a Critical Section?
A critical section is any part of code where shared data might be accessed while being concurrently modified by multiple threads.
Let’s understand this by looking at code:
#define ITERATIONS 1000000
long counter = 0;
void *increment(void *arg) {
for (long i = 0; i < ITERATIONS/2; i++) {
// Critical section
counter++;
}
return NULL;
}
Here, counter++ is the critical section. Multiple threads are trying to increment the same variable at the same time.
Even counter++ is not atomic. It takes multiple CPU instructions to complete, and the CPU can interrupt execution at any point and switch to another thread.
For example, the CPU might interrupt counter++ before the increment is stored and switch to another thread:
- Thread 1 gets interrupted mid-increment (computed value but not stored)
- Thread 2 increments the counter successfully
- Thread 1 resumes and stores its outdated value
- Counter increases once instead of twice
This happens unpredictably, and the result varies every time I run the program.
Just add another variable
The first approach I tried was to use another variable to prevent the second thread from incrementing the counter while the first thread is still incrementing it.
#define ITERATIONS 1000000
long counter = 0;
bool is_safe = true;
void *increment(void *arg) {
for (long i = 0; i < ITERATIONS/2; i++) {
while (!is_safe); // Wait until safe
is_safe = false; // Claim the lock
counter++; // Critical section
is_safe = true; // Release the lock
}
return NULL;
}
Here’s what I’m trying to do: prevent the second thread from incrementing while the first thread is still in the critical section. The counter can’t be incremented while is_safe is false, so the second thread waits.
Hey Claude fix all problems in my life
The is_safe variable is shared by all threads, we’re just moving the problem somewhere else.
Let’s look at the assembly code generated by the compiler:
; while (!is_safe);
.L3:
movzx eax, BYTE PTR [is_safe] ; load is_safe
xor eax, 1 ; negate
test al, al ; check if zero
jne .L3 ; loop if not safe
; is_safe = false;
mov BYTE PTR [is_safe], 0
; is_safe = true;
mov BYTE PTR [is_safe], 1
See the problem? These are not atomic operations.
Here’s what can happen:
| Time | Thread 1 | Thread 2 | is_safe |
|---|---|---|---|
| t1 | movzx eax, [is_safe] (eax=1) | true | |
| t2 | INTERRUPTED (eax still 1) | movzx eax, [is_safe] (ebx=1) | true |
| t3 | xor eax, 1 (ebx=0) | true | |
| t4 | jne .L3 (loop exits) | true | |
| t5 | mov [is_safe], 0 | false | |
| t6 | counter++ (in critical section) | false | |
| t7 | INTERRUPTED | false | |
| t8 | xor eax, 1 (eax=0) | false | |
| t9 | jne .L3 (loop exits!) | false | |
| t10 | counter++ (in critical section!) | false |
Two threads in the critical section at the same time. Race condition still happens.
Peterson’s Algorithm
Peterson’s algorithm is a classic solution for two threads that uses only shared memory (no hardware support):
int turn; // 0 if thread_0's turn, 1 if thread_1's turn
bool flag[2]; // flag[i]==true if thread_i wants to enter[1]
// Thread i's code:
flag[i] = true; // I want to enter
turn = j; // Give priority to other thread
while (flag[j] && turn == j); // Wait if other wants entry AND has priority
// Critical section here
flag[i] = false; // I'm done
By setting turn = j first, each thread gives priority to the other. If both want to enter, the one who set turn last will wait, ensuring only one enters.
Optimizations
This looks perfect, but we’re still not done. If we run the program with Peterson’s algorithm, we’ll still not get the correct result.
Our enemies: Optimizations.
Two Types of Optimizations That Break Peterson’s
| Type | What It Does | How It Breaks Peterson’s |
|---|---|---|
| Compiler optimizations | Rearranges instructions for performance | May swap flag[i] = true and turn = j |
| CPU optimizations | Executes out of order (store buffers, load forwarding) | flag[i] = true not visible to other thread immediately |
Compiler Optimizations
When we write code, each statement expands to multiple CPU instructions, and the compiler may rearrange them:
// Original order:
flag[i] = true;
turn = j;
// Compiler might change to:
turn = j; // Set turn first
flag[i] = true; // Then set flag
This breaks Peterson’s algorithm because turn is set before the flag. The other thread might see turn == j but flag[j] == false, and both threads enter the critical section.
CPU Optimizations
Disabling compiler optimizations doesn’t solve the problem. The CPU itself may reorder instructions:
Modern CPUs use techniques like:
- Store buffers: Writes might be delayed before becoming visible
- Load forwarding: Reads might get stale values from buffers
- Memory reordering: Instructions execute out of order
This means even if the compiler doesn’t reorder, the CPU might, and flag[i] = true might not be visible to the other thread immediately.
What I Learned
| Takeaway | Explanation |
|---|---|
| But requires many assumptions | No compiler reordering, no CPU reordering |
| Simple flags don’t work | is_safe = false is still shared memory |
Peterson’s algorithm is a beautiful theoretical solution, but in practice, it depend on too many assumptions to work on modern computers