Consider Peterson's algorithm for mutual exclusion between two concurrent…
2001
Consider Peterson's algorithm for mutual exclusion between two concurrent processes i and j. The program executed by process i is shown below.
repeat
flag[i] = true;
turn = j;
while (P) do no-op;
enter critical section, perform actions, and 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
Attempted by 40 students.
Show answer & explanation
Correct answer: B
The correct answer is Option B. In Peterson's algorithm, process i first declares interest by setting flag[i] = true, then gives priority to the other process by setting turn = j. Process i should wait while the other process is interested and it is the other process's turn. Therefore the waiting predicate is flag[j] == true and turn == j. If either process j is not interested or the turn is not j, process i can enter the critical section.