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(N2) where N is the number of proceeds. Another potential problem
is starvation; same process killed repeatedly. |