edited by
22,477 views
70 votes
70 votes

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

  1. a serializable schedule
  2. a schedule that is not conflict serializable
  3. a conflict serializable schedule
  4. a schedule for which a precedence graph cannot be drawn
edited by

7 Answers

2 votes
2 votes

Here, the "non-serial" in "non-serial interleaving" is superfluous (redundant). Interleaving, by its very nature, is non-serial.

You've been asked to interleave, which means, you cannot execute all operations of one transaction in a row followed by all operations of the other transaction. Otherwise it would just be a serial schedule, which we don't want.

Our schedule can start with the first operation of either T1 or T2 (it has to start somewhere). If you start with T1 in your schedule (read1 P) then you cannot end T1 (write1 Q) without first starting T2 (read2 Q). Similarly, if you start with T2 (read2 Q) then you cannot end T2 (write2 P) without first starting T1 (read1 P). In both cases, you are taking a serial(izable) schedule (T1 $\rightarrow$ T2 in the first case, and T2 $\rightarrow$ T1 in the second) and changing the order of two conflicting operations.

We know that the moment we change the order of a pair of conflicting operations in a serial (or serializable) schedule , the schedule no longer remains conflict serializable. Hence, B is the correct answer.

edited by
0 votes
0 votes
option B
0 votes
0 votes

Answer (B)
Two or more actions are said to be in conflict if:
1) The actions belong to different transactions.
2) At least one of the actions is a write operation.
3) The actions access the same object (read or write).

The schedules S1 and S2 are said to be conflict-equivalent if the following conditions are satisfied:
1) Both schedules S1 and S2 involve the same set of transactions (including ordering of actions within each transaction).
2) The order of each pair of conflicting actions in S1 and S2 are the same.

A schedule is said to be conflict-serializable when the schedule is conflict-equivalent to one or more serial schedules.

Source: Wiki Page for Schedule

In the given scenario, there are two possible serial schedules:
1) T1 followed by T2
2) T2 followed by T1.
In both of the serial schedules, one of the transactions reads the value written by other transaction as a first step. Therefore, any non-serial interleaving of T1 and T2 will not be conflict serializable.

Answer:

Related questions

48 votes
48 votes
4 answers
1
go_editor asked Apr 21, 2016
13,587 views
Consider the following relations $A, B$ and $C:$ $$\overset{\textbf{A}}{\begin{array}{|c|c|c|}\hline\\\textbf{Id}& \textbf{Name}& \textbf{Age} \\\hline12& \text{A...
70 votes
70 votes
6 answers
2
gatecse asked Sep 29, 2014
29,076 views
Consider the following relations $A, B$ and $C:$$$\overset{\text{A}}{\begin{array}{|c|c|c|} \hline \text {ID} & \text {Name} & \text {Age} \\\hline\text{12}& \text{Arun}...