NOTE: This type of material will be on the Midterm, to be given Tuesday, May 15th.

Also see the notes describing the various locking protocols, by name, posted 6/5/01.

The first example shown below illustrates the problem we got into in class on Tuesday 5/8. What we had run into was an example of a deadlock arising from contention for a single data item. This is different from the "classic" illustration of a deadlock in which one process holds x and requests y while the other already holds y and then requests x. But in the example below, both transactions can have a lock, a read lock, on the same item and then when they request write locks they both are halted in a deadlock. Any other transactions that then request the same item, x, will also be suspended causing them to "pile up", waiting for the deadlock to be broken. In a fair policy for promotion, even other transactions waiting for read locks will be suspended, waiting for T1 and T2, which were queued earlier, to continue.

This type of deadlock is so simple that it occurs quite often. To quote Professor Salzberg, from email to me,

"Deadlock with a single item is the most important cause of deadlock in most systems. An "update" lock mode has been invented as a cure, where update is compatible with read but not with write or another update."

In this second example, we have chosen an example that is serializable. It is taken from the text, Fig. 23.2(a) on pg. 820. It is equivalent to the serial schedule in Fig. 23(b). Below the figure is a table showing the contents of the Lock and Wait sets for x and y as well as the Lock Lists for T1 and T2 as they change over time. Note that because we are using strict two-phase locking the transactions serialize in commit order, with T1 first and T2 second.

Notes on the table below:

• Time refers to the time points in the figure above
• Lock-x is the lock set L(x) of all read or write locks held on x by transaction 1 and 2, and similarly for Lock-y.
• Wait-x is the wait set W(x) of all locks requested on x by transaction 1 and 2, and similarly for Wait-y.
• T1 shows the status of T1 as running (R) or waiting (W) or not running (N) and similarly for T2.
• Locks-1 is the lock list of all locks held or waited for by T1, and similarly for Locks-2.
• What happens describes the requests, grants, suspension, release and running of the transactions.
• "wwx" means "waiting for a write lock on x".