Consider the methods used by processes P1 and P2 for accessing their critical…

2010

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.

\(\begin{array}{|l|l|}\hline \textbf{Method used by P1} & \textbf{Method used by P2} \\ \hline \text{while (S1 == S2);} & \text{while (S1 != S2);} \\ \text{Critical Section} & \text{Critical Section} \\ \text{S1 = S2;} & \text{S2 = not(S1);} \\\hline \end{array}\)

Which one of the following statements describes the properties achieved?

  1. A.

    Mutual exclusion but not progress

  2. B.

    Progress but not mutual exclusion

  3. C.

    Neither mutual exclusion nor progress

  4. D.

    Both mutual exclusion and progress

Attempted by 286 students.

Show answer & explanation

Correct answer: A

Given Logic

Process P1

  • Waits while S1 equals S2

  • Enters critical section when S1 not equal S2

  • After execution, sets S1 equal to S2

Process P2

  • Waits while S1 not equal S2

  • Enters critical section when S1 equals S2

  • After execution, sets S2 equal to opposite of S1

1. Mutual Exclusion (Satisfied)

  • P1 enters only when S1 and S2 are different

  • P2 enters only when S1 and S2 are same

This means both cannot enter critical section at the same time, because their entry conditions are opposite.

So, mutual exclusion is satisfied

2. Progress (Not Satisfied)

Consider a situation:

  • Suppose S1 equals S2
    → P1 will wait
    → P2 can enter

  • After P2 finishes, it changes S2 to opposite of S1
    → Now S1 not equal S2
    → P1 can enter

So far fine.

But problem occurs in some cases:

  • If one process is not interested in entering (say P2 is idle), and S1 equals S2
    → P1 will keep waiting forever

Even though critical section is free, P1 cannot enter

This violates progress condition

Conclusion

  • Mutual exclusion is ensured because only one process can enter at a time

  • Progress is not guaranteed because a process may wait unnecessarily

Answer:

Mutual exclusion but not progress

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir