Deadlocks in Database: conditions and Methods for handling

A system is said to be in deadlock state if there exist a set of transactions {T₀, T₁,…, Tn} such that each transaction in set is waiting for releasing any resource by any other transaction in that set.  In  this  case,  all  the  transactions  are  in waiting  state.

1. Necessary Conditions for Deadlock

A system  is  in deadlock  state  if  it satisfies  all  of the following  conditions.

• Hold and wait : Whenever a transaction holding at least one resource and waiting for another resources that are currently being held by other processes.
• Mutual Exclusion : When any transaction has obtained a nonsharable lock on any data item and  any  other  transaction  requests  that item.
• No Preemption : When a transaction holds any resource even after its completion.
• Circular Wait : Let T be the set of waiting processes T = {T₀, T₁, …, Ti} such that T₀ is waiting for a resource that is held by T₁, T₁ is waiting for a resource that is held by T2, Ti  is waiting  for  a resource  that  is  held by T₀.

2. Methods for Handling Deadlocks

There are Two methods for handling deadlocks. These are:

2.1. Deadlock Prevention

It is better to prevent the system from deadlock condition then to detect it and then recover it. Different  approaches for preventing  deadlocks are:

1. Advance Locking : It is the simplest technique in which each transaction locks all the required data items at the beginning of its execution in atomic It means all items are locked in  one  step  or  none  is  locked.

Disadvantages : The  disadvantages of  advance locking  are:

1. 1. It is very hard to predict all data items required by transaction at starting.
   2. Under utilization is high.
   3. Reduces concurrency.

2. Ordering Data Items : In this approach, all the data items are assigned in order say 1, 2, 3, … Any transaction Ti can acquire locks in a particular order, such as in ascending order or descending order.

Disadvantages : It reduces concurrency but less  than advance locking.

3. Ordering Data Items with Two-phase Locking : In this approach, two-phase locking with ordering data items is used to increase concurrency.
4. Techniques based on Timestamps : There are Two different techniques to remove deadlock based on time stamps.

• Wait-die : In wait-die technique if any transaction Ti needs any resource that is presently held by Tj then Ti have to wait only if it has timestamp smaller than Tj otherwise Ti is  rolled  back.

If     TS(Ti)<TS(Tj)

Ti waits;

else

Ti is rolled back;

It is a nonpreemptive technique.

• Wound-wait : In wound-wait technique, if any transaction Ti needs any resource that is presently held by Tj then Ti have to wait only if it has timestamp larger then Tj otherwise Tj is  rolled back.

If   TS(Ti)>TS(Tj)

Ti waits;

else

Tj is rolled back;

It is a preemptive technique.

Disadvantage : There are unnecessary roll backs in both techniques that leads to starvation.

2.2. Deadlock Detection and Recovery

In this approach, allow system to enter in deadlock state then detect it and recover it.

To employ this approach, system must have :

1. Mechanism to maintain information of current allocation of data items to transactions and the order  in  which  they are allocated.
2. An algorithm which is invoked periodically by system to determine deadlocks in system.
3. An algorithm to recover from deadlock state.

Deadlock Detection : To detect deadlock, maintain wait-for graph.

1. Wait-for Graph : It consists of a pair G = (V, E), where V is the set of vertices and E is the set of Vertices show transactions and edges show dependency of transactions.

If transaction Ti request a data item which is currently being held by Tj then, an edge Ti → Tj is inserted in graph. When Ti has obtained the required item from Tj remove the edge. Deadlock occurs when there is cycle in wait-for graph.

Algorithm to Construct Wait-for Graph

1. 1. For each transaction Ti active at the time of deadlock detection, create a node labelled Ti in the wait-for graph.
   2. For each case, if there is a transaction Ti, waiting for a data-item that is currently allocated and held by transaction Tj, then there is a directed arc from the node for transaction Ti, to the node for transaction Tj.

