Robot Station Scenario

Two robots sharing a workstation using Peterson’s algorithm

Overview

The Robot Station scenario simulates two robots that need to use a shared workstation to process parts. This demonstrates Peterson’s Algorithm, a classic software-only solution for mutual exclusion between exactly two threads without hardware support.

Real-World Problem

Consider a manufacturing setup where:

• Two robots need to use the same precision workstation
• Only one robot can use the station at a time
• No hardware locks available, must coordinate in software
• Both robots need multiple cycles of access

Peterson’s Algorithm solves this using only shared memory and two primitive operations: read and write.

Shared Resources

The shared resources are:

• Workstation - Can only be used by one robot at a time
• Peterson Lock - Software lock using flags and turn variable
• Usage statistics - Tracks how many times each robot used the station

Protected by: Peterson’s Algorithm (mutual exclusion protocol)

Synchronization Algorithm

Peterson’s Algorithm uses two arrays and one turn variable:

1. Announce Intent

   Robot sets its flag to indicate it wants to enter the critical section

2. Yield Turn

   Robot sets turn variable to the OTHER robot’s ID (polite behavior)

3. Wait for Access

   Robot busy-waits while: (other robot’s flag is set AND it’s the other robot’s turn)

4. Enter Critical Section

   When condition is false, robot safely enters and uses the workstation

5. Exit and Clear Flag

   Robot finishes work and clears its flag, allowing the other robot to enter

Scenario Setup

petersonScenario.js

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

export function createPetersonScenario(engine, cyclesPerRobot) {
  const cycles = Math.max(1, Number(cyclesPerRobot) || 1);
  const lock = new PetersonLock();

  const station = {
    lock,
    usageCount: [0, 0],  // Track usage for each robot
    totalUses: 0,
  };

  // Peterson's algorithm requires exactly 2 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;  // Critical: 0 or 1 for Peterson's algorithm
    engine.addThread(robot);
  }

  return { station };
}

Configuration Options

Parameter	Description	Default
cyclesPerRobot	Number of times each robot uses the station	Minimum 1

Peterson’s Algorithm is designed for exactly 2 threads. The scenario always creates 2 robots regardless of configuration. Generalizing to N threads requires different algorithms (like Lamport’s Bakery Algorithm).

Peterson’s Algorithm Pseudocode

Shared variables:
  flag[2] = {false, false}  // Interest flags
  turn = 0                   // Whose turn is it?

Thread i (where i = 0 or 1):
  j = 1 - i  // Other thread's ID
  
  // Entry protocol
  flag[i] = true      // I want to enter
  turn = j            // But you can go first
  while (flag[j] && turn == j) {
    // Busy wait
  }
  
  // Critical section
  use_workstation()
  
  // Exit protocol
  flag[i] = false     // I'm done

Example Execution Flow

3 Cycles Per Robot

Initial: flag[0]=false, flag[1]=false, turn=0

Time 0:
  Robot-1 (id=0): flag[0]=true, turn=1
  Robot-1: Check flag[1]=false → ENTER
  Robot-2 (id=1): flag[1]=true, turn=0
  Robot-2: Check flag[0]=true AND turn=0 → WAIT

Time 1:
  Robot-1: USE_STATION (cycle 1)
  Robot-2: Still waiting...

Time 2:
  Robot-1: flag[0]=false (unlock)
  Robot-2: Check flag[0]=false → ENTER

Time 3:
  Robot-2: USE_STATION (cycle 1)
  Robot-1: flag[0]=true, turn=1
  Robot-1: Check flag[1]=true AND turn=1 → WAIT

Time 4:
  Robot-2: flag[1]=false (unlock)
  Robot-1: ENTER → USE_STATION (cycle 2)

Time 5:
  Robot-1: flag[0]=false
  Robot-2: flag[1]=true, turn=0 → ENTER
  Robot-2: USE_STATION (cycle 2)

... (pattern continues)

Final:
  Robot-1 usage: 3
  Robot-2 usage: 3
  Total: 6

Thread Instructions

Each robot thread executes (repeated for each cycle):

1. PETERSON_LOCK - Execute Peterson’s entry protocol
2. USE_STATION - Use the workstation (critical section)
3. PETERSON_UNLOCK - Execute Peterson’s exit protocol
4. After all cycles: END - Terminate thread

Why Peterson’s Algorithm Works

Mutual Exclusion

Proof by contradiction:
If both in critical section, both must have seen:
  flag[other]=false OR turn!=other
  
But last write to 'turn' can only be one value.
Contradiction! ✗

Progress (Deadlock-Free)

If Robot-1 wants in and Robot-2 doesn't:
  flag[1]=false → Robot-1 enters immediately
  
If both want in:
  turn has a value → one proceeds

Bounded Waiting (Starvation-Free)

If Robot-1 waiting:
  flag[0]=true and turn=1
  When Robot-2 exits: flag[1]=false
  Robot-1 immediately enters (no further waiting)

Comparison with Hardware Solutions

Aspect	Peterson’s	Mutex (Hardware)
Hardware Support	None needed	Atomic instructions
Thread Count	Exactly 2	Arbitrary
Performance	Busy-waiting	Can sleep/wake
Complexity	Moderate	Simple API
Portability	Requires memory ordering	Hardware-dependent

Key Learning Points

• Software-Only Solution: No special hardware instructions needed
• Two Threads Only: Algorithm designed specifically for N=2
• Busy-Waiting: Threads actively check flag in a loop (spinlock)
• Memory Ordering: Requires proper memory fence/barrier in real systems
• Historical Significance: Proves mutual exclusion possible without hardware
• Fairness: The “turn” variable prevents starvation

Modern Considerations

Important: Peterson’s Algorithm relies on sequential consistency of memory operations. On modern processors with out-of-order execution and caching, you need memory barriers to ensure correctness. Most production code uses hardware-supported primitives instead.

Common Issues

Compiler Optimization

// Compiler might optimize:
while (flag[j] && turn == j) { }

// Into:
if (flag[j] && turn == j) {
  while(true) { }  // Infinite loop!
}

// Solution: Use volatile or memory barriers

Educational Value

Peterson’s Algorithm is rarely used in production but is pedagogically valuable:

• Demonstrates that mutual exclusion is possible in software
• Shows the complexity of lock-free programming
• Illustrates memory model considerations
• Provides foundation for understanding modern synchronization
• Proves that hardware atomics are not strictly necessary

Extensions

Algorithm	Threads	Fairness
Peterson’s	2	Fair
Filter Lock	N	Fair (FIFO)
Bakery Algorithm	N	Fair (ticket-based)
Tournament Tree	N (power of 2)	Fair