+1 vote
1.1k 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 | 1.1k views
0

while loop where ends is confusing because observe below instruction -

" while turn != i do skip; " many of us think that due to semicolon while loop is ended in just one line. But after understanding the question, it seems that complete while loop is below one

while turn != i do skip;
flag [i] := true

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.

0

bro, conclusion of your answer is :- Mutual Exclusion is guaranteed but Progress is not guaranteed.

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.