Database Deadlocks and Detection
DBMS
Deadlock
Deadlocks
•
Detection
–
Wait-for graph
•
Prevention
–
Resource ordering
–
Timeout
–
Wait-die
–
Wound-wait
3
Deadlock Detection
•
Build Wait-For graph
•
Use lock table structures
•
Build incrementally or periodically
•
When cycle found, rollback victim
T
1
T
3
T
2
T
6
T
5
T
4
T
7
Deadlock Detection
•
Deadlocks can be described as
a
wait-for graph
, which consists of a pair
G
= (
V
,
E
),
–
V
is a set of vertices (all the transactions in the system)
–
E
is a set of edges; each element is an ordered pair
T
i
T
j
.
•
If
T
i
T
j
is in
E
, then there is a directed edge from
T
i
to
T
j
–
implying that
T
i
is waiting for
T
j
to release a data item.
•
When
T
i
requests a data item held by
T
j
, then
T
i
T
j
is inserted in the wait-for graph.
–
This edge is removed only when
T
j
is no longer holding a data item needed by
T
i
.
•
The system is in a deadlock state if and only if
the wait-for graph has a cycle.
•
The system invokes
a deadlock-detection algorithm
periodically
to look for cycles.
Wait-for graph without a cycle
Wait-for graph with a cycle
Deadlock Recovery
•
When deadlock is detected:
–
Some transaction will have to rolled back (made a victim) to break deadlock.
•
Select that transaction as
victim that will incur minimum cost
.
–
Rollback -- determine how far to roll back transaction
•
Total rollback
: Abort the transaction and then restart it.
•
Partial rollback
: More effective to roll back transaction only as far as
necessary to break deadlock.
–
Starvation happens if same transaction is always chosen as victim.
•
The system may include the number of rollbacks in the cost factor to avoid
starvation
Deadlock Handling
•
System is deadlocked if there is a set of transactions such that every transaction in the
set is waiting for another transaction in the set.
•
Deadlock prevention
protocols
ensure that the system will
never
enter into a deadlock
state.
•
Some prevention strategies :
–
Require that
each transaction locks all its data items before it begins execution
(predeclaration).
–
Impose
partial ordering of all data items
•
require that a transaction can lock data items only in the order specified by the
partial order (graph-based protocol).
–
Timeout-Based Schemes
:
•
a transaction waits for a lock only for a specified amount of time.
–
After the wait time is out
and the transaction is rolled back. (No deadlock!)
•
simple to implement; but
starvation is possible
•
Also difficult to determine good value of the timeout interval.
–
Use
timestamping
(in the next slide)
Deadlock Handling
•
Consider the following two transactions:
T
1
: write (
X
)
T
2
: write(
Y
)
write(
Y
) write(
X
)
•
Schedule with deadlock
T
1
T
2
lock-X
on
X
write (
X
)
lock-X
on
Y
write (
Y
)
wait for
lock-X
on
X
write(X)
wait for
lock-X
on
Y
write(Y)
Deadlock Prevention with Timestamps
•
Following schemes use
transaction timestamps
for the sake of
deadlock prevention alone.
•
Wait-die
scheme
— non-preemptive
–
Older transaction may
wait
for younger one to release data item.
–
Younger transactions
never wait
for older ones; they are
rolled back
instead.
–
A transaction may die several times before acquiring needed data item
•
Wound-wait
scheme
— preemptive
–
Older transaction
wounds
(forces rollback of) younger transaction instead of waiting
for it.
–
Younger transactions may
wait for
older ones.
–
May be fewer rollbacks than
wait-die
scheme.
•
Both in
wait-die
and in
wound-wait
schemes,
a rolled back transaction
is restarted with
its original timestamp
.
–
Older transactions thus have precedence over newer ones in these schemes, and
starvation is hence avoided
.
Deadlock in DBMSs
•
What is a deadlock?
–
A
cycle
of transactions, T
1
, T
2
, ... , T
n
=T
1
where each T
i
is
waiting
for T
i-1
to
release a lock.
–
Causes these transactions to sleep forever.
•
A Deadlock
can happen
whenever you allow a transaction to
wait
for
a lock, even with strict two phase locking.
–
Simple example:
•
Users can eliminate deadlocks by accessing resources in a fixed order.
•
DBMSs typically detect deadlocks and abort the transaction that (it
thinks) has used the least resources.
T1:
R(B),
W(A)
T2:
R(A),
W
(B)
Review: The ACID properties
•
A
A
tomicity
:
All actions in the transaction happen in their
entirety or none of them happen.
•
C
C
onsistency
:
If each transaction is consistent, and the DB
starts in a consistent state, it ends in a
consistent state.
•
I
I
solation
:
Execution of one transaction is isolated from
that of other transactions.
•
D
D
urability
:
If a transaction commits, its effects persist.
Recovery
System
Recovery
System
Concurrency
Control
System
Programmers
Database Management Systems (DBMS) often face deadlocks, which are situations where transactions are waiting for each other to release data items, leading to a cycle in the wait-for graph. Deadlocks can be detected by analyzing the wait-for graph periodically. If a deadlock is detected, a victim transaction is chosen and rolled back to break the deadlock. Various strategies like prevention protocols and deadlock recovery mechanisms can help handle deadlocks effectively in DBMS.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
DBMS Deadlock
Deadlocks Detection Wait-for graph Prevention Resource ordering Timeout Wait-die Wound-wait
Deadlock Detection Build Wait-For graph Use lock table structures Build incrementally or periodically When cycle found, rollback victim T5 T2 T1 T7 T4 T6 T3 3
Deadlock Detection Deadlocks can be described as a wait-for graph, which consists of a pair G = (V,E), V is a set of vertices (all the transactions in the system) E is a set of edges; each element is an ordered pair Ti Tj. If Ti Tjis in E, then there is a directed edge from Ti to Tj implying that Ti is waiting for Tj to release a data item. When Ti requests a data item held by Tj, then Ti Tjis inserted in the wait-for graph. This edge is removed only when Tj is no longer holding a data item needed by Ti. The system is in a deadlock state if and only if the wait-for graph has a cycle. The system invokes a deadlock-detection algorithm periodically to look for cycles. Wait-for graph with a cycle Wait-for graph without a cycle
Deadlock Recovery When deadlock is detected: Some transaction will have to rolled back (made a victim) to break deadlock. Select that transaction as victim that will incur minimum cost. Rollback -- determine how far to roll back transaction Total rollback: Abort the transaction and then restart it. Partial rollback: More effective to roll back transaction only as far as necessary to break deadlock. Starvation happens if same transaction is always chosen as victim. The system may include the number of rollbacks in the cost factor to avoid starvation
Deadlock Handling System is deadlocked if there is a set of transactions such that every transaction in the set is waiting for another transaction in the set. Deadlock prevention protocols ensure that the system will never enter into a deadlock state. Some prevention strategies : Require that each transaction locks all its data items before it begins execution (predeclaration). Impose partial ordering of all data items require that a transaction can lock data items only in the order specified by the partial order (graph-based protocol). Timeout-Based Schemes : a transaction waits for a lock only for a specified amount of time. After the wait time is out and the transaction is rolled back. (No deadlock!) simple to implement; but starvation is possible Also difficult to determine good value of the timeout interval. Use timestamping (in the next slide)
Deadlock Handling Consider the following two transactions: T1: write (X) T2: write(Y) write(Y) write(X) Schedule with deadlock T1 T2 lock-X on X write (X) lock-X on Y write (Y) wait for lock-X on X write(X) wait for lock-X on Y write(Y)
Deadlock Prevention with Timestamps Following schemes use transaction timestamps for the sake of deadlock prevention alone. Wait-die scheme non-preemptive Older transaction may wait for younger one to release data item. Younger transactions never wait for older ones; they are rolled back instead. A transaction may die several times before acquiring needed data item Wound-wait scheme preemptive Older transaction wounds (forces rollback of) younger transaction instead of waiting for it. Younger transactions may wait for older ones. May be fewer rollbacks than wait-die scheme. Both in wait-die and in wound-wait schemes, a rolled back transaction is restarted with its original timestamp. Older transactions thus have precedence over newer ones in these schemes, and starvation is hence avoided.
Deadlock in DBMSs What is a deadlock? A cycle of transactions, T1, T2, ... , Tn=T1 where each Ti is waiting for Ti-1 to release a lock. Causes these transactions to sleep forever. A Deadlock can happenwhenever you allow a transaction to wait for a lock, even with strict two phase locking. Simple example: T1: T2: R(A), W(B) R(B), W(A) Users can eliminate deadlocks by accessing resources in a fixed order. DBMSs typically detect deadlocks and abort the transaction that (it thinks) has used the least resources.
Review: The ACID properties Recovery System Atomicity: All actions in the transaction happen in their entirety or none of them happen. Consistency: If each transaction is consistent, and the DB starts in a consistent state, it ends in a consistent state. Programmers Concurrency Control System Isolation: Execution of one transaction is isolated from Recovery System that of other transactions. Durability: If a transaction commits, its effects persist.
