Peterson's Algorithm

operating-systems concurrency

Definition

Peterson's Algorithm

Peterson’s algorithm is an elegant software solution for mutual exclusion between two processes. More simplified than Dekker’s algorithm while satisfying progress and bounded waiting.

Uses a boolean array flag[0..1] to indicate intent and a turn variable to handle simultaneous requests:

// Process Pi (i = 0 or 1, j = 1 - i)
while (true) {
    flag[i] = true;      // I want to enter
    turn = j;            // But I yield to the other
 
    while (flag[j] && turn == j);  // Busy waiting
 
    // --- Critical Section ---
 
    flag[i] = false;     // I am done
 
    // --- Remainder Section ---
}

Correctness

Mutual Exclusion

Both flag[0] and flag[1] must be true for both processes to enter. Since turn can only be 0 or 1, one process must wait.

No Deadlock

A process is blocked only if the other is interested (flag[j] = true) AND it is the other’s turn (turn = j).

No Starvation

Upon exiting the critical section, a process sets flag to false, allowing any waiting process to proceed.