11.4.1 Deadlock and Starvation

The set of items that a transaction reads is called its read set, and the set of items that a transaction writes is called its write set. In database processing, it is often difficult to identify the entire read set and write set of a transaction before executing the transaction. Often records are accessed because of their relationship to other records. Often it is impossible to tell in advance exactly which records will be related. For example, in the University database, if we ask for the name and department of all the teachers of a student, we are unable to predict exactly which Enroll records, Class records, and Faculty records will be needed.

Because we cannot always specify in advance which items need to be locked by a transaction, we make lock requests during the execution of the transaction. These requests can result in a situation called deadlock, which occurs when two transactions are each waiting for locks held by the other to be released. FIGURE 11.9 shows two transactions, S and T, which are deadlocked because each is waiting for the other to release a lock on an item it holds. At time t1, transaction S requests an exclusive lock (Xlock) on item a, and at time t2, the lock is granted. At t3, transaction T obtains an exclusive lock on item b, which is granted at t4. Then at t5, S requests a lock on item b. Because T holds an exclusive lock on b, transaction S waits. Then at t6, T requests a shared lock (Slock) on item a, which is held with an exclusive lock by transaction S so transaction T waits. Neither transaction can complete because each is waiting for a lock it cannot obtain until the other completes.

Deadlocks involving several transactions can also occur. For example, FIGURE 11.10 shows four transactions, Q, R, S, and T, that are deadlocked because Q is waiting for a data item locked by R, R is waiting for a data item locked by S, S is waiting for a data item locked by T, and T is waiting for a data item locked by Q. Once deadlock occurs, the applications involved cannot resolve the problem. Instead, the system must recognize that deadlock exists and break the deadlock in some way.

There are two general techniques for handling deadlock: deadlock prevention, in which the system looks ahead to see if a transaction would cause a deadlock and never allows deadlock to occur, and deadlock detection and recovery, which allows deadlock to occur but, once it has, identifies and breaks the deadlock. Because it is easier to test for deadlock and break it when it occurs than to prevent it, many systems use the detection and recovery method.

Deadlock detection schemes use a resource request graph or wait-for graph to show which transactions are waiting for resources locked by other transactions. In such a graph, each node is a transaction. An edge indicates that one transaction is waiting for another to release a lock. For example, FIGURE 11.11(A) shows two transactions, U and V, with the directed edge from U to V showing that U is waiting for a data item locked by V. The wait-for graph is maintained by the system. As new transactions start, new nodes are added to the graph. When a transaction makes a request for a locked resource that is unavailable, an edge is added to the graph. If the resource is unlocked and obtained by the transaction, the edge is erased. Deadlock occurs when the graph contains a cycle.

FIGURE 11.11(B) shows a wait-for graph in which transactions S and T are deadlocked because there is a cycle starting with S, going to T, and then going back to S. This cycle has length 2 because it contains two edges or directed paths, S to T and T to S. (Of course, there is also a cycle starting at T.) This graph corresponds to the transactions in Figure 11.9. FIGURE 11.11(C) shows a wait-for graph with a cycle of length 4. This pictures transactions Q, R, S, and T from Figure 11.10.

The system detects deadlock by periodically checking its wait-for graph for cycles. Note that it must check for cycles of any length because a cycle might involve many transactions. Once a cycle is detected, the system must resolve the deadlock. It does so by choosing one of the transactions in the cycle as the victim, which is a transaction that will be made to fail and will be rolled back so that the other transactions can proceed. The victim may be the newest transaction, one that has not done much work, one that has made the fewest updates, or one that has the lowest priority. If we chose transaction S shown in Figure 11.11(C) as the victim, then R would obtain its requested data items and could complete and release its locks, so that Q could also complete and, finally, T could obtain its data items. Then transaction S, the victim, could be restarted and could obtain its locks at a later time.

A problem that is similar to deadlock, called starvation, arises when a transaction is made to wait for a lock on an item indefinitely while other transactions are granted the locks they request for the item and are permitted to complete normally. Starvation can occur if the same transaction is always chosen as the victim to be rolled back when a deadlock is detected, but it can occur in other ways. FIGURE 11.11(D) shows an example of starvation. Here, transaction Q is unable to obtain an exclusive lock on item x when it initially requests it at time t3 because transaction P already has a shared lock on x. While Q is waiting for P to release its shared lock, transaction R is granted another shared lock on x. When P releases its lock, Q is still unable to obtain an exclusive lock because R now holds a shared lock on x. Overlapping transactions S, T, U, and perhaps other later transactions can continue to prevent Q from obtaining the exclusive lock it needs on x.

FIGURE 11.11(E) shows the wait-for graph, which demonstrates that there is no deadlock because there are no cycles in the graph. Even when one or more edges are erased as other transactions terminate, edges from Q to new overlapping transactions can remain on the graph indefinitely.

Several methods exist for preventing starvation. They include ensuring that transactions are given a higher priority the longer they wait, that the same transaction is not chosen repeatedly to be a victim in case of deadlock, or that a first-come, first-served policy is used in granting locks.

11.4.2 Two-Phase Locking Protocol

