Peterson's Algorithm

Software-only mutual exclusion for exactly two threads using shared memory

Overview

Peterson’s Algorithm is a classic software-based solution for mutual exclusion between exactly two threads. Unlike mutexes and semaphores which typically rely on hardware primitives, Peterson’s algorithm achieves synchronization using only shared memory reads and writes.

When to Use Peterson’s Algorithm

Educational Purpose

Understanding fundamental principles of concurrent programming

Two-Thread Systems

Systems with exactly two competing threads (no more, no less)

Hardware Constraints

Platforms without atomic hardware instructions

Historical Study

Learning the evolution of synchronization algorithms

Modern Usage: Peterson’s algorithm is rarely used in modern systems due to memory ordering issues on contemporary processors. Modern systems use hardware-supported primitives (atomic operations, mutexes). This implementation is for educational purposes.

How It Works

Peterson’s algorithm uses two shared variables:

• flag[2]: Array indicating each thread’s intent to enter critical section
• turn: Indicates which thread has priority when both want to enter

Algorithm Logic

1. Declare Intent

   Thread i sets flag[i] = true to show it wants to enter

2. Yield Priority

   Thread i sets turn = other to give the other thread priority

3. Check Condition

   Thread i waits while flag[other] && turn == other

4. Enter Critical Section

   If condition false, thread enters critical section

5. Exit

   Thread sets flag[i] = false when done

Implementation

Here’s the complete Peterson’s lock implementation from the simulator:

source/js/core/petersonLock.js

// Algoritmo de Peterson para exclusion mutua de 2 hilos/robots.
export class PetersonLock {
  constructor() {
    // flag[i] = true cuando el robot i quiere entrar a seccion critica.
    this.flag = [false, false];
    // turn define quien cede paso en caso de conflicto.
    this.turn = 0;
    // Para visualizacion: dueño actual de la estacion.
    this.owner = null;
  }

  // Intenta tomar lock para robot i (0 o 1). Devuelve true si puede entrar.
  lock(i) {
    const other = 1 - i;
    this.flag[i] = true;
    this.turn = other;

    // Condicion de espera activa de Peterson.
    if (this.flag[other] && this.turn === other) {
      return false;
    }

    this.owner = i;
    return true;
  }

  // Libera lock del robot i.
  unlock(i) {
    this.flag[i] = false;
    if (this.owner === i) this.owner = null;
  }
}

Lock Operation

The lock() method implements Peterson’s entry protocol:

Step 1: Identify other thread (line 14)

Calculate the other thread’s index:

const other = 1 - i;
// If i=0, other=1
// If i=1, other=0

Step 2: Declare intent (line 15)

Set flag to indicate this thread wants to enter:

this.flag[i] = true;

This tells the other thread: “I want the critical section”

Step 3: Yield priority (line 16)

Give priority to the other thread:

this.turn = other;

This implements politeness: “You can go first if you also want in”

Step 4: Check condition (lines 18-21)

Wait if both conditions are true:

if (this.flag[other] && this.turn === other) {
  return false; // Must wait
}

Logic: Wait only if:

• Other thread also wants in (flag[other] == true)
• AND other thread has priority (turn == other)

Step 5: Enter critical section (lines 23-24)

If condition is false, thread can enter:

this.owner = i;
return true;

Unlock Operation

The unlock() method implements the exit protocol:

source/js/core/petersonLock.js

unlock(i) {
  this.flag[i] = false;
  if (this.owner === i) this.owner = null;
}

Simple: Just set flag to false, indicating the thread no longer wants the critical section.

Why It Works

Let’s analyze the three key scenarios:

Scenario 1: No contention - one thread wants in

// Thread 0 wants in, Thread 1 doesn't
flag[0] = true;  // Thread 0 declares intent
turn = 1;        // Thread 0 yields to Thread 1

// Check: flag[1] && turn == 1?
// flag[1] is false (Thread 1 not interested)
// → Condition false, Thread 0 enters immediately

Result: Thread 0 enters without waiting.

Scenario 2: Both threads want in - no race

// Thread 0 executes first
flag[0] = true;
turn = 1;
// Check: flag[1] && turn == 1?
// flag[1] still false → Thread 0 enters

// Thread 1 executes later
flag[1] = true;
turn = 0;
// Check: flag[0] && turn == 0?
// flag[0] is true AND turn is 0
// → Thread 1 must wait

Result: First thread enters, second thread waits.

Scenario 3: Both threads want in - race condition

// Both threads execute simultaneously
flag[0] = true;  // Thread 0
flag[1] = true;  // Thread 1
turn = 1;        // Thread 0 sets turn
turn = 0;        // Thread 1 sets turn (overwrites!)

// Thread 0 checks: flag[1] && turn == 1?
// flag[1] is true, but turn is 0 (not 1)
// → Thread 0 enters

// Thread 1 checks: flag[0] && turn == 0?
// flag[0] is true AND turn is 0
// → Thread 1 waits

Result: The thread that writes turn last waits. The other enters.

Key insight: The turn variable acts as a tiebreaker. When both threads want in, whoever writes to turn last will wait. This guarantees mutual exclusion.

Proof of Correctness

Mutual Exclusion: At most one thread in critical section

Proof by contradiction:
Assume both Thread 0 and Thread 1 are in critical section.

For Thread 0 to enter:
  NOT (flag[1] && turn == 1)
  → Either flag[1] == false OR turn == 0

