IAE Academy

GATE 2026 CS2 Q.51: solution and answer

GATE 2026 · CS2Q.51 · 2 marks · MSQ

Consider three processes P1, P2, and P3 running identical code, as shown in the pseudocode below. A and B are two binary semaphores initialized to 1 and 0, respectively. X is a shared variable initialized to 0. Each line in the pseudocode is executed atomically.

Pseudocode of P1, P2, and P3

Wait(A);
Print(*);
X = X+1;
If (X == 2)
   {
      Print($);
      Signal(B);
   }
Signal(A);
Wait(B);
Print(#);
Signal(B);

Assume that any of the three processes can start to execute first and context switching can happen between these processes at any arbitrary time and in any arbitrary order.

Which of the following patterns is/are possible to be generated as an outcome of the execution of these three processes?

  1. (A)

    **$*###

  2. (B)

    **$#*##

  3. (C)

    **$##*#

  4. (D)

    ***$###

See the question in the paper
GATE 2026 CS2 question 51Tap to open full size

Answer and solution

ANSWER

Options A, B and C are possible. Option D is not.

Official answer: A, B, CSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

  1. Call the processes in the order in which they get through Wait(A): first, second, third. A starts at 1 and Signal(A) comes only after Print(*), X = X+1 and the If test. So that part is a critical section. The three * prints and the increments of X happen one process at a time.

  2. X becomes 2 in the second process to enter. That process prints $ straight after its own *, then does Signal(B). So the output always starts with *, *, $. The third * cannot appear before $, because the third process enters only after the second process does Signal(A), and that comes after $. Option D (***$###) has three * before $ and is impossible.

  3. B starts at 0 and the only Signal(B) before any # is the one in the second process, after $. Until then every process that has left its critical section is blocked on Wait(B). So no # can appear before $.

  4. After Signal(B), B = 1. A process that passes Wait(B) sets B = 0, prints #, and Signal(B) sets it back to 1. The waiting processes therefore get through one at a time, and all three # are eventually printed. Nothing deadlocks.

  5. After the prefix **$ the remaining output is the third process's * and three #. The first and second processes have left their critical sections, so their # may be printed before or after the third *. The third process's own # comes after its own *.

  6. So the third * cannot come after all three #. The possible tails are *### (A), #*## (B) and ##*# (C). Each is reachable. For example, for C, let the first and second processes print their #, and only then let the third process enter and print * and #.

  7. The pattern ***$### is impossible, so only A, B and C are possible.

KEY IDEA

Semaphore A makes the first half a critical section, so $ is always printed right after the second *. The semaphore B (initially 0) holds back every # until $. After that the three # print one at a time. The third * may fall anywhere in the tail except after all three #.

WATCH OUT FOR

Allowing a # before $, or a third * before $ (option D). Another slip is forgetting that the third process's * has to wait for Signal(A), which comes after $.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 7 Synchronisation questions, with notes

More Synchronisation questions