GATE CSE 2024 | Set 1 | Question: 30

Question

​​​Consider the following two threads $\mathrm{T} 1$ and $\mathrm{T} 2$ that update two shared variables $\mathrm{a}$ and $\mathrm{b}$. Assume that initially $\mathrm{a}=\mathrm{b}=1$. Though context switching between threads can happen at any time, each statement of  $\mathrm{T} 1$ or  $\mathrm{T} 2$ is executed atomically without interruption.

$\begin{gathered}\mathrm{T} 1 \\ \mathrm{a}=\mathrm{a}+1; \\ \mathrm{~b}=\mathrm{b}+1;\end{gathered}$ $\quad$ $\begin{gathered}\mathrm{T} 2 \\ \mathrm{b}=\mathrm {2 * b};  \\ \mathrm{a}=\mathrm 2 * {a}; \end{gathered}$

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. $(\mathrm{a}=4, \mathrm{~b}=4) ;(\mathrm{a}=3, \mathrm{~b}=3) ;(\mathrm{a}=4, \mathrm{~b}=3)$
• B. $(\mathrm{a}=3, \mathrm{~b}=4) ;(\mathrm{a}=4, \mathrm{~b}=3) ;(\mathrm{a}=3, \mathrm{~b}=3)$
• C. $(\mathrm{a}=4, \mathrm{~b}=4) ;(\mathrm{a}=4, \mathrm{~b}=3) ;(\mathrm{a}=3, \mathrm{~b}=4)$
• D. $(\mathrm{a}=2, \mathrm{~b}=2) ;(\mathrm{a}=2, \mathrm{~b}=3) ;(\mathrm{a}=3, \mathrm{~b}=4)$ 

Answer 1

Notation - $(x, y)$ means value of variable $a=x, b=y$.

Serial execution T1 followed by T2 results in $(4, 4)$.

Serial execution T2 followed by T1 results in $(3, 3)$.

Execution in the order T21 - T11 - T12 - T22 results in $(4, 3)$.

Getting result $(3, 4)$, $(2, 3)$ and $(2, 2)$ are not possible.

Answer - A

T1i and T2j means $i^{th}$ instruction of T1 and $j^{th}$ instruction of T2.

Answer 2

Let's assume that the given statements are as $A, B,C,D$. we can execute these statements in any order and can preempt at any point in time.

• $A: a=a+1$
• $B: b=b+1$
• $C: b=2\times b$
• $D:a=a\times 2$

 The possible execution sequences are as follows:

1. $A,B,C,D$
2. $A,C,D,B$
3. $A,C,B,D$
4. $C,D,A,B$
5. $C,A,B,D$
6. $C,A,D,B$

Let's understand how different output is generated when we interchange the execution order.

1) $A,B,C,D$: in this sequence initial value of $a=1,b=1$. 

    when $A$ is executed $a$ update it's value as $a=2$,$b=1$

    when $B$ is executed $b$ update it's value as $a=2$,$b=2$

   when $C$ is executed $b$ update it's value as $a=2$,$b=4$

   when $D$ is executed $a$ update it's value as $a=4$,$b=4$

___________________________________________________________________

2) $A,C,D,B$: in this sequence initial value of $a=1,b=1$. 

    when $A$ is executed $a$ update it's value as $a=2$,$b=1$

    when $C$ is executed $b$ update it's value as $a=2$,$b=2$

   when $D$ is executed $b$ update it's value as $a=4$,$b=2$

   when $B$ is executed $a$ update it's value as $a=4$,$b=3$

___________________________________________________________________

3) $A,C,B,D$: in this sequence initial value of $a=1,b=1$. 

    when $A$ is executed $a$ update it's value as $a=2$,$b=1$

    when $C$ is executed $b$ update it's value as $a=2$,$b=2$

   when $B$ is executed $b$ update it's value as $a=2$,$b=3$

   when $D$ is executed $a$ update it's value as $a=4$,$b=3$

___________________________________________________________________

4) $C,D,A,B$: in this sequence initial value of $a=1,b=1$. 

    when $C$ is executed $a$ update it's value as $a=1$,$b=2$

    when $D$ is executed $b$ update it's value as $a=2$,$b=2$

   when $A$ is executed $b$ update it's value as $a=3$,$b=2$

   when $B$ is executed $a$ update it's value as $a=3$,$b=3$

___________________________________________________________________

5) $C,A,B,D$: in this sequence initial value of $a=1,b=1$. 

    when $C$ is executed $a$ update it's value as $a=3$,$b=2$

    when $A$ is executed $b$ update it's value as $a=2$,$b=2$

   when $B$ is executed $b$ update it's value as $a=2$,$b=3$

   when $D$ is executed $a$ update it's value as $a=4$,$b=3$

___________________________________________________________________

6) $C,A,D,B$: in this sequence initial value of $a=1,b=1$. 

    when $C$ is executed $a$ update it's value as $a=1$,$b=2$

    when $A$ is executed $b$ update it's value as $a=2$,$b=2$

   when $D$ is executed $b$ update it's value as $a=4$,$b=2$

   when $B$ is executed $a$ update it's value as $a=4$,$b=3$

___________________________________________________________________

We can see that the given program produces three different values of $a's.b's$ as $(4,4),(4,3),(3,3)$

Option $(A)$ is correct.

A similar concept was asked in GATE CSE 2015 Set 1 | Question: 9