GATE CSE 2012 | Question: 27

Question

Consider the following transactions with data items $P$ and $Q$ initialized to zero:
$${\begin{array}{|c|l|r|c|}\hline
   \textbf{$T_1$}&    \text{read (P);}\\ & \text{read (Q);} \\ & \text{if P = 0 then Q := Q + 1; }\\ &      \text{write (Q)}  \\ \hline   
\textbf{$T_2$}& \text{read (Q);}\\& \text{read (P);} \\ & \text{if Q = 0 then P := P + 1;}   \\ & \text{write (P)} \\     \hline
\end{array}}$$

Any non-serial interleaving of T1 and T2 for concurrent execution leads to

• A. a serializable schedule
• B. a schedule that is not conflict serializable
• C. a conflict serializable schedule
• D. a schedule for which a precedence graph cannot be drawn

Comments

Just write the transaction as T1 -> T2 and T2 -> T1. You will notice that the no movement of instruction is possible as the first instruction at point of intersection itself is conflicting.

---

it wont be VS also right bcoz of no blind write?

---

As it is non serial interleaving so if u arrange then total 2 serial arrangements possible and 4 non serial arrangements possible and if u try to draw graph in all those 4 non serial arrangements u get cycle so thats why this schedule is not conflict serializable

Answer 1

option B

Comments

is this schedule view serializable. i guess its not.

---

how?pls explain

---

If a schedule has to be view serializable, then it must have blind writes in the transaction, as we see there are no blind writes, it is not view serializable.

Answer 2

read(p) in T1 will always be executed before write(p) in T2

I.e, T->T2

And

read(Q) in T2 will always be executed before Write(Q) in T1

I.e, T2->T1

So,if we take any interleaving execution these two conflict pairs will always form a cycle if we draw a precedence graph hence ,it is not conflict serializable the only way to avoid this cycle is they must be executed serially but in question it is asked about any non serial interleaving so, option B is correct

Answer 3

Serial schedules allow only 1 r-w problem on either P or Q at a time , any non serial inter leaving creates 2  r-w problems on p or q . Hence not css . No blind write so vs==css

Answer 4

As here No blind writes.Conflict Serializability = View Serializability.

But computations are there Therefore both are not equivalent to general serializability..

Initially P=Q=0

For Serial schedule T1->T2 Result is Q=1,P=0

For Serial Schedule T2->T1 Result is Q=0,P=1

For any concurrent Execution Result is P=1,Q=1.So No non serial execution is serializable.

Hence as it is not Serializable(General), it is not Conflic Serializable also. Since CS⊂VS⊂General Serializability

Option B