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

T2 T3 T2 T3

T1 T4 T1 T4

Before deadlock After deadlock

Figure 15-24 Wait-for graph: before and after deadlock.

Deadlock Detection If transactions are generally short and each transaction
usually locks only a few data items, you can assume that deadlocks are quite infre-
quent in such environments. Then you can let deadlocks happen, detect them, and
take action. What is the resolution when a deadlock is detected? On the basis of a
chosen set of criteria, the system is allowed to abort one of the contending trans-
actions. Of course, before the DBMS can take this action, it must first be able to
detect that two or more transactions are in a deadlock.
Here are the common methods for detecting deadlocks:

Wait-for graph. The DBMS maintains a wait-for graph with a node for each cur-
rently executing transaction. If transaction T1 is waiting to lock data item D that is
currently locked by T2, draw a directed line from node T1 to node T2. When T2
releases the locks on the data items T1 is waiting for, drop the line from T1 to T2
in the graph. Figure 15-24 shows a sample wait-for graph before and after deadlock.
When the wait-for graph has a cycle, the DBMS detects a deadlock. Two major
issues arise with this deadlock detection approach. First, how often should the
DBMS check the wait-for graph? Common methods are based on the number of
currently executing transactions or based on the waiting times of several transac-
tions. The second issue relates to choosing the transactions for aborting. Tip: Avoid
aborting long-running transactions or transactions that have already performed
many write operations.

Timeouts. The DBMS assumes a deadlock if a transaction is waiting too long for a
lock and aborts the transaction. A predefined period is used as the waiting time
after which a transaction is subject to be aborted. This is a simpler scheme with very
little overhead.

Deadlock Prevention If most of the transactions in a database environment run
long and update many data items, deliberately allowing deadlocks and aborting the
long-running transactions frequently may not be the acceptable approach. In such
environments, you must adopt deadlock prevention schemes and avoid deadlocks.
Deadlock prevention or avoidance schemes are based on the answer to the ques-
tion of what should be done to a transaction proceeding toward a possible dead-
lock. Should the transaction be put on hold and made to wait, or should it be
aborted? Should the transaction preempt and abort another possible contending
transaction?
Each transaction is given a logical timestamp, a unique identifier assigned to each
transaction in chronological sequence of the start times of transactions. If transac-