in Operating System recategorized by
3,973 views
14 votes
14 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
4.0k views

1 comment

@Sachin Mittal 1  sir here Mutual exclusion is not satified then how best answers considered it . ?

0
0

3 Answers

15 votes
15 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
1 flag:
✌ Edit necessary (Shukla_ “Mutual exclusion is not satisfied. Refer to the last comment”)

4 Comments

no bro , it doesnt get stuck as when turn =0 , then in process P1 turn != 1 gets true , it goes in the while loop ,  then in that while loop it will check again the condition of while loop while(flag[0]); it becomes while(0) ;  and comes out of loop and make turn =1 . and goes into the critical section . Hence , progress ( when only one process wants critical section ) .
1
1

It does not get stuck. There is no semicolon for the while loop. If it had semicolon, then it would have got stuck. As the condition is true in the while(turn!=1) it will enter the loop and execute the inside conditions.

0
0
Consider the simplified versions of code for P0 and P1
[You can ignore line 14 and 30 for now]

 

 

Assume initally turn = 1

So we have

FLAG = [FALSE, FALSE]

turn = 1

 

P0 starts initally

=====================================================================================

executes line 3: flag[0]:= true;

So we have

FLAG = [TRUE, FALSE]

turn = 1

 

executes line 5: while (turn != 0) // here turn is 1, so go inside the body

executes line 7: while (flag [1] == True); // here condition is false, so go to next line

P0 now preempts

=====================================================================================

Just before executing line 8, P0 preempts

Upon returning back, it will execute at line 8

turn=0;

 

So we have

FLAG = [TRUE, FALSE]

turn = 1

 

P1 starts nextly

=====================================================================================

executes line 19: flag[1]:= true;

 

So we have

FLAG = [TRUE, TRUE]

turn = 1

 

executes line 21: while (turn != 1) // here turn is 1, so go inside the CS

executes line 27: [Critical Section] //P1 currently enjoying CS

 

P1 now preempts

=====================================================================================

P1 while holding CS preempts

Upon returning back, it will resume at line 27

[Critical Section]


 

P0 now resumes

=====================================================================================

executes line 8: turn=0;

 

So we have

FLAG = [TRUE, TRUE]

turn = 0

 

executes line 8: turn=0;

executes line 5: while (turn != 0) // here turn is 0, so go inside the CS

executes line 27: [Critical Section] //P0 currently enjoying CS

 

 

Now, P0 entered CS when P1 is already holding CS, so mutual exclusion is violated

5
5
20 votes
20 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.

3
3
5 votes
5 votes
Consider the simplified versions of code for P0 and P1
[You can ignore line 14 and 30 for now]

 

 

Assume initally turn = 1

So we have

FLAG = [FALSE, FALSE]

turn = 1

 

P0 starts initally

=====================================================================================

executes line 3: flag[0]:= true;

So we have

FLAG = [TRUE, FALSE]

turn = 1

 

executes line 5: while (turn != 0) // here turn is 1, so go inside the body

executes line 7: while (flag [1] == True); // here condition is false, so go to next line

P0 now preempts

=====================================================================================

Just before executing line 8, P0 preempts

Upon returning back, it will execute at line 8

turn=0;

 

So we have

FLAG = [TRUE, FALSE]

turn = 1

 

P1 starts nextly

=====================================================================================

executes line 19: flag[1]:= true;

 

So we have

FLAG = [TRUE, TRUE]

turn = 1

 

executes line 21: while (turn != 1) // here turn is 1, so go inside the CS

executes line 27: [Critical Section] //P1 currently enjoying CS

 

P1 now preempts

=====================================================================================

P1 while holding CS preempts

Upon returning back, it will resume at line 27

[Critical Section]


 

P0 now resumes

=====================================================================================

executes line 8: turn=0;

 

So we have

FLAG = [TRUE, TRUE]

turn = 0

 

executes line 8: turn=0;

executes line 5: while (turn != 0) // here turn is 0, so go inside the CS

executes line 27: [Critical Section] //P0 currently enjoying CS

 

 

Now, P0 entered CS when P1 is already holding CS, so mutual exclusion is violated

Related questions