One locking scheme that ensures serializability is the two-phase locking protocol. According to the rules of this protocol, every transaction can go through two phases: first, a growing phase, in which it acquires all the locks needed for the transaction; and then a shrinking phase, in which it releases its locks. There is no requirement that all locks be obtained simultaneously. Normally the transaction acquires some locks, does some processing, and goes on to acquire additional locks as needed. However, it never releases any lock until it has reached a stage where no new locks will be needed. The rules are as follows:

• A transaction must acquire a lock on an item before operating on the item. For read-only access, a shared lock is sufficient. For write access, an exclusive lock is required.

• Once the transaction releases a single lock, it can never acquire any new locks.

FIGURE 11.12 shows how the two-phase locking protocol could be applied to Figure 11.3. Note that both transactions needed an exclusive lock on BAL because both were planning to update it. Jack’s transaction requested and obtained the lock first, and held the lock until it finished the update on BAL. Then it released the lock and Jill’s transaction, which had been suspended (put in a wait state) while it waited for the lock, could now obtain it and complete.

In the standard two-phase locking protocol, described by the two rules given previously, locks can be released before COMMIT, provided no new locks are requested after any are released. A problem that can arise is that an uncommitted transaction that has released its locks may be rolled back. If a second transaction has been permitted to read a value written by the rolled-back transaction, it must also roll back because it has read dirty data. This problem is called a cascading rollback. FIGURE 11.13 shows a case of cascading rollbacks. Transaction R wrote a value of 4 for a, then released its lock because it was no longer using a and it did not need any additional locks in the future. Transaction S read the value of 4 that R had written, and wrote a new value, 8, for a and released its lock on a. Transaction T read the value of 8 and calculated yet another value, 18. When R rolled back, the value of 4 that it wrote became invalid, which caused S to roll back as well. Then the write of 8 by transaction S became invalid, so T had to roll back as well.

Rollbacks are undesirable because they represent wasted processing time. A variation called strict two-phase locking requires that transactions hold their exclusive locks until COMMIT, preventing cascading rollbacks. An even stricter protocol is rigorous two-phase locking, which requires that transactions hold all locks, both shared and exclusive, until they commit.

The two-phase locking protocol can be refined slightly using lock upgrading to maximize concurrency. In this version of two-phase locking, a transaction may at first request shared locks that will allow other concurrent transactions read access to the items. Then when the transaction is ready to do an update, it requests that the shared lock be upgraded, or converted into an exclusive lock. Upgrading can take place only during the growing phase and may require that the transaction wait until another transaction releases a shared lock on the item. Once an item has been updated, its lock can be downgraded—converted from an exclusive to a shared mode. Downgrading can take place only during the shrinking phase.

While all forms of the two-phase protocol guarantee serializability, they can cause deadlock because transactions can wait for locks on data items.

11.4.3 Levels of Locking

Locks can be applied to a single data item, a single tuple, a page, a group of pages, or the entire database. Few systems implement data item–level locks because of the overhead involved. Some lock pages at a time, while others, like Oracle, support row-level locking.

We can express the fineness or granularity of locks by a hierarchical structure in which nodes represent data objects of different sizes, as shown in FIGURE 11.14. Here, the root node represents the entire database, the level 1 nodes represent tables, the level 2 nodes represent pages of tables, the level 3 nodes represent tuples, and the leaves represent data items. Whenever a node is locked, all its descendants are also locked. For example, if a transaction locks page A1 of Figure 11.14, it also locks records A11 and A12 as well as all their data items. If a second transaction requests an incompatible lock on the same node, the system clearly knows that the lock cannot be granted. For example, a request for an exclusive lock on page A1 will be denied. If the second transaction requests an incompatible lock on any of the descendants of the locked node, the system should check the hierarchical path from the root to the requested node to see if any of its ancestors are locked before deciding whether to grant the lock. Thus, if the request is for an exclusive lock on tuple A11, the system should check its parent, page A1, its grandparent, table A, and the database itself to see if any of them are locked. When the system finds that page A1 is already locked, it denies the request.

What happens if a transaction requests a lock on a node when a descendant of a node is already locked? For example, if a lock is requested on table A, the system would have to check every page in the table, every row in those pages, and every data item in those rows to see if any of them are locked. To reduce the searching involved in locating locks on descendants, the system can use another type of lock called an intention lock. When any node is locked, an intention lock is placed on all the ancestors of the node. Thus, if some descendant of table A (e.g., page A1) is locked, and a request is made for a lock on table A, the presence of an intention lock on table A would indicate that some descendant of that node is already locked. Intention locks can use either exclusive or shared mode.

To ensure serializability with locking levels, a modified two-phase protocol is used, meaning no lock can be granted to a transaction once any node has been unlocked by that transaction, no node can be locked by a transaction until its parent is locked by an intention lock, and no node can be unlocked by a transaction until all its descendants are unlocked. The effect of these rules is to apply locking from the root down, using intention locks until the node requiring an actual shared or exclusive lock is reached, and to release locks from the leaves up. However, deadlock is still possible, and must be detected and resolved using the methods discussed previously.