Deadlock detection is the process of identifying whether a system has entered a deadlock state.
Deadlock Detection for Single Instance of Each Resource
For single-instance resources, a Wait-For Graph is used:
- A Wait-For Graph is constructed by removing resource nodes from a Resource Allocation Graph and only keeping edges representing waiting conditions between processes.
- If a cycle exists in the Wait-For Graph, deadlock is detected because each process in the cycle is waiting for a resource held by another process in the cycle.
Example:
- If process P1 is waiting for a resource held by P2, and P2 is waiting for a resource held by P1, there is a cycle, indicating a deadlock.
Deadlock Detection for Multiple Instances of Each Resource
For multiple-instance resources, an algorithm similar to Banker’s Algorithm is used:
- Work Array: Initialize a work array with the currently available resources.
- Finish Array: Mark all processes as unfinished initially.
- Find Satisfiable Process: Find an unfinished process whose needs are less than or equal to the available resources (in the work array).
- Simulate Resource Release: Pretend the process finishes, release its allocated resources back to the available pool, and mark the process as finished.
- Check for Deadlock: If no such process can be found, and some processes are still unfinished, then the system is in a deadlock.
Example:
- Suppose three processes request varying amounts of resources from a shared pool. If the detection algorithm cannot find any safe sequence of processes to complete, then a deadlock has been detected.
