Consider a multi-threaded program with two threads T1 and T2. The threads…
2024
Consider a multi-threaded program with two threads T1 and T2. The threads share two semaphores: s1 (initialized to 1) and s2 (initialized to 0). The threads also share a global variable x (initialized to 0). The threads execute the code shown below.
Which of the following outcomes is/are possible when threads T1 and T2 execute concurrently?
- A.
T1 runs first and prints 1, T2 runs next and prints 2
- B.
T2 runs first and prints 1, T1 runs next and prints 2
- C.
T1 runs first and prints 1, T2 does not print anything (deadlock)
- D.
T2 runs first and prints 1, T1 does not print anything (deadlock)
Attempted by 155 students.
Show answer & explanation
Correct answer: B, C
Key idea: s1 enforces mutual exclusion for the critical section that updates and prints x; s2 is used by the thread that runs second to unblock the thread that waits on s2.
Case where the thread that performs signal(s2) runs first: That thread does wait(s1) → x = 1 → print(1) → signal(s2) → signal(s1). After it releases s1, the other thread can do wait(s1) → x = 2 → print(2) → wait(s2) (which succeeds because s2 was signalled). Outcome: the program prints 1 then 2.
Case where the thread that does wait(s2) runs first: That thread does wait(s1) → x = 1 → print(1) → wait(s2) and then blocks because s2 = 0. It still holds s1, so the other thread cannot pass wait(s1) to execute and signal s2. Result: deadlock — only the first thread printed 1 and the other thread prints nothing.
No other outcomes are possible because whichever thread acquires s1 first either signals s2 (allowing the other to run and print 2) or blocks on s2 while holding s1 (preventing the other from running).
A video solution is available for this question — log in and enroll to watch it.