The GATE Grind

GATE 2024 CS (CS2) – Question 46

Operating System · Concurrency and Synchronization · 2 marks · Multiple select

Consider a multi-threaded program with two threads T1 and T2 sharing semaphores s1 (initialized to 1) and s2 (initialized to 0) and a global variable x (initialized to 0). T1: wait(s1); x = x+1; print(x); wait(s2); signal(s1). 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. T1 runs first and prints 1, T2 runs next and prints 2
  2. T2 runs first and prints 1, T1 runs next and prints 2
  3. T1 runs first and prints 1, T2 does not print anything (deadlock)
  4. T2 runs first and prints 1, T1 does not print anything (deadlock)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (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)

Explanation

If T1 goes first it holds s1 and blocks on wait(s2), which only T2 can signal, but T2 is blocked on s1: deadlock (C). If T2 goes first it prints 1, signals s2 and s1, then T1 runs and prints 2 (B). A is impossible and D cannot deadlock.