The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+29 votes
3.2k 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
asked in Operating System by Veteran (59.6k points)
edited by | 3.2k views
0

I think if we will change 

turn = j; --> turn = i; 

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

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

5 Answers

+29 votes
Best answer

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[1]=$ true $f[2]=$true turn$=2$ $p1$ will now check for condition while($f[2]=$ 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[1]=$ 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[1]=$ false hence, no two process can enter into CS at a time so predicate $p$ is option (B).

answered by Loyal (8.3k points)
edited by
0
C is also correct ans...........
0

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

0
@bikram sir Are B and C both the correct answer?
+5
+2
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:-

c:) creates deadlock

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.
0
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.
0
can anybody explain what is the issue with option A?
0
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...
0
After exit of critical section by pi it will set the flag to false, so that pj can enter
+1

@Shubhgupta

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! 

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

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

0
in pj flag[j]=false i think
+12 votes

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 :)

answered by Active (1.7k points)
+3 votes

Option C is correct(Best option)

First of all its not a complete implementation of Peterson Algorithm. Here we need to check Mutual Exclusion. Now for that Process i is in CS and Process j is trying to enter into CS. How I know it ? It can be seen in code " turn = j " that means Process j is trying to enter CS. Therefore to make sure Mutual Exclusion is there Process j should keep on iterating in the while( ) loop while Process i is in CS . Now since Process i is in CS we need to make sure that when Process i exits CS then only Process j enters. Therefore for that to happen Process i must execute " Flag[i] = false". From this we can take condition that  "Flag[i] = true " should be put in while loop. Secondly since "turn = j" therefore " turn == j " should also be added in while loop. Since turn = j is given therefore i would best choose option c rather d.

answered by Junior (603 points)
edited by
+10
Here first flag[i] and turn vaiables are set and then compared with same value:

flag[i] = true; 
turn = j; 
while(flag[i] == true and turn ==j); // it will always give infinite loop
0
but when the second process executes line no.2 won't the condition in while of the first process become(true&&false) and it would enter the critical section?
0 votes

Ans should be (c) as it should be FLAG[other] which is i and turn of current is checked i.e j

answered by (451 points)
0
'i' is the process which is executing the code!
–2 votes
ans is C is correct because in case of option B, the process will enter simultaneously enter into the critical section but incase of C mutual exclusion will be ensured.
answered by (205 points)
Answer:

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

42,513 questions
48,529 answers
155,004 comments
63,365 users