For Thread 1 to enter:
  NOT (flag[0] && turn == 0)
  → Either flag[0] == false OR turn == 1

But we know both flag[0] and flag[1] are true (both declared intent).
Therefore:
  Thread 0 entered means turn == 0
  Thread 1 entered means turn == 1
  
Contradiction! turn cannot be both 0 and 1.
Therefore, both cannot be in critical section.

Progress: If no thread in critical section, one will eventually enter

Bounded Waiting: A waiting thread will enter in finite time

Usage Example: Robot Station

The Peterson scenario demonstrates two robots sharing a station:

Scenario setup

import { PetersonLock } from "../core/petersonLock.js";
import { Thread } from "../core/thread.js";
import { Instructions } from "../core/instructions.js";

const lock = new PetersonLock();

const station = {
  lock,
  usageCount: [0, 0],
  totalUses: 0,
};

// Create exactly 2 robot threads
for (let i = 0; i < 2; i++) {
  const instructions = [];
  for (let c = 0; c < cycles; c++) {
    instructions.push({ type: Instructions.PETERSON_LOCK });
    instructions.push({ type: Instructions.USE_STATION, cycle: c + 1 });
    instructions.push({ type: Instructions.PETERSON_UNLOCK });
  }
  instructions.push({ type: Instructions.END });
  
  const robot = new Thread(`Robot-${i + 1}`, instructions);
  robot.petersonId = i; // 0 or 1
  engine.addThread(robot);
}

Execution Timeline

Let’s trace two robots competing for the station:

Busy Waiting vs Blocking

Peterson’s algorithm uses busy waiting (spin lock):

// Busy waiting in Peterson's
while (flag[other] && turn === other) {
  // Keep checking condition
}

In the simulator:

if (this.flag[other] && this.turn === other) {
  return false; // Thread will retry on next step
}

Comparison: Busy waiting vs Blocking

Aspect	Peterson’s (Busy Wait)	Mutex (Blocking)
CPU usage	High (constantly checking)	Low (thread sleeps)
Latency	Low (no context switch)	Higher (context switch overhead)
Fairness	Guaranteed by algorithm	Guaranteed by FIFO queue
Scalability	Poor (>2 threads)	Good (N threads)
Best for	Short critical sections	Long critical sections

Limitations

Exactly Two Threads: Peterson’s algorithm only works for exactly 2 threads. For N threads, you need generalized algorithms or hardware primitives.

Memory Ordering: On modern processors with weak memory models, Peterson’s algorithm requires memory barriers to work correctly. Simple reads/writes may be reordered by the CPU or compiler.

// Modern C++ would need:
flag[i].store(true, std::memory_order_seq_cst);
turn.store(other, std::memory_order_seq_cst);

Busy Waiting: Wastes CPU cycles spinning. Not suitable for long critical sections or systems with limited CPU resources.

Peterson’s Algorithm Invariants

The algorithm maintains these invariants:

1. Mutual Exclusion

   At most one thread can hold the lock at any time

2. Progress

   If a thread wants the lock and no one holds it, it will acquire it

3. Bounded Waiting

   A thread will not wait forever if the other thread eventually exits

4. Flag Semantics

   flag[i] == true means thread i wants to enter (or is in) critical section

5. Turn Semantics

   turn == i means thread i has priority when both want to enter

Visualizing Peterson’s Algorithm

In the simulator, you can observe:

• Flag status: Visual indicators for flag[0] and flag[1]
• Turn indicator: Which robot has priority
• Station owner: Which robot is currently using the station
• Busy waiting: Robot repeatedly checking condition
• Usage counts: How many times each robot used the station

Historical Context

Gary Peterson published this algorithm in 1981. It was groundbreaking because:

• Simpler than earlier algorithms (Dekker’s algorithm, 1965)
• Proved mutual exclusion possible with only loads and stores
• Influenced development of memory models in concurrent programming

Dekker’s Algorithm (1965) was the first solution but more complex:

// Dekker's has 3 shared variables vs Peterson's 2
flag[2], turn, and additional logic

Filter Algorithm (generalization to N threads) followed Peterson’s work.

Common Pitfalls

Wrong Thread ID: Using the same ID for both threads causes both to compete for flag[0]:

// WRONG
robot1.petersonId = 0;
robot2.petersonId = 0; // Should be 1!

Forgot to Unlock: If a thread locks but never unlocks, the other thread waits forever:

lock.lock(0);
// ... use station ...
// Forgot lock.unlock(0)!

Three or More Threads: Peterson’s algorithm does not generalize to 3+ threads without modification:

// WRONG: Adding third thread
const robot3 = new Thread("Robot-3");
robot3.petersonId = 2; // Won't work!

Related Scenarios

Robot Station (Peterson)

Two robots sharing a workstation using Peterson’s algorithm for mutual exclusion

Key Takeaways

1. Software-Only

   Achieves mutual exclusion using only loads and stores, no hardware atomics

2. Two Threads Only

   Designed for exactly 2 threads, does not scale to more

3. Flag + Turn

   Uses flags for intent and turn for priority/tiebreaking

4. Busy Waiting

   Spins while waiting, consuming CPU cycles

5. Educational Value

   Teaches fundamental concepts but rarely used in modern systems

6. Memory Ordering

   Requires memory barriers on modern hardware with weak memory models

See Also

• Mutex - Modern alternative with blocking and N threads
• Semaphores - Counting version for resource pools
• Barriers - Synchronization points for multiple threads