BCS401 Operating System Semester IV · AY 2025-26 onward
Unit 2 · Concurrent Processes

Lecture 5: Peterson’s solution

Back to contents ← Previous Next →

Learning outcomes

  • Describe Peterson’s algorithm for mutual exclusion and reason about its correctness.
Lecture Notes

Main content

Learning Outcomes
  • Write Peterson’s algorithm using flag[2] and turn.
  • Explain the meaning of flag and turn in the protocol.
  • Justify (idea level) how the algorithm satisfies mutual exclusion, progress, and bounded waiting.
  • Identify limitations: busy waiting and why classic software-only algorithms are mainly for conceptual understanding.

Prerequisites

  • Critical Section Problem: mutual exclusion, progress, bounded waiting.
  • Race condition idea: shared data becomes incorrect if updated concurrently.
  • Understanding that processes can be interleaved unpredictably due to scheduling/interrupts.

Notes

1) Context and scope

Peterson’s solution is a classic software-based solution to the critical-section problem. It is restricted to two processes (P0 and P1) that alternate between their critical sections and remainder sections. For process Pi, we denote the other process as Pj, where j = 1 − i.

2) Shared variables used

Shared data items

  • boolean flag[2]: flag[i] = true means Pi is ready to enter its critical section.
  • int turn: indicates whose turn it is to enter the critical section (tie-breaker).

Meaning (must remember)

  • flag = intention (“I want to enter”).
  • turn = tie-break when both intend to enter.
The “gate condition” (easy memory)

A process waits only when: (other is interested) AND (it is the other’s turn).
In code: while (flag[j] && turn == j) { /* wait */ }

3) Peterson’s algorithm (standard pseudocode)

// Shared variables:
boolean flag[2] = {false, false};
int turn = 0;

// Code for process Pi (i = 0 or 1), where j = 1 - i
do {
  flag[i] = true;     // I want to enter the critical section
  turn = j;           // give the other process priority

  while (flag[j] && turn == j) {
    ;                 // busy wait (spin)
  }

  // -------- critical section --------

  flag[i] = false;    // I am leaving the critical section

  // -------- remainder section --------
} while (true);
Fig 5.1: Peterson’s entry protocol (for process Pᵢ) Declare intent → give turn to other → wait only if other wants in AND has the turn. 1) flag[i] = true 2) turn = j “Let the other go first if needed” 3) while (flag[j] && turn==j) wait (busy spin) Critical Section flag[i] = false exit protocol
Peterson’s solution uses two intent flags and one turn variable to control entry to the critical section.

4) Scenario walkthrough (both try to enter at the same time)

Suppose P0 and P1 attempt to enter together:

  1. P0 sets flag[0]=true and then sets turn=1.
  2. P1 sets flag[1]=true and then sets turn=0.
  3. turn is a single shared variable, so only the last write remains.
  4. If the last value becomes turn=0, then P1 waits (because turn==0 and flag[0]==true), while P0 enters.
  5. If the last value becomes turn=1, then P0 waits, while P1 enters.

Result: exactly one process enters first; the other waits at the gate and enters after the first clears its flag.

5) Why Peterson satisfies the three requirements (exam-ready points)

Mutual Exclusion

  • If both are interested (flag[0]=flag[1]=true), only one can pass because turn can hold only one value.
  • The process that does not have the other’s turn proceeds; the other remains in the while loop.

Progress

  • If only one process wants to enter, it does not wait (the other’s flag is false).
  • If both want to enter, the turn mechanism ensures one is selected (no indefinite postponement).

Bounded Waiting

  • Each process gives priority to the other by setting turn=j.
  • After a process exits (sets flag[i]=false), the waiting process can proceed, preventing starvation in the two-process case.
Limitation (must mention)
  • Busy waiting: the waiting process spins and wastes CPU cycles.
  • Modern CPUs/compilers may reorder memory operations; classic Peterson logic is taught for algorithmic understanding, while real systems use hardware-supported synchronization primitives.

Worked Example

Shared counter update protected by Peterson’s solution (concept)

Two processes update a shared variable count. The update must be inside the critical section.

Critical section example

// shared
int count = 0;

// critical section (protected by Peterson entry gate)
count = count + 1;

What Peterson ensures

  • Only one process executes count = count + 1 at a time.
  • No lost updates due to unsafe interleavings.
  • The other process waits at the gate condition and enters after exit.

One-Page Summary

  • Peterson’s solution is a classic software-only mutual exclusion algorithm for two processes.
  • Shared variables: flag[2] (intent) and turn (tie-breaker).
  • Entry protocol: set flag[i]=true, set turn=j, then wait while (flag[j] && turn==j).
  • Gate condition: a process waits only if the other is interested and it is the other’s turn.
  • Satisfies: mutual exclusion, progress, bounded waiting (for two processes, under classic assumptions).
  • Limitation: uses busy waiting; modern systems typically rely on hardware-supported primitives for real locking.