Peterson’s Solution

A classic software based solution to the critical section problem is Peterson’s solution. It is not guaranteed that Peterson’s solution will work correctly on modern architectures.

Peterson’s solution is restricted to two processes that alternate execution between their critical sections and remainder sections.

Peterson’s solution requires the two processes to share two data items:

int turn; - Indicates whose turn it is to enter into the critical section. If turn = = i, then process i is allowed into their critical section.

boolean flag[2]; - Indicates when a process wants to enter into their critical section. When process i wants to enter their critical section, it sets flag[ i ] to true.

In the above diagram, the entry and exit sections are enclosed in boxes.

• In the entry section, process i first raises a flag indicating a desire to enter the critical section.
• Then turn is set to j to allow the other process to enter their critical section if process j desires.
• The while loop is a busy loop ( notice the semicolon at the end ), which makes process i wait as long as process j has the turn and wants to enter the critical section.
• Process i lowers the flag[ i ] in the exit section, allowing process j to continue if it has been waiting.

To prove that the solution is correct, examine the three conditions listed:

1. Mutual exclusion - If one process is executing their critical section when the other wishes to do so, the second process will become blocked by the flag of the first process. If both processes attempt to enter at the same time, the last process to execute "turn = j" will be blocked.
2. Progress - Each process can only be blocked at the while if the other process wants to use the critical section (flag[j] = = true), AND it is the other process's turn to use the critical section (turn = = j). If both of those conditions are true, then the other process ( j ) will be allowed to enter the critical section, and upon exiting the critical section, will set flag[ j ] to false, releasing process i. The shared variable turn assures that only one process at a time can be blocked, and the flag variable allows one process to release the other when exiting their critical section.
3. Bounded Waiting - As each process enters their entry section, they set the turn variable to be the other processes turn. Since no process ever sets it back to their own turn, this ensures that each process will have to let the other process go first at most one time before it becomes their turn again.