1. 3. For each case, if there is a directed arc from the node for transaction Ti, to the node for transaction Tj and transaction Tj released the lock, then remove the arc between them.
   4. There exists no deadlock if the wait-for graph is Consider wait-for graph as shown in Figure 8.17.

There are three transactions T1, T2 and T3. The transaction T1 is waiting for any data item held by T₂ and T₂ is waiting for any data item held by T₃. But there is no deadlock because there  is  no  cycle  in  wait-for  graph.

Consider the graph as shown in Figure 8.18, where T₃ is also waiting for any data item held by T₁.

Thus, there exists  a cycle  in wait-for  graph.

 T1 → T2 → T3 → T1

which results system in deadlock state and T₁, T₂ and T₃ are all blocked.

Now a major question arises : How much will be the time interval after which system invokes deadlock detection  algorithm? It depends  upon Two  factors:

1. After how much time a deadlock occurs?
2. How many transactions are deadlocked?
3. Recovery from Deadlock : When deadlock detection algorithm detects any deadlock in system, system  must take  necessary  actions to  recover  from deadlock.

Steps of recovery algorithm are:

1. Select a victim : To recover from deadlock, break the cycle in wait-for To break this cycle, rollback any of the deadlocked transaction. The transaction which is rolled back  is  known  as  victim.

Various factors to determine victim are:

• Cost of transaction.
• How many more data items it required to complete its task?
• How many more transactions affected by its rollback?
• How much the transaction is completed and left?

2. Rollback : After selection of victim, it is rollbacked.
   There are Two types of rollback to break the cycle:
   • Total rollback : This is simple In total rollback, the victim is rolled back completely.
   • Partial rollback : In this approach, rollback the transaction upto that point which is necessary to break deadlock. Here transaction is partially rolled back. It is an effective technique but system have to maintain additional information about the state of all running transactions.
3. Prevent Starvation : Sometimes, a particular transaction is rolledback several times and never completes which causes starvation of that transaction. To prevent starvation, set the limit of rollbacks or the maximum number, the same transaction chooses as Also, the number of rollback can be added in cost factor to reduce starvation.

2.3. Timeout-based Schemes

Timeout-based scheme exists in between deadlock prevention and deadlock detection and recovery. In this scheme, the transaction waits for at most a fixed time for any resource. If transaction is not able to get resource in that fixed time then it is said to be timeout and transaction is  rollbacked  and  restarted  after sometime.

This approach is preferred where transactions are short and long waits cause deadlocks. It is  typical  to  choose  appropriate  time  for  timeout.

If it is too long then it results unnecessary delays and if it is too short then it cause unnecessary rollbacks.

SOLVED PROBLEMS

Problem 1. Consider the following two transactions:

T1: read(A);

read(B);

if A=0 then B := B+1;

write(B).

T2: read(B);

read(A);

if B=0 then A := A+1;

write(A).

Let the consistency requirement be   (A=0 or B=0), with A=B=0 the initial values.

• Show that every serial execution involving these two transactions preserves the consistency of database.
• Show a concurrent execution of T1 and T2 that produces a nonserializable schedule.

Solution.

• There are two possible executions: T1 T2 and T2 T1.

Case 1:

Consistency met: (A = 0 or B = 0) = T

Case 2:

Consistency met: (A = 0 or B = 0) = T

• Any interleaving of T1  and  T2 results  in  a non-serializable schedule.

Problem 2. Add lock and unlock instructions to transactions T1 and T2 from Problem 1 so that they observe the two-phase locking protocol. Can the execution of these transactions result in  a  deadlock?

Solution.

• Lock and unlock instructions:

T31:   lock-S(A)

read(A)

lock-X(B)

read(B)

if A=0

then B:=B+1

write(B)

unlock(A)

unlock(B)

T32:  lock-S(B)

read(B)

lock-X(A)

read(A)

if B=0

then A:=A+1

write(A)

unlock(B)

unlock(A)

