GATE 2024 CS2 Q.46: solution and answer

GATE 2024 · CS2Q.46 · 2 marks · MSQ

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?

GATE 2024 CS2 question 46: Two columns of code side by side, T1 on the left and T2 on the right, as given in the stem. — Figure from the GATE 2024 CS2 paper. It is part of the question.

(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)

Answer and solution

ANSWER

The possible outcomes are (B) and (C).

Official answer: B, CSource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

Initial values: $s 1 = 1$ , $s 2 = 0$ , $x = 0$ . Both threads begin with wait(s1), so whichever thread gets s1 first is alone in the section that follows. s1 acts as a lock.
Case 1, T1 first. wait(s1) makes $s 1 = 0$ , then $x = 1$ and T1 prints 1. T1 then calls wait(s2), but $s 2 = 0$ , so it blocks while still holding s1.
T2 now calls wait(s1), and $s 1 = 0$ , so it blocks too. Only T2 could signal(s2) and only T1 could signal(s1), and each is waiting for the other. This is a deadlock: T1 prints 1 and T2 prints nothing. So (C) is possible.
(A) is impossible. If T1 runs first, T2 can never get past wait(s1), because T1 releases s1 only after wait(s2), and only T2 can signal s2. So T2 never prints 2.
Case 2, T2 first. wait(s1) makes $s 1 = 0$ , then $x = 1$ and T2 prints 1. T2 never blocks after this point. signal(s2) makes $s 2 = 1$ and signal(s1) makes $s 1 = 1$ .
T1 now runs. wait(s1) gives $s 1 = 0$ , then $x = 2$ and T1 prints 2. wait(s2) succeeds ( $s 2$ goes from 1 to 0) and signal(s1) makes $s 1 = 1$ . Both threads finish, so (B) is possible.
(D) is impossible. After T2 runs first, it signals s2 before releasing s1, so by the time T1 can pass wait(s1) the value of s2 is already 1. T1 therefore never blocks on wait(s2) and always prints 2.
Possible outcomes: (B) and (C).

KEY IDEA

Trace each possible first thread. Whoever gets s1 first holds it as a lock. T1 holds s1 while it waits on s2, and only T2 can signal s2, but T2 is stuck at wait(s1). That is a deadlock. T2 signals s2 before it releases s1, so it never blocks and T1 always finishes after it.

WATCH OUT FOR

Thinking that T1 first can still let T2 print 2 (option A), or that T2 first can leave T1 stuck on wait(s2) (option D). Both miss that T1 keeps s1 while it waits, and that T2 signals s2 before it releases s1.

From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 7 Synchronisation questions, with notes

GATE 2024 CS2 Q.46: solution and answer

Answer and solution

More Synchronisation questions