C191-Terms-Chapter-6

Question 1

reusable resource

Answer 1

A reusable resource may be requested, acquired, and later released by a process. Ex: processors, devices, memory blocks, and files.

Question 2

consumable resource

Answer 2

A consumable resource is created by a process and consumed by another process. Ex: messages, interrupts, or signals. This chapter deals with only reusable resources.

Question 3

resource allocation graph

Answer 3

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

Processes are represented by circles.

Resources are represented by rectangles. If a resource contains multiple units then each unit is represented by a small circle.

Resource allocations are represented by edges directed from a resource to a process.

Resource requests are represented by edges directed from a process to a resource.

Question 4

blocked

Answer 4

A process p is blocked 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 5

resource request

Answer 5

(req r, m) by a process p for m units of a resource, r creates m new edges directed from p to r. A resource request may be issued only 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 before a new request.

Question 6

resource acquisition

Answer 6

(acq r, m) by a process, p of m units of a resource r reverses the direction of the corresponding request edges to point from the units of r to p.

A resource acquisition is executed by the system and is allowed only when r currently contains at least m free units. No partial allocation of units is permitted.

Question 7

resource release

Answer 7

(rel r, m) operation by a process p of m units of a resource r deletes m allocation edges between p and r.

A resource release may be issued only 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.

Question 8

deadlocked

Answer 8

A process is deadlocked in a state s if the process is blocked in s and if no matter what state transitions occur in the future, the process remains blocked.

Question 9

deadlock state

Answer 9

A state s is called a deadlock state if s contains two or more deadlocked processes.

Question 10

safe state

Answer 10

A state s is a safe state if no sequence of state transitions exists that would lead from s to a deadlock state.

When the sequence of all requests and releases by each process is known, a complete state transition graph can be constructed and analyzed for the presence of deadlock states and safe states.

Question 11

A deadlock in a resource allocation graph can be detected by executing a graph reduction algorithm:

Answer 11

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.

Question 12

completely reducible

Answer 12

if at the termination of the graph reduction algorithm, all processes have been deleted.

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

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

The consequence of the two theorems is that any sequence of reductions will determine whether a given resource allocation graph represents a deadlock state.

Question 13

Continuous deadlock detection

Answer 13

Testing for deadlock can be accomplished more efficiently if done on a continuous basis. If the current state s is not deadlocked, then the next state s’ can be a deadlock state only if

the operation that caused the transition was a request for a resource and

the process p that issued the request is deadlocked in s’.

Question 14

Continuous deadlock detection then proceeds as follows:

Answer 14

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

If p is removed then s’ is not a deadlock state and the algorithm terminates.

Question 15

wait-for graph

Answer 15

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

The term “wait-for” indicates that process p is blocked on a resource currently held by another process p’.

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

Question 16

Recovery from a deadlock

Answer 16

can be accomplished by destroying one or more of the processes involved in the deadlock, or by removing some of the resources held by the deadlocked processes.

An alternative is to avoid the possibility of a deadlock by delaying the acquisition of resources that could cause the system to enter a deadlock state.

Question 17

maximum claim

Answer 17

of a process is the set of all resources the process may ever request. Each potential future claim of a resource is represented by a dashed edge in the resource allocation graph.

Question 18

resource claim graph

Answer 18

is an extension of the general resource allocation graph. The extended graph shows

the current allocation of resources to processes and
all current as well as all potential future requests by processes for new resources.

Question 19

The banker’s algorithm

Answer 19

emulates the strategy used by a bank when issuing loans. A loan corresponds to a resource allocation and a maximum claim corresponds to the credit limit of a customer (requesting process).

The bank grants a request as long as a sequence of loans exists that would satisfy the needs of all customers in some order. Otherwise, the granting of the request is postponed.

Question 20

The banker’s algorithm:

Answer 20

Given a resource request in a state s, temporarily grant the request by changing the request edges to allocation edges.

Execute a graph reduction on the new state s’.

If the graph of state s’ is completely reducible then accept s’ as the new state. Otherwise disallow the acquisition by reverting to state s.

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

Question 21

Deadlock avoidance with single-unit resources

Answer 21

With single-unit resources, a process p can be blocked only if p is waiting for a resource held by another blocked process p’.

Since p’ is blocked, p’ must be waiting for another resource held by yet another process p”, etc. To make the chain irreducible in the claim graph, the processes must be blocked in a directed cycle.

Question 22

Deadlock avoidance with single-unit resources

Answer 22

The banker’s algorithm is then simplified:

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.

Question 23

Deadlock avoidance with single-unit resources. Checking for a safe state is also simplified:

Answer 23

A directed cycle can be formed only if the graph already contains an undirected cycle.

The reason is that no new edges are added to or removed from a claim graph. A claim edge can only change into a request edge, which in turn can change into an allocation edge, and eventually back to a claim edge.

Thus the initial claim graph can be analyzed for the presence of undirected cycles. If no cycle exists then all states are safe and no other checks at runtime are needed.

Question 24

Conditions for a deadlock

Answer 24

Two conditions must hold for a deadlock to occur with reusable resources:

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.

Deadlock is structurally impossible if either of the two conditions are eliminated.

Question 25

Eliminating hold-and-wait

Answer 25

Several alternatives to eliminating the hold-and-wait condition exist:

Every process must request all resources ever needed at the same time. The price paid for the simplicity of the approach is poor resource utilization since resources are held for unnecessarily long periods of time and thus unavailable to other processes.

Every process must release all currently held resources prior to making any new request. The approach improves resource utilization but results in repeated requests and releases of frequently used resources.

A process can be given the ability to test whether a needed resource is currently available. The process must release all currently held resources only if the requested resource is not currently available. Otherwise, the new resource may be requested and allocated immediately.

Question 26

Eliminating circular wait

Answer 26

A cycle in the resource graph can be closed only when two or more processes request the same resources but in a different order.

A circular wait is prevented if all processes are required to request all resources in the same order.

One approach is to assign a sequential ordering, seq, to all existing resources, such that seq(ri) ≠ seq(rj) for all i ≠ j. All processes are then required to request resources in only increasing sequential order.

The strict ordering rule can be relaxed if the needs of individual processes are known in advance.

In particular, any resource used by only one process cannot be part of any cycle and may be requested at any time.