GATE CS 2010 Q45 — Concurrency and Synchronization

To determine how many times process $P_0$ prints '0', let us trace the execution of the concurrent processes with binary semaphores initialized to $S_0 = 1, S_1 = 0, S_2 = 0$.

Initial State: $S_0 = 1, S_1 = 0, S_2 = 0$.

1. $P_0$ executes wait(S0), decrements $S_0$ to $0$, prints '0' (1st print), and executes release(S1) and release(S2).
   Current state: $S_0 = 0, S_1 = 1, S_2 = 1$.

Since $P_1$ and $P_2$ are non-looping processes, they can each execute their release(S0) at most once. Depending on the scheduling order, we have two possible cases:

• Case 1 (Interleaved execution - 3 prints):
  • $P_1$ runs: wait(S1) $\rightarrow S_1 = 0$, then release(S0) $\rightarrow S_0 = 1$.
  • $P_0$ runs: wait(S0) $\rightarrow S_0 = 0$, prints '0' (2nd print), and sets $S_1 = 1, S_2 = 1$.
  • $P_2$ runs: wait(S2) $\rightarrow S_2 = 0$, then release(S0) $\rightarrow S_0 = 1$.
  • $P_0$ runs: wait(S0) $\rightarrow S_0 = 0$, prints '0' (3rd print), and sets $S_1 = 1, S_2 = 1$.
  • $P_0$ loops and blocks on wait(S0). Since both $P_1$ and $P_2$ have terminated, $P_0$ is blocked forever. Total prints = 3.
• Case 2 (Consecutive execution - 2 prints):
  • $P_1$ runs: wait(S1) $\rightarrow S_1 = 0$, then release(S0) $\rightarrow S_0 = 1$.
  • $P_2$ runs: wait(S2) $\rightarrow S_2 = 0$, then release(S0). Since $S_0$ is a binary semaphore and already $1$, it remains $1$.
  • $P_0$ runs: wait(S0) $\rightarrow S_0 = 0$, prints '0' (2nd print), and sets $S_1 = 1, S_2 = 1$.
  • $P_0$ loops and blocks on wait(S0). Since both $P_1$ and $P_2$ have terminated, $P_0$ is blocked forever. Total prints = 2.

Since the minimum number of prints is 2 and the maximum is 3, process $P_0$ will print '0' at least twice.