Information Technology Reference
In-Depth Information
a
b
Fig. 6.4
Deadlock between two transactions: (
a
) locking two data items in different orders; (
b)
upgrading locks on a single data item. The arcs indicate wait-for relationships between transactions
waiting for locks
Now both transactions need to wait for each other forever (see Fig.
6.4
a).
t
In the above example, the deadlock results from two transactions operating on
two data items in different orders and locking the keys with incompatible locks. A
lock upgrade from a read lock to a write lock can also lead to a deadlock.
Example 6.18
Let T
1
and T
2
be active transactions.
1. T
1
acquires an S lock on key x and reads the tuple with key x.
2. T
2
acquires an S lock on key x and reads the tuple with key x. Recall that S locks
are compatible.
3. T
1
wants to update the tuple with key x. Therefore it requests an X lock on x,
that is, a lock upgrade from its S lock to an X lock. Because of the S lock held
by T
2
on x, the upgrade cannot be granted immediately, and so T
1
is put to sleep
to wait for T
2
to release its lock.
4. T
2
wants to update the tuple with key x. Therefore it requests an X lock on x,
that is, a lock upgrade from its S lock to an X lock. Because of the S lock held
by T
1
on x, the upgrade cannot be granted immediately, and so T
2
is put to sleep
to wait for T
1
to release its lock.
Again both transactions need to wait for each other forever (Fig.
6.4
b).
t
Actually, in practice lock upgrades are the most important reason for deadlocks.
This is because the following operation sequence is very common in transactions:
1. Acquire an S lock on key x and read the tuple with key x.
2. Find out if the tuple needs to be updated.
3. If an update is needed, upgrade the S lock on x to an X lock and perform the
update.
Ifthetupleisa
hotspot tuple
, one that is updated very often from different
transactions, the possibility of a deadlock is high.
In general: the database system is
in deadlock
, if the following holds for some
active transactions T
1
;:::;T
n
:
T
1
waits for access to a data item that is locked by T
2
.
T
2
waits for access to a data item that is locked by T
3
.
