Peterson’s solution is a software based solution to the critical section problem.
Consider two processes P0 and P1. For convenience, when presenting Pi, we use Pi to denote the other process; that is, j == 1 - i.
The processes share two variables: boolean flag [2] ;
int turn;
Initially flag [0] = flag [1] = false, and the value of turn is immaterial (but is either 0 or 1). The structure of process Pi is shown below.
do{
flag[i]=true turn=j
while(flag[j] && turn==j); critical section
flag[i]=false
Remainder section
}while(1);
To enter the critical section, process Pi first sets flag [il to be true and then sets turn to the value j, thereby asserting that if the other process wishes to enter the critical section it can do so. If both processes try to enter at the same time, turn will be set to both i and j at roughly the same time. Only one of these assignments will last; the other will occur, but will be overwritten immediately. The eventual value of turn decides which of the two processes is allowed to enter its critical section first.
We now prove that this solution is correct. We need to show that:
- Mutual exclusion is preserved,
- The progress requirement is satisfied,
- The bounded-waiting requirement is met.
To prove property 1, we note that each Pi enters its critical section only if either flag [jl == false or turn == i. Also note that, if both processes can be executing in their critical sections at the same time, then flag [i] ==flag [jl == true. These two observations imply that P0 and P1 could not have successfully executed their while statements at about the same time, since the value of turn can be either
0 or 1, but cannot be both. Hence, one of the processes say Pj-must have successfully executed the while statement, whereas Pi had to execute at least one additional statement ("turn == j"). However, since, at that time, flag [j] == true, and turn == j, and this condition will persist as long as Pi is in its critical section, the result follows:
To prove properties 2 and 3, we note that a process Pi can be prevented from entering the critical section only if it is stuck in the while loop with the condition flag [j] == true and turn == j; this loop is the only one. If Pi is not ready to enter the critical section, then flag [ j ] == false and Pi can enter its critical section. If Pi has set flag[j] to true and is also executing in its while statement, then either turn == i or turn == j. If turn == i, then Pi will enter the critical section. If turn == j, then Pi will enter the critical section. However, once Pi exits its critical section, it will
reset flag [ jl to false, allowing Pi to enter its critical section. If Pi resets flag [ j 1 to true, it must also set turn to i.
Thus, since Pi does not change the value of the variable turn while executing the while statement, Pi will enter the critical section (progress) after at most one entry by Pi (bounded waiting).
