Consider the following two threads T1 and T2 that update two shared variables…
2024
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. Which one of the following options lists all the possible combinations of values of a and b after both T1 and T2 finish execution?
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.
(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)
Attempted by 197 students.
Show answer & explanation
Correct answer: A
Key insight: the final value of each variable depends only on the relative order of that variable's two operations.
For a: if "a = a + 1" happens before "a = 2 * a", final a = (1 + 1) * 2 = 4; if "a = 2 * a" happens before "a = a + 1", final a = (1 * 2) + 1 = 3.
For b: if "b = b + 1" happens before "b = 2 * b", final b = (1 + 1) * 2 = 4; if "b = 2 * b" happens before "b = b + 1", final b = (1 * 2) + 1 = 3.
Because each thread preserves the order of its two statements, not all four cross-combinations are achievable. Considering the valid interleavings gives exactly three distinct final states:
(a = 4, b = 4) — both increments happen before both doubles.
(a = 3, b = 3) — both doubles happen before the increments.
(a = 4, b = 3) — the increment of a happens before its doubling (so a = 4) while the doubling of b happens before its increment (so b = 3). Several interleavings produce this combination.
Therefore the complete set of possible final (a, b) pairs is: (a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3).
A video solution is available for this question — log in and enroll to watch it.