Expected Deadlock Time in a Multiprocessing System Kevin J. Compton* and Chinya Ravishankart November 19. 1992 Abstract We consider multiprocessing systems where processes make independent, Poisson distributed resource requests with mean arrival time 1. We assume that resources are not released. It is shown that the expected deadlock time is never less than 1, no matter how many processes and resources are in the system. Also, the expected number of processes blocked by deadlock time is one half more than half the number of initially active processes. We obtain expressions for system statistics such as expected deadlock time, expected total processing time, and system efficiency in terms of Abel sums. We derive asymptotic expressions for these statistics in the case of systems with many processes and the case of systems with a fixed numberof processes. In the latter, generalizations of the Ramanujan Q-function arise. We use singularity analysis to obtain asymptotics of coefficients of generalized Q-functions. 1 Introduction. Deadlock detection and resolution is a major issue in the design of multiprocessing systems (see Tanenbaum [18]). While in some systems (Unix for example) deadlock is rare and the cost of resolution is low, in many others (such as database systems) the likelihood of deadlock may be quite high and resolution requires an expensive rollback and recovery. It would be useful to know under what circumstances deadlock is likely and (especially when resolution is costly) the expected time for the occurrence of deadlock. This paper presents a model of multiprocessing systems where processes make resource requests independently and with Poisson distributions of mean 1. We derive exact and asymptotic expressions for system statistics such as expected time to deadlock, expected total processing time, and system efficiency. We make the simplifying assumption that resources are never released. Thus, our results may be viewed as upper bounds or bounds for an extreme case of system behavior. Let us describe our model a little more precisely. A multiprocessing system is composed of two types of entities: processes and resources. Processes are the active entities of the *Present address: EECS Department, University of Michigan, Ann Arbor, MI 48109-2122. Part of this research was done while the author was on sabbatical leave at the Institut National de Recherche en Informatique et en Automatique, Rocquencourt, France. tEECS Department, University of Michigan, Ann Arbor, MI 48109-2122 1

system. They can change the system state by requesting new resources or releasing resources allocated to them. Resources are serially reusable: they may be reallocated once they are released. Examples of such resources are hardware units such as memory pages or printers, and software resources such as database locks. We do not examine systems with consumable resources such as messages, signals, and input data. We also assume that each process requests only one resource at a time. A system state is represented by a resource allocation graph. This is a directed graph whose vertices are the processes and resources in the system. The graph is bipartite; edges are directed from resources to processes or processes to resources (see Figure 1). rl 10 O P r2 2___ ) P2 r62 0^ ~ ^0 P6 rS 6I ^-s^ \) P6 r 7 D' ~ P7 r8 p 0 Resources Processes Figure 1: A Resource Allocation Graph A resource is free if it has not been allocated to a process. If a process p requests a free resource r, an edge is inserted in the resource allocation graph from r to p to indicate that r has been allocated to p and is no longer free. When p releases r the edge is erased. If p requests a resource r which is not free, an edge is drawn from p to r, indicating that p is waiting for r to be released. In this case, p becomes inactive or blocked and can make no more requests until r is released. Thus, an active process has out-degree 0 and an inactive process has out-degree 1. Deadlock occurs when a directed cycle appears in the resource allocation graph. Since all the processes on the directed cycle are blocked, the resources on the cycle can never be released. They become useless until the deadlock is detected and resolved. For example, if process p7 requests resource r4 in Figure 1, deadlock occurs there a cycle p7 -- r4 -> P2 - r2 - p3 -- r5 -> p7 results when the edge p7 -b r4 (indicated by the dotted arrow) is added. A more detailed description of the model is given in the following section. 2

