2,500 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 $P_{i} (i=0\;\text{or}\; 1)$ where process $P_{j} (j=1\; \text{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.

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

Here is a sample run

suppose turn =j initially;

Pi runs its first statement then Pj runs its first statement then $P_{i}$ run $2,3,4$ statement, It will block on statement $4$

Now $P_{j}$ start executing its statements goes to critical section and then flag[j] = false

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

Now if $P_{j}$ is coming continuously then process $P_{i}$ will suffer starvation.

the correct implementation ( for Bounded waiting ) is, at the exit section we have to update the turn variable at the 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

someone just number this  which is which line
the solution is unclear.

@Prateek.pyThe given Critical section problem satisfies only Mutual Exclusion and Progress but not Bounded waiting hence it’s not correct. We have to check all the 3 things to identify whether solution is correct or not. You may refer below ss taken from Galvin to understand the concept.

flag[0]=flag[1]=FALSE initially.

Assume turn =1 (initially).

1) P1 starts executing . Makes flag[0]=True.

while(turn!=0)    //Enter this Loop Bcoz Turn=1 actually.

{

​​​​​​​2) P1 gets preempted here and P2 starts.Makes flag[1]=True

while(turn!=1) //False bcoz turn=1 actually.Dont enter loop.

ENTER CRITICAL SECTION

Make flag[1] = False.

​​​​​​​3) Now P2 gets Preempted and P1 continue from where it left.

while flag[1]==TRUE  then keep moving in Loop . // but flag[1] is False already.So dont enter it.

​​​​​​​4) Now P1 gets Preempted and P2 starts again.Makes flag[1]=True.

while(turn!=1) // turn is still Equal to 1 bcoz no one updated it to 0. So dont enter loop.

ENTER CS.

​​​​​​​5) Now P2 gets Preempted and P1 continues from where it left.

turn = 0

So now WHILE  loop breaks and P0 also enter CS.

So MUTUAL EXCLUSION itself is Not guaranteed if this order is followed.

by

Your 3rd point has a mistake @

while flag[j] do skip” is equivalent to saying “ if( ! flag[j] )

You considered it the other way round.

I think there is some mistake in this solution!

as pointed out by @reboot

@reboot it still does not satisfy mutual exclusion. Let’s say initially turn = 1 and P0 starts execution.

1)It will enter the loop while turn != i because here i is 0 and turn is 1

2)Next it executes if( !flag[ j ] )//(as you told) { turn = i //(here i is 0) }

3)here if( !flag[ j ] ) satisfies and just before executing turn = i it gets preempted by P1

4)Now P1 makes flag[i] = true;(here i is 1 for P1 process)

5)while turn != i return false and P1 doesn’t enter the loop as turn = 1

6)Goes directly to critical section and let’s say P1 gets preempted.

7)Now P0 will execute from where it left of that is it executes turn = i (here i is 0 for P0) and comes out the if block

8)It will break out of the loop  while turn != i (as turn is now made 0) and enters into critical section

9)Both processes are in critical section hence there is no mutual exclusion.