13,933 views

Consider Peterson's algorithm for mutual exclusion between two concurrent processes i and j. The program executed by process is shown below.

repeat
flag[i] = true;
turn = j;
while (P) do no-op;
Enter critical section, perform actions, then
exit critical section
Flag[i] = false;
Perform other non-critical section actions.
Until false;



For the program to guarantee mutual exclusion, the predicate P in the while loop should be

1. flag[j] = true and turn = i
2. flag[j] = true and turn = j
3. flag[i] = true and turn = j
4. flag[i] = true and turn = i

I think if we will change

turn = j; --> turn = i;

Then also it will work. Please correct me if i am wrong.

yes it will work but condition P statement will change to flag[j]==true and turn==i
option B

Suppose

1. there are two processes P1 and P2

2. flag , flag, turn are the variables

when P1 will execute first two lines and enter CS status of variables will be flag= T and turn = 2 and it got preempted.

when P2 execute first two lines, flag= T and turn will be set to 1.

Now to stop P2 at entry point I agree option 2 is clearly the choice but according to above values I am getting turn == i to stop P2. Where I am going wrong?

you are confused, to clearly understood it

First write P1 code separately and P2 code separately ( i mean don't use i and j instead of them fix the values ), then analyse the code, automatically you will understood !
turn is a global variable right?

Can you please point out the mistake in above interleaving of processes. It will really be helpful. I am stuck here. Can you please proceed after this

Yes to block P2 flag[j]= T and turn ==j . Sorry @Shaik Masthan missed it.

as per option B :-  flag[j] = true and turn = j

for P$_1$ it would be like :- flag = true and turn = 2

for P$_2$ it would be like :- flag = true and turn = 1.

Note that current context of your code is flag = true , flag=true and turn = 1

Now P$_1$ comes, it have to executes the line while ( flag == true and turn == 2 ), it gives false ==> enter into CS

A) flag[i] = true;
turn = j;
while (flag[j] == true && turn == j) do no-op;
B)  flag[i] = true;
turn = i;
while (flag[j] == true && turn == i) do no-op;
C)  flag[i] = true;
turn = j;
while (flag[j] == true && turn == i) do no-op;

@Shaik Masthan

@tusharp

A) and B) will be peterson solution

C) Violates ME so it is not peterson solution  ....all are for Process i

correct if wrong

Please check @MiNiPanda's comment to know why Option A does not satisfy mutual exclusion. It has been explained very well there.

(The comment is below the answer provided by @jayendra)

to clear this concept watch in order:

1.

2.

3.

Question Only Asks “For The Program To Guarantee Mutual Exclusion…..”, Option © might lead to deadlock but still mutual exclusion is guaranteed. I think it would be really confusing if such a question is asked in gate 2021 where there are MSQs !
Why Option C is Wrong ,,, it is perfectly valid for mutual exclusion
Yes , it is true.

Answer is Option B as used in Peterson's solution for Two Process Critical Section Problem which guarantees

1. Mutual Exclusion
2. Progress
3. Bounded Waiting

Both $i$ and $j$ are concurrent processes. So, whichever process wants to enter critical section(CS) that will execute the given code.

A process $i$ shows it's interest to enter CS by setting $flag[i]$ = TRUE and only when $i$ leaves CS it sets $flag[i]$= FALSE.

From this it's clear that when some process wants to enter CS then it must check value of $flag[ ]$ of the other process.

$\therefore$     " $flag[j]$ == TRUE " must be one condition that must be checked by process $i$.

Here, the $turn$ variable specifies whose turn is next i.e. which process can enter the CS next time. "$turn$ " acts like an unbiased scheduler, it ensures giving fair chance to the processes for execution. When a process sets $flag[ ]$ value, then $turn$ value is set equal to other process so that same process is not executed again (strict alteration when both processes are ready). i.e., usage of turn variable here ensures "Bounded Waiting" property.

Before entering CS every process needs to check whether other process has shown interest first and which process is scheduled by the $turn$ variable. If other process is not ready, $flag[other]$ will be false and the current process can enter the CS irrespective of the value of $turn.$ Thus, the usage of $flag$ variable ensures "Progress" property.

If $flag[other]$ = TRUE and $turn$ = other, then the process has to wait until one of the conditions becomes false. (because it is the turn of other process to enter CS). This ensures Mutual Exclusion.

Thus, ans is $(b)$.