Lynch [14], in enumerating the number of cycle-free resource allocation graphs for given numbers of resources and processes, gave the following necessary and sufficient conditions for a bipartite directed graph to be a resource allocation graph. (i) Every vertex has out-degree at most one. (ii) Every resource with nonzero in-degree has out-degree exactly one. To see this, observe that a resource acquires an out-edge the first time it is requested; thereafter, it acquires only in-edges. A process, on the other hand, acquires in-edges until it acquires its first out-edge; thereafter, it is inactive. From his enumeration, Lynch derived some system statistics for a model where resource allocation graphs with the same number of directed edges are equally likely. Our model is quite different. It is more closely related to problems such as linear probe hashing (see Knuth [11] and Vitter and Flajolet [19]), computation of random mapping statistics (see Flajolet, Gardy, and Thimonier [4] and Flajolet and Odlyzko [6]), analysis of union-find algorithms (see Yao [21] and Knuth and Sch6nhage [13]), and optimum caching (see Knuth [12]). These problems are all analyzed in terms of Abel sums (so called because many of them can be evaluated explicitly by generalizations of Abel's identity). The outline of the paper is as follows. In section 2 we describe our model and derive recurrence relations for various system statistics. In section 3 we note that all of these recurrences have a common form and give solutions in terms of Abel sums. We prove a result we call the Half and Half Theorem. It says that beginning from any state with j active processes, the expected number of these processes blocked by deadlock time is (j + 1)/2, one half more than half of the half the number of initially active processes. In section 4 we develop a general theory for the evaluation of Abel sums. This is applied to the recurrence solutions of section 3 to give expressions and inequalities for system statistics. In section 5 we give asymptotic expressions for these expressions in the case where systems have many processes. In section 6 we do the same for the case where systems have a fixed number of processes. Here functions generalizing the Q-function arise. This function was studied by Legendre, Cauchy [1], and later by Ramanujan [15]. Ramanujan actually denoted it 0 (as he did several other functions). Knuth was the one to name it Q in his first expected time analysis of an algorithm [10, pages 113-118] (see also Flajolet, Grabner, Kirschenhofer, and Prodinger [5]). We use singular expansions to obtain the asymptotics of coefficients of functions of this type. We observe several notational conventions. The expression [zn]s(z) denotes the n-th coefficient of the generating function s(z). The expression na denotes the falling factorial n(n - 1)... (n - m + 1). Stacked numbers in braces {(} denote Stirling numbers of the second kind (or in the terminology of Graham, Knuth, and Patashnik [8] the subset Stirling numbers). The expression j!! denotes the double factorial function 1 3 * 5 * * * (2j - 1). E(X) is the expectation of the random variable X. We write f < g if f (n)/g(n) approaches 0 as n - oo; this is just another way of writing f(n) = o(g(n)). 2 Recurrence Equations. In this section we give a more detailed description of our model and derive recurrence relations for system statistics. 3

Let m be the number of resources and n be the number of processes in a multiprocessing system. Suppose that the system has just entered a state where there are i free resources and j active processes. Let Tij be a random variable representing the time to deadlock. Tij depends on m as well as i and j, but for notational convenience we suppress m. We shall see that Tij does not depend at all on n. Consider the arrival time for the next request. If there were just a single active process, this value would be an exponentially distributed random variable with mean 1. For j active processes it is the minimum of j independent, exponentially distributed random variables with mean 1. A straightforward calculation shows that this is an exponentially distributed random variable with mean j-1. That is, we may express the arrival time for the next request as j-'Xi~j, where Xij is an exponentially distributed random variable with mean 1. Thus, after a time interval of length j-'Xij, a process p chooses a resource r. Now r may be one of the i free resources or one of the m - i allocated resources. The event that r is free is represented by a random variable Aij where P[A,, = 1] = 1 - P[Aij = 01] = i/m. When Aij is 1, an edge is inserted from r to p and the system enters a new state in which there are i- 1 free resources and j active processes. When Aij is 0, we check to see if an edge inserted from p to r would result in deadlock. We do this by constructing a directed path from r as follows. Follow the unique out-edge from r to a process. If this process has out-degree one, follow its unique out-edge. Continue in this fashion. The resource allocation graph contains no directed cycle yet so this path terminates. In fact, it terminates at a process, since resources with nonzero in-degree have out-degree one. If the process where this path terminates is p, an edge from p to r would complete a directed cycle and deadlock results. If the path terminates at any of the other j - 1 active processes, we do not have deadlock. Thus, the probability that deadlock does not occur is (j - 1)/j. The event that deadlock does not occur may be represented by a random variable Bij where P[Bij = 1] = 1 - P[Bij = 0] = (j - l)/j. Putting this al together, we have Tj = j-Xi,, + A1,jTil,j + (1 - Aij)BjTij_ (1) where the random variables Aij and Bij are independent of each other and of the random variables Xij, Ti1,j, and Tij-i. This model is counterintuitive in one respect. Suppose that process p requests a resource r and at some later time p requests r again. This is not precluded in our description of the model. The system enters deadlock at this point because a 2-cycle appears in the resource allocation graph. If we do not allow the possibility of a process requesting a resource already allocated to it, then the system may never reach deadlock. It may instead reach a state in which all resources have been allocated to a particular process and all other processes are blocked. If we wanted to forbid the possibility of a process requesting a resource already allocated to it, we would have to be more careful about what we mean by expected deadlock time. Of course, the main reason for considering the model here is that it is analytically more tractable. In the case where thee is a single process our model is an instance of the famous birthday problem (see Knuth [10]). This problem asks how many people one must choose at random to find a pair with the same birthday. This is equivalent to labeling 365 resources with the days of the year (we ignore leap days) and computing the expected deadlock time, which, 4

with just one process, occurs only when a resource is repeated. In general, Tm,1 is the expected number of people one must choose for a year with m days. Closely related to the problem of finding the expected deadlock time is the problem of finding the total processing time Pij before deadlock. This requires only a minor modification of the argument used to derive equation (1). Observe that if j processes are active for a time interval given by j1-Xij then the total processing time over that interval is Xij. Hence, Pij = Xi + AijPij + (1 - Aij)BjPij1 (2) Now if we let Tij = E(Tij) and Pij = E(Pij), from (1) and (2) we have, using linearity of expectation and independence, then multiplying by j, jTij = 1 +-T j + -- ( j-)Tij_1, (3) Jij = + Pi-l, + (1- ) (-1)Pj-1 (4) for j > 0. A system statistic that will be especially important is Fij = Pij/jTi,j which measures system efficiency. Note that jTij is total processing time in system where j processes are active for a time interval of T,j. The ratio of actual total processing time to this quantity is the expected fraction of time that processes are active. We will also be interested in the variances of Tj and Pij. Therefore, we wish to compute the expectations Uij = E(T2j) and Qij = E(Pj). Squaring both sides of (1) and using the identities A,j(l - A,j) = 0, A = A,j, (1- Ai,)2 = 1 — Aj B2 = B-j, we have T 2 = j2X,. + AijT_ 1 + (1 - Ai)Bi,jTj-l + 2j-XijAijTi i + 2j-1X,(l - Ai,)BiTi-. Now take expectations and use equation (3). Note that E(X?2,) = 2. Then multiply by j to obtain jUi, = 2T,i + - jUi,- + - - (j - ),j-1 (5) Performing the same series of computations beginning with (2) we have jQi, = 2jP,, + jiQi-j + (-) - )j. (6) rn The last statistic we consider measures how well the system allocates resources. This is also important for system design. Even if the expected deadlock time is fairly long, system performance still might be poor if processes requesting resources are usually blocked. We are interested, therefore, in the expected number of resources Rij that will be allocated by the time deadlock occurs. This is easy to determine from our model. Notice that whenever a process requests a resource, the probability that the request will be granted is i/m. Thus, jRij, = - + -jR,_, + (1 - -)(j - )Rj. (7) 5

