DEADLOCK NOTES
Compiled by N. Guydosh
CS 350 – Fall 2003, 10/22/03
Introduction
Note to Fall 2002 students: These notes were intended and used during a past course in which Stallings book was used. They were intended as a supplement and clarification to the more difficult treatment given in Stallings book. These notes also serve as a clarification, supplement, and summary to the material in Chapter 8 of Silberschatz’s book (6th ed.) and are considered required reading for Fall 2002.
These notes will focus on the methods and algorithms used in dealing with deadlock. For an introduction to the basic concepts and theory of deadlock, see section 6.1 of Stallings text and the first 16 slides of Roy’s PowerPoint slides (used in class)*. The material in these notes is largely (but not entirely) based on “Operating System Concepts”, 5th edition, by Silberschatz and Galvin. (referred to as Silber below). Silberschatz’s book was given emphasis because in the instructor’s opinion, the material on Deadlock in Sillberschatz’s book is significantly more clear and simple than the corresponding material in Stallings. But it is pointed out that both books are consistent with each other and use the same basic approaches to this topic.
* For users of Stallings book only.
Conditions for Deadlock:
Deadlock can occur if the following four conditions hold simultaneously:
1. Mutual exclusion: Only one process at a time can hold the resource.
2. Hold and wait: A process is holding at least one resource that is needed along with resources to proceed. The process waits for the other required resources to be released by other processes holding them.
3. No preemption: Resources cannot be preempted. Resources can be released only voluntarily by the process holding it after the process is finished with it.
4. Circular wait: A set of waiting processes {P1, P2, …, Pn}must exist, such that, P0 waits 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.
These four conditions are not independent. The first three are necessary condition, and the fourth is necessary and sufficient. The fourth condition incorporates the first three.
Deadlock Prevention
Make it impossible to happen:
Indirect method: disallow one the three necessary conditions for deadlock.
Direct method: disallow circular wait, the fourth condition which is necessary and sufficient
Disallow mutual exclusion: cannot be used because it generally is a functional requirement
Disallow Hold and wait: require that a process request all of its required resources at one time and blocking the process until all requests can be granted simultaneously. This method is inefficient: a process may be held up a long time waiting for all its resources (starvation possible). Resource utilization may be low – allocated resources may go unused.
Disallow “No preemption”: If a process holding certain resources is denied a further request, that process must release its original resources and try again later.
also:
if a process requests a resources that is currently held by another process, the OS may preempt the second process and require it to release its resources.
Disallow Circular Wait: Associate an index with each resource type and make the indices strictly monotonically increasing. The process must access these resources in the order of the sequence. Example, Suppose process P1 and P2 are deadlocked because P1 has acquired B with index i and requested A with index j, and P2 has acquired A with index j and requested B with index i, then this would be a contradiction since it would imply that i < j and j < i. Thus, the deadlock could not happen. This approach may be inefficient:
Resource-Allocation State – A basic concept
Definition: A resource type is a set of n resources of the same type, ie., the resources in a resource type are equivalent, and can be used interchangeably. Each resource is an instantiation of he resource type it is in.
Definition: The Resource Allocation State of a system is the current resource allocation and resource requirement status of each process.
Let n = number of processes
m = number of resource types
This state is specified by three data structures:
Available: A vector of length m giving the number of resources currently available for each type. Example: available[3] is the number of available instances of resource type 3. It takes into account the number of resources currently allocated.
Available = total resources of each type - amount allocated of each type
Available[j] = k means that there are k instances of resource Rj available.
Example (Resource types are A, B, C) :
A | B | C _
|2_|_4_|_1_|
MAX matrix: An n x m matrix which defines the maximum demand of each process . If MAX[i,j] = k then Pi may request at most k instances of resource type Rj .
Notation: this matrix is called “Claim” in Stallings’s book.
Example (Resource types are A, B, C and three processes: p1, p2, p3):
A | B | C
p1 2_|_3_| 2_
p2 4_|_2_|_4_
p3 0_|_1_|_1_
Allocation matrix: An n x m matrix which defines the number of resources of each type currently allocated to each process.
Allocation[i,j] = k means that process Pi is currently allocated k instances of resource
type Rj .
Example:
A | B | C
p1 2_|_0_| 1_
p2 1_|_1_|_3_
p3 0_|_0_|_1_
SUMS 3 | 1 | 5 <== total-allocate for each resource type
· Deadlock Avoidance
Allow deadlock to occur, but provide a means to avoid it – live with it without getting deadlocked.
Resource types and resource instances: A resource type is a set of n identical system resources of a specified type. For example, five tape units, which are functionally equivalent. A process, P1, makes a request for some number of instances of this resource, for example process a wants two of the tape drives. If all instances are already claimed, P1 must wait.
Deadlock prevention generally results in low device utilization and reduced cystem throughput. See deadlock prevention notes ... An improvement is Deadlock Avoidance.
Each process must declare some additional a priori information about its resources requirements:
- Each process declares the maximum number of resources of each type that it may need.
- Safe State:
A resource allocation state is safe if the system can allocate resources to each process (up to its maximum ) in some order and still avoid deadlock.
Or
A system is in a safe state only if there exists a safe sequence. A sequence of processes <P1, P2, . . ., Pn> is in a safe sequence for the current allocation state if, for each Pi , the resources that Pi can still request, can be satisfied by the currently available resources + the resources held by all the Pj with j < i. If no such sequence exists, then the system state is said to be unsafe.
If the resources that Pi needs are not immediately available, then Pi can wait until all Pj have finished thus releasing the resources needed by Pi .
A safe state can never be a deadlock state
Not all unsafe states are deadlocks ... but an unsafe state may lead to a deadlock.
See diagram below:
from Silberschatz, fig. 7.4, p. 218
Chapter 8 Deadlock CS350 Page 1
- Before proceeding to the avoidance algorithm called the “Banker’s Algorithm”, we define two useful matrices derived from the resource-allocation state. They are the “need matrix” and the “Total Resource Vector” or TRV.
Need Matrix: An n x m matrix which indicates the remaining resources needed by each process to complete.
Need[i,j] = k means that Pi may need k more instances of resource type Rj .
Note that: Need[i,j] = MAX[i,j] - allocation[i,j].
An example of the need matrix based on our example above (from p. 4) is:
A | B | C
p1 0_|_3_| 1_
p2 3_|_1 |_1_
p3 0_|_1_|_0
Total Resource Vector (TRV): an m element vector giving the total amount of each resource belonging to the system, or the available resources before anything is allocated to any process.
An example of the TRV vector based on our example above is:
TRV = available + total allocated
= [2, 4, 1] + [3, 1, 5] = [5, 5, 6],
ie., 5 units of A, 5 units of B, and 6 units of C.
- Bankers Algorithm
Allows multiple instances per resource type.
- Lemma: Safety Algorithm (part of the bankers Algorithm):
Let m = number of resource types, and n = number of processes
1. Let work and finish be vectors of length m and n respectively.
Initialize: work = available, and finish = all zeros for i = 1, 2, ..., n.
… Think of the work vector as a “dynamic available vector”.
2. Find an i such that both
Finish[i] == 0 AND
Needi <= work. (Needi is the ith row of need[i,j].)
If no such i exists goto step 4
3. Work = work + allocationi ,
where allocationi is the ith row if allocation[i,j]
Finish[i] = 1
Goto step 2
4. If finish[i] = 1 for all i, then the system is in a safe state.
else not safe.
Notation: X and Y are vectors of length n. Then X £ Y iff X[i] £ Y[i] for all i=1, ... n. Else X > Y
Chapter 8 Deadlock CS350 Page 1
- Banker’s Algorithm (or Resource-Request Algorithm) – the “main” 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 Pi , the following actions are taken:
1. If requesti £ needi (the old or original needi), goto step 2. Otherwise, raise an error condition, since the process has exceeded its maximum claim
2. If requesti £ available (ie., old or original available), goto step 3. Otherwise, Pi must wait , since the resources are not available. .... all must be available to go on.
3. Have the system pretend to have allocated the requested resources to Pi by modifying the state as follows:
Available = available - requesti;
Allocationi = allocationi + requesti;
Needi = needi - requesti;
Now using the safety algorithm, check the “new” state for safety. If the resulting resource-allocation state is safe, the transaction is completed and process Pi is allocated its resources. If the new state is unsafe, then Pi must wait for requesti and the old resource- allocation state is restored.
NOTE that steps 1 and 2 are a preliminary “sanity” or consistency check, and not part of the main “loop”
Example (next page):
Chapter 8 Deadlock CS350 Page 1
Banker’s Algorithm - Example
CS 350, 03/29/99
Given: 5 processes: p0, p1, p2, p3, p4
3 resource types: A, B, C
A has 10 instances
B has 5 instances
C has 7 instances
Total Resource Vector = TRV = [10, 5, 7]
Resource-Allocation State:
MAX - Allocation =
Process Allocation MAX Available Need
ABC ABC ABC ABC
p0 0 1 0 7 5 3 3 3 2 7 4 3
p1 2 0 0 3 2 2 = [10, 5, 7] - [7, 2, 5] 1 2 2
p2 3 0 2 9 0 2 6 0 0
p3 2 1 1 2 2 2 0 1 1
p4 0 0 2 4 3 3 4 3 1
------
Total Alloc: 7 2 5
Show that this is a Safe State using the safety algorithm:
Initialization:
work = available = [3 3 2]
finish = 0 0 0 0 0
Notation: “>” means “NOT <=”
Search for a safe sequence:
p0: need0 = 7 4 3 > work = 3 3 2, doesn’t work - try later, finish = 0 0 0 0 0
p1: need1 = 1 2 2 <= work = 3 3 2, finish = 0 1 0 0 0, work = 3 3 2 + 2 0 0 = 5 3 2
p2: need2 = 6 0 0 > work = 5 3 2, doesn’t work - try later, finish = 0 1 0 0 0
p3: need3 = 0 1 1 <= work = 5 3 2, finish = 0 1 0 1 0, work = 5 3 2 + 2 1 1 = 7 4 3
p4: need4 = 4 3 1 <= work = 7 4 3, finish = 0 1 0 1 1, work = 7 4 3 + 0 0 2 = 7 4 5
p2: need2 = 6 0 0 <= work = 7 4 5, finish = 0 1 1 1 1, work = 7 4 5 + 3 0 2 = 10, 4, 7
p0: need0 = 7 4 3 <= work = 10,4,7 finish = 1 1 1 1 1, work = 10 4 7 + 0 1 0 = 10, 5, 7
State is Safe:
sequence is <p1, p3, p4, p2, p0>
Solution is not unique:
Alternate Safe Sequence: <p1, p3, p4, p0, p2> ... reverse p0 and p2
Chapter 8 Deadlock CS350 Page 1
The Bankers Algorithm (putting it all together):
Assume the resource-allocation state of the previous example.
Suppose p1 requests one additional instance of resource type A and two instances of type C.
Thus request1 = [1 0 2]
Application of the steps of the algorithm:
1. Request1 = 1 0 2 <= need1 = 1 2 2, “Sanity” check
2. Request1 = 1 0 2 <= available = 3 3 2, “Sanity check”
3. Pretend to make the allocation and check to see if new state is safe:
The changes are:
allocation1 = 2 0 0 + 1 0 2 = 3 0 2
need 1 = 1 2 2 - 1 0 2 = 0 2 0
available = 3 3 2 - 1 0 2 = 2 3 0
The “new” resource allocation state is now (changes indicated by “==>”):
MAX - Allocation =
Process Allocation MAX Available Need
ABC ABC ABC ABC
p0 0 1 0 7 5 3 ==>2 3 0 7 4 3
p1 3 0 2 <== 3 2 2 ==>0 2 0
p2 3 0 2 9 0 2 6 0 0
p3 2 1 1 2 2 2 0 1 1