Journal of the Association for Computing Machinery, Vol. 42, No. 3, May 1995, pp. 562–583.

Expected Deadlock Time in a Multiprocessing System

KEVIN J. COMPTON

AND

CHINYA RAVISHANKAR

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 number of processes. In the latter, generalizations of the Ramanujan Q-function arise. We use singularity analysis to obtain asymptotics of coefficients of generalized Q-functions.

Categories and Subject Descriptors. D.4.1 [deadlocks]; [multiprocessing/multiprogramming]; F.2.2 [computations on discrete structures]; G.2.1 [generating functions]; G.2.2 [path and circuit problems]

General Terms. Theory

Additional Key words and Phrases. Asymptotic analysis, expected time analysis, singularity analysis

Copyright 1995 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.