Peterson's Solution for Process Synchronization: A Classic Algorithm for Mutual Exclusion

Understand Peterson's solution, a classic algorithm for achieving mutual exclusion in concurrent programming. This guide explains the algorithm's mechanism using shared variables (`flag`, `turn`), its guarantee of mutual exclusion, progress, and bounded waiting, and its limitations (only for two processes).

Peterson's Solution for Process Synchronization

Peterson's Algorithm: A Software Solution

Peterson's solution is a classic software-based algorithm for achieving process synchronization, specifically addressing the critical section problem for two processes. It uses two key variables:

• turn: Indicates which process has the right to enter the critical section.
• interested: An array (size 2) where interested[i] is true if process i wants to enter the critical section.

The algorithm employs busy-waiting (a process repeatedly checks a condition), which is generally inefficient, but it's a simple way to illustrate the concepts.

#define N 2
#define TRUE 1
#define FALSE 0

int interested[N] = {FALSE, FALSE};
int turn;

void entry_section(int process) {
  int other = 1 - process;
  interested[process] = TRUE;
  turn = process;
  while (interested[other] && turn == process); // Busy wait
}

void critical_section() {
  // Code to execute in critical section
}

void exit_section(int process) {
  interested[process] = FALSE;
}

Analysis of Peterson's Solution

Let's trace the execution with two processes, P1 and P2. Initially, interested[0] = interested[1] = FALSE, and turn can be either 0 or 1.

1. P1 wants to enter the critical section: It sets interested[0] = TRUE and turn = 0. The while loop condition is false, so P1 enters the critical section.
2. Meanwhile, P2 arrives and sets interested[1] = TRUE and turn = 1. The while loop condition in P2 is true (interested[0] == TRUE and turn == 1), so P2 waits.
3. P1 exits the critical section: It sets interested[0] = FALSE.
4. Now, the while loop condition in P2 becomes false, allowing P2 to enter the critical section.

This process repeats cyclically. Peterson's solution guarantees:

• Mutual Exclusion: Only one process can be in the critical section at a time.
• Progress: If no process is in the critical section, and some processes wish to enter, only those not in the critical section can participate in deciding which will enter next.
• Bounded Waiting: A process will enter the critical section within a bounded number of attempts.
• Portability: The solution is purely software-based and thus portable to any hardware platform.