edited by
4,067 views
9 votes
9 votes

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.

edited by

3 Answers

11 votes
11 votes

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.

2 votes
2 votes

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.

0 votes
0 votes

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.

Related questions

52 votes
52 votes
2 answers
2
Kathleen asked Sep 12, 2014
6,337 views
Find the number of binary strings $w$ of length $2n$ with an equal number of $1's$ and $0's$ and the property that every prefix of $w$ has at least as many $0's$ as $1's....
27 votes
27 votes
1 answer
4
Kathleen asked Sep 12, 2014
3,811 views
Analyse the circuit in Fig below and complete the following table$${\begin{array}{|c|c|c|}\hline\textbf{a}& \textbf{b}& \bf{ Q_n} \\\hline0&0\\\ 0&1 \\ 1&0 \\ 1...