Question

Question Four Explain Peterson’s solution for critical-section problem and show that mutual exclusion is preserved with Peterson’s solution. (Assume there are only two processes P0 and P1)

Answer 1

Peterson's Algorithm:

• The solution is limited to two processes alternating the execution of their critical sections with the remaining sections. Assume Process numbers are P1 and P2.
• Needs the two processes that share two pieces of data.

int turn;

boolean flag[2];

• The variable turn denotes the turn of whose critical section it is to enter i.e. if turn == x, then process Px can be executed in the critical section.
• If a process is ready to enter its critical section, this is indicated through the flag array. For example, if the flag[x] is true, this value shows Px is ready to enter its critical section.

Initialization:

flag[1] := FALSE;

flag[2] := FALSE;

turn := random(1..2)

Algorithm:

//declaring do-while loop to continue execution until the condition is true

do {

   //flag variable for x is true which indicates that process x has requested for

   //critical section.

   flag[x] = true;

   //turn = y indicates that y is in critical section

   turn = y;

   //using while condition to make process x wait until process y is done with its critical         //section

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

   /* executing the critical section */

   flag[x] = false;// its indicates that x is done with its critical section hence its

   //flag value is changed

   /* executing the remainder section */

}

//end of do-while loop

while (true);

Proof that mutual exclusion is preserved in Peterson's Solution:

• Condition for each Px to enter its critical section is:

flag[y] == FALSE i.e. process y has no intention to enter in critical section

OR

turn == x i.e. its turn of process x to enter in critical section.

• If both can run concurrently in their critical sections then flag[1 ] = = flag[2 ] = = TRUE

From the above two observations, we get that both the process P1 and P2 cannot execute there while the statement at the same time as the value of turn variable can be 1 or 2 but cannot be both. Therefore only one of process among them let Py will be executing there while statement successfully

Therefore, one of the processes — say, Py — must have executed the while statement successfully, while Px has to execute at least one additional statement i.e. (turn = = y). Nonetheless, at that time flag[y] = = true and turn = = y, and this state will continue as long as Py is in its critical section; as a result, it maintains the mutual exclusion.