536 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.

| 536 views

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
0
0
Can we get more detailed explanation on this
0

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

In question it is given as flag[i]:=false but not flag[j]:=false.

0
Can't seem to understand the lines :-

while flag[j] do skip

turn = i

Does it mean that while flag[j] is true, turn=i will continue to be executed again and again ?
0
It means when flag[j] returns true skip the rest code and go for the next run of while loop(indefinite looping)  otherwise set turn to i and make while condition false and come out of the loop and execute CS.