Information Technology Reference
In-Depth Information
T
n
waits for access to a data item that is locked by T
1
.
This kind of cycle of transactions that wait for each other can occur only with
locking-based and other pessimistic concurrency-control protocols that ensure
isolation by forcing a transaction to wait if it tries to perform an action that
would introduce an isolation anomaly. This is in contrast to a typical optimistic
concurrency-control protocol, in which an attempted breach of isolation is prevented
by aborting the transaction. With such a protocol, deadlocks cannot occur.
With lock-based concurrency control, there are two basic approaches for
deadlock management: (1) deadlock prevention protocols and (2) deadlock
detection and resolution schemes. First we note that, in general, it is not possible
to enforce
deadlock prevention
without forcing some transactions to abort and roll
back. This is because transactions are formed by performing one action at a time,
resulting from
SQL
requests coming from the application process; a transaction
when it starts does not know beforehand what actions it will eventually perform or
in what order it will access the data items or whether or not it will later update a
data item it has read earlier.
Thus, every database management system with lock-based concurrency control
must include a
deadlock detection
and
resolution
scheme. Deadlocks are allowed
to occur, and when so happens, one of the transactions involved in the deadlock is
aborted. That transaction is called the
victim
.
The basic solution is to maintain a
wait-for graph
of transactions waiting for each
other. A directed edge T
!
T
0
is added to the wait-for graph when transaction T
requests a lock on a data item locked by transaction T
0
and needs to wait. The edge
T
!
T
0
is removed when T no longer waits for access to any data item locked
by T
0
.
The system is in deadlock if and only if there is a cycle in the wait-for graph.
To detect deadlocks, an algorithm that looks for cycles in the wait-for graph is run
periodically. A deadlock is resolved by repeatedly aborting a transaction that is a
part of a cycle, until there are no more cycles.
Besides the locks acquired by transactions on data items in the database, the
latches acquired by server-process threads on database pages can be the cause for a
deadlock.
Example 6.19
Assume that a server-process thread executing a transaction T
1
is
running concurrently with a server-process thread executing a transaction T
2
.
1. The thread executing T
1
read-latches page p.
2. The thread executing T
2
read-latches page q.
3. The thread executing T
1
requests a write latch on page q. Because of the latch
held by the other thread, the requested latch cannot be granted immediately, and
so the requester has to wait.
4. The thread executing T
2
requests a write latch on page p. Because of the latch
held by the other thread, the requested latch cannot be granted immediately, and
so the requester has to wait.
