8.
6 Deadlock Avoidance 335
• Max. An n × m matrix defines the maximum demand of each thread.
If Max[i][j] equals k, then thread Ti 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 thread. If Allocation[i][j] equals k, then thread
Ti is currently allocated k instances of resource type Rj .
• Need. An n × m matrix indicates the remaining resource need of each
thread. If Need[i][j] equals k, then thread Ti may need k more instances of
resource type Rj to complete its task. Note that Need[i][j] equals Max[i][j]
− Allocation[i][j].
These data structures vary over time in both size and value.
To simplify the presentation of the banker’s algorithm, we next establish
some notation. Let X and Y be vectors of length n. We say that X ≤ Y if and only
if X[i] ≤ Y[i] for all i = 1, 2, ..., n. For example, if X = (1,7,3,2) and Y = (0,3,2,1),
then Y ≤ X. In addition, Y < X if Y ≤ X and Y ≠ X.
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 thread Ti ; the vector Needi specifies the
additional resources that thread Ti may still request to complete its task.
[Link] 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:
1. 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.
2. 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.
4. 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.
[Link] Resource-Request Algorithm
Next, we describe the algorithm for determining whether requests can be
safely granted. Let Requesti be the request vector for thread Ti . If Requesti
[j] == k, then thread Ti wants k instances of resource type Rj . When a request
for resources is made by thread Ti , the following actions are taken:
336 Chapter 8 Deadlocks
1. If Requesti ≤ Needi , go to step 2. Otherwise, raise an error condition, since
the thread has exceeded its maximum claim.
2. If Requesti ≤ Available, go to step 3. Otherwise, Ti must wait, since the
resources are not available.
3. Have the system pretend to have allocated the requested resources to
thread Ti 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 com-
pleted, and thread Ti is allocated its resources. However, if the new state
is unsafe, then Ti must wait for Requesti , and the old resource-allocation
state is restored.
[Link] An Illustrative Example
To illustrate the use of the banker’s algorithm, consider a system with five
threads T0 through T4 and three resource types A, B, and C. Resource type A
has ten instances, resource type B has five instances, and resource type C has
seven instances. Suppose that the following snapshot represents the current
state of the system:
Allocation Max Available
ABC ABC ABC
T0 010 753 332
T1 200 322
T2 302 902
T3 211 222
T4 002 433
The content of the matrix Need is defined to be Max − Allocation and is as
follows:
Need
ABC
T0 743
T1 122
T2 600
T3 011
T4 431
We claim that the system is currently in a safe state. Indeed, the sequence
<T1 , T3 , T4 , T2 , T0 > satisfies the safety criteria. Suppose now that thread
T1 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