Official PYQ · 2026Set 2 · Q41Concurrency and SynchronizationMSQ2 marks

GATE CS 2026 Set 2 Q41 — Concurrency and Synchronization

Consider three processes $\text{P1, P2}$ , and $\text{P3}$ running identical code, as shown in the pseudocode below. $\text{A}$ and $\text{B}$ are two binary semaphores initialized to $1$ and $0$ , respectively. $\text{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?

View worked solution

Answer: A;B;C

Let us analyze the execution of the three processes step-by-step with the initial values $A = 1$ , $B = 0$ , and $X = 0$ :

First process (say $P_1$ ) enters the critical section:
- Prints *, increments $X$ to $1$ .
- Since $X \neq 2$ , it skips the if block, signals $A$ ( $A=1$ ), and blocks at Wait(B).
Second process (say $P_2$ ) enters the critical section:
- Prints *, increments $X$ to $2$ .
- Since $X == 2$ , it prints $, signals $B$ ( $B=1$ ), and then signals $A$ ( $A=1$ ).
- At this point, the output prefix is strictly **$.

Since $P_3$ cannot enter the critical section until $P_2$ signals $A$ (which happens only after printing $</code>), the third <code>*</code> cannot be printed before <code>$ . Thus, Option D (***$###) is impossible.

After $P_2$ signals $A$ and $B$ :

$P_3$ can enter the critical section to print the third *.
$P_1$ and $P_2$ can proceed past Wait(B) to print #.
$P_3$ can only print its # after it has printed its *. Thus, at most two #s (from $P_1$ and $P_2$ ) can be printed before the third *.

This allows the third * to appear in any of the following positions relative to the #s:

Before any #: **$*### (Option A)
After one #: **$#*## (Option B)
After two #s: **$##*# (Option C)

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Concurrency and Synchronization questions

GATE CS 2026 Set 2 Q41 — Concurrency and Synchronization

Related questions