1,639 views

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}$

### 1 comment

Following the simple steps is also helpful in solving this question:

a.) Make Precedence Graph.

b.) Do topological Sorting to find the serial schedule.

a.) Making Precedence is like Every transaction is a vertex and inserts/creates a directed edge between transaction Ti and Tj, If there is a conflicting pair then Ti proceeds Tj.

If there is a cycle in the precedence graph then it’s not CSS else CSS.

b.) Now find the topological sort. You will get the serial schedule.

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.

reshown

Your point #4 is incorrect as, Line 4 and Line 8 are Non conflicting operations as both are Read operation only. But Line 5 and Line 8 are Conflicting operations as it is Read Write Conflict

edited by
corrected 👍

it was a typo.

Precedence graph from the schedule :

T1,T3,T2,T4 is also possible

@Shashwat Pandey T1, T3, T2, T4 topological order not possible because in finding for topological order from precedence graph, when T3 deleted after T1, in-order of T4 is 0 but T2 in-order is non-zero, so T4 will be deleted first then T2.

@Shashwat Pandey No. T2 is depending upon T4. Hence T4 must be completed before T2.

Correct ordering is only Option A $T1->T3->T4->T2$.

1
2