edited by
26,555 views
58 votes
58 votes

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
edited by

5 Answers

Best answer
52 votes
52 votes

 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$".

selected by
36 votes
36 votes

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

edited by
18 votes
18 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 :)

0 votes
0 votes

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.

Answer:

Related questions

49 votes
49 votes
4 answers
1
Kathleen asked Sep 14, 2014
65,297 views
Consider a machine with $64$ MB physical memory and a $32$-bit virtual address space. If the page size s $4$ KB, what is the approximate size of the page table?$\text{16 ...
25 votes
25 votes
2 answers
2
Kathleen asked Sep 14, 2014
10,420 views
Which of the following requires a device driver?RegisterCacheMain memoryDisk