AbstractWe 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. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: D.4.1 [Operating Systems]: Process Management -- deadlocks; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures; G.2.1 [Discrete Mathematics]: Combinatorics -- generating functions; G.2.2 [Discrete Mathematics]: Graph Theory -- path and circuit problems
General Terms: Theory
Additional Key Words and Phrases: Asymptotic analysis, expected time analysis, singularity analysis
Selected papers that cite this one
- James F. Lynch. Infinitary logics and very sparse random graphs. The Journal of Symbolic Logic, 62(2):609-623, June 1997.
- A. Viola and P. V. Poblete. The analysis of linear probing hashing with buckets. Algorithmica, 21(1):37-71, May 1998.
Selected references
- Andrew Chi-Chih Yao. On the average behavior of set merging algorithms (extended abstract). In Conference Record of the Eighth Annual ACM Symposium on Theory of Computing, pages 192-195, Hershey, Pennsylvania, 3-5 May 1976.