Question

Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned. (GATE 2010)

Method used by P1 :
while(S1==S2);
Critical section
S1 = S2;
Method used by P2 :
while(S1!=S2);
Critical section
S2 = not(S1);

Which of the following statements describes properties achieved ?
a) Mutual exclusion but not progress
b) Progress but not mutual exclusion
c) Neither mutual exclusion nor progress
d) Both mutual exclusion and progress

Answer 1

The methods used by processes P1 and P2 achieve both mutual exclusion and progress.

Step-by-step explanation:

The methods used by processes P1 and P2 are a form of synchronization called busy waiting or spinlock. In P1's method, it continuously checks if S1 is equal to S2. Once S1 and S2 are equal, it enters the critical section, performs its task, and then updates S1 to match S2. Similarly, P2's method checks if S1 is not equal to S2, enters the critical section, performs its task, and then updates S2 to be the opposite of S1.

These methods achieve mutual exclusion because only one process can enter the critical section at a time. When P1 is in the critical section, P2 cannot enter, and vice versa. This ensures that conflicting operations don't occur simultaneously.

These methods also achieve progress because if one process is waiting to enter the critical section, the other process will eventually allow it to enter. For example, if P1 is waiting for P2 to finish, P2 will eventually update S1, allowing P1 to proceed.

Therefore, the correct answer is Both mutual exclusion and progress (option d).