DATA INTEGRITY - Database Design and Development: An Essential Guide for IT Professionals - page 465

TIME T1 -- Chicago Order: T2 -- Boston Order: DB DW

DB 70 copies DW 45 copies

DW 65 copies DB 60 copies

t1 BEGIN T1 200 150

t2 LOCK-X (DB) BEGIN T2 200 150

t3 READ (DB) LOCK-X (DW) 200 150

t4 (DB) : = (DB) - 70 READ (DW) 200 150

t5 WRITE (DB) (DW) : = (DW) - 45 130 150

t6 LOCK-X (DW) WRITE (DW) 130 105

t7 …. wait …. LOCK-X (DB) 130 105

t8 …. wait …. …. wait …. 130 105

t9 …. wait …. …. wait …. 130 105

t10 …. wait …. 130 105

Figure 15-23 Transactions in deadlock.

A cycle of transactions waiting for locks to be released is known as a deadlock.
Two or more deadlocked transactions are in a perpetual wait state. 2PL or any other
lock-based protocol, by itself, cannot avoid deadlock problems. In fact, 2PL is prone
to cause deadlocks whenever the first phases of two or more transactions attempt
to execute simultaneously.
First, let us look at two obvious solutions to resolve deadlocks:

Deadlock prevention protocol. Modify 2PL to include deadlock prevention. In the
growing phase of 2PL, lock all required data items in advance. If any data item is
not available for locking, lock none of the data items. Either lock everyone of the
needed data items or none at all. If locking is not possible, the transaction waits and
tries again. The transaction will be able to lock all data items as and when all become
available. The solution, although workable, limits concurrency a great deal.

Ordering of data items. Order all lockable data items in the database and ensure
that when a transaction needs to lock several data items, it locks them in the given
order. This is not a solution that can be implemented through the DBMS. The pro-
grammers need to know the published order of lockable items. It is not a practical
solution at all.
In practice, these two solutions are not feasible. One solution seriously limits the
advantages of concurrent transaction processing. The other is impractical and too
hard to implement. We have to explore other possibilities. Ask a few questions about
your current or proposed database environment. How frequently do you expect
concurrent transactions to process the same data item simultaneously? What are
the chances? How large is your transaction volume? What kind of overhead can
your environment tolerate for resolving deadlocks?
If deadlocks are expected to be very rare, then it is unwise to take a sophisticated
approach to prevent deadlocks. You might do well to have a method for detecting
the rare deadlocks and deal with them as and when they occur. Deadlock detection
and deadlock prevention are commonly used schemes for resolving deadlocks.
Deadlock detection has wider acceptance and appeal.