GATE CS 2003 Q80 — Concurrency and Synchronization

To obtain the output sequence 001100110011..., we need strict alternation between Process $P$ (which prints 00) and Process $Q$ (which prints 11), starting with Process $P$.

Analyzing Option B:

• Initial State: $S = 1$, $T = 0$.
• Step 1: Process $P$ can proceed because $S = 1$.
  • At $W$, $P(S)$ decrements $S$ to $0$.
  • It prints 00.
  • At $X$, $V(T)$ increments $T$ to $1$.
• Step 2: Now $S = 0$ and $T = 1$.
  • If $P$ tries to run again, it blocks at $W$ because $S = 0$.
  • Process $Q$ can now proceed because $T = 1$.
  • At $Y$, $P(T)$ decrements $T$ to $0$.
  • It prints 11.
  • At $Z$, $V(S)$ increments $S$ to $1$.
• Step 3: Now $S = 1$ and $T = 0$.
  • If $Q$ tries to run again, it blocks at $Y$ because $T = 0$.
  • Process $P$ can run again.

This creates a strict alternating sequence: $P \rightarrow Q \rightarrow P \rightarrow Q \dots$, which guarantees the output 001100110011....

Eliminating Other Options:

• Option A: Since $S$ and $T$ are independent and both initialized to $1$, $P$ can run repeatedly without letting $Q$ run, or vice versa, leading to outputs like 000000....
• Option C: Since both $S$ and $T$ are initially $1$, Process $Q$ could execute first, producing an output starting with 11... instead of 00....
• Option D: Process $P$ only signals itself ($V(S)$ at $X$) and Process $Q$ only signals itself ($V(T)$ at $Z$). Since $T$ starts at $0$, $Q$ will block forever, and $P$ will run infinitely, producing 000000....