GATE CSE 2001 | Question: 2.22

Question

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

Comments

@Arjun if this question comes in MSQ then answer would be b,c ?
as we don’t have to consider deadlocks here.

---

@JAINchiNMay in option c there will be no mutual exclusion as the current process will not check status of another process

---

@cool_dude_69 suppose flag[i] is line 1… and there are 2 processes...then when P1 executes line 1-3 it goes into cs and then prempt it...now when P2 comes it also executes 1-3 but this time the while loop will return true hence i think according to option c ME is also there … correct me where i am wrong ?

Answer 1

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.