Chapter 5: Deadlock

Question 1

Resource Allocation Graph

Answer 1

shows the current allocation of resources to processes and the current requests by processes for new resources

Question 2

A processes p is blocked if? (resource allocation graph)

Answer 2

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.

Question 3

Resource request (req r, m) by process p for m units of resource r

Answer 3

Creates m new edges directed from p to r. Only happens when:

1. Process p has no unsatisfiable requests and thus is not blocked. A blocked process is not running and cannot issue additional requests.
2. 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

Question 4

resource acquisition (acq r, m) by process p of m units of resource r

Answer 4

reverses the direction of the corresponding request edges to point from the units of r to p. No partial allocations are allowed.

Question 5

resource release (rel r, m) by process p of m units of resource r

Answer 5

deletes m allocation edges between p and r. Only happens when:

1. Process p has no unsatisfiable requests and thus is not blocked.
2. the number m of units to be released must not exceed the total number of units p is currently holding.

Question 6

deadlock (state)

Answer 6

no matter what state transitions occur in the future, the process remains blocked

Question 7

deadlock state

Answer 7

state that contains two or more deadlocked processes

Question 8

safe state

Answer 8

State where no sequence of state transitions exists that would lead from the current state to a deadlock state.

Question 9

Graph Reduction Algorithm

Answer 9

Repeat until no unblocked process remains in the graph:

1. Select an unblocked process p.
2. Remove p, including all request and allocation edges connected to p.

Question 10

Completely Reducible (graph)

Answer 10

A graph where at the end of the graph reduction algorithm all processes have been deleted.

Question 11

Theorem 1 (reducibility of graphs)

Answer 11

A state s is a deadlock state if and only if the resource graph of s is not completely reducible.

Question 12

Theorem 2 (reducibility of graphs)

Answer 12

All reduction sequences of a given resource allocation graph lead to the same final graph.

Question 13

Continuous deadlock detection (algorithm)

Answer 13

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

Question 14

wait-for graph

Answer 14

A resource allocation graph containing only processes where each process can have multiple incoming resource allocation edges but only one outgoing resource request edge.

Question 15

Theorem (wait-for graph)

Answer 15

A cycle in the wait-for graph is a necessary and sufficient condition for deadlock.

Question 16

Maximum claim

Answer 16

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.

Question 17

resource claim graph

Answer 17

An extension of the general resource allocation graph. Shows current allocation and all current/future requests by processes for new resources

Question 18

The banker’s algorithm

Answer 18

1. Given a request for a resource in a state s, temporarily grant the request by changing the request edge to an allocation edge.
2. Starting with the requesting process p, determine if the graph in the temporary state s’ contains a directed cycle.
3. If no cycle exists then accept s’ as the new state. Otherwise disallow the acquisition by reverting to the state s.

Question 19

Theorem (safe state)

Answer 19

If acquisition operations that do not result in a completely reducible claim graph are not executed then any system state is safe.

Question 20

Perform graph reduction using table

Answer 20

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.

Question 21

Execute bankers algorithm using table

Answer 21

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.

Question 22

Conditions for Static Deadlock

Answer 22

1. Hold and wait: A process is already holding one resource and is requesting another resource.
2. Circular wait: A process must issue a resource request that closes a cycle involving at least two processes and two resources.

Question 23

How to prevent circular wait

Answer 23

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.