BIT 27 {1987h 290 305

DEADLOCK AVOIDANCE WITH A MODIFIED BANKER'S ALGORITHM * FERENC BELIK

Department of Computer Science, Lund University, Box 118, S-22l O0Lurid, Sweden

Abstract. There are three methods for handling deadlocks in resource allocation systems: deadlock prevention, deadlock avoidance and deadlock detection combined with recovery. Of these three methods deadlock avoidance is preferable in many cases but seldom used on account of its high cost. We present a simple modification of a known deadlock avoidance algorithm, the banker's algorithm, which has a running time O(mn2) in a system consisting of n processes and m different types of resources. Our modified algorithm gives an amortized worst case running time of O(mn) under certain likely conditions and in that way it can be considered a competitive method for handling deadlocks. At worst, our algorithm is twice as fast as the banker's algorithm,

CR categories: D,4.1. Keywords and phrases: resource allocation systems, deadlock avoidance.

Introduction.

There are three methods for dealing with the deadlock problem in resource allocation systems: deadlock prevention, deadlock avoidance and deadlock detection combined with recovery. Deadlock prevention restricts concurrency, while recovery from a deadlock may be quite dimcult and expensive. Deadlock avoidance provides full concurrency but is seldom used on account of its high cost. We present a simple modification of a known deadlock avoidance algorithm, the banker's algorithm. The bankers' algorithm was developed by Dijkstra [1], and was extended to multiple resource types by Haberman [2]. It provides full concurrency and its running time is O(mn2) in a system consisting of n processes and m different type of resources. An O(mn3/2) algorithm, employing a network technique, was presented by Kameda [3]. Our modification of the banker's algorithm limits the concurrency slightly but it gives an O(mn) amortized worst case running time under certain likely conditions, and in that way it can be considered a competitive method for handling deadlocks. At worst, our algorithm * This work was partly supported by The National Swedish Board for Technical Development (STUF) under contract number 85-3127. Received February 1987. Revised June 1987.

DEADLOCK AVOIDANCE WITH A MODIFIED BANKER'S ALGORITHM

291

is twice as fast as the banker's algorithm. In Section 2 we present the modified algorithm, in Section 3 we discuss the running time of the algorithm and in Section 4 we present some simulation results.

2. The modified banker's algorithm. The banker's algorithm (taken from [4]) and our modification of it are given in Appendix A and B, respectively. In this section we present our modification by an example, and in a theorem we prove that our modified algorithm works properly and give an example where it limits concurrency. To argue about the algorithms we need two definitions: DEFINITION. A sequence of processes (Pl, P2 . . . . , p,> is a safe sequence if for each p~, the resource which Pi can still request can be satisfied by the available resources plus the resources held by all the pj with j < i. In this situation, if the resources that process p; needs are not immediately available, Pi can wait until all p j, with j < i, have finished. Then pi can obtain all of its needed resources, complete its designated task, return all of its allocated resources, and terminate. When p~ terminates, Pi+l can obtain its needed resources, and so on. DEFINITION. A system is in a safe state if there exists a safe sequence of the processes in the system. If no such sequence exists then the state of the system is unsafe. Following Haberman [2], we assume that the maximum resource requirement (i.e., claim) of each process is known in advance. It is assumed that within this limitation each process can make requests for resources dynamically in an arbitrary sequence. Given the concept of a safe state, we can define the banker's algorithm which ensures that the system will never deadlock. The idea is simply to ensure that the system will always remain in a safe state. Initially the system is in a safe state. Whenever a process requests a resource that is currentely available, the system must decide if the resource can be immediately allocated or if the process must wait. The request is granted only if it leaves the system in a safe state, that is, if there exists a safe sequence of the processes in the system. The following example shows how the banker's algorithm works: EXAMPLE 1. Consider a system with five processes {Po, Pl .... ,P4} and three resource types {A, B, C}. Resource type A has 10 instances, resource type B has 5 instances, and resource type C has 7 instances. Suppose that at time T~ the

292

FERENC BELIK

following snapshot of the system has been taken :

Po Pl P2 Ps p~

All~ation ABC

Need ABC

Available A B C

0 1 0 200 302 211 002

743 122 600 0 t i 4 3 t

332

The content of the matrix Allocation is defined to be the number of resources of each type currently allocated to each process and the matrix Need is indicating the remaining resource need of each process. The vector Available is indicating the available resources of each type. We claim that the system is currently in a safe state. Indeed, the sequence (Pl, P3, P4, P2, P 0 ) satisfies the safety criteria. Suppose now that process Pl requests one additional instance of resource type A and two instances of resource type C, so Requesti+~ = (1, 0, 2). In order to decide whether this request can be immeditely granted, we first check that Requesti+ ~ < At,ailable (that is, (1, 0, 2) < (3, 2, 2)) which is true. We then pretend that this request has been fulfilled and arrive at the following new state:

Po Pl P2 P3 Pa

Allocation ABC

Need ABC

Available ABC

0 1 0 302 302 211 002

743 020 600 011 431

2

3

0

We must determine whether this new system state is safe. To do so we execute our safety algorithm (see Appendix A) and find that the sequence (Pl,P3,P4,Po, P2) satisfies our safety requirement. Hence we can immediately grant the request of process pl. However, in this state, a request for (3, 3, 0) by P4 cannot be granted since the resources are not available. A request for (0, 2, 0) by P0 cannot be granted even though the resources are available, since the resulting state is unsafe. The main difference between the banker's algorithm and our modified algorithm is in the way of finding a safe sequence. The O(mn z) part of the banker's algorithm is simply finding a safe sequence. At every resource allocation state, the banker's algorithm tries to find a complete safe sequence, consisting of all the n processes, whereas the modified algorithm only tries to find a safe sequence of the necessary length. In our algorithm certain processes (marked by T) need not be checked for belonging to a safe sequence and when a process is checked once, it need not be checked again if it does not allocate any resources. Consider the following example:

293

DEADLOCK AVOIDANCE WITH A MODIFIED BANKER'S ALGORITHM

EXAMPLE 2. We have a system with 5 processes and one resource class, consisting of 13 resources. Since the algorithm works with all resource classes in parallel it is enough to regard the allocation of one type of resource. Let A denote the number of resources allocated to each process, N denote the remaining need of each process, and S denote the status of each process. Underlining indicates which process allocates resources at the current moment. The status of a process can be T (terminatable), M (maybe terminatable) or S (safe). A process that never allocates a resource has an indifferent status (marked by -). In the following we will use the terms T-process, M-process or S-process to express that a process has the status T, M or S. The following table shows eight allocation states : allocation state

0

1

P

A

p~ Pz P3 P4 P5

0 50 80 20 I00 6-

available

N S

13

2

3

4

5

6

7

A NS

ANS

ANS

ANS

ANS

ANS

ANS

2 3T 0 80 20100 6-

2 3T 0 81 IT 0100 6-

2 3T 2 6T t 1T 01006-

23T 26M liT 37 M 06-

23T 26S liT 37 S 24M

23M 26S liT 4.6 M 24S

32M 26S I l T 46 S 24S

8

5

3

2

1

11

10

All eight allocation states are safe. We have to explain the meaning of the status of the processes and the need to check whether a process, with a special status, belongs to a safe sequence. A process has the status T if its remaining need is not greater than the number of resources currently available (we have a row for this number in the table above). These processes need not be checked whether they belong to a safe sequence since they can finish their task with the available resources. To understand the meaning of M and S, look at states 4 and 5. To find a safe sequence we have to use the currently available resources and the resources released by the T-processes. These resources are needed to "start up" a safe sequence. Now, if this number of resources was enough at state 4 to form a safe sequence of M-processes, then at the next state 5 these M-processes obtain the status S and we need not check whether they belong to a safe sequence, since the number of the resources released by the T- and M-processes at this state is not less than the number of the resources released by the T-processes at the previous state. This is the main idea that forms the basis of the modification of the banker's algorithm. We need a more precise description of S and M. A process obtains the status S if it had the status M at the previous state and has not allocated any resource at the current state. A process keeps this status until it allocates some resource at some state or some process finishes its task and its released resources become available again. An S-process need not be checked whether it belongs to a safe sequence as mentioned above (we prove this in Theorem 1).

294

FERENC BELIK

A process obtains the status M if it was a T-process at the previous state and its remaining need is greater than the currently available resources or the process has allocated more resources at the current state (the process may have had an arbitrary status at the previous state) and its remaining need is greater than the currently available resources. Only these processes need to be checked whether or not they belong to a safe sequence. Example 2 only gives an informal description of how the modified algorithm works. The complete algorithm is presented in Appendix B and we refer to it when we prove that the algorithm works properly and when we show how the algorithm limits the concurrency. To prove the following two theorems we need some notations. Let P~ stand for the set of all processes in the system at state i and T~, M~, S~ and Ii the sets of processes in the system with status T, M, S and indifferent respectively, at state i. Note that T~, M~, S~ and li constitute a partition of P~. Further, let A~ stand for the number of resources available at state i and IXl for the number of resources released by processes in set X. THEOREM 1. The modified banker's alyorithm 9uarantees that the system is always in a safe state. PROOF. We use mathematical induction over the allocation states k - l , k , k + l , . . , r - l , r ..... as we have to prove that the S-processes need not be checked for belonging to a safe sequence. a)

Assume that the first M-processes occur at allocation state k - 1 and the state is safe. This means that the number of resources given by Ak-1 and ITk_ tl guarantees that the processes belonging to M k_ 1 can form a safe sequence. The status of the processes at this state is described by the partition

Pk-1 = Tk-, U M k - , W i g - , . Assume further that at the next state the processes belonging to Mk form a safe sequence by means of Ak and ITkl- Then, the processes belonging to SR need not be checked since Mk-1 ~=Sk and ITk u Mkl > lTk-ll (because (Tk u Mk) ----=T~_,). b)

The status .of the processes at state r - 1 is described by the partition P,_ 1 = T,_ 1 w Mr-~ ~ S,_ 1 w I,_ 1. Assume that the allocation state is safe, that is, the number of resources given by A,_ i and tT,-II guarantees that the processes belonging to M,_ I can form a safe sequence, and assume that the process belonging to S,_ ~ need not be checked. Consider the processes P, = T, w Mr w Sr w Ir at the next state and assume that the number of resources given by A, and IT~I is enough for the processes belonging to Mr to form a safe sequence. At state r - 1, the number of resources given by At-1 and [T,-ll was enough for the M,_l-processes and the S,_l-processes did not need to be checked according to the

DEADLOCK AVOIDANCEWITH A MODIFIEDBANKER'SALGORITHM

295

assumption. Then (T, u M,) ~ T~_ 1 guarantees that the processes belonging to S, need not be checked since (M,_ 1 u S,_ 1) ~ S,. • The number of M-processes, that have to be checked is small in Example 2, which is characteristic for our algorithm. We discuss the running time in the next section and present a simulation in Section 4. The simulation shows a drastic improvement. However, we have to pay for this improvement by a slightly restrictive algorithm. It can happen that the modified banker's algorithm rejects a request of a process with M-, S- or indifferent status whereas the banker's algorithm would accept it. This situation will not happen often according to the simulation results, and when it happens it may lead to a more efficient resource allocation (compare the number of rejected and completed processes for the two algorithms in the simulation result, given in Section 4). In the following theorem we give the conditions under which the modified algorithm is restrictive. THEOREM 2. The modified banker's al#orithm is restrictive only when the followiny two conditions hold: a) The number of resources ,qiven by A, and [(Tr u M,)-{Pa}[, where Pa is the process that tries to allocate resources at the current state r, is not enough for pa to finish its task, but it is enough for some S-process p~ which can release enough resources for the remaining processes to finish their tasks (i.e., to form a safe sequence). b) The process Pa had M-, S- or indifferent status (i.e., not T-status) at the previous state r - 1 . PROOF. It is easy to see that the algorithm uses all available resources, including resources released by the T-processes, to find a safe sequence of M-processes, that is, the only occasion for restrictiveness could be that the algorithm does not check the S-processes. a)

It is enough to prove that when there exists no safe sequence of processes belonging to (T, u M,) then a process p~ e S, can only be included in a safe sequence as the last process after the processes belonging to ((T, u M , ) - {po}). Ps c S, implies that there exists a state k < r, where p~ ~ M k and p~ has not allocated any resource since state k. That the processes belonging to (T~ u M,) cannot form a safe sequence means that after the release of the resources allocated by T~- and some of the M,-processes a stoppage occurs, as the sum of the released resources is less than the remaining need of each of the other M,-processes. According to the algorithm we see that Tk 2 ((T~ u M , ) - {p~}). Therefore, when a stoppage occurs p~ can only be put after the processes belonging to ((T~ u M,)-{p~}) since the remaining need of p, is greater (at least in one resource class) than the remaining need of all processes belonging to Tk. That this really can happen is shown in Example 3.

296 b)

FERENC BELIK

In this case we prove that if Pa e T~_l then all S-processes has a greater remaining need (at least in one resource class) than all processes belonging to (T~ u M,). If p ~ T ~ _ l then I~ 2 ( T , u M , ) (since T k 2 T,_~), which gives the proof. II

In the following example we present a situation where the modified algorithm is restrictive. EXAMPLE 3.

allocation state

r- 1

P

AN

Pl Pz P3 P4 P5 P6

14M t3T 28S llT 37S 16M

available

3

r

S

AN

S

I4S 13M 28S lit 37S 25M 2

The modified algorithm rejects the allocation of a resource to process P6 at state r. However, there is a safe sequence at this state, namely (p~, P2, Pl, P6, Ps, P3). We observe that we get the same result if process P6 has S-or indifferent status at state r - 1 . The argumensts in the theorems above were valid under the assumption that the processes did not release any resources, that is, {rilr~ allocated to pj under state k} < {r~lr~allocated to pj under state k + 1} for all resources and processes and all states 1, 2, 3. . . . . What happens when a process releases its resources after it has finished its task is dealt with in the next section.

3. Running time. Since the length of the sequence of M-processes checked varies from state to state and depends on checks made in earlier moments we consider the algorithm during several states. This leads to an amortized cost estimate. To find a safe sequence at steps 2 and 3 in the Safety algorithm is the O(mn 2) part of the banker's algorithm (see Appendix A). The critical part of the modified banker's algorithm is the same, and the other parts have a running time O(mn) (see Appendix B). In the following we discuss the running time only for this part of the modified algorithm. We observe that once a process has been checked for belonging to a safe sequence it does not have to be checked again, unless the process allocates more resources. This means that the sum of the lengths of the checked sequences in

DEADLOCK AVOIDANCE WITH A MODIFIED BANKER'S ALGORITHM

297

the course of q states is limited by q + n. However, our observation is only valid under two assumptions. The first is that no process finishes its task and its released resources become available again during these q states. These released resources can convert S-processes to T-processes, which leads to new checking of processes. The second assumption is that no process is rejected during the q states. A rejection means that the check, made at the current state, is wasted, as the previous status of the process will be restored. Accordingly, the size of q and the number of rejected requests during q states influence the running time. These two factors depend among other things on the number of processes, the number of resources, the number of requested resources by the processes each time and in which order the processes request resources. The interactions between these are hard to estimate and we are forced to make some assumptions about these two factors. Let q = cln be the number of consecutive states during which no process finishes its task and during which the number of rejected processes are c2, where cl and c2 are prositive integers. The sum of the lengths of the checked sequences during these q states is limited by (c2+l)n+(q-c2-1). This limit can be achieved when at the c2 rejections all n processes are checked, which gives c2n(n+ 1)/2 searches at steps 2 and 3 in Safety algorithm. Then at the next state, the allocation succeeds and the number of checked processes is also n. Finally, at the remaining states one process is checked each time. We obtain (c2+l)(nZ+n)/2+(q--c2--1) searches in all during q states, which gives an amortized cost per state of (c2 + 1)(n 2 + n)/2cln + 1 - (c2 + 1)loin searches. Since the cost of one search is tg(m) the modified banker's algorithm has an amortized worst case cost of O(mn) under the assumptions above. The question is how reasonable our assumptions are. That no process finishes its task during q = cln states is reasonable to assume. For example, when the processes are served from a circular queue it is likely that no process finishes its task at its first allocation, which gives q > n. That only a constant number c2 processes are rejected during q states is harder to estimate. However, at the beginning of a period of q states, when the supply of the resources is high, the number of rejected processes should be lower than at the end of the period. Since the number of M-processes at each state should be high at the beginning of the period while at the end of the period most of the processes should be S-processes, the cost of a rejection shbuld be low when most rejections happen. For example, if we have a constant number of rejections at the beginning of the period where the number of searches is O(n 2) per state and~he remaining rejections happen at states where the numbdr of searches is O(n) per state, then the number of remaining rejections can be O(n)and we still have an average constant number of rejected processes with O(n 2) searches per state for the whole period.

298

FERENC BELIK

The arguments here are informal and their purpose is to illuminate situations that can make our assumptions on the length of a period q and on the number of rejected processes during a period of length q reasonable. The simulation, presented in the next section, where the processes are served from a circular queue, gives an O(mn) running time. In the worst case the number of available resources at every pair of states oscillates between a minimum (where all processes will be marked M) and a maximum (where all processes will be marked T) and the time complexity is O(mn2). This situation can happen if one of the processes receives that many resources at the first state that all the processes must be checked in Safety algorithm. At the second state it receives the remaining resources it needs, and, after it has completed its task its allocated resources become available again. Such a situation must be exceptional, but even if it occurs our modified algorithm will work twice as fast as the banker's algorithm (because no T-processes are checked by Safety algorithm at the second state).

4. Simulation. We performed a simulation to compare the banker's algorithm, given in [4], with our modified algorithm. All of the starting values were chosen as pseudorandom numbers and both algorithms were executed on the same series of pseudorandom numbers. The processes were served from a circular queue and their requests (between 1 and Need[i, j], j = 1, 2,..., number of resource classes, for each process i) were also chosen as random numbers. The simulation was done for 10, 20, 30..... "100 processes where the number of resource classes varied by 5, 10 and 50, while the number of resources of each class varied by 10, 50 and 100. The number of allocations were 10000 for each set of data and the whole simulation was repeated for five different series of random numbers. For both algorithms, we counted the number of calls of the Safety algorithm and the number of searches in the Safety algorithm at steps 2 and 3, i.e., at that part of the algorithms that could give O(mn 2) running time. We also counted the number of completed processes (i.e., processes that have finished their tasks) and the number of rejected requests (at step 2 in the main algorithm and after checking by Safety algorihm) for the purpose of studying the restrictiveness of the modified algorithm. All result tables showed a drastic improvement in the number of searches for the modified algorithm. The number of completed and rejected processes were the same with 50 resource classes in all result tables while it varied between the two algorithms with 5 and 10 resource classes. However, more processes were completed in most cases by the modified algorithm; the relation was 60-40 ~o.

DEADLOCK AVOIDANCE WITH A MODIFIED BANKER'S ALGORITHM

299

T a b l e 1. F e w resource classes ( = 5); I0 000 assignments; limit o f resources in each class = 50. Modified banker'salgorithm

Banker's algorithm

n lO 20 30 40 50 60 70 80 90 100

c

s

s/cn 2

2471 126939 ~51 1469 218194 ~37 i138 302252 0.30 1044 381675 0.23 723 494633 ~0.27 761 570163 0.21 606 703908 0.24 558 713560 0.20 657 1002883 ~19 519 1121977 0.22

C

R

c

459 184 137 89 73 58 64 42 65 56

8159 9114 9429 9592 9644 9718 9737 9797 9773 9791

1t98 1063 960 1080 824 977 600 588 534 647

s 1691 3434 3631 4714 6210 8211 5169 6558 5444 11587

s/cn

C

R

~14 0.16 0.13 0.11 0.15 0.14 ~t2 0.14 0.11 ~18

428 205 153 102 73 83 63 58 55 78

8343 9101 9420 9680 9680 9663 9754 9754 8913 9747

We selected T a b l e 1 from the result tables as representative for the simulation. We use the following n o t a t i o n s in the table: n stands for the n u m b e r of processes, c for the n u m b e r of calls of the Safety algorithm, s for the n u m b e r of searches in the Safety algorithm, C for the n u m b e r of completed processes a n d R for the n u m b e r of rejected processes. The c o l u m n , m a r k e d s/cn 2, shows that the b a n k e r ' s a l g o r i t h m works in O(mn 2) time, while the c o l u m n , m a r k e d s/cn, suggests that the modified b a n k e r ' s a l g o r i t h m works in O(mn) time (because the values in the c o l u m n s are almost constant). A c c o r d i n g to the simulation, the n u m b e r of searches was extremely low for the modified a l g o r i t h m in all result tables when the n u m b e r of resource classes was high ( = 50). This is shown in Table 2.

T a b l e 2. M a n y resource classes ( = 50); 10000 assignments; limit o f resources in each class = 50. Banker's algorithm

Modified banker's algorithm

n

c

s

s/cn z

C

R

c

s

s/cn

C

R

10 20 30 40 50 60 70 80 90 100

1149 584 392 300 241 200 171 156 143 122

74685 133690 191715 248980 312950 367020 424480 482280 541125 598000

0.65 0.57 0.54 0.52 ~52 ~51 0.51 0.48 0.47 0.49

165 85 55 40 36 27 23 20 18 16

8851 9419 9613 9711 9764 9806 9834 9855 9871 9884

0 3 5 11 5 6 5 11 14 6

0 3 5 tl 5 6 5 11 14 6

0.050 0.033 0.025 0.020 0.016 0.014 0.012 0.011 ~010

165 85 55 40 36 27 23 20 18 16

8851 9419 9613 9711 9764 9806 9834 9855 9871 9884

300

FERENC BELIK

Comment to Table 2: The question is, why the number of searches is extremely small for the modified algorithm, and why the values of the last two columns become the same for both algorithms. The only explanation we can give is that with many resource classes the system is sluggish and, either almost all of the processes are T-processes, or the requests are rejected at step 2 in the main algorithm.

5. Conclusion. The banker's algorithm provides a general resource allocation but its running time is O(mnZ). Our modification preserves almost all of the generality of the banker's algorithm while it has an amortized worst case running time of O(ml~) under certain conditions, and probably even in the average case according to the simulation result. Our modification is a bit restrictive compared with the banker's algorihm, but it seems to provide a more etficient resource allocation than the banker's algorithm. Future computer systems will be oriented more towards asynchronous parallel operation and multiple processor systems will be common. There will, quite simply, be more operations going on concurrently and the number of processes and resources will increase. The extremely small number of searches showed by the simulation result suggests that our algorithm will fit well for systems with a large number of processes and resources.

APPENDIX A

The banker's algorithm. The deadlock avoidance algorithm described below is commonly known as the banker's algorithm. The name was chosen since the algorithm could be used in a banking system to ensure that the bank never allocates its available cash in such a way that it can 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, it must be determined whether (he allocation of these resources will leave the system in a safe state. If so, the resources are allocated ; otherwise, the process must wait until some other process releases enough resources. Several data structures must be maintained to implement the banker's algorithm. These data structures encode the state of the resource allocation system. Let n be the number of processes in the system and m be the number of resource types. We need the following data structures:

DEADLOCK AVOIDANCE WITH A MODIFIED BANKER'S ALGORITHM

301

- Available. A vector of length m indicating the number of available resources of each type. If Available[j] = k, there are k instances of each resource type r~ available. - Max. An n × m matrix defining the maximum demand of each process. If Max[i, j] = k, then process Pi may request at most k instances of resource type rj. - Allocation. An n x m matrix defining the number of resources of each type currently allocated to each process. If Allocation[i, j] = k, then process Pi is currently allocated k instances of resource type rj. - Need. An n x m matrix indicating the remaining resource need of each process. If Need[i, j] = k, then process Pi may need k more instances of resource type r~, in order to complete its task. Note that Need[i, j] = Max[i, j] Allocation[i, j]. These data structures vary both in size and value with time. To simplify the presentation of the algorithm, let us 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. Further, 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 Allocations and Needs, respectively. Allocation~ specifies the resources currently allocated to process Pi, while Needi specifies the additional resources the process p~ may request in order to complete its task.

Banker's algorithm. Let Requesti be the request vector for process Pv If Requesti[.j] = k, then process Pi wants k instances of resource type rj. When a request for resources is made by process p~, the following actions are taken. 1. 2. 3.

If Requesti <_ Need~ then proceed to step 2. Otherwise we have an error, since the process has exceeded its maximum claim. If Request i <_ Available then proceed to step 3. Otherwise the resources are not available, and Pi must wait. The system pretends to have allocated the requested resources to process pi by modifying the states as follows: Available = Available - Requests; Allocations = Atlocationi + Requesti ; Needi = N e e d i - Requesti ; If the resulting allocation state is safe, the transaction is completed and process p~ is allocated its resources. However, if the new state is unsafe, then Ps must wait for Request~ and the old resource allocation state is restored.

302

FERENC BELIK

Safety algorithm. The algorithm for examining whether a system is in a safe state or not can be described as follows: 1. 2.

Let Work and Finish be vectors of length m and n, respectively. Initialize Work : = Available and Finish[i] : = false for i = 1, 2..... n. Find an i such that:

a. b.

Finish[i] = false, and Needi < Work.

If no such i exists, go to step 4.

3.

4.

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.

APPENDIX B

The modified banker's algorithm. In addition to the data structures used by the banker's algorithm (given in Appendix A) we need the following data structure:

- State. A vector of length n indicating the state of each process. If State[i] = T (terminatable), there are enough available resources process pi may need in order to complete its task, i.e., Need[i, j] <_ Available[j] for all j. If State[i] = m (maybe terminatable), then (Need[i, j] <_ Available[j] for some j at moment r) and [(Need[i, j] < Available[j] for all j at moment r - 1 ) or (process pi has allocated its resources at moment r)], where r means the current resource allocation moment and r - 1 means the previous resource allocation moment. If State[i] = S (safe, i.e., process Pi will be a member of a safe sequence if the M-processes at the current allocation moment form a safe sequence), then process p~ is not the process that has requested resources at the current allocation moment and State[i] had the mark M at some previous resource allocation moment.

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 process Pl, the following actions are taken:

DEADLOCK AVOIDANCE WITH A MODIFIED BANKER'S ALGORITHM

303

.

If Requestl < Needs then proceed to step 2. Otherwise we have an error, since the process has exceeded its maximum claim.

.

If Requesti < Available then proceed to step 3. Otherwise the resources are not available, and pi must wait.

.

If Requesti = Needi then modify the states by Available : = A v a i l a b l e - Request i; Allocation s : = Allocationi + Requesti ; and then proceed to part II in the main algorithm. Otherwise the system pretends to have allocated the requested resources to process p~ by modifying the states as follows: Available : = Available - Requesti ; Alloeationi : = Alloeation~ + Requests; Need~ : = N e e d ~ - Requesti; IF Needi <_ Available THEN BEGIN State[i]:= T;

(* The allocation state is safe *)

F O R p : - - 1 T O n DO IF (p :/: i ) A N D (State[p] = T ) A N D (Needp > Available) T H E N State[p] : = M ELSE I F (p ~ i) A N D (State[p] = M ) T H E N State[p] : = S; END ELSE BEGIN (* The safety of the allocation state must be checked *) State[i] : = M; FORp:= 1 TOn DO IF (p :~ i) A N D (State[p] = T) A N D (Needp > Available) T H E N State[p] : = M ELSE IF (p + i) A N D (State[p] = M ) T H E N State [p] : = S: Check by the Safety algorithm whether the M-processes can form a safe sequence. END If the resulting resource allocation state is safe, the transaction is completed and process Pl is allocated its resources. However, if the new state is unsafe, then Pl must wait for Requests and the old resource allocation state is restored.

304 II.

FERENC BELIK

If process Pi has completed its task the following actions are taken :

Available : = Available + Allocationi ; Allocation~ : = 0; FORp:= 1 TOnDO I F Needp < Available T H E N State[p] : = T E L S E State[p] : = m

Safety algorithm. The algorithm for finding a safe sequence of M-processes can be described as follows : 1.

2.

Let W o r k be a vector of length m and let Finish be an n x 2 matrix. Initialize : c := 1; (*c counts the n u m b e r of M-processes *) W o r k : = Available; FORp:= 1 TO n DO BEGIN I F State[p] = T T H E N W o r k : = W o r k + Allocationp; I F State[p] = M THEN BEGIN Finish[c, 1] : = p; Finish[c, 2] : = F A L S E ; c := c+l; END END Find an i such that i < c a n d : a. Finish[i, 2] = F A L S E , and

b.

NeedFi~i~h[i, l] <- Work.

If no such i exists, go to step 4.

3.

4,

W o r k : = W o r k + AllocationFinish[i, 1] ; Finish[i, 2] : = T R U E ; g o to step 2. If Finish[i, 2] = T R U E for all i < c, then the system is in a safe state.

REMARK. We assume that when a process has finished its task a new process can enter the system and allocate resources, Otherwise there is no need to change the state of the processes in part II of the main algorithm. According to o u r assumption, when a new process allocates resources

DEADLOCK AVOIDANCEWITH A MODIFIED BANKER'S ALGORITHM

305

released by a process that finished its task, the status of the process must be changed since the S-status of the processes, if any, were established by all resources that could be released by all the processes in the system.

Acknowledgements. The a u t h o r is grateful to D r Eric Astor, D r Svante Carlsson, D r g o l f Karlsson and D r Boris M a g n u s s o n for their useful suggestions.

REFERENCES 1. E. W. Dijkstra, Cooperatin9 sequential processes, Technical Report EWD-123, Technological University, Eindhoven, The Netherlands, 1965. 2. A. N. Haberman, Prevention of system deadlocks, Communication of the ACM, Vol. 12, No. 7, July 1969, pp. 373-385. 3. T. Kameda, Testing deadlock-freedom of computer systems, Journal of the ACM, Vol. 27, No. 2, April 1980, pp. 270--280. 4. J. Peterson and A. Silbersehatz, Operatin9 System Concepts, Second Edition, Addison-Wesley, 1985.