GATE CS 2003 Q81 — Concurrency and Synchronization

To prevent the output string from containing substrings of the form $01^n0$ and $10^n1$ where $n$ is odd, we must ensure that any sequence of consecutive $1$s (sandwiched between $0$s) and any sequence of consecutive $0$s (sandwiched between $1$s) always has an even length.

Analyzing Option C:

• Synchronization setup:
  • $P(S)$ at $W$ and $V(S)$ at $X$
  • $P(S)$ at $Y$ and $V(S)$ at $Z$
  • $S$ is a binary semaphore initialized to $1$.
• Effect: Since both processes compete for the same semaphore $S$ at the beginning of their loops ($W$ and $Y$) and release it only at the end ($X$ and $Z$), the critical sections are mutually exclusive.
• This means once process $P$ starts executing, it cannot be interleaved by $Q$ until it finishes printing both $0$s. Similarly, $Q$ cannot be interleaved by $P$ until it finishes printing both $1$s.
• Thus, the characters $0$ and $1$ are always printed in atomic blocks of "00" and "11" respectively.
• Any output sequence will be a combination of these blocks, such as: $$\text{"001111000011"}$$
• In any such sequence, the number of consecutive $1$s or $0$s is always a multiple of $2$ (even). Hence, $n$ can never be odd, which satisfies the requirement.

Eliminating Other Options:

• Options A, B, and D: These options use two different semaphores ($S$ and $T$) initialized to $1$. This allows both processes $P$ and $Q$ to enter their loops simultaneously. Their print statements can interleave, leading to sequences like $010$ (where $n = 1$, which is odd).

Therefore, C is the correct option.