GATE 2022 CS Q.19: solution and answer

GATE 2022 · CSQ.19 · 1 mark · MCQ

Consider the following threads, T1, T2, and T3 executing on a single processor, synchronized using three binary semaphore variables, S1, S2, and S3, operated upon using standard wait() and signal(). The threads can be context switched in any order and at any time.

T_{1} while(true) {wait (S_{3}); print("C"); signal (S_{2});} T_{2} while(true) {wait (S_{1}); print("B"); signal (S_{3});} T_{3} while(true) {wait (S_{2}); print("A"); signal (S_{1});}

Which initialization of the semaphores would print the sequence BCABCABCA....?

GATE 2022 CS question 19: A three-column table with headers T1, T2, T3. — Figure from the GATE 2022 CS paper. It is part of the question.

(A)
S1 = 1; S2 = 1; S3 = 1
(B)
S1 = 1; S2 = 1; S3 = 0
(C)
S1 = 1; S2 = 0; S3 = 0
(D)
S1 = 0; S2 = 1; S3 = 1

Answer and solution

ANSWER

Option (C): $S_{1} = 1; S_{2} = 0; S_{3} = 0$ .

Official answer: CSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

Each thread waits on one semaphore and signals another. $T_{2}$ (prints B) signals $S_{3}$ , which enables $T_{1}$ (prints C). $T_{1}$ signals $S_{2}$ , which enables $T_{3}$ (prints A). $T_{3}$ signals $S_{1}$ , which enables $T_{2}$ again. So the semaphores pass a single token round $T_{2} \to T_{1} \to T_{3} \to T_{2}$ , which gives the output BCABCA....
The output must begin with B, so at the start only $T_{2}$ may be able to pass its wait, and neither $T_{1}$ nor $T_{3}$ may be able to. That requires $S_{1} = 1$ , $S_{2} = 0$ and $S_{3} = 0$ .
Trace from $(S_{1}, S_{2}, S_{3}) = (1, 0, 0)$ . Only $T_{2}$ can pass wait(S_1), because $S_{2} = 0$ and $S_{3} = 0$ block the others. $T_{2}$ prints B and signals $S_{3}$ , giving $(0, 0, 1)$ . Now only $T_{1}$ can proceed.
$T_{1}$ takes $S_{3}$ to 0, prints C and signals $S_{2}$ , giving $(0, 1, 0)$ . Now only $T_{3}$ can proceed. It takes $S_{2}$ to 0, prints A and signals $S_{1}$ , giving $(1, 0, 0)$ . The state is back at the start, so BCA repeats for ever, whatever the context-switch order.
The other options fail. (A) $(1, 1, 1)$ enables all three threads, so A or C can be printed first. (B) $(1, 1, 0)$ enables $T_{2}$ and $T_{3}$ , so $T_{3}$ can print A before any B. (D) $(0, 1, 1)$ enables $T_{1}$ and $T_{3}$ but not $T_{2}$ , so the first letter is C or A, never B.
Answer: (C).

KEY IDEA

Binary semaphores can pass a token around a cycle of threads. To force one fixed order, initialise exactly one semaphore to 1, the one the first thread in the order waits on, and set the rest to 0.

WATCH OUT FOR

Giving the starting semaphores of the other threads a value of 1 as well. Then several threads are enabled at once, and the context-switch order can print A or C before B.

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

GATE 2022 CS Q.19: solution and answer

Answer and solution

More Synchronisation questions