GATE 2022 CS – Question 39
Let $R_i(z)$ and $W_i(z)$ denote read and write operations on a data element $z$ by a transaction $T_i$, respectively. Consider the schedule $S$ with four transactions.
$S: R_4(x)R_2(x)R_3(x)R_1(y)W_1(y)W_2(x)W_3(y)R_4(y)$
Which one of the following serial schedules is conflict equivalent to $S$?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $T_1\to T_3\to T_4\to T_2$
Explanation
Schedule $S: R_4(x)\,R_2(x)\,R_3(x)\,R_1(y)\,W_1(y)\,W_2(x)\,W_3(y)\,R_4(y)$.
List conflicting pairs (same item, different transactions, at least one write), in schedule order:
- On $x$: $R_4(x),R_2(x),R_3(x)$ all come before $W_2(x)$: $T_4\to T_2$ and $T_3\to T_2$.
- On $y$: $R_1(y),W_1(y)$ come before $W_3(y)$: $T_1\to T_3$. $W_1(y)$ and $W_3(y)$ come before $R_4(y)$: $T_1\to T_4$ and $T_3\to T_4$.
Edges: $T_1\to T_3$, $T_1\to T_4$, $T_3\to T_4$, $T_3\to T_2$, $T_4\to T_2$. The only topological order is
$$T_1\to T_3\to T_4\to T_2:\text{ option (A)}.$$