Solved Example on Concurrency Control

Consider the following schedule for transactions T1, T2 and T3: 

T1 T2 T3
R(X)    
  R(Y)  
    R(Y)
  W(Y)  
W(X)    
    W(X)
  R(X)  
  W(X)  

Which one of the schedules below is the correct serialization of the above?

 (A) T1 → T3 →T2               (B) T2→ T1 →T3  
 (C) T2 →T3→ T1                (D) T3 →T1→ T2  

Answer

To solve these types of question, we have to find out conflicting operations pairs. An operation pair is said to be conflicting if:

  1. Two operations belong to different transactions.
  2. They operate on same data item
  3. At least one operation is write operation

The conflicting operations pairs in the schedule given are:

(W1(X), R2(X)), (W1(X), R2(X)), (R3(Y),W2(Y)) , (W1(X), W3(X))

Then, we draw a precedence graph in which nodes are the transactions (T1, T2 and T3 in this case) and an edge exists between Ti and Tj  from Ti to Tj  if there is a conflicting operations pair (Ox,Oy) and Ox belongs to Ti and Oy belongs to Tj and Ox is executes before Oy in schedule. In this case, for conflicting operations pair (W1(X), R2(X)), an edge is inserted from T1 to T2 because W1(X) of T1 is executed before R2(X) of T2. Similarly, we can draw for others. The graph will look like:

As you can see from the graph, T1 is not dependent on any transaction, it will execute first. T2 is dependent on T3, so it will execute after T3. So the correct serial schedule will be:(A) T1 → T3 →T2  

 

0Comment