Question

Why the solution is B?

1) Consider the following transactions with data items P and Q initialized to zero:

T1: read (P) ;
    read (Q) ;
    if P = 0 then Q : = Q + 1 ;
    write (Q) ;
T2: read (Q) ;
    read (P) ;
    if Q = 0 then P : = P + 1 ;
    write (P) ;

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

Answer (B)

Answer 1

Assume that there is some non-serial interleaved concurrent execution.

Consider

T1:

read(P);

read(Q);

Pre-empt it

T2:

read(Q);

read(P);

stmt;

write(P);

Execute T1 from the point of pre-emption.

T1:

stmt;

write(Q);

Now carefully read the below statements.

From T1 -------> T2 there is a read- write conflict of data P.

From T2 --------> T1 there is a read -write conflict of data Q.

So, if we draw a precedence graph for the conflict of the transactions, it forms a cycle

Whenevr a cycle forms in a precedence graph, then it is not conflict serializable.

Option A is false because the schedule which we constructed is not serializable.

option C is false because we didn't get conflict serializable.

Option D is false because we can construct a precedence graph for it.

So, option B is correct.