Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-23T08:35:44.340Z Has data issue: false hasContentIssue false
  • English
  • Français

Sojourn time distribution in some processor-shared queues

Published online by Cambridge University Press:  26 September 2008

Xiaoming Tan  and
Charles Knessl
Xiaoming Tan
Affiliation:
Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago (M/C 249), PO Box 4348, Chicago, IL 60680, USA
Charles Knessl
Affiliation:
Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago (M/C 249), PO Box 4348, Chicago, IL 60680, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

We develop a technique for obtaining asymptotic properties of the sojourn time distribution in processor-sharing queues. We treat the standard M/M/1-PS queue and its finite capacity version, the M/M/1/K-PS queue. Using perturbation methods, we construct asymptotic expansions for the distribution of a tagged customer's sojourn time, conditioned on that customer's total required service. The asymptotic limit assumes that (i) the traffic intensity is close to one for the infinite capacity model, and (ii) that the system's capacity is large for the finite capacity queue.

Type
Research Article
Information
European Journal of Applied Mathematics , Volume 4 , Issue 4 , December 1993 , pp. 437 - 448
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Coffman, E. G., Muntz, R. R. Jr & Trotter, H. 1970 Waiting time distributions for processor-sharing systems. J. ACM 17, 123–130.CrossRefGoogle Scholar
[2]Morrison, J. A. 1985 Response-time distribution for a processor-sharing system. SIAM J. Appl. Math. 45, 152–167.CrossRefGoogle Scholar
[3]Mitra, D. & Morrison, J. A. 1983 Asymptotic expansions of moments of the waiting time in a shared-processor of an interactive system. SIAM J. Comput. 12, 789–802.CrossRefGoogle Scholar
[4]Mitra, D. & Morrison, J. A. 1983 Asymptotic expansions of moments of the waiting time in closed and open processor-sharing systems with multiple job classes. Adv. Appl. Prob. 15, 813–839.CrossRefGoogle Scholar
[5]Morrison, J. A. & Mitra, D. 1985 Heavy usage asymptotic expansions for the waiting time in closed processor-sharing systems with multiple classes. Adv. Appl. Prob. 17, 163–185.CrossRefGoogle Scholar
[6]Morrison, J. A. 1986 Asymptotic analysis of the waiting-time distribution for a large closed processor-sharing system. SIAM J. Appl. Math. 46, 140–170.CrossRefGoogle Scholar
[7]Morrison, J. A. 1986 Moments of the conditioned waiting time in a large closed processor-sharing system. Commun. Statist.-Stochastic Models 2, 293–321.CrossRefGoogle Scholar
[8]Morrison, J. A. 1987 Conditioned response-time distribution for a large closed processor-sharing system in very heavy usage. SIAM J. Appl. Math. 47, 1117–1129.CrossRefGoogle Scholar
[9]Morrison, J. A. 1988 Conditioned response-time distribution for a large closed processor-sharing system with multiple classes in very heavy usage. SIAM J. Appl. Math. 48, 1493–1509.CrossRefGoogle Scholar
[10]Gaver, D. P. & Jacobs, P. A. 1986 Processor-shared time-sharing models in heavy traffic. SIAM J. Comput. 15, 1085–1100.CrossRefGoogle Scholar
[11]Knessl, C. 1990 On finite capacity processor-shared queues. SIAM J. Appl. Math. 50, 264–287.CrossRefGoogle Scholar
[12]Knessl, C. On the sojourn time distribution in a finite capacity processor-shared queue, (to appear in J. ACM).Google Scholar
[13]Rege, K. M. & Sengupta, B. 1985 Sojourn time distribution in a multiprogrammed computer system. AT&T Technical J. 64, 1077–1090.Google Scholar
[14]Bender, C. M. & Orszag, S. A. 1978 Advanced Mathematical Methods for Scientists and Engineers. McGraw-Hill.Google Scholar
[15]Kevorkian, J. & Cole, J. D. 1981 Perturbation Methods in Applied Mathematics. Springer-Verlag.CrossRefGoogle Scholar
[16]Ramaswami, V. 1984 The sojourn time in the GI/M/1 queue with processor sharing. J. Appl. Prob. 21, 437–442.CrossRefGoogle Scholar
[17]Ott, T. J. 1984 The sojourn time distribution in the M/G/l queue with processor sharing. J. Appl. Prob. 21, 368–386.CrossRefGoogle Scholar
[18]Kleinrock, L. 1975 Queueing Systems. Wiley.Google Scholar
[19]Sevcik, K. C. & Mitrani, I. 1981 The distribution of queueing network states at input and output instants. J. ACM 28, 358–371.CrossRefGoogle Scholar
[20]Knessl, C. & Morrison, J. A. 1991 Heavy traffic analysis of the sojourn time in tandem queues with overtaking. SIAM J. Appl. Math. 51, 1740–1763.CrossRefGoogle Scholar