Vaidikalaya
Privious Next

Peterson's Algorithm in Process Synchronization

Peterson’s Algorithm is a classic software-based solution to the critical section problem in operating systems. It coordinates two processes so that only one process can access a shared resource at a time, thereby ensuring mutual exclusion and preventing race conditions.

It guarantees the three essential requirements:

  • Mutual Exclusion- only one process can be in the critical section at a time.
  • Progress- if no process is inside, one of the waiting processes can enter without unnecessary delay.
  • Bounded Waiting- each process will get a turn within a finite number of attempts (no starvation).

It is mainly used for conceptual and educational purposes to show how software alone can synchronize processes.

How It Works

Peterson’s algorithm uses two shared variables:

  1. flag[]: A boolean array where flag[i] indicates whether process i wants to enter the critical section.
  2. turn: An integer variable that stores which process’s turn it is to enter the critical section.
The Algorithm:
For P[i]
do {
    flag[i] = true;  // Pi wants to enter
    turn = j;        // Give turn to Pj

    while (flag[j] && turn == j);// Wait if Pj also wants to enter

    // Critical Section

    flag[i] = false;        // Pi leaves critical section

    // Remainder Section
} while (true);
For P[j]
do {
    flag[j] = true;        
    turn = i;              

    while (flag[i] && turn == i);

    // Critical Section

    flag[j] = false;        

    // Remainder Section
} while (true);

Suppose there are two processes: P0 and P1.

P0
do {
    flag[0] = true;        
    turn = 1;              

    while (flag[0]==true && turn == 1);

    // Critical Section

    flag[0] = false;        

    // Remainder Section
} while (true);
P1
do {
    flag[1] = true;        
    turn = 0;              

    while (flag[1]==true && turn == 0);

    // Critical Section

    flag[1] = false;        

    // Remainder Section
} while (true);

This algorithm satisfy
  • Mutual Exclusion: The while loop ensures that both flags cannot be true with the same turn. Only one process can pass at a time.
  • Progress: If only one process wants to enter, it doesn’t wait. If both want to enter, the one whose turn it is goes first.
  • Bounded Waiting: Turn-taking guarantees that each process gets a chance after a finite number of turns.

Advantages

  • Pure software solution — no special hardware instructions required.
  • Simple and elegant for two processes.
  • Satisfies all three critical section requirements.

Limitations

  • Two processes only – not directly scalable to more than two without complex extensions.
  • Busy waiting – consumes CPU cycles while waiting.
  • Assumes atomic reads/writes – modern CPUs may reorder instructions or cache writes, so memory barriers or fences may be needed.
  • Mostly theoretical/educational; real operating systems use semaphores, mutexes, or monitors instead.
Privious Next