recategorized by
4,025 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.

recategorized by

3 Answers

Best answer
15 votes
15 votes

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”)
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.

 

           

            

 

  

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

2 votes
2 votes
0 answers
1
go_editor asked Dec 18, 2016
662 views
A modern day machine typically has an atomic TEST AND SET instruction. Why?
7 votes
7 votes
4 answers
3
go_editor asked Dec 18, 2016
2,783 views
State any undesirable characteristic of the following criteria for measuring performance of an operating system:Waiting time
9 votes
9 votes
5 answers
4
go_editor asked Dec 18, 2016
4,269 views
State any undesirable characteristic of the following criteria for measuring performance of an operating system:Turn around time