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

@Bikram sir 

wht does it mean non-serial interleaving ?

---

@ set2018 

wht does it mean non-serial interleaving ?

Non serial Interleaving means  :

1. read(P) for T1 is executed before write(P) for T2 and
2. read(q) for T2 is executed before write(q) for T1.

A non-serial schedule is a schedule where the operations of a group of concurrent transactions are interleaved. 

---

what does option (d) mean a schedule for which a precedence graph cannot be drawn
is this possible? , every schedule has transaction represented as nodes and conflicting operations as edges, can someone explain ? @Bikram / @ Arjun ?

---

how to draw graph for this ?

---

@Arjun Sir,

What will be serial schedule output of both transactions?

If T1 -> T2: Conflict between the last operation of T1 with the first operation of T2.

If T2 -> T1: Conflict between the last operation of T2 with the first operation of T1.

What can we infer from the above statements?

---

Non-serial Interleaving means  :

1. read(P) for T1 is executed before write(P) for T2 and
2. read(q) for T2 is executed before write(q) for T1.

How is this derived from the given problem?

---

What is significant of this statement here

P and Q are initialized to zero ?

---

@Bikram sir

Any non-serial interleaving of T₁ and T₂ for concurrent execution leads t

It means we have to check for every possible non serial interleaving possible over T1 and T2 right ?

---

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

Answer is (B).

Explanation: $T_1:r(P),r(Q),w(Q) T_2:r(Q),r(P),w(P).$

Now, consider any non serial schedule for example, $S:r_1(P),r_2(Q),r_1(Q),r2(P),w_1(Q),w_2(P).$

Now, draw a precedence graph for this schedule. Here there is a conflict from $T_1\to T_2$ and there is a conflict from $T_2\to T_1.$ Therefore, the graph will contain a cycle. So we can say that the schedule is not conflict serializable.

Comments

Observe 1^st and last operation of T1 and T2; they are arranged in a such way that whatever non serial schedule you take, you can’t swap the non conflicting pairs. Only two serial schedules possible T1→ T2 and T2 → T1.

---

We cannot directly say that if schedule has no blind write means no view serializable first if check whether it is conflict serializable if we find its not conflict serializable then check blind write if no blind write then no view serializable also

---

concept is if no Blind write then it means view serialiable is equivalent to conflict serialiazable

Answer 2

I found this way much simpler : 

 

Comments

Why Option D is wrong.
this schedule is not even View serializable doesn't option b is partially wrong.

As it is not conflict serializable it can be view serializable but option d clearly say there is no way we
can make a precedence graph for non-serial execution

---

@scholaraniket option d is wrong because we can create a precedence graph with a cycle which contradicts option d.

---

@Abhrajyoti00 bro can u plz explain me the solution for this problem that what exactly they are asking and how can we proceed in this ?

---

@shikhar500 

The question is asking that if we create a non serial schedule for the two transactions, one of the options will be true for any schedule we create no matter how we interleave the operations. There can be two cases, so let us look at them one by one - 

CASE I : $T_1$ $\rightarrow$ $T_2$ 
In this case, the conflicting operations are $W_1(Q)$ $\rightarrow$ $R_2(Q)$. So to create a conflict serializable schedule, $R_2(Q)$ must be executed after $W_1(Q). Since, $W_1(Q) is the last operation of $T_1$ and $R_2(Q)$ is the first operation of $T_2$, we can only generate one conflict serializable scchedule,
$S_1$ $:$  $R_1(P)$ $R_1(Q)$ $W_1(Q)$ $R_2(Q)$ $R_2(P)$ $W_2(P)$ which is a serial schedule.

CASE II : $T_2$ $\rightarrow$ $T_1$ 
Similarly, we can show the only conflict serializable schedule is a serial schedule $S_2$ $:$ $R_2(Q)$ $R_2(P)$ $W_2(P)$ $R_1(P)$ $R_1(Q)$ $W_1(Q)$.

With this we can say that the only conflict serializable schedules are the serial schedules. Any other schedules obtained by interleaving in any fashion is not conflict serializable schedule. Hence, Option (B).

Answer 3

Answer is b:

As for any non serial interleaving it is necessary that read(p) for t1 is executed before write(p) for t2 and read(q) for t2 is executed before write(q) for t1.This will give you a cycle of length 2 in the precedence graph.

Answer 4

P and Q are initialised to 0.

Consider the values of P and Q when T1 is executed followed by T2.

P=0 and Q=1

$T_2\rightarrow T_1$

P=1, Q=0

Consider another schedule

T1      T2
R(P)
R(Q)
        R(Q)
        R(P)
        if(Q=0),P=P+1
        W(P)
if (P=0), Q=Q+1
W(Q)

This execution would set values of P and Q both to 1.

As you can see, here consistency requirement the ACID property is broken. Consistency in results is not ensured.

Hence, any non-serial interleaving would never lead to a serial schedule.

Transactions T1 and T2 are inconsistent.

Answer-B

Comments

here in question it is asking about the ANY so try to take an counter example and try falsify the each statement

A:Can we make non serializable schdule out of give then schedule 

 see S:r1(P),r2(Q),r1(Q),r2(P),w1(Q),w2(P)S:r1(P),r2(Q),r1(Q),r2(P),w1(Q),w2(P) 

C Again false using same example of option a

D:We can draw precedence graph of any schedule  so false 

so OPTION B is correct

 

---

How can we draw precedence graph of this, a precedence graph can be drawn only if it is Conflict serializable, but here on drawing precedence graph, we will get deadlock state. Hence not possible. Please correct me if I'm wrong! (Please tell why option D is FALSE)

---

This should be the best answer as it also covers how transactions update values which is not understood by many.

---

A precedence graph cannot be drawn if the schedule has a cycle or loop, which means it is not conflict serializable.

Answer 5

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.

Comments

explaination is easy to understand and nice. thankyou

Answer 6

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.