Discussion
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?
Answer: A
The conflict equivalent serial schedule is \(T_{1} \to T_{3} \to T_{4} \to T_{2}\).
Two operations conflict when they come from different transactions, touch the same item and at least one is a write. Reading the schedule left to right gives these conflicts:
- on x: \(R_{4}(x)\) and \(R_{3}(x)\) come before \(W_{2}(x)\), giving \(T_{4} \to T_{2}\) and \(T_{3} \to T_{2}\);
- on y: \(R_{1}(y)\) and \(W_{1}(y)\) come before \(W_{3}(y)\) and \(R_{4}(y)\), giving \(T_{1} \to T_{3}\) and \(T_{1} \to T_{4}\); and \(W_{3}(y)\) comes before \(R_{4}(y)\), giving \(T_{3} \to T_{4}\).
The precedence graph has no cycle, and its only topological order is \(T_{1}, T_{3}, T_{4}, T_{2}\). The other orders break an edge: \(T_{1} \to T_{4} \to T_{3} \to T_{2}\) puts \(T_{4}\) before \(T_{3}\), \(T_{4} \to T_{1} \to \cdots\) puts \(T_{4}\) before \(T_{1}\), and \(T_{3} \to T_{1} \to \cdots\) puts \(T_{3}\) before \(T_{1}\).
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development