GATE 2024 CS1 Q.40: solution and answer

GATE 2024 · CS1Q.40 · 2 marks · MCQ

Consider the following two threads T1 and T2 that update two shared variables a and b. Assume that initially a = b = 1. Though context switching between threads can happen at any time, each statement of T1 or T2 is executed atomically without interruption.

T1:

a = a + 1;
b = b + 1;

T2:

b = 2 * b;
a = 2 * a;

Which one of the following options lists all the possible combinations of values of a and b after both T1 and T2 finish execution?

(A)
(a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3)
(B)
(a = 3, b = 4); (a = 4, b = 3); (a = 3, b = 3)
(C)
(a = 4, b = 4); (a = 4, b = 3); (a = 3, b = 4)
(D)
(a = 2, b = 2); (a = 2, b = 3); (a = 3, b = 4)

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Option (A): the possible outcomes are (a = 4, b = 4), (a = 4, b = 3) and (a = 3, b = 3).

Official answer: ASource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

Name the statements: T1 has $s_{1}$ : a = a + 1 then $s_{2}$ : b = b + 1. T2 has $t_{1}$ : b = 2 * b then $t_{2}$ : a = 2 * a. Each statement is atomic, so the outcomes come from the interleavings that keep $s_{1}$ before $s_{2}$ and $t_{1}$ before $t_{2}$ . There are $(2 4) = 6$ of them. Start with $a = b = 1$ .
$s_{1} s_{2} t_{1} t_{2}$ : $a = 2$ , $b = 2$ , then $b = 4$ , $a = 4$ . Result $(a, b) = (4, 4)$ .
$s_{1} t_{1} s_{2} t_{2}$ : $a = 2$ , $b = 2$ , $b = 3$ , $a = 4$ . Result $(4, 3)$ .
$s_{1} t_{1} t_{2} s_{2}$ : $a = 2$ , $b = 2$ , $a = 4$ , $b = 3$ . Result $(4, 3)$ .
$t_{1} s_{1} s_{2} t_{2}$ : $b = 2$ , $a = 2$ , $b = 3$ , $a = 4$ . Result $(4, 3)$ .
$t_{1} s_{1} t_{2} s_{2}$ : $b = 2$ , $a = 2$ , $a = 4$ , $b = 3$ . Result $(4, 3)$ .
$t_{1} t_{2} s_{1} s_{2}$ : $b = 2$ , $a = 2$ , $a = 3$ , $b = 3$ . Result $(3, 3)$ .
The set of possible final values is ${(4, 4), (4, 3), (3, 3)}$ , which is option (A).
$(3, 4)$ never occurs. It would need $a$ to end on the $+ 1$ , so $s_{1}$ runs after $t_{2}$ , giving the order $t_{1} t_{2} s_{1} s_{2}$ . In that order $s_{2}$ is the last write to $b$ , so $b$ ends on the $+ 1$ and equals 3, not 4. Options (B), (C) and (D) each contain a pair that is not in the set, namely $(3, 4)$ or $(2, 2)$ or $(2, 3)$ , so they are wrong.

KEY IDEA

List every interleaving that keeps each thread's statement order, which gives 6 of them, and evaluate each one. Only three distinct pairs of final values appear.

WATCH OUT FOR

Assuming each variable can end on either operation independently, so that (3, 4) looks possible. For a to end on +1, T1's first statement must run after T2 has finished. That forces T1's second statement to be the last write to b.

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

GATE 2024 CS1 Q.40: solution and answer

Answer and solution

More Synchronisation questions