GATE 2026 CS (CS2) – Question 51
Consider three processes $P_1$, $P_2$, and $P_3$ running identical code shown below. $A$ and $B$ are binary semaphores initialized to 1 and 0, respectively. $X$ is a shared variable initialized to 0. Each line executes atomically.
Wait(A);
Print(*);
X = X + 1;
If (X == 2) {
Print(dollar-sign);
Signal(B);
}
Signal(A);
Wait(B);
Print(#);
Signal(B);Assume any process may start first, and context switching may happen arbitrarily. Which of the following output patterns are possible?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) **dollar-sign*###; (B) **dollar-sign#*##; (C) **dollar-sign##*#
Explanation
Semaphore $A$ serializes the critical section containing the `*` prints and the update of $X$. The `dollar-sign` is printed exactly when the second process increments $X$ to 2, so it must appear immediately after the second `*` while that process still holds semaphore $A$. After that, semaphore $B$ becomes available, so the first two `#` prints and the third process's `*` can interleave in different ways, provided each process prints `#` only after it has printed its own `*`. Patterns (A), (B), and (C) satisfy these constraints. Pattern (D) would require the third `*` to appear before `dollar-sign`, which is impossible because `dollar-sign` is printed immediately after the second `*`. Therefore, the possible patterns are (A), (B), and (C).