3 Solving the General Recurrence. The equations (3)-(7) have the form Sij = X,, +, + - 1) Sij_. (8) where Si,0 = Xjo = 0 for all i. (Note that there is no need to specify the values of Soj since SoJ = Xo, + Soj-1.) We summarize the results of the previous section, with respect to this general form, in Figure 2. J Symbol Description Sij Xjj Equation Tij Expected jTij 1 (3) Deadlock Time Pij Expected Total jPij (4) Processing Time Uij Expected Square jUij 2Tj (5) of Deadlock Time Qij Expected Square of jQilj 2jPi,j (6) Total Processing Time Rij Expected Number of jRij ij/m (7) Resources Allocated Figure 2: Summary of Recurrences Recurrence (8) is linear in Xij; that is, if Xj = aX,j + bX'" for all i and j, then,Sij = aS' + bS!', where S' and S'" are solutions of the equations obtained from (8) by replacing Xij with X', and X" respectively. To solve (8), we might try to form a bivariate generating function >i,J Si,jyizi and solve the resulting partial differential equation. Unfortunately, the solution to this equation does not lead easily to a closed form solution for coefficients of the generating function. Instead, we form sequences of generating functions 00 00 s,(z) = E Szi and zx(z) = EXizj. j=1 j=1 Multiply equation (8) by zi and sum over the range j > 1 to obtain Si(Z) = xi(Z) + Si_1(z) + ZS- i(Z). Solving for si(z) gives an expression in terms of si_-(z) and xi(z): m i 8i(Z) = -— 7- - ^i(Z)- i+ - - 1i(Z). m- (m- i)z m - (m - i)z 6

Substitute for sil(z) on the right side of this expression, then substitute for si-2(z), and so on. We have si(Z) = aik(Z)X(Z) (9) k=O where = (z_) _nmi(i- 1)... (k + 1) ( ak(z) (n- (m- - i)z)((m- (m - i + 1)z) -- (m - (m - k)z)'0) It is instructive to use (9) and (10) to compute Tm,1, which, recall, is the expectation in the birthday problem for a year with m days. Take Xij = 1 for i > 0 and j > 0. Then Tml is the linear coefficient of sm(Z) and hence is the sum of the constant coefficients of amk. Thus, T 1 ++ m- + (m- )(m-2) + (m- )(m- 2)..-1 Ti1-l+ 1+ —- + + —-+ m m2 Mmm-I We may regard this as a function of m. The function Tm, - 1 is the Ramanujan Q-function. Tm,i is the linear coefficient of Sm(z) and thus is just the first of a family of functions given by the successive coefficients of Sm(Z). The techniques used by Knuth and others to obtain the asymptotics of coefficients of the Q-function do not seem to extend easily to other functions in the family. In a later section we will develop other asymptotic methods to deal with these functions. Let us return to our analysis of (9) and (10). By partial fraction decomposition ak(z) = -1),-kk) ( ) (- 1 m- ) z) I=k i - I, I - 5, m m Thus, *I / 4 \ / \ ~~-k+* [z]aik(Z) = 1 i- - 11-k,k) ( and consequently i j-1 sij = E ([Iz ai,k(Z))([Zj-']Xk(Z)) k=O r=O i J-l i i i-k+r Z E E(- 1)'i- I-k ) (-) (11) k=0 r=0 =k m/ = (Ec) Xkj- ) (1-~1 1=0 k=O k - —, 1 k, k i /\ I fI I \1-k1- -lir = ExorE ( ) E ( -1 (i Xkj - r=1 1=1 \/ k=O m / This appears a little cumbersome, but for many choices of Xi,j there is a considerable simplification. In particular, if Xij can be written as a product Xij = Yi Zj then we can write Si, = Yo E Z + ) I-' (),(-I,)'-k E fZjrI (12) r=l /=1 V kt=O0' r=O

