Peterson's Solution

Peterson Sync Algorithm.

Ankit Rajvanshi

Peterson solution 

The Peterson solution is a synchronization algorithm used in computer science to solve the critical section problem, which arises when multiple processes or threads are trying to access a shared resource concurrently. The critical section is a part of the program that accesses shared resources and needs to be executed atomically, i.e., without interference from other processes.

The Peterson solution was proposed by Gary Peterson in 1981 and is a simple algorithm that allows two processes to access a shared resource without interference. The algorithm is based on two key concepts: mutual exclusion and progress.

Mutual exclusion ensures that only one process at a time can execute the critical section. The algorithm achieves mutual exclusion by using two shared variables, turn and flag. The turn variable is used to indicate which process is currently allowed to enter the critical section, and the flag variable is used to indicate whether a process is ready to enter the critical section.

Progress ensures that a process that is ready to enter the critical section does not get blocked indefinitely. The algorithm achieves progress by allowing the other process to enter the critical section if it is not ready to do so.

The Peterson solution algorithm works as follows:

do {

    flag[i] = true;

    turn = j;

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

    // critical section

    flag[i] = false;

    // remainder section

} while (true);

In this algorithm, i and j are the two processes, and flag[i] and flag[j] are the flags indicating whether each process is ready to enter the critical section. The turn variable indicates which process is currently allowed to enter the critical section.

The algorithm works as follows:

The flag[i] variable is set to true, indicating that process i is ready to enter the critical section.

The turn variable is set to j, indicating that process j should go first.

The while loop checks whether process j is ready (flag[j] is true) and whether it is its turn to go (turn == j). If both conditions are true, the loop continues. If not, process i enters the critical section.

Once process i exits the critical section, its flag[i] variable is set to false, indicating that it is no longer ready to enter the critical section.

The process then enters the remainder section, where it waits for its turn to come again.

The Peterson solution algorithm ensures mutual exclusion and progress by using the flag and turn variables to ensure that only one process can enter the critical section at a time and that a process that is ready to enter the critical section does not get blocked indefinitely. However, it is important to note that this algorithm only works for two processes and does not scale well for more than two processes.