6.6 Deadlock detection
If the deadlock is allowed to occur in the system, then the system must provide the following:
When the system has resources with single instance in each one, then a variant to the resource-allocation graph called wait-for graph can be used.
In the wait-for graph, nodes are processes. An edge Pi → Pj means Pi is waiting for Pj. This happens if the corresponding resource-allocation graph contains two edges Pi → Rq and Rq → Pj for some resource Rq.
If the system has resources that have several instances, then the algorithm used in this case is similar to the Banker's algorithm. The algorithm has the following data types:
 |
An algorithm that examines the state of the system to determine whether a deadlock has occurred. |
|
An algorithm to recover from the deadlock. |
When the system has resources with single instance in each one, then a variant to the resource-allocation graph called wait-for graph can be used.
In the wait-for graph, nodes are processes. An edge Pi → Pj means Pi is waiting for Pj. This happens if the corresponding resource-allocation graph contains two edges Pi → Rq and Rq → Pj for some resource Rq.
If the system has resources that have several instances, then the algorithm used in this case is similar to the Banker's algorithm. The algorithm has the following data types:
|
Available: A vector of length m indicates the number of available resources of each type. |
|
Allocation: An n x m matrix defines the number of resources of each type currently allocated to each |
| process. |
|
Request: An n x m matrix indicates the current request of each process. If Request [i, j] = k, then |
| process Pi is requesting k more instances of resource type Rj. |
0, then