DEADLOCK
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.
• {T0, T1,…, Tn}
• There are two principal methods for dealing with the deadlock problem.
• We can use a deadlock prevention protocol to ensure that the system will never enter a
deadlock state.
• Alternatively, we can allow the system to enter a deadlock state, and then try to recover
by using a deadlock detection and deadlock recovery scheme
DEADLOCK HANDLING
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
(pre-declaration).
• There are two main disadvantages to this protocol:
1. it is often hard to predict, before the transaction begins, what data items need
to be locked;
2. data-item utilization may be very low, since many of the data
items may be locked but unused for a long time.
• Impose partial ordering of all data items and require that a transaction can lock
data items only in the order specified by the partial order (graph-based
protocol).
MORE DEADLOCK PREVENTION STRATEGIES
The second approach for preventing deadlocks is to use preemption
and transaction rollbacks.
In preemption, when a transaction Tj requests a lock that transaction
Ti holds, the lock granted to Ti may be preempted by rolling back of
Ti, and granting of the lock to Tj.
To control the preemption, we assign a unique timestamp, based on a
counter or on the system clock, to each transaction when it begins.
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 a lock
wound-wait scheme — preemptive
• Older transaction wounds (forces rollback) of younger transaction
instead of waiting for it.
• Younger transactions may wait for older ones.
• Fewer rollbacks than wait-die scheme.
WAIT-DIE SCHEME — NON-
PREEMPTIVE
The wait–die scheme is a non-preemptive technique.
When transaction T requests a data item currently held by T , T
i j i
is allowed to wait only if it has a timestamp smaller than that of
Tj (i.e., Ti is older than Tj).
Otherwise, Ti is rolled back (dies).
For example, suppose that transactions T14, T15, and T16 have
timestamps 5,10, and 15, respectively.
If T14 requests a data item held by T15, then T14 will wait.
If T16 requests a data item held by T15, then T16 will be rolled back.
WOUND-WAIT SCHEME —
PREEMPTIVE
The wound–wait scheme is a preemptive technique. It is a
counterpart to the wait–die scheme.
When transaction Ti requests a data item currently held by Tj, Ti
is allowed to wait only if it has a timestamp larger than that of Tj
(i.e., Ti is younger than Tj).
Otherwise, Tj is rolled back (Tj is wounded by Ti).
Returning to our example, with transactions T14, T15, and T16.
If T14 requests a data item held by T15, then the data item will be
preempted from T15, and T15 will be rolled back.
If T16 requests a data item held by T15, then T16 will wait.
DEADLOCK PREVENTION (CONT.)
Timeout-Based Schemes:
• A transaction waits for a lock only for a specified
amount of time. After that, the wait times out and the
transaction is rolled back.
• Ensures that deadlocks get resolved by timeout if they
occur
• Simple to implement
• But may roll back transaction unnecessarily in
absence of deadlock
Difficult to determine good value of the timeout
interval.
• Starvation is also possible
DEADLOCK DETECTION
Deadlocks can be described precisely in terms of a directed graph called a wait-
for graph.
This graph consists of a pair G = (V , E), where V is a set of vertices and E is
a set of edges.
If Ti → Tj is in E, then there is a directed edge from transaction Ti to Tj,
implying that transaction Ti is waiting for transaction Tj to release a data item
that it needs.
When transaction Ti requests a data item currently being held by transaction Tj,
then the edge Ti → Tj is inserted in the wait-for graph.
This edge is removed only when transaction Tj is no longer holding a data item
needed by tr
A deadlock exists in the system if and only if the wait-for graph contains a
cycle.
Each transaction involved in the cycle is said to be deadlocked. To detect
deadlocks, the system needs to maintain the wait-for graph, and periodically to
invoke an algorithm that searches for a cycle in the graph.
DEADLOCK DETECTION
Wait-for graph
Transaction T is waiting for transactions T and T .
17 18 19
Transaction T is waiting for transaction T .
19 18
Transaction T is waiting for transaction T .
18 20
Wait-for graph without a cycle
DEADLOCK DETECTION
Wait-for graph
Transaction T is waiting for transactions T and T .
17 18 19
Transaction T is waiting for transaction T .
19 18
Transaction T is waiting for transaction T .
18 20
Suppose now that transaction T20 is requesting an item held by
T19.
T18 → T20 → T19 → T18
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 cycle.
Three actions need to be taken:
1. Selection of a victim
2. Rollback
3. Starvation
SELECTION OF A VICTIM
We should roll back those transactions that will incur the minimum
cost. Unfortunately, the term minimum cost is not a precise one.
Many factors may determine the cost of a rollback, including:
• How long the transaction has computed, and how much longer the
transaction will compute before it completes its designated task.
• How many data items the transaction has used.
• How many more data items the transaction needs for it to complete.
• How many transactions will be involved in the rollback.
ROLLBACK
Once we have decided that a particular transaction must be
rolledback, we must determine how far this transaction should be
rolled back.
Total rollback: Abort the transaction and then restart it. However, it
is more effective to roll back the transaction only as far as necessary
to break the deadlock.
Partial rollback requires the system to maintain additional
information about the state of all the running transactions.
STARVATION
In a system where the selection of victims is based primarily on cost
factors, it may happen that the same transaction is always picked as a
victim.
As a result, this transaction never completes its designated task, thus
there is starvation.
We must ensure that a transaction can be picked as a victim only a
(small) finite number of times.
The most common solution is to include the number of rollbacks in
the cost factor.
