in Operating System recategorized by
2,500 views
12 votes
12 votes

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.

in Operating System recategorized by
2.5k views

2 Answers

13 votes
13 votes
Best answer

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
edited by

4 Comments

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

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

0
0
18 votes
18 votes

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.

 

           

            

 

  

4 Comments

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.

1
1

I think there is some mistake in this solution!

as pointed out by @reboot

0
0

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

1
1

Related questions