Peterson's Algorithm

operating-systems concurrency

Definition

Peterson's Algorithm

Peterson’s algorithm is an elegant and correct software solution for the mutual exclusion problem between two processes. It provides a more simplified logic than Dekker’s algorithm while satisfying the requirements of progress and bounded waiting.

The Algorithm

The algorithm uses a boolean array flag[0..1] to indicate intent and a turn variable to handle simultaneous requests.

// Process Pi (where i is 0 or 1, and j is 1 or 0)
loop
    flag[i] := true; // I want to enter
    turn := j;       // But I yield to the other process
    
    while (flag[j] and turn = j) do nothing; // Busy Waiting
    
    // --- Critical Section ---
    
    flag[i] := false; // I am done
    
    // --- Remainder Section ---
end loop;

Correctness

• Mutual Exclusion: For both processes to be in the critical section, flag[0] and flag[1] must both be true. However, turn can only be 0 or 1 at any given time, forcing one process to wait in its while loop.
• No Deadlock: A process can only be blocked if the other process is interested (flag[j] = true) AND it is the other’s turn (turn = j).
• No Starvation: Upon exitingthe critical section, a process sets its flag to false, allowing any waiting process to proceed.

Visual Representation