• Execution of these transactions can result in For example, consider the following partial schedule:

The transactions are now deadlocked.

Problem 3. Let transactions T1, T2 and T3 be defined to perform the following operations:

T1 : Add one to A

T2 : Double A

T3 : Display A on the screen and then set A to one.

(where A is  some item  in  the database)

Suppose transactions T1, T2 and T3 are allowed to execute concurrently. If A has initial value zero, how many possible  correct results are there?  Enumerate them.

Solution. The following three transactions, manipulating the contents of A, are to execute concurrently:

T1 : Add one to A i.e., A = A + 1

T2 : Double A i.e., A + 2 * A

T3 : Display A on screen and then set it to 1 i.e., A = 1

Assuming A has an initial value zero. Now three transactions can execute concurrently in the following different ways. The tables are showing the different transaction schedules along with the changes they make in the value of A and the value of A displayed by T3.

Problem 4. Justify the following statement: Concurrent execution of transactions is more important when data must be fetched from (slow) disk or when transactions are long, and is less  important  when  data  is  in  memory and  transactions  are  very  short.

Solution. If a transaction is very long or when it fetches data from a slow disk, it takes a long time to complete. In absence of concurrency, other transactions will have to wait for longer period of time. Average response time will increase. Also when the transaction is reading data from disk, CPU is idle. So resources are not properly utilized. Hence concurrent execution becomes important in this case. However, when the transactions are short or the data is available in memory, these problems do not occur.

Problem 5. Consider the following two transactions

T1:     read(A);

read(B);

if A = 0 then B := B + 1;

write(B).

T2:     read(B);

read(A);

if B = 0 then A := A + 1;

write(A).

• Add lock and unlock instructions to transactions T1 and T2, so that they observe the two-phase locking (Hint: Use unlock, lock-S and lock-X where appropriate)

• Can the execution of these transactions result in a deadlock? If can, please give an example of how the deadlock can happen using partial schedule for T1 and T2.

Solution. (a) Lock  and unlock  instructions are added  as follows:

(b) Execution of these transactions can result in deadlock. For example, consider the following partial schedule:

The transactions are now deadlocked.

Problem 6. Consider the following sequences of actions, listed in the order they are submitted to the DBMS:

• Sequence S1: T1:R(X), T2:W(X), T2:W(Y), T3:W(Y), T1:W(Y), T1:Commit, T2:Commit, T3:Commit
• Sequence S2: T1:R(X), T2:W(Y), T2:W(X), T3:W(Y), T1:W(Y), T1:Commit, T2:Commit, T3:Commit

For each sequence and for each of the following concurrency control mechanisms, describe how the  concurrency  control  mechanism handles  the  sequence.

Assume that the timestamp of transaction Ti is i. For lock-based concurrency control mechanisms, add lock and unlock requests to the previous sequence of actions as per the locking protocol. The DBMS processes actions in the order shown. If a transaction is blocked, assume that all its actions are queued until it is resumed; the DBMS continues with the next action (according  to  the  listed  sequence)  of  an unblocked  transaction.

1. Strict 2PL with timestamps used for deadlock prevention.
2. Strict 2PL with deadlock (Show the waits-for graph in case of deadlock.)
3. Conservative (and Strict, e., with locks held until end-of-transaction) 2PL.
4. Optimistic concurrency control.

5. Timestamp concurrency control with buffering of reads and writes (to ensure recoverability) and the Thomas  Write Rule.
6. Multiversion concurrency control.

Solution.

1. Assume we use Wait-Die

Sequence S1: T1 acquires shared-lock on X;

When T2 asks for an exclusive lock on X, since T2 has a lower priority, it will be aborted;

T3 now gets exclusive-lock on Y;

When T1 also asks for an exclusive-lock on Y which is still held by T3, since T1 has higher  priority,

T1 will be blocked waiting;

T3 now finishes write, commits and releases all the lock;

T1 wakes up, acquires the lock, proceeds and finishes;

