1
$\begingroup$

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

a) flag[j] = true and turn = i

b) flag[j] = true and turn = j

c) flag[i] = true and turn = j

d) flag[i] = true and turn = i

=============================================================================================

Now, in original peterson algorith, we have - 

I'm writing just the important lines from the algorithm and not the whole algorithm - 

1) flag [process] = 1;

2) turn = process ;

3) while (interested [other] == True && turn == process);

4) ///////***CS///////

5) flag [process] = false;

out of CS

Now, according to given question - 

flag[i] = true; turn = j; i.e process i is interested as flag[i] = true, but turn = j i.e turn is of process J.

So, which process is exactly currently executing? 

Question 1) Process i or Process j 

Question 2) Which process are we blocking in while loop i.e stopping to enter CS?

Also, at exit of CS - flag[i] = false;

this means, Process i, is already in CS?

Now Pi is already in CS, this means, process j is executing and we should hold it in while loop and not let process j eneter CS.

So, according to know peterson algo I mentioned above - 

line 3) while (flag [other] == True && turn == process);

while(flag [i] ==true && turn = j);

both are true so, while loop is true and process Pj should spin here and not go to CS. 

and this matches with option c. but answer is option b)

Also, folks are saying that option c) will allow both Pi and Pj into CS.

May you guys please explain, how option b) is answer!

$\endgroup$
1
$\begingroup$

Firstly, since the program at the start the question starts with "flag[$i$] = true", it should be run by Process $i$. Here is the full program again formatted slightly better. Note that the I replace "Enter critical section" and "exit critical section" with comment "// inside the critical section", since there is no code that actually corresponds to them. Once the process breaks out of the "while (P) do no-op" loop, it is in the critical section (CS). The process is exiting the critical section at the exact point of time when it is executing "flag[$i$] = false".

repeat

  • flag[$i$] = true;
  • turn = $j$;
  • while ($P$) do no-op;
  • Perform some actions // inside the critical section
  • flag[$i$] = false;
  • Perform other non-critical section actions.

Until false;

The following is the full program run by Process $j$. You should be able to figure out the code represented by $Q$ once you have accepted my answer. :)

repeat

  • flag[$j$] = true;
  • turn = $i$;
  • while ($Q$) do no-op;
  • Perform some actions // inside the critical section
  • flag[$j$] = false;
  • Perform other non-critical section actions.

Until false;

These two different programs together that are run by two different processes respectively at the same time competing for (some resources inside) the critical section (CS) is Peterson's algorithm.

Secondly, there is a fatal typo in the "important lines from the algorithm" with line numbers in the question. The second line

2) turn = process ;

should be

2) turn = other ;

Indeed, this line is the key to understand how Peterson's algorithm ensures mutual exclusion. Please note "the important lines from the algorithm" are executed sequentially at the same time by two processes, each considering itself as the "process" and the other process as "other" in those "important lines". By executing this line, each process tries letting the other process to have a higher priority over itself to enter CS..

A minor typo in OP's question is "while (interested [other] == True" should be "while flag [other] == True".

Thirdly, OP asks which process is exactly currently executing. The answer is not just Process $i$. The answer is not just Process $j$. The answer is both processes. In fact, we can assume both process are executing at all times, each executing a different program. That is what we mean by concurrent processes or concurrent programming. Is it surprising? Please note, however, if the question is which process is exactly executing the program written at the start of OP's question, then, as I have said at first, the answer is Process $i$.

Fourthly, OP asks "which process are we blocking in while loop i.e stopping to enter CS?". Of course, the answer is the current process, that is, the process that is currently executing that line of code. It is the other process if you write the loop uniformly as "while (flag [other] == True && turn == process)", which can be either Process $i$ or $i$. It can only be Process $i$ if the loop is "while (flag[$j$] = true and turn = $j$)". It can only be Process $j$ if the while loop is "flag[$i$] = true and turn = $i$)".

Lastly, the "option b) flag[$j$] = true and turn = $j$" should be what $P$ stands for. Here "flag[$j$] = true" means process $j$, the other process, is interested in entering or staying in the critical section(CS) while "turn = $j$" say that the other process is either holding CS or, if other process is interested in entering CS, it has the priority over the current process to enter CS. Both conditions together imply the current process cannot enter CS. Once Process $j$ is not interested in CS by setting flag[$j$] to false, or once the value of variable "turn" is $i$, meaning Process $i$ has a higher priority over Process $j$ to enter CS, the "while (P)" loop is broken and Process $i$ is in CS. (I am avoiding to say "enter CS" here, just to emphasize the fact that there is no other code that enables or represents the act of entering CS. Process $i$ enters CS by breaking out of that while loop.)

All other options, (a), (c) and (d), are apparently wrong. For more detailed analysis, please check Peterson algorithm at Wikipedia.

$\endgroup$
  • $\begingroup$ May you please tell me one more time, what's really happening! I get that, first Process Pi was running and you're saying that Process Pi is running with turn =j or Process j is running! I'm so confused, what process is currently running Pi or Pj? Also, which process is currently in CS? $\endgroup$ – Geeklovenerds Aug 1 '18 at 17:01
  • $\begingroup$ Jack Which is the process executing and what's the other process. Also, which process we want to spin at the while loop i.e not letting it into CS? I get that Pi is running and other process would be Pj, right? $\endgroup$ – Geeklovenerds Aug 1 '18 at 17:09
  • $\begingroup$ I've edited the question. $\endgroup$ – Geeklovenerds Aug 1 '18 at 17:12
  • 1
    $\begingroup$ Whichever process that is running the code in CS is currently in CS. Note there are multiple meanings of CS. One meaning is the textual code in the program of the two processes. There are two instance of this meaning: one in Process i's program and one in Process j's program. The other meaning is the time-space when one process is executing that part of the code, which can appear arbitrarily many times but without overlapping in time. I've edited my answer as well. $\endgroup$ – Apass.Jack Aug 1 '18 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.