Database Transactions, Lock Management and Deadlock - Part 3

Deadlock

Consider the following example.

T1	T2	Comment
S(A)		Shared lock granted.
R(A)		T1 reads values of A.
	S(A)	T2 asks for shared lock. It can be granted.
	R(A)	T2 reads values of A.
	X(A)	Cannot be granted because T1 holds a shared lock.
X(A)		Cannot be granted because T2 holds a shared lock.
DEADLOCK

Such a cycle of transactions waiting for locks to be released is called a deadlock. Clearly, these two transactions will make no further progress. Worse, they hold locks that may be required by other transactions. The DBMS must either prevent or detect (and resolve) such deadlock situations.

Deadlock Prevention

In deadlock prevention the transactions are processed in such a way that it never leads to a deadlock. Hence when deadlock prevention is used then deadlock detection mechanism is not required.

We can prevent deadlocks by giving each transaction a priority and ensuring that lower priority transactions are not allowed to wait for higher priority transactions. 

One way to assign priorities is to give each transaction a timestamp when it starts up. The lower the timestamp, the higher the transaction's priority, that is, the oldest transaction has the highest priority.

If a transaction Ti requests a lock and transaction Tj holds a conflicting lock, the lock manager can use one of the following two policies:

·         Wait-die: If Ti has higher priority, it is allowed to wait; otherwise it is aborted.

·         Wound-wait: If Ti has higher priority, abort Tj; otherwise Ti waits.

In the wait-die scheme, lower priority transactions can never wait for higher priority transactions. In the wound-wait scheme, higher priority transactions never wait for lower priority transactions. In either case no deadlock cycle can develop.

Deadlock Detection

Deadlocks tend to be rare and typically involve very few transactions. This observation suggests that rather than taking measures to prevent deadlocks, it may be better to detect and resolve deadlocks as they arise.

In deadlock detection the transactions are allowed to happen without any prior planning and the system is periodically checked for deadlocks. If deadlock is detected then some of the transactions are aborted because "abortion of transaction(s) is must to resolve a deadlock".

The lock manager maintains a structure called a waits-for graph to detect deadlock cycles. The nodes correspond to active transactions, and there is an arc from Ti to Tj if (and only if) Ti is waiting for Tj to release a lock. The lock manager adds edges to this graph when it queues lock requests and removes edges when it grants lock requests.

T1	T2	T3	Comment
X(A)			Exclusive lock granted.
W(A)
	X(B)		Exclusive lock granted.
	W(B)
		X(C)	Exclusive lock granted.
		W(C)
X(B)			Wait. T2 holds exclusive lock on B.
	X(C)		Wait. T3 holds exclusive lock on C.
		X(A)	Wait. T1 holds exclusive lock on A.
DEADLOCK

The corresponding waits-for graph is

The waits-for graph is shows a cycle, which indicate deadlock. A deadlock is resolved by aborting a transaction that is on a cycle and releasing its locks; this action allows some of the waiting transactions to proceed.

How frequently you check the graph for deadlock depends upon activity and urgency of the transaction. If an urgent query is executing and the results are not coming then check for deadlock detection every 2 minutes.