T2 now can be restarted successfully.

Sequence S2: The sequence and consequence are the same with Sequence S1, except T2 was  able  to  advance a  little  more  before it  gets  aborted.

2. In deadlock detection, transactions are allowed to wait, they are not aborted until a deadlock has been (Compared to prevention schema, some transactions may have been aborted prematurely.)

Sequence S1:  T1 gets  a shared-lock  on X;

T2 blocks waiting for an exclusive-lock on X;

T3 gets an exclusive-lock on Y;

T1 blocks waiting for an exclusive-lock on Y;

T3 finishes, commits and  releases locks;

T1 wakes up, gets an exclusive-lock on Y, finishes up and releases lock on X and Y;

T2 now gets both an exclusive-lock on X and Y, and proceeds to finish.

No deadlock.

Sequence S2:  There  is  a deadlock.  T1  waits  for T2,  while  T2  waits for  T1.

3. Sequence S1: With conservative and strict 2PL, the sequence is T1 acquires lock on both X and Y, commits, releases locks; then T2; then T3.

Sequence S2: Same as Sequence S1.

4. For both S1 and S2: each transaction will execute, read values from the database and write to a private workspace; they then acquire a timestamp to enter the validation The timestamp of transaction Ti is i.

Sequence S1: Since T1 gets the earliest timestamp, it will commit without problem; but when  validating  T2  against  T1, one  of  the  three  conditions must  hold:

• T1 completes before T2 begins.

• T1 completes before T2 starts its write phase, and T1 does not write any database object read by T2.
• T1 completes its read phase before T2 completes its write phase , and T1 does not write any  database  object  that is  either  read  or  written by T2.

Since none of the three conditions hold,so T2 will be aborted and restarted later; so is T3 (same as T2).

Sequence S2: The fate is the same as in Sequence S1.

5. Initiate the timestamp of objects X and Y to

Sequence S1:

T1: R(X) is allowed since TS(T1)=1 and WTS(X)=0 => TS(T1) ≥ WTS(X). RTS(X)

is set to 1.

T2: W(X) is allowed since TS(T2)=2, RTS(X) =1, and WTS(X)=0 => TS(T2) ≥ RTS(X)

and TS(T2) ≥

WTS(X). WTS(X) is set to 2.

T2: W(Y) is allowed since TS(T2)=2, RTS(Y) =0, and WTS(Y)=0 => TS(T2) ≥ RTS(X)

and TS(T2) ≥

WTS(X). WTS(Y) is set to 2.

T3: W(Y) is allowed since TS(T3)=3, RTS(Y) =0, and WTS(Y)=2 => TS(T2) ≥ RTS(X)

and TS(T2) ≥

WTS(X). WTS(Y) is set to 3.

T1: W(Y) is ignored since TS(T1)=1, RTS(Y) =0, and WTS(Y)=3 => TS(T2) ≥ RTS(X) and TS(T1) <

WTS(Y).

Sequence S2: Same as above.

6. Sequence S1: T1 reads X, so RTS(X) = 1;

T2 is able to write X, since TS(T2) ³ RTS(X); and RTS(X) and WTS(X) are setto 2; T2 writes Y, RTS(Y) and WTS(Y) are  set to 2;

T3 is able to write Y as well, so RTS(Y) and WTS(Y) are  set to 3;

Now when T1 tries to write Y, since TS(T1) < RTS(Y), T1 needs to be aborted and restarted  later  with  larger  timestamp.

Sequence S2: The fate is similar to the one in Sequence S1.

Problem 7. For each of the following locking protocols, assuming that every transaction follows that locking protocol, state which of these desirable properties are ensured: serializability, conflict serializability, recoverability, avoidance of cascading aborts.

1. Always obtain an exclusive lock before writing; hold exclusive locks until end of No shared  locks  are  ever obtained.
2. In addition to (1), obtain a shared lock before reading; shared locks can be released at any time.
3. As in (2), and in addition, locking is two-phase.
4. As in (2), and in addition, all locks held until end-of-transaction.

