GATE CS 2024 Set 1 Q.40: Process Synchronization and Concurrency

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	T2
a = a + 1;	b = 2 * b;
b = b + 1;	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 = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3)

(a = 3, b = 4); (a = 4, b = 3); (a = 3, b = 3)

(a = 4, b = 4); (a = 4, b = 3); (a = 3, b = 4)

(a = 2, b = 2); (a = 2, b = 3); (a = 3, b = 4)

Official answer and solution

Official answer: A
From: Official GATE 2024 answer key

Solution

Label the four atomic statements $S_1, S_2$ (in T1) and $S_3, S_4$ (in T2) and evaluate all valid topological interleavings preserving $S_1 \prec S_2$ and $S_3 \prec S_4$ .

Let T1 consist of $S_1:$ a = a + 1; followed by $S_2:$ b = b + 1;, and T2 consist of $S_3:$ b = 2 * b; followed by $S_4:$ a = 2 * a;.

For variable a (initially $1$ ): if $S_1 \prec S_4$ , then $a = 2(1 + 1) = 4$ ; if $S_4 \prec S_1$ , then $a = 2(1) + 1 = 3$ .
For variable b (initially $1$ ): if $S_2 \prec S_3$ , then $b = 2(1 + 1) = 4$ ; if $S_3 \prec S_2$ , then $b = 2(1) + 1 = 3$ .

Notice that $(a = 3, b = 4)$ requires both $S_4 \prec S_1$ and $S_2 \prec S_3$ . Combined with the thread program orders $S_1 \prec S_2$ and $S_3 \prec S_4$ , this would create a cycle $S_1 \prec S_2 \prec S_3 \prec S_4 \prec S_1$ , which is impossible! The other three outcomes are all realizable:

$S_1, S_2, S_3, S_4 \implies (a = 4, b = 4)$
$S_3, S_4, S_1, S_2 \implies (a = 3, b = 3)$
$S_1, S_3, S_2, S_4 \implies (a = 4, b = 3)$

Final answer

Option (A)

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 1 (CS1)
Question: 40 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