Peterson Lock

Peterson’s algorithm for mutual exclusion between two threads

Overview

The PetersonLock class implements Peterson’s algorithm for mutual exclusion between exactly two threads (robots). It’s a classic software-based synchronization algorithm that guarantees mutual exclusion, progress, and bounded waiting without hardware support.

Constructor

PetersonLock · class

Creates a new Peterson lock for two participants (indexed 0 and 1).

const petersonLock = new PetersonLock();

Initial State:

• flag: [false, false]
• turn: 0
• owner: null

Properties

flag · Array<boolean>

Two-element array where flag[i] is true when robot i wants to enter the critical section.

turn · number

Indicates who yields in case of conflict (0 or 1). The robot that sets turn to the other robot’s ID is willing to wait.

owner · number | null

The robot ID (0 or 1) currently in the critical section, or null if no owner.

Methods

lock(i)

Attempts to acquire the lock for robot i.

i · number · required

The robot ID (0 or 1) attempting to acquire the lock.

return · boolean

• true: Robot successfully acquired the lock and can enter critical section
• false: Robot must wait (other robot has priority)

Peterson’s Algorithm:

1. Sets flag[i] = true to indicate intent to enter
2. Sets turn = other to give the other robot priority
3. Checks Peterson’s wait condition: flag[other] && turn === other
4. If condition is true, must wait (return false)
5. Otherwise, acquires lock and returns true

Source: petersonLock.js:13

// Example: Robot 0 trying to acquire lock
const acquired = petersonLock.lock(0);

if (acquired) {
  console.log('Robot 0 entered critical section');
  // Access shared resource
} else {
  console.log('Robot 0 must wait');
  // Try again later
}

unlock(i)

Releases the lock for robot i.

i · number · required

The robot ID (0 or 1) releasing the lock.

Behavior:

• Sets flag[i] = false to indicate robot no longer wants to enter
• Clears owner if this robot was the owner
• No return value (void)

Source: petersonLock.js:28

// Example: Robot 0 releasing lock
petersonLock.unlock(0);
console.log('Robot 0 exited critical section');

Usage Example

import { PetersonLock } from './core/petersonLock.js';

const lock = new PetersonLock();
const sharedStation = { resource: 0 };

// Robot 0 code
function robot0Code() {
  const acquired = lock.lock(0);
  
  if (!acquired) {
    console.log('Robot 0 waiting for station');
    return; // Try again later
  }
  
  // Critical section
  console.log('Robot 0 using station');
  sharedStation.resource += 1;
  
  // Exit critical section
  lock.unlock(0);
  console.log('Robot 0 released station');
}

// Robot 1 code
function robot1Code() {
  const acquired = lock.lock(1);
  
  if (!acquired) {
    console.log('Robot 1 waiting for station');
    return; // Try again later
  }
  
  // Critical section
  console.log('Robot 1 using station');
  sharedStation.resource += 1;
  
  // Exit critical section
  lock.unlock(1);
  console.log('Robot 1 released station');
}

Peterson’s Algorithm Explained

The algorithm ensures mutual exclusion through two mechanisms:

1. Intent Declaration (flag)

Each robot declares intent before trying to enter:

this.flag[i] = true; // "I want to enter"

2. Conflict Resolution (turn)

If both robots want to enter simultaneously, turn determines who waits:

this.turn = other; // "You can go first if you also want to enter"

3. Wait Condition

A robot must wait if:

• The other robot wants to enter (flag[other] === true)
• AND it’s the other robot’s turn (turn === other)

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

Correctness Properties

Mutual Exclusion

Only one robot can be in the critical section at a time.

Proof sketch: If both robots are in CS, both must have seen flag[other] === false or turn === self. But the last robot to set turn set it to other, so it would have waited.

Progress

If no robot is in the critical section and one wants to enter, it will eventually enter.

Proof sketch: If only one robot wants to enter (flag[0] = true, flag[1] = false), the wait condition flag[other] && turn === other is false, so it enters immediately.

Bounded Waiting

A robot waiting to enter will enter before the other robot enters twice.

Proof sketch: After robot 0 enters and exits, it sets flag[0] = false. If robot 1 is waiting, it will enter next. Even if robot 0 wants to re-enter, it will set turn = 1, giving robot 1 priority.

Timeline Example

const lock = new PetersonLock();
// State: flag = [false, false], turn = 0

// Robot 0 tries to enter
lock.lock(0);
// flag[0] = true, turn = 1
// flag[1] === false → enters immediately
// State: flag = [true, false], turn = 1, owner = 0
// Returns: true

// Robot 1 tries to enter (while 0 is in CS)
lock.lock(1);
// flag[1] = true, turn = 0  
// flag[0] === true && turn === 0 → must wait
// State: flag = [true, true], turn = 0, owner = 0
// Returns: false

// Robot 0 exits
lock.unlock(0);
// flag[0] = false, owner = null
// State: flag = [false, true], turn = 0

// Robot 1 tries again
lock.lock(1);
// flag[1] = true (already true), turn = 0
// flag[0] === false → enters immediately  
// State: flag = [false, true], turn = 0, owner = 1
// Returns: true

Race Conditions Handled

Both try to enter simultaneously:

// Robot 0:                      Robot 1:
flag[0] = true;                 flag[1] = true;
turn = 1;                       turn = 0;
// Checks: flag[1] && turn==1   // Checks: flag[0] && turn==0
// → TRUE, waits                // → FALSE, enters!

The robot that sets turn last gets to enter (its competitor sees the updated turn value).

Limitations

1. Two threads only: Peterson’s algorithm works for exactly 2 participants
2. Busy waiting: The waiting robot repeatedly checks the condition (no blocking)
3. Memory model assumptions: Requires sequential consistency (modern CPUs may need memory barriers)

Busy-Wait Pattern

In a real implementation, the calling code would retry in a loop:

// Busy-wait loop (not recommended for production)
while (!lock.lock(robotId)) {
  // Spin - repeatedly try to acquire
}

// Critical section
accessSharedResource();

// Release
lock.unlock(robotId);

In the simulator, this is handled by the thread scheduler - threads are blocked and resumed rather than spinning.

Comparison with Mutex

Feature	PetersonLock	Mutex
Participants	Exactly 2	Any number
Waiting	Busy-wait (active)	Queue (passive)
Hardware support	None required	May use atomic operations
Fairness	Alternation guaranteed	FIFO queue
Use case	Educational/embedded	General purpose

Educational Value

Peterson’s algorithm demonstrates:

• Software-only synchronization is possible
• The importance of memory ordering
• How to reason about concurrent algorithms
• Classic mutual exclusion problem solving

It’s primarily used for teaching concurrency concepts rather than production systems.