Deadlock Detection

Deadlock detection is the process of actually determining that a deadlock exists and identifying the processes and resources involved in the deadlock.
The basic idea is to check allocation against resource availability for all possible allocation sequences to determine if the system is in deadlocked state a. Of course, the deadlock detection algorithm is only half of this strategy. Once a deadlock is detected, there needs to be a way to recover several alternatives exists:

• 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.

These methods are expensive in the sense that each iteration calls the detection algorithm until the system proves to be deadlock free. The complexity of algorithm is O(N²) where N is the number of proceeds. Another potential problem is starvation; same process killed repeatedly.