** one interesting point that can be observed is, if 2 processes wants to enter the CS, the process which executes " $turn = j$" statement first is always the first one to enter the CS (after the other process executes $turn = j$".

Answer is (B). suppose two processes $p1$ and $p2$. To gurantee mutual exclusion only $1$ process must be in $CS$ at a time. now, shared variable is turn $P1 P2 f=$ true $f=$true turn$=2$ $p1$ will now check for condition while($f=$ true and turn $=2$) then it will go for busy wait. Then, $p2$ will execute and it will update turn $=1$ $p2$ will now check condition while($f=$ true and turn $=1$) then it will go for busy wait, but here as the value of turn is updated by $p2$; $p1$ will be able to enter into CS as the condition will become false therefore, $p1$ will enter CS and $p2$ will be in busy wai until the $p1$ will come out and make $f=$ false hence, no two process can enter into CS at a time so predicate $p$ is option (B).

by

C is also correct ans...........

@ jayendra what about option c can you explain....

@bikram sir Are B and C both the correct answer?

No, option B is only correct.

Here the question should mention that this is the code executed by the process Pi.Otherwise it creates  confusion.

It is a tricky question.We should eliminate options if possible:-

a& d:)will fail mutual inclusion as the process has set turn =j. Now it will check turn =i in for loop .so,both can enter.So remaining is b.which is surely the answer

Let us say both the processes tries to enter now both set flag to 1 but the key is turn variable.it will have i or j ,so one of the process will fail and other will pass and enter.
Hi Bikram Sir,

Please correct me if I am wrong here for not taking option C.

If Pi enters first and doesn't wish to enter second time, then Pj will never be able to enter in CS as for PJ the condition is

flag[j] = true and turn = i both are true, so it will loop forever and Pj will never be able to enter CS.
can anybody explain what is the issue with option A?
C is wrong option..suppose p0 enters into the cs and in between p1 struck into the while loop..and if p0 after completing its task its not interested to execute once again then at that situation p1 is not able to came out of the while loop..so it strucks forever (untill and unless p0 want to exaecute one more time...but there might be the casr that p0 does not want to execute in its lifetime) which cause a deadlock here...
After exit of critical section by pi it will set the flag to false, so that pj can enter

Pi

L1:repeat
L2:    flag[i] = true;
L3:    turn = j;
L4:    while (flag[j]==True && turn==i) do no-op;
L5:    Enter critical section, perform actions, then
L6:    exit critical section
L7:    Flag[i] = false;
L8:    Perform other non-critical section actions.
L9:Until false;

Pj

L1':repeat
L2':    flag[j] = true;
L3':    turn = i;
L4':    while (flag[i]==True && turn==j) do no-op;
L5':    Enter critical section, perform actions, then
L6':    exit critical section
L7':    Flag[i] = false;
L8':    Perform other non-critical section actions.
L9':Until false;

Now see this sequence :

L2 -> L2' -> L3 -> L4 -> L3' ->L4'

L2: flag[i]=true

L2': flag[j]=true

L3: turn=j

L4: flag[j]==true --> TRUE and turn==i -->FALSE. Pi enters in CS

L3': turn =i

L4': flag[i]==true --> TRUE and turn==j -->FALSE. Pj enters in CS

No mutual exclusion!

Thanks @MiNiPanda, Don't know what i was thinking at that time.

@MiNi Panda please make me clear what happening when we are putting options in code

repeat
flag[i] = true;
turn = j;
while (P) do no-op;
Enter critical section, perform actions, then
exit critical section
Flag[i] = false;
Perform other non-critical section actions.
Until false; 

if we are putting option A at the place of P THEN

while (flag[j] = true and turn = i) do no-op;

 i=true
 turn=j

now this is 2 process solution to here flag j will True so i=true j=true and turn=j in option A, flag j=true and turn=i but here turn =j so loop will break and process will enter in to the critical section. it means the process j is in C.S. now if how process i will enter in the critical section and violate the M.E.

in pj flag[j]=false i think
As it is mentioned that below code is running by a processor,

flag[i] --- Pi is running,

then we should check others interest p[j] == true.

and they gave

turn = j;

dont consider this as process name for time being.

as per the petersons concept,

when a & b are need CS,

then

we keep

I[a] = true.

turn =a;

we check condition by

(I[b]== true and turn == a);

now similarly they mentioned turn = j;

then we have to check (flag[j] and turn =j;)

so option is B
edited by

@Arjun Please have a look at this.

I have a doubt regarding Option C. The question says that mutual exclusion should be guaranteed and nothing is said about deadlock. So even if putting flag[i] = true and turn = j in predicate P makes the algorithm suffer from deadlock because the second process didn't execute twice , doesn't it guarantee mutual exclusion? Because mutual exclusion says that if one process is in CS, another process cannot enter CS. So I don't think that deadlock implies no mutual exclusion.

edited

@avistein

Peterson's algorithm must satisfy Mutual exclusion, Progress and Bounded waiting properties.

flag[i] = true and turn = j

The above option does not satisfy Progress and also does not satisfy Bounded waiting(a process can get stuck in the while loop for infinite time).

If process Pi wants to enter into CS then it will make Flag[i]=True and turn=j. Now for while loop, consider 2 points:

(i)  If we take turn=i, then it already makes condition False in while loop and thus both processes can enter simultaneously into  CS. So, take turn=j

(ii)  if we take flag[i]=TRUE, then the condition will become like process ' i ' wants to enter which made flag[i]=TRUE and        turn=j already, so it will always remain in while loop forever. So, take Flag[j]=TRUE

Thus (B) is the answer for sure :)

by

