GATE CS 2024 Set 2 Q.46: Process Synchronization and Concurrency

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                 // code of T2
wait(s1);                     wait(s1);
x = x+1;                      x = x+1;
print(x);                     print(x);
wait(s2);                     signal(s2);
signal(s1);                   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)

Official answer and solution

Official answer: B and C
From: Official GATE 2024 answer key

Solution

Trace both possible interleavings depending on whether T1 or T2 acquires semaphore s1 first.

Since s1 = 1 acts as a mutex protecting the start of both threads, either T1 or T2 acquires s1 first:

Case 1: T1 acquires s1 first (s1 becomes 0):
- T1 increments x to 1 and prints 1.
- T1 then executes wait(s2). Because s2 = 0, T1 blocks on s2 while still holding s1.
- T2 executes wait(s1) and blocks because s1 = 0. Neither thread can proceed (deadlock).
- This yields outcome (C) (and makes (A) impossible).
Case 2: T2 acquires s1 first (s1 becomes 0):
- T2 increments x to 1, prints 1, executes signal(s2) (s2 becomes 1), and executes signal(s1) (s1 becomes 1).
- T1 then acquires s1, increments x to 2, prints 2, passes wait(s2) (since s2 = 1), and releases s1.
- This yields outcome (B) (and makes (D) impossible).

Final answer

Options (B), (C)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 2 (CS2)
Question: 46 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source