Skip to content
GATETECH
Official PYQ · 2022Q9Concurrency and SynchronizationMCQ1 mark

GATE CS 2022 Q9 — Concurrency and Synchronization

Explain with AI

Consider the following threads, T1,T2,\text{T}_{1}, \text{T}_{2}, and T3\text{T}_{3} executing on a single processor, synchronized using three binary semaphore variables, S1,S2,\text{S}_{1}, \text{S}_{2}, and S3,\text{S}_{3}, operated upon using standard wait()\textsf{wait}() and signal().\textsf{signal}(). The threads can be context switched in any order and at any time.

T1T2T3while(true){while(true){while(true){wait(S3);wait(S1);wait(S2);print(“C”);print(“B”);print(“A”);signal(S2);}signal(S3);}signal(S1);}\begin{array}{|c|c|c|} \hline \text{T}_{1} & \text{T}_{2} & \text{T}_{3} \\ \hline \text{while(true)} \{ & \text{while(true)} \{& \text{while(true)} \{ \\ \text{wait(S}_{3}); & \text{wait(S}_{1}); & \text{wait(S}_{2}); \\ \text{print(“C”)}; & \text{print(“B”)}; & \text{print(“A”)}; \\ \text{signal(S}_{2}); \} & \text{signal(S}_{3}); \} & \text{signal(S}_{1}); \} \\ \hline \end{array}

Which initialization of the semaphores would print the sequence BCABCABCA…?\text{BCABCABCA} \dots ?

Choose one option
View worked solution

Answer: C

To print the sequence BCABCABCA…\text{BCABCABCA}\dots, the first character printed must be B, followed by C, and then A.

  1. First print (B): Thread T2T_2 prints "B". For T2T_2 to execute first, its initial wait(S_1) must succeed. Thus, we must initialize S1=1S_1 = 1.
  2. Blocking other threads initially:
    • T1T_1 (which prints "C") must not run first, so wait(S_3) must block. Thus, S3=0S_3 = 0.
    • T3T_3 (which prints "A") must not run first, so wait(S_2) must block. Thus, S2=0S_2 = 0.

Let us trace the execution with the initialization S1=1,S2=0,S3=0S_1 = 1, S_2 = 0, S_3 = 0:

  • T2T_2 executes: wait(S_1) succeeds →\rightarrow prints "B" →\rightarrow signal(S_3) sets S3=1S_3 = 1.
  • T1T_1 executes: wait(S_3) succeeds →\rightarrow prints "C" →\rightarrow signal(S_2) sets S2=1S_2 = 1.
  • T3T_3 executes: wait(S_2) succeeds →\rightarrow prints "A" →\rightarrow signal(S_1) sets S1=1S_1 = 1.

This cycle repeats indefinitely, producing the desired sequence BCABCABCA…\text{BCABCABCA}\dots.

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

Published
Report a correction
Keep exploringMore Concurrency and Synchronization questions