GATE CS 2026 Set 2 Q.51: Process Synchronization and Concurrency

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.

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?

**$*###

**$#*##

**$##*#

***$###

Official answer and solution

Official answer: A, B and C
From: Official GATE 2026 answer key

Solution

Trace the critical section protected by semaphore $A$ : the second process to enter prints the second * and immediately prints $ before releasing $A$ .

Semaphore $A$ (initialized to $1$ ) provides mutual exclusion over the block from Wait(A) through Signal(A):

The first process to acquire $A$ prints *, sets $X = 1$ , and executes Signal(A).
The second process to acquire $A$ prints *, sets $X = 2$ , and inside the same critical section executes Print($) and Signal(B) before calling Signal(A).
Therefore, every valid output must begin with **$ (ruling out Option D ***$###, since the third process cannot enter Wait(A) and print the third * until the second process has already printed $ and called Signal(A)).
Once Signal(B) and Signal(A) are executed by the second process, two processes have completed the first phase and can pass through Wait(B); Print(#); Signal(B); in any interleaved order with the third process executing Wait(A); Print(*); X=3; Signal(A);.
- If the third process prints * before any # is printed: **$*### (Option A).
- If one process prints #, then the third process prints *, then the remaining two # are printed: **$#*## (Option B).
- If both of the first two processes print # before the third process prints *: **$##*# (Option C).

Final answer

Options (A), (B), (C)

Common trap

Selecting (D) by forgetting that Print($) is inside the critical section guarded by semaphore A.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 51 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source