Claim edge หมายถึงความสัมพันธ์ใดระหว่าง process กับ resource

� A deadlock exists iff the wait-for graph contains a cycle.

� Cycles can be detected by O(n

2) algorithm.

� If deadlock does exist, it can be eliminated by selecting a single victim.

Deadlock avoidance (in reusable-resource systems):

Requires some additional information on resource requests�for example, we can require each process to declare the maximum amount of each resource that it will ever need.

The concept of a safe state is important. Here, a resource-allocation state consists of�

� the number of allocated and available resources, and

� the maximum claim (or maximum demands) of each process.

Outline for Lecture 13

I. Deadlock avoidance

A. Safe states
B. Algorithm for deciding
safety
C. Banker�s algorithm
D. Single instance of each resource type

II. Deadlock recovery

A. Combined approach
to deadlock handling

A state is safe if the system can�

� allocate resources to each process (up to its maximum), and

� still avoid a deadlock.

Example: Suppose the system has three processes p

1, p2, and p3, and twelve units of one resource (e.g., tape drives).

State 1: Process Allocated Maximum

Need

1 1 4

2 4 6

3 5 8

Available: 2

This state is safe, because requests of , , and can be satisfied, in that order.

State 2: Process Allocated Maximum

Need

1 8 10

2 2 5

3 1 3

Available: 1

This state is unsafe: regardless of which process is next granted the available drive, we can�t guarantee that all 3 processes will finish.

Notice that

It just implies that some unfortunate sequence of requests might lead unavoidably to deadlock.

"Unavoidably"

Þ we can�t avoid deadlock by choosing to delay some processes� resource requests.

To avoid entering an unsafe state, we must carefully consider resource requests before granting them. For example, suppose the system is in State I (safe state).

Now suppose p

3 requests and is granted an additional tape drive:

State 3: Process Allocated Maximum

Need

1 1 4

2 4 6

3 6 8

Available: 1

Why is this now an unsafe state?

Example:

Assume a maximum-claim reusable-resource system with four processes and three resource types. The maximum-claim matrix is given by

where Max

ij denotes the maximum claim of process i for resource j. The total number of units of each resource type is given by the vector (4 8 16). The allocation of resources is given by the matrix

where A

ij denotes the number of units of resource j that are currently allocated to process i.

Processes are numbered p

1 through p4, and resources are numbered r1 through r3.

Suppose process 1 requests 1 more unit of resource 1.

Then, after the allocation is made, the matrix A is

and the maximum-remaining demand matrix

The Avail vector is [0 5 7].

The state is unsafe, because the system cannot guarantee to meet the maximum demands of any process.

For example, if all of the processes request an extra unit of resource 1 before any process releases a resource 1, all the processes will be deadlocked.

They are not deadlocked now, because they might release their resources before demanding more.

Now, suppose process 4 requests 3 more units of resource 3.

The processes can finish in the order p

4, p2, p3, p1. To see this, note that after the allocation is made, the matrix A is

and the maximum-remaining demand matrix

The Avail vector is [1 5 4]. The remaining demand of p

4 is � Avail, so p4 may complete.

Now Avail is [1 5 10]. The remaining demand of p

2 is � Avail, so p2 may complete.

Now Avail is [3 5 11]. The remaining demand of p

3 is � Avail, so p3 may

Now Avail is [4 7 12]. The remaining demand of p

1 is � Avail, so p1 may complete. Thus the state is safe.

Algorithm for deadlock avoidance

(Banker�s algorithm): The deadlock-avoidance algorithm is very similar to the deadlock-detection algorithm, but it uses the processes� maximum claim rather than their current allocations.

Let us introduce a new kind of edge, a claim edge, represented by a dashed line. Like a request edge, a claim edge points from a process to a resource type.

� A claim edge indicates that a process p

i may request the resource rj some time in the future .

� All claim edges for p

i must be present before pi starts executing.

� Thus, a request edge (p

i, rj) may be added only if a claim edge

i, rj) is already present. A resource-allocation graph with claim edges is called a maximum-claim graph. It reflects the projected worst-case future state in resource allocation.

A state is safe iff its corresponding maximum-claim graph is deadlock free.

Whenever a process makes a request, the following algorithm is executed:

Algorithm: Deadlock avoidance (Banker�s algorithm).

1. Project the future state by changing the request edge to an assignment edge.

2. Construct the maximum-claim graph for this state and analyze it for deadlock. If deadlock would exist, defer the request. Otherwise grant the request.

Example:

Suppose we are given the following system. The process�s maximum claims are represented as a claim matrix C, where cij is the maximum claim of process pi for units of type rj.

Suppose p

1 requests one unit of r2. Can this request be granted? To see, "grant" the request, then construct the maximum-claim graph and see if it contains a deadlock:

Suppose that process p2 then requests a unit of r1. Can this request now be granted?

Single instance of each resource type

: The deadlock avoidance algorithm can require O(mn2) operations. If there is only one instance of each resource type, an O(mn ) algorithm can be devised.

Algorithm: Deadlock-avoidance with a single instance of each resource type.

� Assume we are given a maximum-claim graph.

� Then when a process makes a request, it can be granted only if converting the request edge (p

i, rj) to an assignment edge (rj, pi) does not create a cycle in the resource-allocation graph. (The detection of a cycle takes time O(mn).)

For example, in the diagram below, we cannot grant r

2 to p2. Why?

In general, deadlock avoidance is more expensive than deadlock detection:

� The algorithm must be executed for every request prior to granting it.

� It restricts resource utilization, so it may degrade system performance. (Assumes that the "worst-case" request sequence will come true.)

This is especially severe if the claims are not precisely known.

Deadlock recovery: Several methods can be used.

� Abort one or more processes to break the circular-wait condition.

Considerations: Priority, used computing time, expected remaining time, etc.

� Preempt resources from one or more processes.

� "Roll back" a process. Sometimes also called "checkpoint/restart." "Snapshots" of process state saved at periodic intervals, usually specified by the process itself. To break a deadlock,

° Process is aborted.

° Later resumed at the previous checkpoint.

Rarely used except for very long processes.

Also useful in dealing with system crashes.

In general, victims are selected for deadlock recovery on the basis of priority. May also depend on how "close" a process is to finishing.

Combined approach to deadlock handling:

� Order resource classes (not resource types), e.g.,

° Internal resources (resources used by operating system, including process-control blocks).

° Central memory.

° Peripherals (tape drives, printers, etc.).

° Swappable space (secondary storage required for process).

� If a deadlock does occur, it must involve only one class of resources. Strategy for recovery depends on which class is involved.