+1 vote
657 views

Consider the following scheme for implementing a critical section in a situation with three processes $P_i, P_j$ and $P_k$.

Pi;
repeat
flag[i] := true;
while flag [j] or flag[k] do
case turn of
j: if flag [j] then
begin
flag [i] := false;
while turn != i do skip;
flag [i] := true;
end;
k: if flag [k] then
begin
flag [i] := false,
while turn != i do skip;
flag [i] := true
end
end
critical section
if turn = i then turn := j;
flag [i] := false
non-critical section
until false;
1. Does the scheme ensure mutual exclusion in the critical section? Briefly explain.

retagged | 657 views

+1 vote

Assume all 3 process has same implementation of code except flag variable indices changes accordingly for Pj and Pk and turn is shared variable among 3 process.

Initially Flag[i]=F,Flag[j]=F,Flag[k]=F and assume turn =i

1)Let Pi and Pk want to enter CS then set Flag[i] =T and  Flag[k]=T

2)Pi will enter CS while Pk will wait because case turn =j is true and flag[i]=T,it will wait till turn =k therefore Mutual exclusion is satisfy other process agree to wait

3)here if initially turn =j then both Pi and Pk will wait even when no process in CS.

0
)Pi will enter CS while Pk will wait because case turn =j is true and flag[i]=T,it will wait till turn =k therefore Mutual exclusion is satisfy other process agree to wait

3)here if initially turn =j then both Pi and Pk will wait even when no process in CS.

Plz clear my doubt.
+1 vote

Pre-requisite: Assume all 3 processes have same implementation of code except flag variable indices changes accordingly for Pj and Pk and turn is shared variable among 3 process.

The condition:

while flag [j] or flag[k] do

ensures mutual exclusion as no process can enter critical section until flag of other processes is false.

-----------------------------------------------------------------------

Consider the case: turn = k

Pj wants to enter the critical section. It enters the critical section easily as

flag [k] or flag[i]

will be false and the loop will break.

Now, while Pj is executing in its critical section Pi arrives. For Pi :

flag [j] or flag[k]

will be true and it will enter the while loop. Since, turn = k, Pi will execute the loop:

while turn != i do skip;

Now, even if Pj finishes executing it's critical section, it will execute:

if turn = j then turn := k;

which is false and thus the turn will remain k making Pi to execute an infinite loop until Pk arrives which can update turn = i.

So if Pk never arrives Pi will be waiting indefinitely.

+1 vote
1
2