%%% ====================================================================
%%% @LaTeX-file{
%%% filename = "comptonr95.ltx",
%%% date = "20 November 1995",
%%% time = "21:41:34 EST",
%%% author = "David M. Jones",
%%% email = "jacm@theory.lcs.mit.edu",
%%% url = "http://theory.lcs.mit.edu/~jacm/",
%%% address = "Journal of the ACM
%%% MIT Laboratory for Computer Science
%%% Room NE43-316
%%% 545 Technology Square
%%% Cambridge, MA 02139
%%% USA",
%%% telephone = "(617) 253-5936",
%%% FAX = "(617) 253-3480",
%%% checksum = "56623 107 447 3765",
%%% codetable = "ISO/ASCII",
%%% supported = "yes",
%%% docstring = "Copyright (c) 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.
%%%
%%% This is a LaTeX2e file. To process it, you will
%%% need a copy of the acmabs document class, which is
%%% available via the following URL:
%%%
%%% http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%% ",
%%% }
%%% ====================================================================
\documentclass{acmabs}
\begin{document}
\Journal{Journal of the ACM}
\refkey{ComptonR95}
\title{Expected Deadlock Time in a Multiprocessing System}
\author{Kevin~J. Compton \and Chinya Ravishankar}
\Pages{562--583}
\Month{May}
\Year{1995}
\Volume{42}
\Number{3}
\maketitle
\begin{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.
\end{abstract}
\begin{categories}
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]
\end{categories}
\begin{terms}
Theory
\end{terms}
\begin{keywords}
Asymptotic analysis, expected time analysis, singularity analysis
\end{keywords}
\end{document}