259 views

Given below is solution for the critical section problem of two processes $P_0$ and $P_1$ sharing the following variables:

var flag :array [0..1] of boolean; (initially false)
turn: 0 .. 1;

The program below is for process Pi (i=0 or 1) where process Pj (j=1 or 0) being the other one.

repeat
flag[i]:= true;
while turn != i
do begin
while flag [j] do skip
turn:=i;
end

critical section

flag[i]:=false;
until false

Determine of the above solution is correct. If it is incorrect, demonstrate with an example how it violates the conditions.

+1 vote

the above solution for critical section isn't correct because it satisfies Mutual exclusion and Progress but it violates the bounded waiting.

here is sample run

suppose turn =j initially;

Pi runs its first statement then Pj runs its first statement then Pi run 2,3,4 statement, It will block on statement 4

Now Pj start executing its statements goes to critical section and then flag[j]=false

Now suppose Pj comes again immediately after execution then it will again execute its critical section and then flag[j]=false

Now if Pj is coming continuously then process Pi will suffer starvation

the correct implementation ( for Bounded waiting ) is, at the exit section we have to update the turn variable at exit section.

repeat
flag[i]:= true;
while turn != i
do begin
while flag [j] do skip
turn:=i;
end

critical section

flag[i]:=false;
turn = j;

until false
selected

1
2