Chapter 5: Deadlock Flashcards
Resource Allocation Graph
shows the current allocation of resources to processes and the current requests by processes for new resources
A processes p is blocked if? (resource allocation graph)
on a resource r if one or more request edges directed from p to r exist and r does not contain sufficient free units to satisfy all requests.
Resource request (req r, m) by process p for m units of resource r
Creates m new edges directed from p to r. Only happens when:
- Process p has no unsatisfiable requests and thus is not blocked. A blocked process is not running and cannot issue additional requests.
- The number m of request edges plus the number k of allocation edges between a process and a resource must not exceed the total number of units of the resource. Exceeding m + k implies erroneous code, where a process failed to perform a release prior
resource acquisition (acq r, m) by process p of m units of resource r
reverses the direction of the corresponding request edges to point from the units of r to p. No partial allocations are allowed.
resource release (rel r, m) by process p of m units of resource r
deletes m allocation edges between p and r. Only happens when:
- Process p has no unsatisfiable requests and thus is not blocked.
- the number m of units to be released must not exceed the total number of units p is currently holding.
deadlock (state)
no matter what state transitions occur in the future, the process remains blocked
deadlock state
state that contains two or more deadlocked processes
safe state
State where no sequence of state transitions exists that would lead from the current state to a deadlock state.
Graph Reduction Algorithm
Repeat until no unblocked process remains in the graph:
- Select an unblocked process p.
- Remove p, including all request and allocation edges connected to p.
Completely Reducible (graph)
A graph where at the end of the graph reduction algorithm all processes have been deleted.
Theorem 1 (reducibility of graphs)
A state s is a deadlock state if and only if the resource graph of s is not completely reducible.
Theorem 2 (reducibility of graphs)
All reduction sequences of a given resource allocation graph lead to the same final graph.
Continuous deadlock detection (algorithm)
If the current operation is a request for a resource and the requesting process p becomes blocked in s’ then execute the graph reduction algorithm until
- either p is removed from the graph
- or no unblocked process remains in the graph
wait-for graph
A resource allocation graph containing only processes where each process can have multiple incoming resource allocation edges but only one outgoing resource request edge.
Theorem (wait-for graph)
A cycle in the wait-for graph is a necessary and sufficient condition for deadlock.
Maximum claim
The set of all resources the process may ever request. Each potential future claim of a resource is represented by dashed edges in the resource allocation graph.
resource claim graph
An extension of the general resource allocation graph. Shows current allocation and all current/future requests by processes for new resources
The banker’s algorithm
- Given a request for a resource in a state s, temporarily grant the request by changing the request edge to an allocation edge.
- Starting with the requesting process p, determine if the graph in the temporary state s’ contains a directed cycle.
- If no cycle exists then accept s’ as the new state. Otherwise disallow the acquisition by reverting to the state s.
Theorem (safe state)
If acquisition operations that do not result in a completely reducible claim graph are not executed then any system state is safe.
Perform graph reduction using table
To perform graph reduction, each unblocked process p is removed by deleting the corresponding row. The number of available resource units is increased by p’s current allocation for each resource.
Execute bankers algorithm using table
To execute the Banker’s algorithm, the request by a process p for n units of a resource is tentatively granted: n is subtracted from the current requests, the potential requests and the available units, and is added to the allocations. If the new graph is completely reducible, p’s request is granted. Otherwise the state reverts to the previous state.
Conditions for Static Deadlock
- Hold and wait: A process is already holding one resource and is requesting another resource.
- Circular wait: A process must issue a resource request that closes a cycle involving at least two processes and two resources.
How to prevent circular wait
A process p already holding a resource ri with the sequence number seq(ri) may only request resource rj where seq(ri) < seq(rj).
If all processes follow the rule then circular wait is prevented.
