GATE 2024 CS (CS1) – Question 40
Two threads T1 (a=a+1; b=b+1;) and T2 (b=2*b; a=2*a;) update shared variables a and b, initially a=b=1. Each statement is atomic. Which option lists all possible combinations of a and b after both finish?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) (a=4,b=4); (a=3,b=3); (a=4,b=3)
Explanation
Let T1: $A_1: a{+}{+}$, then $B_1: b{+}{+}$. Let T2: $B_2: b\leftarrow2b$, then $A_2: a\leftarrow2a$. Start $a=b=1$. Each thread keeps its own order: $A_1<B_1$ and $B_2<A_2$.
Final $a$ depends only on the order of $A_1,A_2$: $A_1$ first gives $(1+1)\cdot2=4$; $A_2$ first gives $1\cdot2+1=3$.
Final $b$ depends only on the order of $B_1,B_2$: $B_1$ first gives $4$; $B_2$ first gives $3$.
- $(4,4)$: $A_1<A_2$ and $B_1<B_2$, e.g. $A_1,B_1,B_2,A_2$. Possible.
- $(4,3)$: $A_1<A_2$ and $B_2<B_1$, e.g. $B_2,A_1,A_2,B_1$. Possible.
- $(3,3)$: $A_2<A_1$ and $B_2<B_1$, e.g. $B_2,A_2,A_1,B_1$. Possible.
- $(3,4)$: needs $A_2<A_1<B_1<B_2<A_2$, a cycle. **Impossible.**
So the outcomes are $(4,4),(4,3),(3,3)$, option (A).