Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict serializable?

GATE : Computer Science and IT

Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict serializable?

A. r1(x); r2(x); w1(x); r3(x); w2(x)

B. r2(x); r1(x); w2(x); r3(x); w1(x)

C. r3(x); r2(x); r1(x); w2(x); w1(x)

D. r2(x); w2(x); r3(x); r1(x); w1(x)

Solution

D. r2(x); w2(x); r3(x); r1(x); w1(x)

Explanation

If there is a cycle in precedence graph then the schedule is not conflict serializable. But in option D, there is no interleaving of operations. The option D has first all operations of transaction T2, then T3 and T1.It is a conflict equivalent to T2→T3→T1 & T3→T2→T1