Consider a multi-threaded program with two threads T1 and T2. The threads share two semaphores: s1 (initialized to 1) an...

Question

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.

// Code of T1
wait(s1);
x = x + 1;
print(x);
wait(s2);
signal(s1);

// Code of T2
wait(s1);
x = x + 1;
print(x);
signal(s2);
signal(s1);

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)

Accepted Answer

Option B: T2 runs first and prints 1, T1 runs next and prints 2 (and also C: T1 runs first prints 1, deadlock prevents T2 from printing). The primary possible correct completion outcome is B. Two threads share semaphores s1 (mutual exclusion, init=1) and s2 (synchronization, init=0). T1 must wait on s2 before it can signal(s1), meaning T1 needs T2 to signal(s2) first. If T1 runs first, it increments x, prints 1, then blocks on wait(s2). T2 cannot run because s1=0 (T1 holds it). T1 holds s1 and waits for s2; T2 waits for s1 — deadlock. If T2 runs first, it gets s1, prints 1, signals s2, signals s1; T1 can then get s1, print 2, wait(s2) blocks, but T2 already signaled s2 so T1 gets it, signals s1 — everything completes normally.