Solution. As a general rule, if a protocol is defined such that transaction T can commit only after all transactions whose changes it reads commit, the protocol is recoverable. If the protocol is defined such that each transaction can only read the changes of committed transactions, it will not cause any cascading abort.

Problem 8. Consider the  following tree.

Describe the steps involved in executing each of the following operations according to the tree-index concurrency control algorithm, in terms of the order in which nodes are locked, unlocked, read, and written. Be specific about the kind of lock obtained and answer each part independently  of  the  others,  always  starting with  the  original  tree.

1. Search for data entry 40*.
2. Search for all data  entries k*  with  k ≤ 40.
3. Insert data entry 62*.
4. Insert data entry 40*.

Solution. The following abbreviation are used in the solution:

S(A): Obtains  shared  lock  on A.

X(A): Obtains exclusive lock on A.

RS(A): Release shared lock on A.

RX(A): Release exclusive lock on A.

R(A): Read node A.

W(A): Write node A.

1. S(A),R(A),S(B),RS(A),R(B),S(C),RS(B),R(C),S(D),RS(C),R(D),…(obtain other locks needed for further operation), then release lock on D when the transaction is going to commit(Strict 2PL).
2. S(A), R(A), S(J), S(B), RS(A), R(J), R(B),S(K), S(L), RS(J), S(F), S(C), RS(B), R(K), R(L), R(F), R(C), S(M), S(N), S(O), S(P), S(G), S(H), S(I), S(D), RS(K), RS(L), RS(F), RS(C), R(M), R(N), R(O), R(P), R(G), R(H), R(I), R(D), …, then release locks on M, N, O, P,G, H, I, D when the transaction is going to commit.

3. X(A), R(A), X(B), R(B), RX(A), X(C), R(C), X(E), R(E), RX(B), RX(C) W(E), …, then release lock  on E  when  the transaction  is  going to  commit.

4. X(A), R(A), X(B), R(B), RX(A), X(C), R(C), X(D), R(D), New Node Z, X(Z), X(I), R(I), W(I), W(Z), W(D), New Node Y (For a split on C), X(Y), W(Y), W(C), W(B), RX(B), RX(C), RX(Y) …, then release locks on I, Z, D when the transaction is going to commit.

Problem 9. Consider the following actions taken by transaction T1 on databases X and Y:

R(X), W(X),

R(Y), W(Y)

1. Give an example of another transaction T2 that, if run concurrently to transaction T1 without some form of  concurrency control,  could interfere  with T1.
2. Explain how the use of Strict 2PL would prevent interference between the two transactions.
3. Strict 2PL is used in many database Give two reasons for its popularity.

Solution.

1. If the transaction T2 performed W(Y) before T1 performed R(Y), and then T2 aborted, the value read by T1 would be invalid and the abort would be cascaded to T1 (e. T1 would also have to abort.).
2. Strict 2PL would require T2 to obtain an exclusive lock on Y before writing to This lock would have to be held until T2 committed or aborted; this would block T1 from reading Y until T2 was finished, but there would be no interference.
3. Strict 2PL is popular for many One reason is that it ensures only ‘safe’ interleaving of transactions so that transactions are recoverable, avoid cascading aborts, etc. Another reason is that strict 2PL is very simple and easy to implement. The lock manager only needs to provide a lookup for exclusive locks and an atomic locking mechanism (such  as  with  a  semaphore).

Problem 10. A transaction that only reads database object is called a read-only transaction, otherwise the transaction is called a read-write transaction. Give brief answers to the following questions:

1. What is lock thrashing and when does it occur?
2. What happens to the database system throughput if the number of read-write transactions is increased?
3. What happens to the database system throughput if the number of read-only transactions is increased?
4. Describe three ways of turning your system to increase transaction throughput

Solution.