### 1 comment

you cleared my doubt thanks brother

Basically, Peterson’s algorithm provides guaranteed mutual exclusion by using the two following constructs – flag[] and turnflag[] controls that the willingness of a process to be entered in critical section. While turn controls the process that is allowed to be entered in critical section. So by replacing P with the following,

flag [j] = true and turn = j

process i will not enter critical section if process j wants to enter critical section and it is process j’s turn to enter critical section. The same concept can be extended for more than two processes.

@iwasifirshad A small point i would like to make clear , in normal peterson Algo what we have seen is , the process trying to enter CS will check if interested[other]==True and turn==current process(P1) , if both the conditions are met ,P1 will be busy in waiting in the while loop ( P1 will understand , there is a chance that P2 might be in CS or iterating in while loop)---

Case 1: If P2 is iterating in while loop ( interested[p1]==T && turn ==P2 is true)  so as soon as P1 sets the turn=P1 , P2 will break the while loop and enter the CS

(PS- the first process to set the turn variable will get first chance to access CS )

Case 2: If P2 is in CS, P1 will iterate in the while loop untill P2 sets interested[P2]=false i.e it comes out of the CS

P1

:repeat
L1:    intersted = true;
L2:    turn = 2; // turn= other process
L3:    while (intersted==True && turn==2) do no-op;
L4:    Enter critical section, perform actions, then
L5:    exit critical section
L6:    intersted = false;
L7:    Perform other non-critical section actions.
L8:Until false;

P2

:repeat
L1':    intersted = true;
L2':    turn = 1; // other process
L3':    while (intersted​​​​​​​​​​​​​​==True && turn==1) do no-op;
L4':    Enter critical section, perform actions, then
L5':    exit critical section
L6':    intersted​​​​​​​ = false;
L7':    Perform other non-critical section actions.
L8':Until false;

BUT here in this question , turn variable is not used in the same way ,here turn=other process

so now how to identify the correct option , option C and D are eliminated as we always check interested [other process] == true and now setting turn=current process will violate Mutual Exclusion principle , consider Line 1,2,3 in the given code,initially interested &  interested= FALSE

P1:1,2,3,CS | P2:1,2,3,CS ( violates Mutual Exclusion )

so , turn =other process ,option B is correct.

@iwasifirshad A small point i would like to make clear , in normal peterson Algo what we have seen is , the process trying to enter CS will check if interested[other]==True and turn==current process(P1) , if both the conditions are met ,P1 will be busy in waiting in the while loop ( P1 will understand , there is a chance that P2 might be in CS or iterating in while loop)---

Case 1: If P2 is iterating in while loop ( interested[p1]==T && turn ==P2 is true)  so as soon as P1 sets the turn=P1 , P2 will break the while loop and enter the CS

(PS- the first process to set the turn variable will get first chance to access CS )

Case 2: If P2 is in CS, P1 will iterate in the while loop untill P2 sets interested[P2]=false i.e it comes out of the CS

P1

:repeat
L1:    intersted = true;
L2:    turn = 2; // turn= other process
L3:    while (intersted==True && turn==2) do no-op;
L4:    Enter critical section, perform actions, then
L5:    exit critical section
L6:    intersted = false;
L7:    Perform other non-critical section actions.
L8:Until false;

P2

:repeat
L1':    intersted = true;
L2':    turn = 1; // other process
L3':    while (intersted​​​​​​​==True && turn==1) do no-op;
L4':    Enter critical section, perform actions, then
L5':    exit critical section
L6':    intersted​​​​​​​ = false;
L7':    Perform other non-critical section actions.
L8':Until false;

BUT here in this question , turn variable is not used in the same way ,here turn=other process

so now how to identify the correct option , option C and D are eliminated as we always check interested [other process] == true and now setting turn=current process will violate Mutual Exclusion principle , consider Line 1,2,3 in the given code,initially interested &  interested= FALSE

P1:1,2,3,CS | P2:1,2,3,CS ( violates Mutual Exclusion )

so , turn =other process ,option B is correct.

Here, Question should specify this code section is executed by Process Pi. At first look it creates confusion.

code for Process Pi:

L1:repeat
L2:    flag[i] = true;
L3:    turn = j;
L4:    while (flag[j]==True && turn==j) // becoz you are the one who sets turn variable to j
do no-op;                    // if other process is interested then you should wait.
L5:    Enter critical section, perform actions, then
L6:    exit critical section
L7:    Flag[i] = false;
L8:    Perform other non-critical section actions.
L9:Until false;

Similarly code for Pj:

L1:repeat
L2:    flag[j] = true;
L3:    turn = i;
L4:    while (flag[i]==True && turn==i) // becoz you are the one who sets turn variable to j
do no-op;                       // if other process is interested then you should wait.
L5:    Enter critical section, perform actions, then
L6:    exit critical section
L7:    Flag[j] = false;
L8:    Perform other non-critical section actions.
L9:Until false;

This way solution ensures mutual exclusion. Hence option (b) is correct answer.