COM1317 Spring 2001 -- Lock and Wait Sets for Atomicity

May 9, Prof. Futrelle (slight revisions 5/10)

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 Lock-x Wait-x Lock-y Wait-y T1 Locks-1 T2 Locks-2 What happens
0 r1       R rx R   r1(x) requested and granted
1 r1, r2       R rx R rx r2(x) requested and granted
2 r1, r2   r1   R rx, ry R rx r1(y) requested and granted
3 r1, r2 w2 r1   R rx, ry W rx, wwx w2(x) requested, 2 suspended
4 r1, r2 w2 w1   R rx, wy W rx, wwx w1(y) requested and granted
5 r1, r2 w2 w1   R rx, wy W rx, wwx T2 continues to wait
6 r2 w2     N   W rx, wwx T1 commits, releases its locks
7 w2       N   R wx Lock wait promoted for 2, 2 runs
8         N   N   T2 commits, releases its lock