2 of 57

Chapter 7: Deadlocks

System Model
Deadlock Characterization
Methods for Handling Deadlocks
Deadlock Prevention
Deadlock Avoidance
Deadlock Detection
Recovery from Deadlock

7.2

Operating System Concepts – 9^th Edition

3 of 57

Deadlocks

In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources; if the resources are not available at that time, the process enters a waiting state. Sometimes, a waiting process is never again able to change state, because the resources it has requested are held by other waiting processes. This situation is called a deadlock.

7.3

Operating System Concepts – 9^th Edition

4 of 57

System Model

A system consists of a finite number of resources to be distributed among a number of competing processes. The resources may be partitioned into several types (or classes), each consisting of some number of identical instances. CPU cycles, files, and I/O devices (such as printers and DVD drives) are examples of resource types.
If a system has two CPUs, then the resource type CPU has two instances.
A process must request a resource before using it and must release the resource after using it. A process may request as many resources as it requires to carry out its designated task. Obviously, the number of resources requested may not exceed the total number of resources available in the system. In other words, a process cannot request three printers if the system has only two.

7.4

Operating System Concepts – 9^th Edition

5 of 57

System Model

Under the normal mode of operation, a process may utilize a resource in only the following sequence:
Request. The process requests the resource. If the request cannot be granted immediately (for example, if the resource is being used by another process), then the requesting process must wait until it can acquire the resource.
Use. The process can operate on the resource (for example, if the resource is a printer, the process can print on the printer).
Release. The process releases the resource.
A system table records whether each resource is free or allocated. For each resource that is allocated, the table also records the process to which it is allocated. If a process requests a resource that is currently allocated to another process, it can be added to a queue of processes waiting for this resource.

7.5

Operating System Concepts – 9^th Edition

6 of 57

Deadlock Characterization

In a deadlock, processes never finish executing, and system resources are tied up, preventing other jobs from starting.

Necessary Conditions

A deadlock situation can arise if the following four conditions hold simultaneously in a system:
Mutual exclusion. At least one resource must be held in a non sharable mode; that is, only one process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released.
Hold and wait. A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
No preemption. Resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task.

7.6

Operating System Concepts – 9^th Edition

7 of 57

Deadlock Characterization

4. Circular wait. A set {P0, P1, ..., Pn} of waiting processes must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, ..., Pn−1 is waiting for a resource held by Pn, and Pn is waiting for a resource held by P0.

We emphasize that all four conditions must hold for a deadlock to occur. The circular-wait condition implies the hold-and-wait condition, so the four conditions are not completely independent.

7.7

Operating System Concepts – 9^th Edition

8 of 57

Resource-Allocation Graph

Deadlocks can be described more precisely in terms of a directed graph called a system resource-allocation graph.
This graph consists of a set of vertices V and a set of edges E. The set of vertices V is partitioned into two different types of nodes: P = {P1, P2, ..., Pn}, the set consisting of all the active processes in the system, and R = {R1, R2, ..., Rm}, the set consisting of all resource types in the system.
A directed edge from process Pi to resource type Rj is denoted by Pi → Rj ; it signifies that process Pi has requested an instance of resource type Rj and is currently waiting for that resource. A directed edge from resource type Rj to process Pi is denoted by Rj → Pi ; it signifies that an instance of resource type Rj has been allocated to process Pi . A directed edge Pi → Rj is called a request edge; a directed edge Rj → Pi is called an assignment edge.

7.8

Operating System Concepts – 9^th Edition

9 of 57

Resource-Allocation Graph

Pictorially, we represent each process Pi as a circle and each resource type Rj as a rectangle. Since resource type Rj may have more than one instance, we represent each such instance as a dot within the rectangle.
Note that a request edge points to only the rectangle Rj , whereas an assignment edge must also designate one of the dots in the rectangle.
When process Pi requests an instance of resource type Rj , a request edge is inserted in the resource-allocation graph. When this request can be fulfilled, the request edge is instantaneously transformed to an assignment edge. When the process no longer needs access to the resource, it releases the resource. As a result, the assignment edge is deleted.
The resource-allocation graph shown in Figure depicts the following situation.

