retagged by
8,321 views
12 votes
12 votes

Let $\textit{R}_{i}(z)$ and $\textit{W}_{i}(z)$ denote read and write operations on a data element $z$ by a transaction $\textit{T}_{i},$ respectively. Consider the schedule $\textit{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 $\textit{S}?$

  1. $T_{1} \rightarrow T_{3} \rightarrow T_{4} \rightarrow T_{2}$
  2. $T_{1} \rightarrow T_{4} \rightarrow T_{3} \rightarrow T_{2}$
  3. $T_{4} \rightarrow T_{1} \rightarrow T_{3} \rightarrow T_{2}$
  4. $T_{3} \rightarrow T_{1} \rightarrow T_{4} \rightarrow T_{2}$
retagged by

2 Answers

Best answer
13 votes
13 votes

Answer : Option A


Conflict operations:

  1. Transaction $T_i$ reading data item K, after that Transaction $T_j$ writing data item K
  2. Transaction $T_i$ writing data item K, after that Transaction $T_j$ reading data item K
  3. Transaction $T_i$ writing data item K, after that Transaction $T_j$ writing data item K.

Note that, Transaction $T_i$ writing data item ‘K’, after that Transaction $T_j$ writing data item ‘P’ are not conflict operations due to those are different data items.

Tabular representation of given schedule is :

If you observe,

  1. Line 1 and Line 6 are conflict operations. So in Serial schedule Transaction $T_4$ must be before  $T_2$
  2. Line 3 and Line 6 are conflict operations. So in Serial schedule Transaction $T_3$ must be before  $T_2$
  3. Line 4 and Line 7 are conflict operations. So in Serial schedule Transaction $T_1$ must be before  $T_3$
  4. Line 5 and Line 8 are conflict operations. So in Serial schedule Transaction $T_1$ must be before  $T_4$
  5. Line 7 and Line 8 are conflict operations. So in Serial schedule Transaction $T_3$ must be before  $T_4$

Accumulating all these points and running Topological sort, $T_1$ should be first followed by $T_3,T_4$ and $T_2$ in order.

selected by
12 votes
12 votes

Precedence graph from the schedule :

Answer:

Related questions

61 votes
61 votes
3 answers
2