where I, = 1 - I/m. The sums 0 ()Y(-I)I-k and E,- ZjrI can then be evaluated separately. Results below follow in this way. It is convenient to introduce the notation c(p, q)- (I) m 1 - m (13) Note that c(p + 1, + 1) = ci(p + 1, q) - c,(p, q). In the next section we explain how ci(p, q) may be computed in closed form for some values of p and q. Theorem 3.1 We have the following expressions for expected deadlock time, expected total processing time, and expected number of resources allocated at deadlock time. (i) Ti, = 1 + (c(1, 0)-c,(1, j))/j. (ii) Pi,, = (j + 1)/2 + ci(l, 0)- (c(2, 1)- c(2,j + l))/j. (iii) Rij = c,(l, 0) - (c,(2, 1) - c(2,j + l))/j. Proof. For (i) take Xij = 1 in equation (3) so that t = Zj = 1. Use the Binomial Theorem and summation of geometric series to obtain T /j = 1 + n - m/) Similarly, (ii) and (iii) follow from the identities'=o V"'/ (k k(-II =I(1-It (14) j-1 + 1,-H(j =1' - r(15) which are derived by standard techniques. 0 Parts (ii) and (iii) of the theorem already provide useful information about system behavior. The expected total processing time Pij is the also the expected number of requests since the request arrival time for each process is 1. The difference between this value and Rij,, the expected number of resources allocated, is the expected number of processes blocked by deadlock time. We see that this quantity is always (j + 1)/2, one half more than half the number of initially active processes. Thus, we have the following surprising result about system performance. Theorem 3.2 (The Half and Half Theorem) Beginning from any state with j active processes, the expected number of these processes blocked by deadlock time is (j + 1)/2. There is an easier way to prove the Half and Half Theorem. The theorem is clearly true when j = 1. Now suppose the system is in a state where the number j of active processes is more than one and assume the Half and Half Theorem holds for states with j- 1 processes. 8

The system may change states a number of times before it changes from a state with j active processes to a state with j - 1 active processes. Let us call state changes where the number of active processes decreases critical A system can deadlock only at a critical state change. The probability of deadlock at the first critical state change is 1/j; in this event just one of the original processes is blocked. The probability, then, that deadlock does not occur at the first critical state change is (j - 1)/j; in this event the system enters a state with j - 1 active processes and the expected number of remaining processes that will be blocked by deadlock time is j/2, by the induction hypothesis. Thus, the expected number of processes blocked by deadlock time is (1/j) + (1 + j/2)(j - l)/j = (j + 1)/2. Using these ideas we can determine how many processes must be blocked for the probability of deadlock to exceed 6 > 0. The probability of reaching deadlock after k critical state changes is 1 j-1 1 j-lj-2 1 j-lj-2 j-k+ 1 1 k j j j-1 j j-lj 2 j -1 j-k+2j-k+l j so we set k = 6j. We have the following result Theorem 3.3 If we allow a system with j initially active processes to operate until 6j of those processes are blocked, the probability that deadlock has occurred is 6. Before concluding this section, let us explore another consequence of equation (11). Consider the case where i = m, that is, where all resources are initially free. Changing the order of summation we have j-1 m M /m\k k+r Smj'= m () } )_l) [ 1) r —=O =0 1=0 V m/ ZLj m m-k k Xm-kj-r r=O k= { The last equation follows from formula (6.19) of Graham, Knuth, and Patashnik [8]. While this is a more pleasing form than equation (12) (and shows, in particular, that Smj is a positive linear combination of the quantities Xk,r), it is not as useful. 4 Evaluation of Abel Sums. Abel's identity is expressed in several different forms in the literature. Here is one of them (see Riordan [16, page 18]): X=E O ( + y + i - l)i^1 = (x + y + i)i. It follows immediately that E ( + l)-(y + i- )- = (X + y + i)'- (y + i) 9

Taking the limit as x approaches 0 we have E (1)1-1(y + i -1- = i(y + j)i-l 1=0 If we put y = m - i and divide by mi"1 we have one of the cases of (13) needed to evaluate the expression in Theorem 3.1(i), viz., c(l,0) = i. Riordan [16, pages 18-23] considers several generalizations of Abel's identity. These give some of the other cases c(p, q) by the same argument. (N.B. There are some typographical errors in Riordan's formulas.) However, in order to get good asymptotic results we must develop a more general theory for expressions of the form C(p q y) = E ( P(Y + i - I)/ 1=1 \/ and then evaluate ci(p, q) = Ci(p, q, m - i)/mi-P+. First note that Ci(p, q, y) is a convolution. Let oo k-p (y+k)k+q fp z) = E k- z and () + k)=+ ~i k=l k=O (If p = 0 then it will be convenient to begin the summation for fp(z) at k = 0 rather than k = 1 so that the constant coefficient is 1.) Then Ci(p,q,y)= [/ili!]fp(z)gq(z). The function fi(z) = f(z) is well known in combinatorial enumeration. A standard textbook application of the Lagrange Inversion Formula is to show that f(z) is the solution of the functional equation f(z) = zef(z) (see Wilf [20]). If we differentiate both sides of this equation, substitute ef() = f(z)/z, and solve for f'(z) we have zf'(z) = f(z)/(l - f(z)). Thus, f2() = f) dx = (i - f())'() dx = f(z) - f(Z)2, from which it follows that f2 (X) fZ!f)x)3 21 3 f3(2) = X r ( d:= X (1-(x) (1- f(x))f'() dx = f(z)-f(z) + z) If we use the Lagrange Inversion Theorem to compute the coefficients of eyf(z) and then substitute f(z)/z for eyf() we have = 0z - (y + y+k Differentiate, multiply by z, and replace zf'(z) with f(z)/(l - f(z)). We obtain g() = E (y + k)kZk f ) 1 It follows that Ez- Z +1 10 f 1 10~~~~~~~~~te

and so Ci(l,0, y) = i(y + i)'-. A similar evaluation of f2(z)go(z) and f3(z)go(z) shows that 2 C,(2,0,y) = i(y+ i)'- -iI(y+ i)-2, Ci(3, 0, Y) = i(y + i)- iy + i)'-2 + y + i)-3. We can use the method above to compute values of Ci(p, 0, y) whenever p > 0. We can show easily by induction that p fp(Z) = Z Dp,kf(Z)k k=1 where for all positive p, Dpal = 1 and Dp+,k+I = (Dp,k+ - Dp,k)/k. These coefficients are the "differences of reciprocals of unity" appearing on page 248 of David, Kendall, and Barton [2]. (This source was located with the help of Sloane [17]; cf. sequences 2049 and 2305.) It follows that p Ci(p,, y) = E DP, i(y + i)i-k. k=1 We can now compute the values of c,(p, q) when p > q > 0. The first few values are as follows. c,(1,0) = i, c,(2,0) = im- i(i- ) ci(3,0) = ia 3i(i - + i(i-)(i-2) 4 6 ci(2,1) = ci(2, 0) - c(1,0) = im r 2 - ) c,(3,1) = c,(3,0)- c(2,0) = im2 (3i + 1)i ( + )i(i- 1) 4 6 c,(3,2) = ci(3,1)- c(2,1) = im2 (3i + 5)i+ (i + 2)(i + )i 4 6 In general, p Cj(p, 0) = E D,, i-km k=l and values of ci(p, q) for 1 < q < p are obtained by differencing. Substituting these values for ci(p, q) into Theorem 3.1 we have the following theorem giving expressions for various system statistics in terms of Abel sums. Theorem 4.1 The expected deadlock time, expected total processing time, and expected number of resources allocated at deadlock time are as follows. (i) Ti = 1 + i/j - c,(1,j)/j. (ii) Pij = (j + 1)/2 + i - im/j + i(i + 1)/2j + c(2,j + l)/j. (iii) Ri.j = i - im/j + i(i + 1)/2j + c,(2,j + 1)/j. 11

From equation (13) we see immediately that c(1l,j) < ci(1,0) and c(2,j+ 1) < c,(2, 1) so we have the following important corollary. Corollary 4.2 The expected deadlock time, expected total processing time, and expected number of resources allocated at deadlock time satisfy the following inequalities. (i) 1 < Tij _ 1 + i/j. (ii) (j + 1)/2 + i - im/j + i(i + 1)/2j < Pj < (j + 1)/2 + i. (iii) i - im/j + i(i + 1)/2j < Rij < i. The first of the these inequalities suggests that we may want to do deadlock detection at regular intervals rather than at each change of the system state. It shows that even in the worst possible circumstance where resources are never released, expected deadlock time is never less than 1. There is an absolute lower bound for expected deadlock time. 5 Systems with Many Processes. The case of systems with many processes is important for applications. This occurs, for example, when i, the number of free resources, is much less than j, the number of active processes. A few of our results require slightly stronger assumptions, either that m, the total number of resources, is much less than j or that m log log m is less than j. The following result is an immediate consequence of Corollary 4.2. Theorem 5.1 Suppose that a system that begins from a state with m resources, i free resources, and j active processes. (i) (Expected deadlock time.) If i = o(j), then Tij ~ 1. (ii) (Expected total processing time.) If i = o(j) and m = O(j), then Pij, j/2, (iii) (Expected number of allocated resources, and system efficiency.) If m = o(j), then Rij i, and Fij = Pi,j/jTi, 1/2. We see that a system with many processes performs well; it assigns nearly all resources before deadlock and even though most requests result in a blocked process (since the total number of requests is asymptotically j/2 which is much larger than i, the number of resources allocated) system efficiency is still reasonably good. Now let us consider the variances of Tij and Pij. The proofs are more involved so we state the results separately. Theorem 5.2 In a system that begins from a state with m resources, i free resources, and j active processes, if mloglog m = O(j), then the variance of deadlock time approaches 1. Proof. We must first obtain bounds on Uj, the mean square of Tij. Recall from Figure 2 that we take Xi, = 2Ti,j in equation (8). Direct substitution gives a very complicated expression, so we substitute instead the lower and upper bounds given by Corollary 4.2. 12

First, let us derive a lower bound. Let Atj = 2 in equation (8). Then we have immediately from Corollary 4.2 that Sij/j is at least 2. To obtain an upper bound we need to solve (8) when Xij = 2 + 2i/j. By linearity, we may solve the cases where Xij = 2 and Xij = 2i/j separately. In the first case Sij/j has an upper bound of 2 + 2i/j by Corollary 4.2. In the second case an explicit solution seems difficult. Instead, we obtain estimates on equation (12) with Yi = 2i and Zj = 1/j. By equation (14) we have (:)l 2 1 A 1r iI: o ----- = 1iE (I) (m) (:m) j —r m) 1=k3)krn)1rn) r=O j r Recall that E()r (-) (1- -) = Ci(lO)= i1 Thus, Sij j is a weighted average of the values 2i11 1 ( I 3 EX-r ( m) (16) j -"j-r m where I ranges from 1 to i. These values can be expressed as [zJ]g1(z) where 2il log(l - z) 1- (1- /m)z' We will show that (16) is o(l) uniformly in I as j -- oo. We do this using ideas related to singularity analysis originally formulated by Darboux (see Henrici [9] and Flajolet and Odlyzko [7]). The dominant singularity of gz(z) is a logarithmic singularity at z = 1 and the only other singularity is at z = 1 + l/(m - I). Apply Cauchy's formula to obtain [z-g(z) = il log( 1 - ) dz. (17) [ z ]g(' — j (1 - (1 - ilm)z)zj+l We choose a contour r consisting of several parts and bound the integral on each part (see Figure 3). Let S vary with j so that 0 < -61og < 1/j. Take e = 1/2(m - 1) and let 77 > E be a fixed constant. r consists of six pieces ri,..., F6. 7r is a circle of radius 6 centered at 1 taken clockwise beginning at 1 + 6. r2 is a line segment from 1 + 6 to 1 + e. r3 is a line segment at an angle of 7r/3 beginning at 1 + e ending at a point on the circle of radius 1 + 7 centered at 0. We obtain r4 by following this circle counterclockwise from this point to its conjugate. r5 is a reflection of r3 through the real axis, but with reversed orientation. r6 is r2 with reversed orientation. Note, however that we use the principal branch of log z. That is, the complex plane is slit from 1 to oo with r2 and r6 on opposite sides of the slit. Let us derive bounds on factors of the integrand in (17). First note that r was chosen so that it does not come close to the point 1 + l/(m - 1); for j sufficiently large the distance is always at least l/2(m - 1) so for all z on r 1 2m 1-(1-/m)z - I 13

Figure 3: Contour for Evaluation of Uj Also, log(l - z) < -log 1i - zI + Xr everywhere on r with the possible exception of some points on r4. For ri we take z = 1 - be —e for -ir < 0 < ir so (1 - b)i < Izil (1 + 6)i and fzli approaches 1 uniformly. Thus, (17) is bounded in modulus by a constant multiple of 4im6(- log + r)/j which approaches 0 as j increases. Next combine the contributions to (17) from r2 and r6. These two contours are the same, except for orientation, but the branches of log(l - z) used differ by -27r/ —T. Therefore, the total contribution is 2il fr+ dx < 4im rf+ dx 4im J+6 (1 - (1 - l/m)x)xj+l ~ J 1+^ j+ j which approaches 0 as j increases. Next, for r3 we take z = 1 + e + xev1l/3 where x ranges from 0 to a value slightly less than 2(yr - e) - the exact value is not crucial. Notice that - log(l - z) attains its maximum modulus on this contour when x = 0 and it is less than log m there. Notice also that Izi > 1 + e + x/2 on r3 so the contribution is bounded by 4imlogmjo~ dx 4imlogm ( I x 4imlogm j/m j(1+~+x^ ~+) j2 kr2) log / (1 + e + x+l= j 1- < j2 eI l which approaches 0 since m log log m < j. We obtain a bound on r5 in exactly the same way. Finally, on r4 we see that the modulus of the denominator of the integrand grows exponentially in j and the numerator is bounded, so the contribution to (17) approaches 0. We conclude that Ui, ~ 2 and hence that the variance of Tij approaches 1. 0 14

The log log m factor in the preceding theorem is somewhat annoying. It seems likely that it can be eliminated. Note that the only place in the proof where we used this condition, rather than the weaker assumption that m = o(j), was in bounding the integral on r3 and r6. We could instead have used the condition that i < m/log m. Theorem 5.3 In a system that begins from a state with m resources, i free resources, and j active processes, if i = o(j) and m = O(j), then the variance of total processing time is asymptotic to j2/12. Proof. We begin similarly to the proof of the previous theorem. We obtain bounds on Q5j, the mean square of Pij by substituting the lower and upper bounds given by Corollary 4.2. For the lower bound we take Xij = j(j + 1) + 2ij - 2im + i(i + 1) in equation (8) and for the upper bound we take Xij = j(j + 1) + 2ij. Thus, by linearity, we have four cases to consider. Case 1: Xj = j(j + 1). In (12) we let Y, = 1 and Zj = j(j + 1). Use the identities fr(r+ 1) =j(j + l)(j+ 2)/3, r=1 and j-1 12 +2 (j - r)(j-r + 1)I = (j + 1) 2 2 1 - +2 r'0 (1- I,)2 (1 -I)3 to obtain S/jl = (j + 1)(j + 2)/3 + (j + 1)cj(l,0) - 2ci(2, 1) + 2(ci(3, 2) - c(3, j + 2))/j. Case 2: Xij = 2ij. In (12) we let Y1 = 2i and Zj = j. We have from (14) and (15) that Stirling'sSij/j = 2mc(1, 0)- 2m(c(2, 1)- ci(2,j + 1))/j. Case 3: X, = -2im. In (12) we let Y, = -2im and Zj = 1. We have Si,lj = -2m2(c(, O) - c(1,j))/j. Case 4: X,j = i(i + 1). In (12) we let Y, = i(i + 1) and Zj = 1. Use the identity 4E flk k(k + 1)(- )-k = 1(1 - 1)(1 - I)'-2 + 21(1 - I,)'to obtain Si,/lj = (m2 + m)(c,(l,0)- c,(l,j))/j - m(c(2, 0)- c,(2,j))/j. A lower bound for Si/jj in case 1 is (j + 1)(j + 2)/3 + i(j + 1) - 2im + i(i + 1). 15

Add the values of Sij/j for cases 2, 3, and 4. Using the identities for ci(p, q) developed in section 3 we have 2im - 3m(c,(2, 1)- c,(2,j + l))/j - (m2 - m)(c,(1, O)- c(l1,j))/j. A lower bound for this is 2im - 4im2/j + i(3i + 5)m/2j. Thus, taking all the cases together we have a lower bound for Qij of (j + 1)(j + 2)/3 + i(j + 1) + i(i + 1) - 4im2/j + i(3i + 5)m/2j. To obtain an upper bound for Qij, add the values of Sij/j in cases 1 and 2. This is less than (j + 1)(j + 2)/3 + i(j + 1) + i(i + 1) + 2im2/j - i(3i + 5)m/2j + (i + 2)(i + 1)i/3j. We see that under the hypotheses of the theorem that Qij t j2/3. The square of the mean of P,j is asymptotic to j2/4 so the variance is asymptotic to j2/12. 0 These two results on the the variance of Tij and Pit,j show that we must be cautious if we consider doing deadlock detection only at regular intervals in systems with many processes. Even though deadlock time and total processing time have reasonable means, their standard deviations are constant multiples of their means. For design purposes we would like to have more information about the distributions of these random variables. We have not yet succeeded in determining the distributions explicitly. Perhaps simulations would give some insight. We will make some brief comments about the distributions in the last section. 6 Systems with a Fixed Number of Processes. Systems with a fixed number of processes are also important for applications. We will need more sophisticated asymptotic techniques than in the last section to carry out the analysis of these systems. We will also need to restrict to the case i = m, i.e., the case where all resources are initially free. By Theorem 4.1 we see that we need to determine asymptotic expansions of cm(1,j) = [zm/m!](f(z)fj(z)/mm+j-l) and cm(2,j + 1) = [zm/m!](f2(z))f_-j l(z)/mm+i -). We first need to find the singular expansions of the functions fp. The singular expansion of fi(z) = f(z) can be derived without too much difficulty from the Implicit Function Theorem and the defining equation f(z) = zef(z). Set g(z, w) = w - zew and note that w = f(z) is the solution of g(z,w) = 0. Now g(l/e, ) = (9g/Qw)(1/e,w) = 0 and (02g/Ow2)(1/e, 1) $ 0, so f has an algebraic singularity of of order 1/2 at z = 1/e. Let 6 = (2 - 2ez)1/2 (the 21/2 factor is to simplify succeeding expressions) so z = (2 - 2)/2e. Substituting into the equation g(z, w) = 0 we have 6 = (2 - 2we'-w)l/2. That is, f, considered as a function of 6, satisfies 6 = (2 - 2f(,)el-f(6))'/2. In this context, f is the functional inverse of h(w) = (2 - 2wel'")1/2. It is a simple matter to compute the Taylor 16

expansion of h and then of its inverse (in Maple, the reversion operation accomplishes this). We obtain / l 1 11 3 747695+.... f(z)= -+3 72 540 17280 A similar derivation of this formula can be found in Flajolet and Odlyzko [6]. The singular expansion of f2(z) = f(z)- f(z)2/2 can now be seen to be 1 162 + 13 564 + 47.. f2(z) -2 2 3 24 3-60 Note that application of the operator z(d/dz) to fj(z) gives fj_l(z). Now z(d/dz)m = -m6m-2 + mnm/2 so 1 2 1 2 23 fo(z) = 6-+ + T 2 _ + 3 6 + 3 24 135 3456 f_l(z) = 6-3 116-1 4 24 135 1152 In general, 0o f-j W L bjkbk /- ()= E bi6 k=-2j-1 where bj,k = kbj-l,k/2-(k+ 2)b6l,k+2. We can solve this recurrence first for the coefficients bj,-2j-l, then for the coefficients bj,-2j and so on. For j > 2 we have f j(Z) = j!! (^-2j- 122 - 1 _-2j+1 + 144j4 - 384j + 264j2 - 23 2j+3 + fj(z) =j! (1j-I24(2j -1)' 1152(2j- l)(2j- 3) Thus, f(z)f_(z) = 6-3_ 62 _ + 149 767 + 8 540 17280 f(f _j(z) = (-2j-1 -_ -2j 12j2 - 16j + 7 2j+1 18j2 - 11j + 4^2j+2 24(2j'- 1) - 36(2j - 1) 2160j4 - 11520j3 + 18104j2 - 10528j + 3063_2j+3 17280(2j - 1)(2j - 3) for j > 2, and f2(z)f_,j_-() = (j + 1)(6 - 12j2j- + 35 -2j-1 + 1f2(Z)f.-1(z) = (j +1)!! (-623 482j+) 2 48(2j + 1) 3 144j4 + 1344j3 - 216j2 - 144j - 476_2j+l + 2304(2j + 1)(2j - 1) for j > 1. By the Binomial Theorem and formula [zm/m!]6-~ is r1/2 mm+(a-1)/2 3a2 - 6a + 2 9a4 - 60a3 + 120a2 - 72a + 4 ( 1 r(a/2) 2(@-1)/2 k 24m 1152m2+ m3 17

Substituting this into the expressions above and simplifying, we have (27r)'21/2 1 (2ir)1/2 4 - Cm(1, 1) = m- m(2l 1/2 + - 2- 2+ -'1 + O(m-3/2) 2 3 24 3135 21/2r(j + 1/2) 12 + 2j - 1 21/2r(j + 1/2) 4j2 - 6j + 5 1/2 r(j) 3 36r(j) 2j- 1 2j2 - 4j -6 + 1 2 2j + 21/2r( +12)2j + 1 1/2 j 2 cm(2,j + 1) -= Mn+ _m + O(m-1/2) ~~2 2 r~(j) 3 3 The asymptotic formula for c,(l,1) agrees with equation (25) in section 1.2.11.3 of Knuth [10]. Our approach seems somewhat simpler since it does not require analysis of the incomplete gamma function. From Theorem 4.1 we now have the main result of this section. Theorem 6.1 Fix j. For systems beginning from a state with j processes and all resources free, we have the following asymptotic formulas for expected deadlock time, expected total processing time, expected number of resources allocated at deadlock time, and system efficiency. T.,, = (2^ ^ +j+(2~ 22?r), Tm,1 (27r) /2 l1/2+ 2 + (27r)/2 -2 _ 4m + O(m-3/2) 2 3 24 135 T = 2'/2Pr(j + 1/2)m /2 j + 1 21/2(4j2 - 6j + 5)r(j- 1/2) 1/2 (j + 1) 3j 72F(j + 1) + 22- 4j-6 m +0(m-3/2), when j > 2!35j 23/2r(j + 3/2)m12 j + 3 -2 2I r(j + 3/2)1 + O(m Rmj = 32j+/2 ) + O(m-1/2),'O = 3r(j + 1) 3- 2 1 Fm, 2= + 1 + O(m-112). 3j Thus, we find that for a fixed number of processes, deadlock time, total processing time, and number of resources allocated are asymptotic to a constant multiple of m1/2. System efficiency always approaches a value greater than 2/3. This seems very promising. Unfortunately, we have not yet determined the order of the variances for deadlock time and total processing time and we have no idea of the distribution. 7 Conclusions. Our results suggest that it may be worthwhile to investigate doing deadlock detection at regular intervals in some systems. The most compelling evidence for this is the absolute lower bound for expected deadlock time (Corollary 4.2(i)). Also, the high values for system 18

efficiency for systems with many processes (Theorem 5.1(iii)) and systems with a fixed number of processes (Theorem 6.1) are encouraging. If we knew the distribution of deadlock time Ti we could determine, for a given 6 > 0, the length of time the system must operate for the probability of deadlock to be 6. We could then compare the cost of continuously updating to do deadlock detection versus the expected cost of resolution and rollback when doing deadlock detection at regular intervals. Even though we do not know the distribution, Theorem 3.3 provides a similar, but less satisfactory, approach. We can count blocked processes. Unfortunately, this requires some communication between processes and could therefore cost more than waiting for some fixed time interval. What do we have to do to determine the distribution of deadlock time Tij as i or j increase? A standard approach for determining the distribution of a limit random variable is to find its characteristic function (see Feller [3]). From equation (1) we have the following recurrence for the characteristic function TiJ, of Tij: _ - izlj im m Ti J = 1- / j ( mA+ ) 1) TiJ-1 + 1-m ) J)' This may lead to a solution, but it does not seem to work well with the generating function methods used here. There are other important questions still to be answered. First, the absolute lower bound we derived for expected deadlock time, although theoretically optimal, certainly does not come near what occurs in practice. The most obvious reason for this is that processes do release resources in multiprocessing systems so deadlock time is usually much greater than than in the model here. We need to develop a more realistic model, but this will not be easy. It will require adding a queueing theoretical dimension to the combinatorial problem of determining when cycles emerge in certain kinds of random bipartite graphs. Second, we need to deal with the problem of 2-cycles mentioned in section 2. We would expect processes to remember the resources allocated to them and to avoid making duplicate requests. As we noted, iwe e prohibit 2-cycles, then it is no longer clear what is meant by expected deadlock time. It is also not clear how to modify the model. Should we proceed as before with a process randomly choosing a resource but have the system to continue in case a-cycle arises? Or shoud we require a process to choose randomly among resources not allocated to it? In either case, the model becomes much more complicated. We must keep track not only of the number of active processes, but also of the number of resources allocated to each active process. In addition to the cases in sections 4 and 5, we would like to have asymptotic expressions for system statistics when i = Kj. We would like to know in section 4 if conditions like m = o(j) and m log log m = o(j) can be replaced with i = o(j). We would like to solve the general case in section 5, not just the case i = m. Finally, we would like to know the variances of Ti,J and Pi,j for fixed j. As far as we know this has not been determined even in the case j = 1. This is closely related to the problem of determining the variance of the birthday problem. (Even though the mean of Tmi1 is the expected number of people needed to find a pair with the same birthday, variance behaves differently. The model with one process is like a person standing on a 19

busy street corner asking passers-by their birthdays until a repetition is found.) The first author has used the birthday problem in data structure classes (of at least 24 students) to illustrate hash table collisions. He has always been uneasy about this, however, because he does not know the variance of the birthday problem random variable. Fortunately, the demonstration has always worked. This is probably a good omen for deadlock detection. Acknowledgements. We would like to thank Philippe Flajolet for many useful suggestions and discussions. We would also like to thank Yuri Gurevich and Andreas Blass for making a fundamental observation that led to the development of the the model in equation (1). The first author would like to express his appreciation to the Institut National de Recherche en Informatique et en Automatique and l'Ecole Polytechnique for partial support during the period this research was done. He would also like to thank the members of Projet Algo at INRIA for providing a supportive research environment and good camaraderie in the 1991-92 academic year. Finally, both authors would like to thank the creators of Maple system. Most of the computations in this paper were carried out or checked in Maple. References [1] A. L. CAUCHY, Exercises de Mathematique, Chez de Bure Freres, Paris, 1826. [2] F. N. DAVID, M. G. KENDALL, AND D. E. BARTON, Symmetric Function and Allied Tables, Cambridge Univ. Press, 1966. [3] W. FELLER, Introduction to Probability Theory and its Applications, vol. 2, Wiley, New York, 1971. [4] P. FLAJOLET, D. GARDY, AND L. THIMONIER, Probabilistic languages and random allocations, in Automata, Languages and Programming, T. Lepisto and A. Salomaa, eds., vol. 317 of Lecture Notes in Computer Science, Springer-Verlag, 1988, pp. 239253. [5] P. FLAJOLET, P. J. GRABNER, P. KIRSCHENHOFER, AND H. PRODINGER, On Ramanujan's Q-function. preprint. [6] P. FLAJOLET AND A. M. ODLYZKO, Random mapping statistics, in Advances in Cryptology, J.-J. Quisquater and J. Vandewalle, eds., vol. 434 of Lecture Notes in Computer Science, Springer-Verlag, 1990, pp. 329-354. [7], Singularity analysis of generating functions, SIAM J. Discrete Math., 3 (1990), pp. 216-240. [8] R. L. GRAHAM, D. E. KNUTH, AND 0. PATASHNIK, Concrete Mathematics, AddisonWesley, Reading, Mass., 1989. [9] P. HENRICI, Applied and Computational Complex Analysis, vol. 2, Wiley, 1977. 20

[10] D. E. KNUTH, The Art of Computer Programming, vol. 1: Fundamental Algorithms, Addison-Wesley, Reading, Mass., second ed., 1968. [11] -, The Art of Computer Programming, vol. 3: Sorting and Searching, AddisonWesley, Reading, Mass., 1973. [12] -, An analysis of optimum caching, J. Algorithms, 6 (1985), pp. 181-199. [13] D. E. KNUTH AND A. SCHONHAGE, The expected linearity of a simple equivalence algorithm, Theoret. Comput. Sci., 6 (1978), pp. 281-315. [14] J. LYNCH, Random resource allocation graphs and the probability of deadlock. preprint. [15] S. RAMANUJAN, Question 294, J. Indian Math. Soc., 4 (1912), pp. 151-152. [16] J. RIORDAN, Combinatorial Identities, Wiley, New York, 1968. [17] N. J. A. SLOANE, Handbook of Integer Sequences, Academic Press, San Diego, 1973. [18] A. S. TANENBAUM, Operating Systems: Design and Implementation, Prentice-Hall, Englewood Cliffs, N.J., 1987. [19] J. S. VITTER AND P. FLAJOLET, Analysis of algorithms and data structures, in Handbook of Theoretical Computer Science, J. van Leeuwen, ed., vol. A: Algorithms and Complexity, North Holland, 1990, pp. 431-524. [20] H. S. WILF, generatingfunctionology, Academic Press, San Diego, 1990. [21] A. C.-C. YAO, On the average behavior of set merging algorithms, in Proc. 8th ACM Symp. on Theory of Computing, New York, 1976, Association for Computing Machinery, pp. 192-195. 21