GATE CSE 1991 | Question: 11,a

Question

Consider the following scheme for implementing a critical section in a situation with three processes $P_i, P_j$ and $P_k$.

Pi;
repeat
    flag[i] := true;
    while flag [j] or flag[k] do
        case turn of
        j: if flag [j] then
        begin
            flag [i] := false;
            while turn != i do skip;
            flag [i] := true;
        end;
        k: if flag [k] then
        begin
            flag [i] := false,
            while turn != i do skip;
            flag [i] := true
        end
    end
    critical section
    if turn = i then turn := j;
        flag [i] := false
    non-critical section
until false;

1. Does the scheme ensure mutual exclusion in the critical section? Briefly explain.

Comments

while loop where ends is confusing because observe below instruction -

" while turn != i do skip; " many of us think that due to semicolon while loop is ended in just one line. But after understanding the question, it seems that complete while loop is below one

while turn != i do skip;
    flag [i] := true

---

“the process which  use critical section should hold turn variable otherwise other waiting process will wait for indefinite time if some process does not wants to enter  in cs“

---

for such questions can somebody write code in c

Answer 1

Pre-requisite: Assume all 3 processes have same implementation of code except flag variable indices changes accordingly for Pj and Pk and turn is shared variable among 3 process.

 

The condition:

while flag [j] or flag[k] do

ensures mutual exclusion as no process can enter critical section until flag of other processes is false.

 

-----------------------------------------------------------------------

 

Consider the case: turn = k

Pj wants to enter the critical section. It enters the critical section easily as 

flag [k] or flag[i]

will be false and the loop will break.

Now, while Pj is executing in its critical section Pi arrives. For Pi :

flag [j] or flag[k]

will be true and it will enter the while loop. Since, turn = k, Pi will execute the loop:

while turn != i do skip;

Now, even if Pj finishes executing it's critical section, it will execute:

if turn = j then turn := k;

which is false and thus the turn will remain k making Pi to execute an infinite loop until Pk arrives which can update turn = i.

So if Pk never arrives Pi will be waiting indefinitely.

Comments

bro, conclusion of your answer is :- Mutual Exclusion is guaranteed but Progress is not guaranteed. 

---

In addition, I think Bounded Waiting is also guaranteed as strict alteration(for 3 processes) is being used by this synchronization construct by setting turn variable appropriately in the exit section before the control passes to other process.

---

since they are in infinite loop how can we say that Pk will never arrive ?

we can starve Pk but not stop it

Answer 2

Assume all 3 process has same implementation of code except flag variable indices changes accordingly for Pj and Pk and turn is shared variable among 3 process.  

Initially Flag[i]=F,Flag[j]=F,Flag[k]=F and assume turn =i

1)Let Pi and Pk want to enter CS then set Flag[i] =T and  Flag[k]=T

2)Pi will enter CS while Pk will wait because case turn =j is true and flag[i]=T,it will wait till turn =k therefore Mutual exclusion is satisfy other process agree to wait

3)here if initially turn =j then both Pi and Pk will wait even when no process in CS.

Comments

)Pi will enter CS while Pk will wait because case turn =j is true and flag[i]=T,it will wait till turn =k therefore Mutual exclusion is satisfy other process agree to wait

3)here if initially turn =j then both Pi and Pk will wait even when no process in CS.

Isn't it contradictory ??
Plz clear my doubt.

Answer 3

Mutual Exclusion is Satisfied because ,If we assume all 3 processes wants to enter in Critical Section at Same time , then the one whose id(i,j,k) is same as turn variable will get into Critical section . rest will wait in entry section.

 

Progress in Code is Not satisfied ,because next who will enter in Critical section is determined by the one who comes out of critical section.

So decision is not totally dependent on them who wants to go in Critical section.