Two-Process Solutions-Peterson's Solution

 Two process P0 & P1 // the restriction is on two processes for pi use pj.

Algorithm 1

Repeat

While turn i;

Critical section

Turn :=j;

Remainder section

Until false;

let the processes share a common integer variable turn initialized to 0 (or 1). If turn == i, then process Pi is allowed to execute in its critical section.

Only one process at a time can be in its critical section. if turn == 0 and P1 is ready to enter its critical section, P1 cannot do so, even though Po may be in its remainder section.

Algorithm 2

Repeat

Flag[i] := true

While flag[j];

Critical section

Flag[i] := false;

Remainder section

Until false;

The problem with algorithm 1 is that it does not retain sufficient information about the state of each process; it remembers only which process is allowed to enter its critical section. To remedy this problem, we can replace the variable turn with the following array:

 boolean flag [2] ;

The elements of the array are initialized to false. If flag[i] is true, this value indicates that Pi is ready to enter the critical section. The structure of process Pi is shown.

Algorithm 3(Peterson's Solution)

By combining the key ideas of algorithm 1 and algorithm 2, we obtain a correct solution to the critical-section problem, where all three requirements are met. The processes share two variables: 

boolean flag [2];

int turn;

Repeat Flag[i] :=true;

Turn := j;

While(flag[j] and turn = j);

Critical section

Flag[i] = false;

Remainder section

Until false; 

Initially flag[O] = flag[I] = false, and the value of turn is immaterial (but is either 0 or 1). The structure of process Pi is shown in Figure

To enter into critical section pi sets flag[i] to be true and asserts that it is the other process turn to enter if appropriate (turn = j). If both process try to enter at the same time, the eventual value of turn decides which of the two processes is allowed to enter its critical section first. We prove that this solution is correct. We need to show that:

1.      Mutual exclusion is preserved,

2.      The progress requirement is satisfied,

3.      The bounded-waiting requirement is met.

To prove property 1, we note that each P, enters its critical section only if either flag[j]==false or turn==i. Also note that, if both processes can be executing in their critical sections at the same time, then flag COI == flag [l] == true. These two observations imply that Po and PI 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.

Since at that time, flag[j] =true, and turn = i and this condition will persist as long as pj is in critical section the result follows: mutual exclusion is preserved. Similarly 2 & 3 is preserved.