7.9

Operating System Concepts – 9^th Edition

10 of 57

Resource-Allocation Graph (Cont.)

Process��
Resource Type with 4 instances

P_i requests instance of R_j

P_i is holding an instance of R_j

P_i

R_j

7.10

Operating System Concepts – 9^th Edition

11 of 57

Example of a Resource Allocation Graph

Figure: Resource-allocation graph.

7.11

Operating System Concepts – 9^th Edition

12 of 57

Resource-Allocation Graph

The sets P, R, and E:

P = {P1, P2, P3}
R = {R1, R2, R3, R4}
E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3}

Resource instances:

One instance of resource type R1
Two instances of resource type R2
One instance of resource type R3
Three instances of resource type R4

Process states:

Process P1 is holding an instance of resource type R2 and is waiting for an instance of resource type R1.
Process P2 is holding an instance of R1 and an instance of R2 and is waiting for an instance of R3.
Process P3 is holding an instance of R3.

7.12

Operating System Concepts – 9^th Edition

13 of 57

Resource-Allocation Graph

Given the definition of a resource-allocation graph, it can be shown that, if the graph contains no cycles, then no process in the system is deadlocked. If the graph does contain a cycle, then a deadlock may exist.
If each resource type has exactly one instance, then a cycle implies that a deadlock has occurred. If the cycle involves only a set of resource types, each of which has only a single instance, then a deadlock has occurred.
Each process involved in the cycle is deadlocked. In this case, a cycle in the graph is both a necessary and a sufficient condition for the existence of deadlock.
If each resource type has several instances, then a cycle does not necessarily imply that a deadlock has occurred. In this case, a cycle in the graph is a necessary but not a sufficient condition for the existence of deadlock.

7.13

Operating System Concepts – 9^th Edition

14 of 57

Resource-Allocation Graph

To illustrate this concept, we return to the resource-allocation graph depicted in Figure 7.1. Suppose that process P3 requests an instance of resource type R2.
Since no resource instance is currently available, we add a request edge P3→ R2 to the graph (Figure 7.2). At this point, two minimal cycles exist in the system:
P1 → R1 → P2 → R3 → P3 → R2 → P1
P2 → R3 → P3 → R2 → P2
Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which is held by process P3. Process P3 is waiting for either process P1 or process P2 to release resource R2. In addition, process P1 is waiting for process P2 to release resource R1.

7.14

Operating System Concepts – 9^th Edition

15 of 57

Resource Allocation Graph With A Deadlock

Figure 7.2 Resource-allocation graph with a deadlock.

7.15

Operating System Concepts – 9^th Edition

16 of 57

Resource-Allocation Graph

Now consider the resource-allocation graph in Figure 7.3. In this example, we also have a cycle:
P1 → R1 → P3 → R2 → P1
However, there is no deadlock. Observe that process P4 may release its instance of resource type R2. That resource can then be allocated to P3, breaking the cycle.
In summary, if a resource-allocation graph does not have a cycle, then the system is not in a deadlocked state. If there is a cycle, then the system may or may not be in a deadlocked state.
This observation is important when we deal with the deadlock problem.

7.16

Operating System Concepts – 9^th Edition

17 of 57

Graph With A Cycle But No Deadlock

Figure 7.3 Resource-allocation graph with a cycle but no deadlock.

7.17

Operating System Concepts – 9^th Edition

18 of 57

Methods for Handling Deadlocks

Generally speaking, we can deal with the deadlock problem in one of three ways:
We can use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlocked state.
We can allow the system to enter a deadlocked state, detect it, and recover.
We can ignore the problem altogether and pretend that deadlocks never occur in the system.
The third solution is the one used by most operating systems, including Linux and Windows.
To ensure that deadlocks never occur, the system can use either a deadlock prevention or a deadlock-avoidance scheme.
Deadlock prevention provides a set of methods to ensure that at least one of the necessary conditions cannot hold. These methods prevent deadlocks by constraining how requests for resources can be made.

