GATE CS 1997 Q6.8 — Concurrency and Synchronization

Let us analyze the behavior of the processes. Typically, a semaphore mutex used for mutual exclusion is initialized to $1$.

For processes $P_1$ to $P_9$, the code is:

repeat 
    P(mutex)
    {Critical Section}
    V(mutex)
forever

For process $P_{10}$, replacing the entry P(mutex) with V(mutex) gives:

repeat 
    V(mutex)
    {Critical Section}
    V(mutex)
forever

Step-by-Step Execution Trace:

1. Initially, mutex = 1.
2. Process $P_{10}$ executes its entry operation V(mutex). Since V is an increment operation, mutex becomes $2$. $P_{10}$ enters the critical section.
3. Inside the loop, $P_{10}$ can execute V(mutex) again at the exit, making mutex = 3.
4. Since $P_{10}$ does not have any blocking P(mutex) operation, it can loop repeatedly, executing V(mutex) each time and increasing the value of mutex arbitrarily high (e.g., $10$ or more).
5. With mutex ≥ 9, all other nine processes ($P_1$ to $P_9$) can execute their P(mutex) operations without blocking and enter the critical section simultaneously.

Thus, all $10$ processes can be inside the critical section at the same time. Since $10$ is not listed in options A, B, or C, the correct option is D (None of the above).