GATE CS 2024 Set 2 | Question 46

MSQ · 2 marks

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?

  1. Option A: T1 runs first and prints 1, T2 runs next and prints 2
  2. Option B: T2 runs first and prints 1, T1 runs next and prints 2 (correct)
  3. Option C: T1 runs first and prints 1, T2 does not print anything (deadlock) (correct)
  4. Option D: T2 runs first and prints 1, T1 does not print anything (deadlock)

Answer

(B), (C)

Explanation

Only one thread at a time can be between wait(s1) and signal(s1), and s2 starts at 0.

  • If T2 gets s1 first, it prints 1, and its signal(s2) and signal(s1) never block. T1 then enters, prints 2, finds s2 at 1 and finishes. So (B) is possible, and (D) is not: T1 cannot stay blocked.
  • If T1 gets s1 first, it prints 1 and blocks on wait(s2) while still holding s1. Only T2 could signal s2, but it is stuck at wait(s1), so both wait forever and T2 prints nothing. So (C) is possible and (A) is not.

Answer: B, C