7.18

Operating System Concepts – 9^th Edition

19 of 57

Methods for Handling Deadlocks

Deadlock avoidance requires that the operating system be given additional information in advance concerning which resources a process will request and use during its lifetime.
With this additional knowledge, the operating system can decide for each request whether or not the process should wait.
To decide whether the current request can be satisfied or must be delayed, the system must consider the resources currently available, the resources currently allocated to each process, and the future requests and releases of each process.
If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm, then a deadlock situation may arise.
In this environment, the system can provide an algorithm that examines the state of the system to determine whether a deadlock has occurred and an algorithm to recover from the deadlock

7.19

Operating System Concepts – 9^th Edition

20 of 57

Deadlock Prevention

For a deadlock to occur, each of the four necessary conditions must hold. By ensuring that at least one of these conditions cannot hold, we can prevent the occurrence of a deadlock.

Mutual Exclusion

The mutual exclusion condition must hold. That is, at least one resource must be Non sharable. Sharable resources, in contrast, do not require mutually exclusive access and thus cannot be involved in a deadlock.
Read-only files are a good example of a sharable resource.
If several processes attempt to open a read-only file at the same time, they can be granted simultaneous access to the file.
A process never needs to wait for a sharable resource. In general, however, we cannot prevent deadlocks by denying the mutual-exclusion condition, because some resources are intrinsically non sharable.
For example, a mutex lock cannot be simultaneously shared by several processes.

7.20

Operating System Concepts – 9^th Edition

21 of 57

Deadlock Prevention (Cont.)

Hold and Wait

To ensure that the hold-and-wait condition never occurs in the system, we must guarantee that, whenever a process requests a resource, it does not hold any other resources.
One protocol that we can use requires each process to request and be allocated all its resources before it begins execution.
An alternative protocol allows a process to request resources only when it has none. A process may request some resources and use them. Before it can request any additional resources, it must release all the resources that it is currently allocated.
Both these protocols have two main disadvantages. First, resource utilization may be low, since resources may be allocated but unused for a long period.
Second, starvation is possible. A process that needs several popular resources may have to wait indefinitely, because at least one of the resources that it needs is always allocated to some other process.

7.21

Operating System Concepts – 9^th Edition

22 of 57

Deadlock Prevention (Cont.)

No Preemption

The third necessary condition for deadlocks is that there be no preemption of resources that have already been allocated. To ensure that this condition does not hold, we can use the following protocol.
If a process is holding some resources and requests another resource that cannot be immediately allocated to it (that is, the process must wait), then all resources the process is currently holding are preempted.
The preempted resources are added to the list of resources for which the process is waiting. The process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting.
Alternatively, if a process requests some resources, we first check whether they are available. If they are, we allocate them. If they are not, we check whether they are allocated to some other process that is waiting for additional resources. If so, we preempt the desired resources from the waiting process and allocate them to the requesting process.

7.22

Operating System Concepts – 9^th Edition

23 of 57

Deadlock Prevention (Cont.)

If the resources are neither available nor held by a waiting process, the requesting process must wait. While it is waiting, some of its resources may be preempted, but only if another process requests them.
A process can be restarted only when it is allocated the new resources it is requesting and recovers any resources that were preempted while it was waiting.

Circular Wait

The fourth and final condition for deadlocks is the circular-wait condition. One way to ensure that this condition never holds is to impose a total ordering of all resource types and to require that each process requests resources in an increasing order of enumeration.
To illustrate, we let R = {R1, R2, ..., Rm} be the set of resource types. We assign to each resource type a unique integer number, which allows us to compare two resources and to determine whether one precedes another in our ordering.

7.23

Operating System Concepts – 9^th Edition

24 of 57

Deadlock Prevention (Cont.)

