GATE CSE 1991 | Question: 11,b

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;

Is there a situation in which a waiting process can never enter the critical section? If so, explain and suggest modifications to the code to solve this problem

Comments

To better understand above synchronization mechanism, see answer of below question's link:-

https://gateoverflow.in/538/gate1991-11-a

---

@ Arjun sir, @Bikram sir, please provide detailed solution for above problem. I am facing problem in finding "the modification" which will ensure Progress in synchronization mechanism given in above question.

---

modification can be to replace 

if turn = i then turn := j; 
to 

if flag[j]: then turn=j;

if flag[k] then turn =k;

---

Thanks for reply mam, currently i am on another subject, so, not able to recall concept needed to solve this question. But whenever i revise Operating System then i will definitely evaluate modification provided by you.

Answer 1

“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“
 

1. progress not satisfied
   2. no deadlock 

Answer 2

Here 3 processes are there.

Now, at least 2 processes are ready to enter into CS at the same time

Here, as flag[i]=false // means flag[i] not ready to enter CS

So, P_j enters in CS

But CS depends on turn=i and turn=j and not on turn=k

So, if there is a situation turn=j is always false ,then P_k never go inside CS

Comments

lets suppose Pi wants to enter in critical section so it set its flag=true and now suppose at the same times other two does not want to enter the critical section so the program does not enter in the while loop and process Pi went to critical section and after coming out of critical section it will give turn to Pj

because 

if turn = i then turn := j;
        flag [i] := false
    non-critical section

now suppose Pj want to enter the critical section same thing will happen (if other two does not want to enter in critical section ) and it will give turn to Pk . and pk give turn to its next i.e. Pi 

now consider another scenario where Pj does not want to enter the critical section and Pk is waiting and Pi is in critical section and after coming out of critical section   Pi set own flag false and turn =j 

now suppose pj does not want to enter the critical section then how the Pk can enter 

please correct me  i am wrong

---

Can you explain the functionality in while loop?

---

@srestha mam, please explain the solution in detail and please tell about how synchronization mechanism is working.