COMP 322 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

Process state blocked

Answer 2

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

State transitions: A resource request

Answer 3

A process p from m units of a resource r creates m new edges directed from p to r.

They can only be issued only when:
1. Process p has no unsatisfied requests and it is not blocked. A blocked process is not running any additional requests.

2. The number m of request edges plus the k of allocation edges between a process and a resource must not exceed the total amount units of the resource

Question 4

State transitions: A resource acquisition

Answer 4

a process resource r reverses the direction of the corresponding request edges to point from the units r to p.
It is allowed only when r currently contains the least m free units.

Question 5

State transitions: A resource release

Answer 5

Operation by process p of m units of a resource r deletes the m allocation edges between p and r.

Only occurs when:
1. Process p has no unsatisfied requests and it is not blocked.
2. The number of m of units to be released must not exceed the total number of units p is currently holding.

Question 6

Deadlocked

Answer 6

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

Question 7

Deadlock state

Answer 7

A state s where s contains two or more deadlock processes.

Question 8

Safe state

Answer 8

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

Question 9

Deadlock detection (Graph reduction)

Answer 9

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

Question 10

Completely reducible

Answer 10

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

Question 11

Wait-for graph

Answer 11

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

A process is blocked on a resource that is currently held by another process.

Question 12

Maximum claim

Answer 12

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

Question 13

Resource claim graph

Answer 13

It is an extension of a general resource allocation graph.
The extended graph shows:
The current allocation of resources to processes.
All current and all potential future requests by processes for new resources.

Question 14

The banker’s algorithm: (What is it)

Answer 14

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

Question 15

The banker’s algorithm: (How it works)

Answer 15

1- Given a resource request in a state s, temporarily grants the request by changing the request edges to allocation edges.
2- Execute a graph reduction on the new state s’. (Claim edges are treated as request edges.)
3- 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.

Question 16

Single-unit resources

Answer 16

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

Question 17

Simplified banker’s algorithm

Answer 17

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, determine if the graph in the temporarily 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 18

First condition for a deadlock to occur

Answer 18

Hold and wait: A process is already holding one resource and is requesting another resource.

Question 19

Second condition for a deadlock to occur

Answer 19

Circular wait: A process must issue a resource request that closes a cycle involving at least two processes and two resources.

Both conditions must hold for a deadlock to occur.

Question 20

Eliminating hold and wait

Answer 20

There are several alternatives to eliminating the hold and wait condition:

1- Every process must request all resources ever needed at the same time.

2- Every process must release all currently held resources prior to making any new request.

3- A process can be given the ability to test whether a needed resource is currently available.

Question 21

Eliminating circular wait

Answer 21

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

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