GATE CSE 2007 | Question: 64

Question

Consider the following schedules involving two transactions. Which one of the following statements is TRUE?

• $S_1 :r_1(X); r_1(Y); r_2(X); r_2(Y); w_2(Y); w_1(X)$
• $S_2 :r_1(X); r_2(X); r_2(Y); w_2(Y); r_1(Y); w_1(X)$

• A. Both $S_1$ and $S_2$ are conflict serializable.

• B. $S_1$ is conflict serializable and $S_2$ is not conflict serializable.

• C. $S_1$ is not conflict serializable and $S_2$ is conflict serializable.

• D. Both $S_1$ and $S_2$ are not conflict serializable.

Comments

Also S1: not a view serializable as no blind write present

---

How to check? (to minimize chances of silly error during exams)

1st instruction is read on X from T1, so look for W. We get w2(Y), see if it for same variable and then if its from different transaction. Here its not so ignore and move ahead. w1(X), same transaction so ignore.

2nd instruction is read on Y from T2, so look for W. We get w2(Y), see if it for same variable and then if its from different transaction. Here it is both, so draw a directed edge from T1 -> T2. As there are only 2 transaction and we already have an edge from T1->T2, so no need to check for subsequent instructions.

3rd instruction is read on X from T2, so look for W. We get w2(Y), see if it for same variable and then if its from different transaction. Here it is both, so draw a directed edge from T2 -> T1.

As there is a cycle so its not CS.

Answer 1

• For $S_1$ : it is not conflict serializable 
• For $S_2$ : it is conflict serializable

Answer is option C.

Answer 2

You can make a Precedence graph for the two schedules.And check for the conflicts pairs making a Cycle.

S1 makes a cycle. T1-->T2 and T2-->T1. And hence is not Conflict Serializable.

S2 does not makes cycle and has transition from T2-->T1 only. And hence is Conflict Serializable.

Conflict Pairs: RW, WR, WW.

Comments

These WR RW WW are adjacent in the transactions T1 and T2 or any where (in cross or different) in the transaction. please mention. Gate Keeda

Answer 3

Ans - Option C

In S1: RW conflict from 1-2 and 2-1 so It is not C.S.

In S2: RW conflict AND WR conflict from 2-1 only so it is C.S.

Answer 4

As per the precedence graph there is a cycle in schedule S1 T1--->T2 and T2---->T1
 so that's why it is not conflict serializable. 

Schedule S1
   T1            T2
---------------------
  r1(X)
  r1(Y)
                r2(X)
                r2(Y)
                w2(Y)
  w1(X)

Schedule S2
   T1            T2
---------------------
  r1(X)
                r2(X)
                r2(Y)
                w2(Y)
  r1(Y)
  w1(X)
In precedence graph for S2 there is only one edge that is T2--->T1(no cycle) so S2 is conflict serializable