1. Lock Thrashing is the point where system performance(throughput) decreases with increasing load (adding more active transactions). It happens due to the contention of Transactions waste  time on  lock  waits.

2. At the beginning, with the increase of transactions, throughput will increase, but the increase will stop at the thrashing point, after the point the throughput will drop with the increasing  number  of transactions.
3. For read-only transactions, there is no lock The throughput will increase with the increasing  number  of concurrent  transactions.
4. Three ways of turning your system to increase transaction throughput:
   • By locking the smallest sized objects possible (reducing the likelihood that two transactions need the same lock).
   • By reducing the time that transaction hold locks (so that other transactions are blocked for a shorter time).
   • By reducing hot A hot spot is a database object that is frequently accessed and modified, and causes a lot of blocking delays. Hot spots can significantly affect performance.

Problem 11. Consider the following classes of schedules: serializable, conflict-serializable, view-serializable, recoverable, avoids-cascading-aborts, and strict. For each of the following schedules, state which of the preceding classes it belongs to. If you cannot decide whether a schedule belongs in a certain class based on the listed actions, explain briefly.

The actions are listed in the order they are scheduled and prefixed with the transaction name. If a commit or abort is not shown, the schedule is incomplete; assume that abort or commit must follow all the listed actions.

1. T1: R(X), T2: R(X), T1: W(X), T2: W(X)
2. T1: W(X), T2: R(Y), T1: R(Y), T2: R(X)
3. T1: R(X), T2: R(Y), T3: W(X), T2: R(X), T1: R(Y)
4. T1: R(X), T1: R(Y), T1: W(X), T2: R(Y), T3: W(Y), T1: W(X), T2: R(Y)

5. T1: R(X), T2: W(X), T1: W(X), T2: Abort, T1: Commit
6. T1: R(X), T2: W(X), T1: W(X), T2: Commit, T1: Commit
7. T1: W(X), T2: R(X), T1: W(X), T2: Abort, T1: Commit
8. T1: W(X), T2: R(X), T1: W(X), T2: Commit, T1: Commit
9. T1: W(X), T2: R(X), T1: W(X), T2: Commit, T1: Abort
10. T2: R(X), T3: W(X), T3: Commit, T1: W(Y), T1: Commit, T2: R(Y), T2: W(Z), T2:

Commit

11. T1: R(X), T2: W(X), T2: Commit, T1: W(X), T1: Commit, T3: R(X), T3: Commit
12. T1: R(X), T2: W(X), T1: W(X), T3: R(X), T1: Commit, T2: Commit, T3: Commit

Solution.

1. Serizability (or view) cannot be decided but NOT conflict serizability. It is recoverable and avoid cascading aborts; NOT strict
2. It is serializable, conflict-serializable, and view-serializable regardless which action (commit or abort) follows. It is NOT avoid cascading aborts, NOT strict; We can not decide whether it’s recoverable or not, since the abort/commit sequence of these two transactions are not specified.

3. It is the same with 2.
4. Serizability (or view) cannot be decided but NOT conflict It is NOT avoid cascading aborts, NOT strict; We can not decide whether it’s recoverable or not, since the abort/commit sequence of these transactions are not specified.
5. It is serializable, conflict-serializable, and view-serializable; It is recoverable and avoid cascading aborts; it is NOT strict.
6. It is NOT serializable, NOT view-serializable, NOT conflict-serializable; it is recoverable and avoid cascading aborts; It is NOT strict.
7. It belongs to all classes
8. It is serializable, NOT view-serializable, NOT conflict-serializable; It is NOT recoverable, therefore NOT avoid  cascading  aborts, NOT strict.
9. It is serializable, view-serializable, and conflict-serializable; It is NOT recoverable, therefore NOT avoid  cascading  aborts, NOT  strict.
10. It belongs to all above classes.
11. It is NOT serializable and NOT view-serializable, NOT conflict-serializable; it is recoverable, avoid cascading  aborts  and strict.
12. It is NOT serializable and NOT view-serializable, NOT conflict-serializable; it is recoverable, but NOT  avoid  cascading  aborts,  NOT strict.

