Deadlock detection and recovery

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 Detection

• If the deadlocks are not avoided then another approach is to detect them when they have occurred and recover from them.

• The basic idea is to check allocation against availability for all possible allocation sequences to determine if the system is in deadlocked state.

Once detected there needs to be way to recover several alternatives exist:

• Temporarily prevent resources from deadlocked processes

• Back Off a process to some check point allowing preemption of a needed resource and restarting the process at the checkpoint later

• Successively kill processes until the system is deadlock free.

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 currently being held by Tj, then the edge TiTj is 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. Must invoke a deadlock-detection algorithm periodically to look for cycles.

Deadlock Recovery Deadlock recovery is generally used when deadlocks are rare and the cost of recovery is low.

Methods for Recovery

1. Termination of processes

• Some victim process is chosen for termination from the cycle of deadlocked processes.

• This process is terminated, requiring a later restart.

• All the resources allocated to this processes are released, so that they may be reassigned to other deadlocked processes.

• With an appropriately chosen victim process, this should resolve the deadlock.

2. Rolling back processes

• In order to rollback a victim process, there needs to have been some previous checkpoint at which time the state of the victim process was saved to stable storage.

• There must also be an assurance that the rolled back process is not holding any resource needed by the other deadlocked processes at that point.

• With an appropriately chosen victim process, needed resources will be released and assigned to other deadlocked processes.

• This resolves deadlock.