Peterson's algorithm

Peterson's Algorithm is a classic software-based solution used for process synchronization, specifically to solve the Critical Section Problem for two processes.

1. Critical Section Problem Requirements

To ensure proper synchronization, any solution to the Critical Section Problem must satisfy three requirements:

Mutual Exclusion: Only one process can be inside the critical section at any given time.
Progress: If no process is in the critical section and some processes want to enter, only those processes not in their remainder section can participate in the decision of which process will enter the critical section next. This decision cannot be postponed indefinitely.
Bounded Waiting: There must be a limit on the number of times other processes are allowed to enter their critical section after a process has made a request to enter its critical section and before that request is granted.

2. Algorithm Variables

Peterson's Algorithm uses two shared variables, initialized globally:

boolean flag[2]: An array where flag[i] = true indicates that process $P_i$ wants to enter the critical section. Initially, both flag[0] and flag[1] are false.
int turn: An integer variable, initialized to either $0$ or $1$ . It indicates whose turn it is to enter the critical section if both processes want to enter simultaneously.

3. Algorithm for Process $P_i$

Let's consider process $Pi$ and the other process as $Pj$ . The algorithm for process $P_i$ is as follows:

do {
    flag[i] = true;
    turn = j; // Indicate that it's Pj's turn
    while (flag[j] && turn == j); // Wait if Pj wants to enter AND it's Pj's turn

    // CRITICAL SECTION

    flag[i] = false; // Indicate Pi is done with critical section

    // REMAINDER SECTION
} while (true);

4. How it Satisfies Requirements

Mutual Exclusion: If process $Pi$ is in its critical section, it means it broke out of the while loop. This could only happen if either flag[j] was false (meaning $Pj$ didn't want to enter) or turn was i (meaning $Pj$ yielded its turn). If both $Pi$ and $P_j$ try to enter simultaneously, one will set turn to the other's index, and the other will wait.
Progress: If $Pi$ wants to enter and $Pj$ doesn't (flag[j] is false), then $P_i$ proceeds directly. If both want to enter, the turn variable resolves the contention, allowing one to proceed.
Bounded Waiting: If $Pi$ is waiting, it means flag[j] is true and turn == j. This state means $Pj$ is either in its critical section or about to enter. Once $Pj$ exits its critical section, it sets flag[j] = false, allowing $Pi$ to enter. If $Pj$ tries to re-enter, it will set turn = i, giving $Pi$ priority. Thus, waiting is bounded.

5. Advantages

Simple to understand and implement.
Guarantees mutual exclusion, progress, and bounded waiting.

6. Disadvantages

Limited to Two Processes: It cannot be easily extended to synchronize more than two processes.
Busy Waiting (Spin Lock): Processes actively wait in a loop while checking conditions, consuming CPU cycles unnecessarily. This is inefficient, especially in multi-programming environments where a process could yield the CPU instead.