Problem 12. Consider the following sequences of actions, listed in the order in which they are  submitted  to  the  DBMS:

• Sequence S1: T1:R(X), T2:W(X), T2:W(Y), T3:W(Y), T1:W(Y), T1:Commit, T2:Commit,
• Sequence S2: T1:R(X), T2:W(Y), T2:W(X), T3:W(Y), T1:W(Y), T1:Commit,

For each sequence and for each of the following concurrency control mechanisms, describe how the  concurrency  control  mechanism handless  the  sequence.

Assume that the timestamp of transaction Ti is i. For lock-based concurrency control mechanism, add lock and unlock requests to the above sequence of actions as per the locking protocol. If a transaction is blocked, assume that all of its actions are queued until it is resumed; the DBMS continues with the next action (according to the listed sequence) of an unblocked transaction.

1. Strict 2PL with timestamps used for deadlock
2. Strict 2PL with deadlock Show the waits-for graph if a deadlock cycle develops.

Solution.

1. Assume we use Wait-Die policy.

Sequence S1:

T1 acquires shared-lock on X; for an exclusive-lock on X, since T2 has a lower priority, it  will be  aborted when  T2 asks;

T3 now gets exclusive-lock on Y;

When T1 also asks for an exclusive-lock on Y, which is still held by T3, since T1 has higher  priority,

T1 will be blocked waiting;

T3 now finishes write, commits and releases all the lock;

T1 wakes up, acquires the lock, proceeds and finishes;

T2 now can be restarted successfully.

Sequence S2:

The sequence and consequence are the same with sequence S1, except T2 was able to advance  a  little  more  before it  gets  aborted.

2. In deadlock detection, transactions are allowed to wait, they are not aborted until a deadlock has been (Compared to prevention schema, some transactions may have been aborted prematurely.)

Sequence S1:

T1 gets a shared-lock  on X;

T2 blocks waiting for an exclusive-lock on X;

T3 gets an exclusive-lock on Y;

T1 blocks waiting for an exclusive-lock on Y;

T3 finishes, commits and  releases locks;

T1 wakes up, get an exclusive-lock on Y, finishes up and releases lock on X and Y;

T2 now gets both an exclusive-lock on X and Y, and proceeds to finish.

No deadlock.

Sequence S2:

There is  a  deadlock. T1  waits  for T2,  while  T2  waits for  T1.

Problem 13. The following represents the sequence of events in a schedule involving transactions T1,  T2,  T3,  T4  and  T5. A, B,  C,  D,  E,  F  are  items  in the  database.

Draw a wait-for-graph for the data above and find whether the transactions are in a deadlock or not?

Solution.

1. T2 : Read B

The data  item  B is  locked  by T2  and  no  change in  the  wait-for-graph

2. T4 : Read D

The data  item  D is  locked  by T4  and  no  change in  the  wait-for-graph

3. T2 : Read E

The data  item  E is  locked  by T2  and  no  change in  the  wait-for-graph

4. T3 : Write E

The data  item  E is  unlocked  by T2  and  no  change in  the  wait-for-graph

5. T3 : Read F

The data  item  F is  locked  by T3  and  no  change in  the  wait-for-graph

6. T2 : Read F

Now T2 wants to lock F, which is already locked by T3 (in step 5) so insert an edge from  T2  to  T3  in the  wait-for-graph.

7. T1 : Read C

The data  item  C is  locked  by T1  and  no  change in  the  wait-for-graph.

8. T5 : Read A

The data  item A is  locked  by T5 and  no  change in  the  wait-for-graph.

9. T5 : Write A

The data  item  B is  locked  by T5  and  no  change in  the  wait-for-graph.

10. T1 : Read E

The data  item  E is  locked  by T1  and  no  change in  the  wait-for-graph.