Formally, we define a one-to-one function F: R→N, where N is the set of natural numbers. For example, if the set of resource types R includes tape drives, disk drives, and printers, then the function F might be defined as follows:
F(tape drive) = 1
F(disk drive) = 5
F(printer) = 12
We can now consider the following protocol to prevent deadlocks: Each process can request resources only in an increasing order of enumeration. That is, a process can initially request any number of instances of a resource type —say, Ri . After that, the process can request instances of resource type Rj if and only if F(Rj ) > F(Ri ).

7.24

Operating System Concepts – 9^th Edition

25 of 57

Deadlock Avoidance

Deadlock-prevention algorithms, prevent deadlocks by limiting how requests can be made. The limits ensure that at least one of the necessary conditions for deadlock cannot occur.
Possible side effects of preventing deadlocks by this method, however, are low device utilization and reduced system throughput.
An alternative method for avoiding deadlocks is to require additional information about how resources are to be requested.
For example, in a system with one tape drive and one printer, the system might need to know that process P will request first the tape drive and then the printer before releasing both resources, whereas process Q will request first the printer and then the tape drive.
With this knowledge of the complete sequence of requests and releases for each process, the system can decide for each request whether or not the process should wait in order to avoid a possible future deadlock.

7.25

Operating System Concepts – 9^th Edition

26 of 57

Deadlock Avoidance

Each request requires that in making this decision the system consider the resources currently available, the resources currently allocated to each process, and the future requests and releases of each process.
The simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need.
Given this a priori information, it is possible to construct an algorithm that ensures that the system will never enter a deadlocked state.
A deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that a circular-wait condition can never exist.
The resource allocation state is defined by the number of available and allocated resources and the maximum demands of the processes. We explore two deadlock-avoidance algorithms.

7.26

Operating System Concepts – 9^th Edition

27 of 57

Safe State

A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock. More formally, a system is in a safe state only if there exists a safe sequence.
A sequence of processes <P1, P2, ..., Pn> is a safe sequence for the current allocation state if, for each Pi , the resource requests that Pi can still make can be satisfied by the currently available resources plus the resources held by all Pj, with j < i.
In this situation, if the resources that Pi needs are not immediately available, then Pi can wait until all Pj have finished.
When they have finished, Pi can obtain all of its needed resources, complete its designated task, return its allocated resources, and terminate. When Pi terminates, Pi+1 can obtain its needed resources, and so on. If no such sequence exists, then the system state is said to be unsafe.

7.27

Operating System Concepts – 9^th Edition

28 of 57

Safe State

A safe state is not a deadlocked state. Conversely, a deadlocked state is an unsafe state.
An unsafe state may lead to a deadlock. As long as the state is safe, the operating system can avoid unsafe (and deadlocked) states. In an unsafe state, the operating system cannot prevent processes from requesting resources in such a way that a deadlock occurs.
Figure Safe, unsafe, and deadlocked state spaces.

7.28

Operating System Concepts – 9^th Edition

29 of 57

Safe State

To illustrate, we consider a system with twelve magnetic tape drives and three processes: P0, P1, and P2. Process P0 requires ten tape drives, process P1 may need as many as four tape drives, and process P2 may need up to nine tape drives.
Suppose that, at time t0, process P0 is holding five tape drives, process P1 is holding two tape drives, and process P2 is holding two tape drives. (Thus, there are three free tape drives.)

At time t0, the system is in a safe state. The sequence <P1, P0, P2> satisfies the safety condition.

Process	Maximum Needs	Current Needs
P1	10	5
P2	4	2
P3	9	2

7.29

Operating System Concepts – 9^th Edition

30 of 57

Safe State

Process P1 can immediately be allocated all its tape drives and then return them (the system will then have five available tape drives); then process P0 can get all its tape drives and return them (the system will then have ten available tape drives); and finally process P2 can get all its tape drives and return them (the system will then have all twelve tape drives available).

7.30

Operating System Concepts – 9^th Edition

31 of 57

Avoidance Algorithms

Single instance of a resource type

Use a resource-allocation graph

Multiple instances of a resource type

Use the banker’s algorithm

