A deadlock in a resource allocation graph can be detected by executing a graph reduction algorithm by repeating this process:
- Select an unblocked process p.
- Remove p, including all request and allocation edges connected to p.
Anything left is blocked, and risks deadlock. However, it is considered completely reducible if there are no processes left on the graph after they have been removed.
Testing for deadlock can be accomplished more efficiently if done on a continuous basis. If the current state is not deadlocked, then the next state can be a deadlock state only if
- the operation that caused the transition was a request for a resource and
- the process that issued the request is deadlocked in the next state.
A wait-for graph is a resource allocation graph containing only processes that can have multiple incoming resource allocation edges but only one outgoing resource request edge.
Deadlock Detection was originally found on Access 2 Learn