11. T5 : Read C

Now T5 wants to lock C, which is already locked by T1 (in step 7) so insert an edge from  T5  to  T1  in the  wait-for-graph.

12. T3 : Read A

The data  item A is  locked  by T3 and  no  change in  the  wait-for-graph.

13. T5 : Write C

The transaction cannot proceed further as it was not able to lock data item C (in step 11) so the transaction has to wait, hence there is no change in the wait-for-graph.

14. T2 : Write F

The transaction cannot proceed further as it was not able to lock data item F (in step 6) so the transaction has to wait, hence there is no change in the wait-for-graph.

15. T4 : Read A

Now T4 wants to lock A, which is already locked by T3 (in step 13) so insert an edge from  T4  to  T3  in the  wait-for-graph.

Thus finally  the wait-for  graph will  be as  follows:

Since there is  no cycle  in the  wait-for-graph, the  system is not  in a  deadlock.

Problem 14. Consider the following two transactions:

T1 :   read (A);

read (B);

B = A + B;

write (B)

T2 :   write (A)

read (B)

Add lock and unlock instructions so that the transaction T1 and T2 observe two-phase locking protocol.  Is  it  deadlock  free?

Solution.

T1:     lock-S(A)

Read (A)

Lock-X(B)

Read (B)

B = A + B

Write (B)

Unlock (A)

Unlock(B)

T2:      lock-X(A)

Lock-S(B)

write (A)

Read (B)

Unlock(A)

Unlock(B)

Execution of these transactions can result in deadlock. For example, consider the following partial schedule:

Problem 15. Produce a wait-for graph for the following transaction scenario and determine whether a deadlock exists

Solution. The wait for graph for the given scenario is as follows:

Since there is cycle in the wait-for graph (T2®T4®T5®T2) in the graph, therefore, system is in a deadlock.

Problem 16. Consider three transactions: T1, T2 and T3. Draw the precedence graph for the following schedule consisting of these three transactions and determine whether it is serializable. If  so,  give  its  serial  order(s).

Solution. The precedence  graph is  shown below:

The given schedule is serializable. The serial orders of the transactions are: T3, T1, and T2.

Problem 17. Consider the transactions t1, t2 and t3 and a schedule S given below.

S : read1(A); read2(B); write1(C); read3(B); read3(C); write2(B); write3(A)

Where the subscript denotes the transaction number. Assume that the time stamp of t1<t2<t3. Using time-stamp ordering scheme for concurrency control find out if the schedule will go through. If there  is to be a rollback,  which transaction(s) will be rolled  back?

Solution. The schedule is as follows:

Since this write in t₂ is after a younger transaction (t₃) has read the value of B, therefore t₂ will be rolled back.

Problem 18. The following is a schedule with one action missing

You are asked to figure out what actions could replace the ??? and make the schedule not serializable.  List  all  possible  non-serializable replacements.

Note that a possible replacement is an action of the form R(Ti,Q) or W(Ti,Q), where i = 1, 2, and Q is one of A, B, C, indicating that transaction Ti reads from (or, write onto) data item Q. A non-serializable replacement is a replacement R(Ti,Q) (or W(Ti,Q)) such that the given schedule is not serializable when ??? is replaced by R(Ti,Q) (or W(Ti,Q)).

Solution.

W(T1,B), W(T2,C), and R(T2,C) are all non-serializable replacements.

Problem 19. Draw the precedence graph of the following schedule and determine whether the schedule is serializable.

(Note that all instructions, except lock and unlock, are omitted. We assume the transaction that requests a read-lock on T will read from T and one that requests the write-lock on T will read  from and  write  into T.)

Solution. The precedence graph is given below, and the schedule is not serializable for the precedency  graph  is  cyclic.

Source: Gupta Satinder Bal, Mittal Aditya (2017), Introduction to Basic Database Management System, 2nd Edition-University Science Press (2017)