7.31

Operating System Concepts – 9^th Edition

32 of 57

Resource-Allocation-Graph Algorithm

In addition to the request and assignment edges already described, we introduce a new type of edge, called a claim edge.
A claim edge Pi → Rj indicates that process Pi may request resource Rj at some time in the future. This edge resembles a request edge in direction but is represented in the graph by a dashed line.
When process Pi requests resource Rj , the claim edge Pi → Rj is converted to a request edge.
Before process Pi starts executing, all its claim edges must already appear in the resource-allocation graph.
We can relax this condition by allowing a claim edge Pi → Rj to be added to the graph only if all the edges associated with process Pi are claim edges.

7.32

Operating System Concepts – 9^th Edition

33 of 57

Resource-Allocation Graph

Figure 7.7 : Resource-allocation graph for deadlock avoidance.

7.33

Operating System Concepts – 9^th Edition

34 of 57

Resource-Allocation-Graph Algorithm

Now suppose that process Pi requests resource Rj. The request can be granted only if converting the request edge Pi → Rj to an assignment edge Rj → Pi does not result in the formation of a cycle in the resource-allocation graph.
We check for safety by using a cycle-detection algorithm. An algorithm for detecting a cycle in this graph requires an order of n2 operations, where n is the number of processes in the system.
If no cycle exists, then the allocation of the resource will leave the system in a safe state. If a cycle is found, then the allocation will put the system in an unsafe state. In that case, process Pi will have to wait for its requests to be satisfied.
To illustrate this algorithm, we consider the resource-allocation graph of Figure 7.7. Suppose that P2 requests R2. Although R2 is currently free, we cannot allocate it to P2, since this action will create a cycle in the graph (Figure 7.8). A cycle, as mentioned, indicates that the system is in an unsafe state. If P1 requests R2, and P2 requests R1, then a deadlock will occur.

7.34

Operating System Concepts – 9^th Edition

35 of 57

Unsafe State In Resource-Allocation Graph

Figure 7.8 An unsafe state in a resource-allocation graph.

7.35

Operating System Concepts – 9^th Edition

36 of 57

Banker’s Algorithm

The resource-allocation-graph algorithm is not applicable to a resource allocation system with multiple instances of each resource type. The deadlock avoidance algorithm that we describe next is applicable to such a system but is less efficient than the resource-allocation graph scheme.
This algorithm is commonly known as the banker’s algorithm. The name was chosen because the algorithm could be used in a banking system to ensure that the bank never allocated its available cash in such a way that it could no longer satisfy the needs of all its customers.
When a new process enters the system, it must declare the maximum number of instances of each resource type that it may need. This number may not exceed the total number of resources in the system.
When a user requests a set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state. If it will, the resources are allocated; otherwise, the process must wait until some other process releases enough resources.

7.36

Operating System Concepts – 9^th Edition

37 of 57

Data Structures for the Banker’s Algorithm

We need the following data structures, where n is the number of processes in the system and m is the number of resource types:
Available. A vector of length m indicates the number of available resources of each type. If Available[j] equals k, then k instances of resource type Rj are available.
Max. An n × m matrix defines the maximum demand of each process. If Max[i][j] equals k, then process Pi may request at most k instances of resource type Rj.
Allocation. An n × m matrix defines the number of resources of each type currently allocated to each process. If Allocation[i][j] equals k, then process Pi is currently allocated k instances of resource type Rj .
Need. An n × m matrix indicates the remaining resource need of each process. If Need[i][j] equals k, then process Pi may need k more instances of resource type Rj to complete its task. Note that Need[i][j] equalsMax[i][j] − Allocation[i][j].

7.37

Operating System Concepts – 9^th Edition

38 of 57

Data Structures for the Banker’s Algorithm

These data structures vary over time in both size and value.
We can treat each row in the matrices Allocation and Need as vectors and refer to them as Allocationi and Needi .
The vector Allocationi specifies the resources currently allocated to process Pi ; the vector Needi specifies the additional resources that process Pi may still request to complete its task.

