The Gateway to Computer Science Excellence
+1 vote
1.1k views

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.

in Operating System by
retagged by | 1.1k views
0

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

2 Answers

+5 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.

by
0

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

+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.

by
0
)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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,513 answers
201,930 comments
95,355 users