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.

Note

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:

  1. Thread 1 gets interrupted mid-increment (computed value but not stored)
  2. Thread 2 increments the counter successfully
  3. Thread 1 resumes and stores its outdated value
  4. 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:

TimeThread 1Thread 2is_safe
t1movzx eax, [is_safe] (eax=1)true
t2INTERRUPTED (eax still 1)movzx eax, [is_safe] (ebx=1)true
t3xor eax, 1 (ebx=0)true
t4jne .L3 (loop exits)true
t5mov [is_safe], 0false
t6counter++ (in critical section)false
t7INTERRUPTEDfalse
t8xor eax, 1 (eax=0)false
t9jne .L3 (loop exits!)false
t10counter++ (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

TypeWhat It DoesHow It Breaks Peterson’s
Compiler optimizationsRearranges instructions for performanceMay swap flag[i] = true and turn = j
CPU optimizationsExecutes 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

TakeawayExplanation
But requires many assumptionsNo compiler reordering, no CPU reordering
Simple flags don’t workis_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