7.38

Operating System Concepts – 9^th Edition

39 of 57

Safety Algorithm

We can now present the algorithm for finding out whether or not a system is in a safe state. This algorithm can be described as follows:
Let Work and Finish be vectors of length m and n, respectively. Initialize Work = Available and Finish[i] = false for i = 0, 1, ..., n − 1.
Find an index i such that both

a. Finish[i] == false

b. Needi ≤Work

If no such i exists, go to step 4.

3. Work =Work + Allocationi

Finish[i] = true

Go to step 2.

If Finish[i] == true for all i, then the system is in a safe state.
This algorithm may require an order of m × n2 operations to determine whether a state is safe.

7.39

Operating System Concepts – 9^th Edition

40 of 57

Resource-Request Algorithm

Let Requesti be the request vector for process Pi . If Requesti [ j] == k, then process Pi wants k instances of resource type Rj .
When a request for resources is made by process Pi , the following actions are taken:
If Requesti ≤Needi , go to step 2. Otherwise, raise an error condition, since the process has exceeded its maximum claim.
If Requesti ≤ Available, go to step 3. Otherwise, Pi must wait, since the resources are not available.
Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows:

Available = Available–Requesti ;

Allocationi = Allocationi + Requesti ;

Needi = Needi –Requesti ;

If the resulting resource-allocation state is safe, the transaction is completed, and process Pi is allocated its resources. However, if the new state is unsafe, then Pi must wait for Requesti , and the old resource-allocation state is restored.

7.40

Operating System Concepts – 9^th Edition

41 of 57

Example of Banker’s Algorithm

5 processes P₀through P₄;

3 resource types:

A (10 instances), B (5instances), and C (7 instances)

Snapshot at time T₀:

Allocation Max Available

A B C A B C A B C

P₀0 1 0 7 5 3 3 3 2

P₁2 0 0 3 2 2

P₂ 3 0 2 9 0 2

P₃ 2 1 1 2 2 2

P₄ 0 0 2 4 3 3

7.41

Operating System Concepts – 9^th Edition

42 of 57

Example (Cont.)

The content of the matrix Need is defined to be Max – Allocation.

Need

A B C

P₀7 4 3

P₁1 2 2

P₂ 6 0 0

P₃ 0 1 1

P₄ 4 3 1 �

The system is in a safe state since the sequence < P₁, P₃, P₄, P₂, P₀> satisfies safety criteria.
Suppose now that process P1 requests one additional instance of resource type A and two instances of resource type C, so Request1 = (1,0,2). To decide whether this request can be immediately granted, we first check that Request1 ≤ Available—that is, that (1,0,2) ≤ (3,3,2), which is true. We then pretend that this request has been fulfilled, and we arrive at the following new state:

7.42

Operating System Concepts – 9^th Edition

43 of 57

Example: P₁ Request (1,0,2)

