Abstract
We present the first near-exact analysis of an M/PH/k queue with m > 2 preemptive-resume priority classes. Our analysis introduces a new technique, which we refer to as Recursive Dimensionality Reduction (RDR). The key idea in RDR is that the m-dimensionally infinite Markov chain, representing the m class state space, is recursively reduced to a 1-dimensionally infinite Markov chain, that is easily and quickly solved. RDR involves no truncation and results in only small inaccuracy when compared with simulation, for a wide range of loads and variability in the job size distribution.
Our analytic methods are then used to derive insights on how multi-server systems with prioritization compare with their single server counterparts with respect to response time. Multi-server systems are also compared with single server systems with respect to the effect of different prioritization schemes—“smart” prioritization (giving priority to the smaller jobs) versus “stupid” prioritization (giving priority to the larger jobs). We also study the effect of approximating m class performance by collapsing the m classes into just two classes.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Change history
27 September 2021
A Correction to this paper has been published: https://doi.org/10.1007/s11134-021-09710-1
References
D. Bertsimas and D. Nakazato, The distributional {Little's Law} and its applications, {Operations Research} 43(2) (1995) 298–310.
A. Bondi and J. Buzen, The response times of priority classes under preemptive resume in {M/G/m} queues, in: ACM Sigmetrics., (August 1984) pp. 195–201.
L. Bright and P. Taylor, Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes, {Stochastic Models} 11 (1995) 497–514.
J. Buzen and A. Bondi, The response times of priority classes under preemptive resume in {M/M/m} queues, {Operations Research} 31 (1983) 456–465.
A. Cobham, Priority assignment in waiting line problems. {Operations Research} 2 (1954) 70–76.
R. Davis, Waiting-time distribution of a multi-server, priority queueing system, {Operations Research} 14 (1966) 133–136.
W. Feng, M. Kowada and K. Adachi, Analysis of a multiserver queue with two priority classes and {(M,N)}-threshold service schedule ii: preemptive priority, {Asia-Pacific Journal of Operations Research} 18 (2001) 101–124.
H. Gail, S. Hantler, and B. Taylor, Analysis of a non-preemptive priority multiserver queue. {Advances in Applied Probability} 20 (1988) 852–879.
H. Gail, S. Hantler and B. Taylor, On a preemptive {M}arkovian queue with multiple servers and two priority classes, {Mathematics of Operations Research} 17 (1992) 365–391.
R. Jain, The Art of Computer Systems Performance Analysis. (John Wiley and Sons, 1991).
E. Kao and K. Narayanan, Modeling a multiprocessor system with preemptive priorities, {Management Science} 2 (1991) 185–197.
E. Kao and S. Wilson, Analysis of nonpreemptive priority queues with multiple servers and two priority classes, {European Journal of Operational Research} 118 (1999) 181–193.
E.P.C. Kao and K.S. Narayanan, Computing steady-state probabilities of a nonpreemptive priority multiserver queue, {Journal on Computing} 2(3) (1990) 211–218.
A. Kapadia, M. Kazumi and A. Mitchell, Analysis of a finite capacity nonpreemptive priority queue, {Computers and Operations Research} 11 (1984) 337–343.
O. Kella and U. Yechiali, Waiting times in the non-preemptive priority {M/M/c} queue, {Stochastic Models} 1 (1985) 257–262.
G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling. ({ASA-SIAM}, 1999).
H. Leemans, {The Two-Class Two-Server Queue with Nonpreemptive Heterogeneous Priority Structures}. PhD thesis, K.U.Leuven, 1998.
D. McWherter, B. Schroeder, N. Ailamaki and M. Harchol-Balter, Priority mechanisms for {OLTP} and transactional web applications, in: Proceedings of the 20th International Conference on Data Engineering (ICDE 2004). (2004) pp. 535–546.
D. Miller, Steady-state algorithmic analysis of {M/M/c} two-priority queues with heterogeneous servers, in: Applied probability—Computer science, The Interface, eds., R.L. Disney and T.J. Ott, volume II, (Birkhauser, 1992), pp. 207–222.
I. Mitrani and P. King, Multiprocessor systems with preemptive priorities, {Performance Evaluation} 1 (1981) 118–125.
M. Neuts, Moment formulas for the {M}arkov renewal branching process, {Advances in Applied Probabilities} 8 (1978) 690–711.
B. Ngo and H. Lee, Analysis of a pre-emptive priority {M/M/c} model with two types of customers and restriction, Electronics Letters 26 (1990) 1190–1192.
T. Nishida, Approximate analysis for heterogeneous multiprocessor systems with priority jobs, {Performance Evaluation} 15 (1992) 77–88.
T. Osogami, Analysis of multiserver systems via dimensionality reduction of Markov chains, Ph.D. thesis. School of Computer Science, Carnegie Mellon University (2005).
T. Osogami and M. Harchol-Balter, A closed-form solution for mapping general distributions to minimal {PH} distributions, in: Performance TOOLS. (2003) pp. 200–217.
T. Osogami, M. Harchol-Balter and A. Scheller-Wolf, Analysis of cycle stealing with switching costs and thresholds, Performance Evaluation 61(4) (2005) 347–369.
A. Sleptchenko, Multi-class, multi-server queues with non-preemptive priorities. Technical Report 2003-016, EURANDOM, Eindhoven University of Technology, 2003.
A. Sleptchenko, A. van Harten and M. van der Heijden, An exact solution for the state probabilities of the multi-class, multi-server queue with preemptive priorities, Queueing Systems 50 (2005) 81–107.
W. Whitt, A review of L. = λ W. and extensions, {Queueing Systems} 9 (1991) 235–268.
A. Wierman, T. Osogami, M. Harchol-Balter and A. Scheller-Wolf, How many servers are best in a dual-priority {M/PH/k} system, {Unpublished Manuscript. In submission}, 2005.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by NSF Career Grant CCR-0133077, NSF Theory CCR-0311383, NSF ITR CCR-0313148, and IBM Corporation via Pittsburgh Digital Greenhouse Grant 2003.
AMS subject classification: 60K25, 68M20, 90B22, 90B36
Rights and permissions
About this article
Cite this article
Harchol-Balter, M., Osogami, T., Scheller-Wolf, A. et al. Multi-Server Queueing Systems with Multiple Priority Classes. Queueing Syst 51, 331–360 (2005). https://doi.org/10.1007/s11134-005-2898-7
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/s11134-005-2898-7