GATE CS 2024 Set 1 | Question 40

MCQ · 2 marks · −0.66

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?

  1. Option A: (a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3) (correct)
  2. Option B: (a = 3, b = 4); (a = 4, b = 3); (a = 3, b = 3)
  3. Option C: (a = 4, b = 4); (a = 4, b = 3); (a = 3, b = 4)
  4. Option D: (a = 2, b = 2); (a = 2, b = 3); (a = 3, b = 4)

Answer

(A)

Explanation

Each thread runs its two statements in order, so the four atomic statements interleave in \(\binom{4}{2} = 6\) ways. Writing the results as \((a, b)\):

  • T1 entirely first: \(a = 2\), \(b = 2\), then \(b = 4\), \(a = 4\): (4, 4).
  • T2 entirely first: \(b = 2\), \(a = 2\), then \(a = 3\), \(b = 3\): (3, 3).
  • Each of the other four orders runs a = a + 1 before a = 2 * a and b = 2 * b before b = b + 1, giving (4, 3).

(3, 4) is impossible: \(a = 3\) needs T2 to finish before T1 starts, while \(b = 4\) needs T1 to finish before T2 starts. Options B, C and D all contain it.

Answer: A