Check that Request ≤ Available (that is, (1,0,2) ≤ (3,3,2) ⇒ true

Allocation Need Available

A B C A B C A B C

P₀ 0 1 0 7 4 3 2 3 0

P₁ 3 0 2 0 2 0

P₂ 3 0 2 6 0 0

P₃ 2 1 1 0 1 1

P₄ 0 0 2 4 3 1

Executing safety algorithm shows that sequence < P₁, P₃, P₄, P₀, P₂> satisfies safety requirement.
Hence, we can immediately grant the request of process P1.
You should be able to see, however, that when the system is in this state, a request for (3,3,0) by P4 cannot be granted, since the resources are not available. Furthermore, a request for (0,2,0) by P0 cannot be granted, even though the resources are available, since the resulting state is unsafe.

7.43

Operating System Concepts – 9^th Edition

44 of 57

Example (Cont.)

7.44

Operating System Concepts – 9^th Edition

45 of 57

Deadlock Detection

If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm, then a deadlock situation may occur. In this environment, the system may provide:
An algorithm that examines the state of the system to determine whether a deadlock has occurred.
An algorithm to recover from the deadlock.
We elaborate on these two requirements as they pertain to systems with only a single instance of each resource type, as well as to systems with several instances of each resource type.

7.45

Operating System Concepts – 9^th Edition

46 of 57

Single Instance of Each Resource Type

If all resources have only a single instance, then we can define a deadlock detection algorithm that uses a variant of the resource-allocation graph, called a wait-for graph. We obtain this graph from the resource-allocation graph by removing the resource nodes and collapsing the appropriate edges.
More precisely, an edge from Pi to Pj in a wait-for graph implies that process Pi is waiting for process Pj to release a resource that Pi needs. An edge Pi → Pj exists in a wait-for graph if and only if the corresponding resource allocation graph contains two edges Pi → Rq and Rq → Pj for some resource Rq . In Figure 7.9, we present a resource-allocation graph and the corresponding wait-for graph.
As before, a deadlock exists in the system if and only if the wait-for graph contains a cycle. To detect deadlocks, the system needs to maintain the wait for graph and periodically invoke an algorithm that searches for a cycle in the graph. An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in the graph.

7.46

Operating System Concepts – 9^th Edition

47 of 57

Resource-Allocation Graph and Wait-for Graph

Figure 7.9 (a) Resource-allocation graph. (b) Corresponding wait-for graph.

7.47

Operating System Concepts – 9^th Edition

48 of 57

Several Instances of a Resource Type

The wait-for graph scheme is not applicable to a resource-allocation system with multiple instances of each resource type.
The algorithm employs several time-varying data structures that are similar to those used in the banker’s algorithm.
Available. A vector of length m indicates the number of available resources of each type.
Allocation. An n × m matrix defines the number of resources of each type currently allocated to each process.
Request. An n × m matrix indicates the current request of each process. If Request[i][j] equals k, then process Pi is requesting k more instances of resource type Rj .
Compare this algorithm with the banker’s algorithm.

7.48

Operating System Concepts – 9^th Edition

49 of 57

Detection Algorithm

Let Work and Finish be vectors of length m and n, respectively. Initialize Work = Available. For i = 0, 1, ..., n–1, if Allocationi = 0, then Finish[i] = false. Otherwise, Finish[i] = true.
Find an index i such that both

a. Finish[i] == false

b. Requesti ≤Work

If no such i exists, go to step 4.

3. Work =Work + Allocationi

Finish[i] = true

Go to step 2.

If Finish[i] ==false for some i, 0≤i<n, then the system is in a deadlocked state.

Moreover, if Finish[i] == false, then process Pi is deadlocked.

This algorithm requires an order of m × n2 operations to detect whether the system is in a deadlocked state.

7.49

Operating System Concepts – 9^th Edition

50 of 57

Example of Detection Algorithm

Five processes P₀ through P₄;three resource types �A (7 instances), B (2 instances), and C (6 instances)
Snapshot at time T₀:

Allocation Request Available

A B C A B C A B C

P₀ 0 1 0 0 0 0 0 0 0

P₁ 2 0 0 2 0 2

P₂ 3 0 3 0 0 0

P₃ 2 1 1 1 0 0

P₄ 0 0 2 0 0 2

We claim that the system is not in a deadlocked state. Indeed, if we execute our algorithm, we will find that the sequence <P0, P2, P3, P1, P4> results in Finish[i] == true for all i.

7.50

Operating System Concepts – 9^th Edition

51 of 57

Example (Cont.)

Suppose now that process P2 makes one additional request for an instance of type C. The Request matrix is modified as follows: Request

A B C

P₀ 0 0 0

P₁ 2 0 2

P₂ 0 0 1

P₃ 1 0 0

P₄ 0 0 2

We claim that the system is now deadlocked. Although we can reclaim the resources held by process P0, the number of available resources is not sufficient to fulfill the requests of the other processes. Thus, a deadlock exists, consisting of processes P1, P2, P3, and P4.

7.51

Operating System Concepts – 9^th Edition

52 of 57

Detection-Algorithm Usage

When should we invoke the detection algorithm? The answer depends on two factors:
How often is a deadlock likely to occur?
How many processes will be affected by deadlock when it happens?
If deadlocks occur frequently, then the detection algorithm should be invoked frequently. Resources allocated to deadlocked processes will be idle until the deadlock can be broken. In addition, the number of processes involved in the deadlock cycle may grow.
Deadlocks occur only when some process makes a request that cannot be granted immediately. This request may be the final request that completes a chain of waiting processes.
In the extreme, then, we can invoke the deadlock detection algorithm every time a request for allocation cannot be granted immediately.

7.52

Operating System Concepts – 9^th Edition

53 of 57

Recovery from Deadlock: Process Termination

When a detection algorithm determines that a deadlock exists, several alternatives are available.
One possibility is to inform the operator that a deadlock has occurred and to let the operator deal with the deadlock manually.
Another possibility is to let the system recover from the deadlock automatically.
There are two options for breaking a deadlock. One is simply to abort one or more processes to break the circular wait. The other is to preempt some resources from one or more of the deadlocked processes.

Process Termination

To eliminate deadlocks by aborting a process, we use one of two methods. In both methods, the system reclaims all resources allocated to the terminated processes.

7.53

Operating System Concepts – 9^th Edition

54 of 57

Recovery from Deadlock: Process Termination

Abort all deadlocked processes. This method clearly will break the deadlock cycle, but at great expense. (The deadlocked processes may have computed for a long time.)
Abort one process at a time until the deadlock cycle is eliminated. This method incurs considerable overhead, since after each process is aborted, a deadlock-detection algorithm must be invoked to determine whether any processes are still deadlocked.
Aborting a process may not be easy. If the process was in the midst of updating a file, terminating it will leave that file in an incorrect state.
Similarly, if the process was in the midst of printing data on a printer, the system must reset the printer to a correct state before printing the next job.
we should abort those processes whose termination will incur the minimum cost.
Many factors may affect which process is chosen, including:

7.54

Operating System Concepts – 9^th Edition

55 of 57

Recovery from Deadlock: Process Termination

What the priority of the process is
How long the process has computed and how much longer the process will compute before completing its designated task
How many and what types of resources the process has used(for example, whether the resources are simple to preempt)
How many more resources the process needs in order to complete
How many processes will need to be terminated
Whether the process is interactive or batch

7.55

Operating System Concepts – 9^th Edition

56 of 57

Recovery from Deadlock: Resource Preemption

To eliminate deadlocks using resource preemption, we successively preempt some resources from processes and give these resources to other processes until the deadlock cycle is broken.
If preemption is required to deal with deadlocks, then three issues need to be addressed:
Selecting a victim. Which resources and which processes are to be preempted? Cost factors may include such parameters as the number of resources a deadlocked process is holding and the amount of time the process has thus far consumed.
Rollback. If we preempt a resource from a process, what should be done with that process? We must roll back the process to some safe state and restart it from that state.
Starvation. How do we ensure that starvation will not occur? That is, how can we guarantee that resources will not always be preempted from the same process?

7.56

Operating System Concepts – 9^th Edition

1 of 57

2 of 57

3 of 57

4 of 57

5 of 57

6 of 57

7 of 57

8 of 57

9 of 57

10 of 57

11 of 57

12 of 57

13 of 57

14 of 57

15 of 57

16 of 57

17 of 57

18 of 57

19 of 57

20 of 57

21 of 57

22 of 57

23 of 57

24 of 57

25 of 57

26 of 57

27 of 57

28 of 57

29 of 57

30 of 57

31 of 57

32 of 57

33 of 57

34 of 57

35 of 57

36 of 57

37 of 57

38 of 57

39 of 57

40 of 57

41 of 57

42 of 57

43 of 57

44 of 57

45 of 57

46 of 57

47 of 57

48 of 57

49 of 57

50 of 57

51 of 57

52 of 57

53 of 57

54 of 57

55 of 57

56 of 57

57 of 57