GATE CS 2024 Set 2 — Question 46

MSQ+2 / -0MediumSemaphoresProcess SynchronizationOperating System

Operating System → Process Synchronization → Semaphores

Last updated 20 August 2026

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?

T1 runs first and prints 1, T2 runs next and prints 2

T2 runs first and prints 1, T1 runs next and prints 2

T1 runs first and prints 1, T2 does not print anything (deadlock)

T2 runs first and prints 1, T1 does not print anything (deadlock)

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)

Solution

The semaphore s1 acts as a mutex protecting the critical sections of both threads. s2 is a synchronization semaphore.

Case 1: T1 executes first.

1.T1 executes wait(s1). s1 becomes 0. T1 enters its critical section.

2.T1 increments x to 1 and prints 1.

3.T1 executes wait(s2). Since s2 is 0, T1 blocks and waits for s2 to be signaled. T1 still holds s1 (s1=0).

4.T2 tries to execute wait(s1). Since s1 is 0, T2 blocks and waits for s1.

5.Result: T1 is waiting for s2 (signaled by T2), and T2 is waiting for s1 (signaled by T1). This is a deadlock. T1 has printed 1, T2 has printed nothing. This corresponds to option (C).

Case 2: T2 executes first.

1.T2 executes wait(s1). s1 becomes 0. T2 enters its critical section.

2.T2 increments x to 1 and prints 1.

3.T2 executes signal(s2). s2 becomes 1.

4.T2 executes signal(s1). s1 becomes 1.

5.T2 finishes.

6.Now T1 can execute wait(s1). s1 becomes 0.

7.T1 increments x to 2 and prints 2.

8.T1 executes wait(s2). Since s2 is 1 (signaled by T2), s2 becomes 0 and T1 proceeds.

9.T1 executes signal(s1).

10.Result: T2 prints 1, then T1 prints 2. This corresponds to option (B).

Option (A) is impossible because if T1 runs first, it deadlocks and never releases s1, so T2 cannot run to print 2.
Option (D) is impossible because if T2 runs first, it releases s1 and signals s2, allowing T1 to complete, so no deadlock occurs.

Thus, both (B) and (C) are possible outcomes.

GATE CS 2024 Set 2 — Question 46

Question

Correct answer

Solution

More questions on Process Synchronization