article

Classifying scheduling policies with respect to higher moments of conditional response time

Authors:

Mor Harchol-BalterAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 33, Issue 1

Pages 229 - 240

https://doi.org/10.1145/1071690.1064238

Published: 06 June 2005 Publication History

Abstract

In addition to providing small mean response times, modern applications seek to provide users predictable service and, in some cases, Quality of Service (QoS) guarantees. In order to understand the predictability of response times under a range of scheduling policies, we study the conditional variance in response times seen by jobs of different sizes. We define a metric and a criterion that distinguish between contrasting functional behaviors of conditional variance, and we then classify large groups of scheduling policies.In addition to studying the conditional variance of response times, we also derive metrics appropriate for comparing higher conditional moments of response time across job sizes. We illustrate that common statistics such as raw and central moments are not appropriate when comparing higher conditional moments of response time. Instead, we find that cumulant moments should be used.

References

[1]

N. Bansal and M. Harchol-Balter. Analysis of SRPT scheduling: Investigating unfairness. In Proceedings of ACM Sigmetrics, 2001.]]

Digital Library

[2]

M. Bender, S. Chakrabarti, and S. Muthukrishnan. Flow and stretch metrics for scheduling continous job streams. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998.]]

Digital Library

[3]

B. Dellart. How tolerable is delay? consumers evaluations of internet web sites after waiting. J. of Interactive Marketing, 13:41--54, 1999.]]

[4]

N. Duffield, W. Massey, and W. Whitt. A nonstationary offered-load model for packet networks. Telecommunication Systems, 13:271--296, 2001.]]

Digital Library

[5]

E. Friedman and S. Henderson. Fairness and efficiency in web server protocols. In Proceedings of ACM Sigmetrics, 2003.]]

Digital Library

[6]

G. L. Choudhury and W. Whitt. Heavy-traffic asymptotic expansions for the asymptotic decay rates in the BMAP/G/1 queue. Stochastic Models, 10:453--498, 1994.]]

[7]

M. Gong and C. Williamson. Quantifying the properties of SRPT scheduling. In IEEE/ACM Symposium on Mod., Anal., and Sim. of Comp. and Telecomm. Sys. (MASCOTS), 2003.]]

[8]

I. Gradshteyn and I. Ryzhik. Tables of Integrals, Series, and Products. Academic Press, 2000.]]

[9]

M. Harchol-Balter, B. Schroeder, N. Bansal, and M. Agrawal. Implementation of SRPT scheduling in web servers. ACM Transactions on Computer Systems, 21(2), May 2003.]]

Digital Library

[10]

M. Harchol-Balter, K. Sigman, and A. Wierman. Asymptotic convergence of scheduling policies with respect to slowdown. Performance Evaluation, 49(1-4):241--256, 2002.]]

Digital Library

[11]

M. Kendall. The Advanced Theory of Statistics. Griffin, London, 1945.]]

Digital Library

[12]

L. Kleinrock. Queueing Systems, volume I. Theory. John Wiley & Sons, 1975.]]

Digital Library

[13]

L. Kleinrock. Queueing Systems, volume II. Computer Applications. John Wiley & Sons, 1976.]]

[14]

T. Matis and R. Feldman. Using cumulant functions in queueing theory. Queueing Systems, 40:341--353, 2002.]]

Digital Library

[15]

R. Nunez-Queija. Queues with equally heavy sojourn time and service requirement distributions. Ann. Oper. Res, 113:101--117, 2002.]]

[16]

T. Osogami and M. Harchol-Balter. A closed-form solution for mapping general distributions to minimal PH distributions. In Modelling Tools and Techniques for Comp. and Comm. System Perf. Eval., 2003.]]

[17]

I. Rai, G. Urvoy-Keller, and E. Biersack. Analysis of LAS scheduling for job size distributions with high variance. In Proceedings of ACM Sigmetrics, 2003.]]

Digital Library

[18]

I. A. Rai, G. Urvoy-Keller, M. Vernon, and E. W. Biersack. Performance modeling of LAS based scheduling in packet switched networks. In Proc. of ACM Sigmetrics-Performance, 2004.]]

Digital Library

[19]

M. Rawat and A. Kshemkalyani. SWIFT: Scheduling in web servers for fast response time. In Symp. on Network Computing and App., 2003.]]

Digital Library

[20]

D. Raz, H. Levy, and B. Avi-Itzhak. A resource-allocation queueing fairness measure. In Proc. of ACM Sigmetrics-Performance, 2004.]]

Digital Library

[21]

R. Righter, J. Shanthikumar, and G. Yamazaki. On external service disciplines in single stage queueing systems. J. of Applied Probability, 27:409--416, 1990.]]

[22]

S. Ross. Introduction to Probability Models. Academic Press, 1997.]]

Digital Library

[23]

L. E. Schrage. A proof of the optimality of the shortest remaining processing time discipline. Operations Research, 16:678--690, 1968.]]

Digital Library

[24]

L. E. Schrage and L. W. Miller. The queue M/G/1 with the shortest remaining processing time discipline. Operations Research, 14:670--684, 1966.]]

Digital Library

[25]

A. Silberschatz and P. Galvin. Operating System Concepts, 5th Edition. John Wiley & Sons, 1998.]]

Digital Library

[26]

H. Takagi. Queueing Analysis: Volume 1: Vacation and Priority Systems. North-Holland, 1991.]]

[27]

A. Tanenbaum. Modern Operating Systems. Prentice Hall, 1992.]]

Digital Library

[28]

A. Ward and W. Whitt. Predicting response times in processor-sharing queues. In Proc. of the Fields Institute Conf. on Comm. Networks, 2000.]]

[29]

W. Whitt. Improving service by informing jobs about anticipated delays. Managemet Science, 45:870--888, 1999.]]

Digital Library

[30]

W. Whitt. Predicting queueing delays. Management Science, 45:192--207, 1999.]]

[31]

A. Wierman and M. Harchol-Balter. Classifying scheduling policies with respect to unfairness in an M/GI/1. In Proceedings of ACM Sigmetrics, 2003.]]

Digital Library

[32]

A. Wierman, M. Harchol-Balter, and T. Osogami. Nearly insensitive bounds on SMART scheduling. In Proc. of ACM Sigmetrics, 2005.]]

Digital Library

[33]

S. Yang and G. de Veciana. Enhancing both network and user performance for networks supporting best effort traffic. volume 12, pages 349--360, 2004.]]

Digital Library

[34]

S. Yashkov. Processor sharing queues: Some progress in analysis. Queueing Systems, 2:1--17, 1987.]]

Digital Library

[35]

S. Yashkov. Mathematical problems in the theory of shared-processor systems. J. of Soviet Mathematics, 58:101--147, 1992.]]

[36]

M. Zhou and L. Zhou. How does waiting duration information influence customers' reactions to waiting for services. J. of Applied Social Psychology, 26:1702--1717, 1996.]]

[37]

A. Zwart and O. Boxma. Sojourn time asymptotics in the M/G/1 processor sharing queue. Queueing Sys. Thry. and App., 35:141--166, 2000.]]

Digital Library

Cited By

Behrouzi-Far ASoljanin E(2022)Balanced Nonadaptive Redundancy SchedulingIEEE Journal on Selected Areas in Information Theory10.1109/JSAIT.2022.31976753:2(422-430)Online publication date: Jun-2022
https://doi.org/10.1109/JSAIT.2022.3197675
Nuyens MWierman A(2019)The Foreground-Background queuePerformance Evaluation10.1016/j.peva.2007.06.02865:3-4(286-307)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.peva.2007.06.028
Drakopoulos GMegalooikonomou V(2016)An adaptive higher order scheduling policy with an application to biosignal processing2016 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI.2016.7849897(1-8)Online publication date: Dec-2016
https://doi.org/10.1109/SSCI.2016.7849897
Show More Cited By

Index Terms

Classifying scheduling policies with respect to higher moments of conditional response time

Recommendations

Classifying scheduling policies with respect to unfairness in an M/GI/1

It is common to evaluate scheduling policies based on their mean response times. Another important, but sometimes opposing, performance metric is a scheduling policy's fairness. For example, a policy that biases towards small job sizes so as to minimize ...
Classifying scheduling policies with respect to higher moments of conditional response time
SIGMETRICS '05: Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

In addition to providing small mean response times, modern applications seek to provide users predictable service and, in some cases, Quality of Service (QoS) guarantees. In order to understand the predictability of response times under a range of ...
Classifying scheduling policies with respect to unfairness in an M/GI/1
SIGMETRICS '03: Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

It is common to evaluate scheduling policies based on their mean response times. Another important, but sometimes opposing, performance metric is a scheduling policy's fairness. For example, a policy that biases towards small job sizes so as to minimize ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 33, Issue 1

Performance evaluation review

June 2005

417 pages

ISSN:0163-5999

DOI:10.1145/1071690

Issue’s Table of Contents

SIGMETRICS '05: Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
June 2005
428 pages
ISBN:1595930221
DOI:10.1145/1064212
General Chairs:
Derek Eager
University of Saskatchewan, Canada
,
Carey Williamson
University of Calgary, Canada
,
Program Chairs:
Sem Borst
Bell Labs, USA & CWI, The Netherlands
,
John C. S. Lui
Chinese University of Hong Kong, China

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or 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, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2005

Published in SIGMETRICS Volume 33, Issue 1

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
428
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Behrouzi-Far ASoljanin E(2022)Balanced Nonadaptive Redundancy SchedulingIEEE Journal on Selected Areas in Information Theory10.1109/JSAIT.2022.31976753:2(422-430)Online publication date: Jun-2022
https://doi.org/10.1109/JSAIT.2022.3197675
Nuyens MWierman A(2019)The Foreground-Background queuePerformance Evaluation10.1016/j.peva.2007.06.02865:3-4(286-307)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.peva.2007.06.028
Drakopoulos GMegalooikonomou V(2016)An adaptive higher order scheduling policy with an application to biosignal processing2016 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI.2016.7849897(1-8)Online publication date: Dec-2016
https://doi.org/10.1109/SSCI.2016.7849897
Ren SHe YGropp WMatsuoka S(2013)COCAProceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis10.1145/2503210.2503248(1-12)Online publication date: 17-Nov-2013
https://dl.acm.org/doi/10.1145/2503210.2503248
Auchmann MUrvoy-Keller G(2009)On the Variance of the Least Attained Service Policy and Its Use in Multiple Bottleneck NetworksNetwork Control and Optimization10.1007/978-3-642-00393-6_9(70-77)Online publication date: 27-Feb-2009
https://dl.acm.org/doi/10.1007/978-3-642-00393-6_9
Behrouzi-Far ASoljanin E(undefined)Redundancy Scheduling in Systems with Bi-Modal Job Service Time Distributions2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)10.1109/ALLERTON.2019.8919929(9-16)
https://dl.acm.org/doi/10.1109/ALLERTON.2019.8919929
Faisal AMartin NBashir HLamelas SDogar FGavrilovska ATerry D(2024)When will my ML job finish? toward providing completion time estimates through predictability-centric schedulingProceedings of the 18th USENIX Conference on Operating Systems Design and Implementation10.5555/3691938.3691964(487-505)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.5555/3691938.3691964
Chis THarrison P(2015)Moment-Generating Algorithm for Response Time in Processor Sharing Queueing SystemsComputer Performance Engineering10.1007/978-3-319-23267-6_6(80-95)Online publication date: 22-Aug-2015
https://doi.org/10.1007/978-3-319-23267-6_6
Ren SHe YMcKinley K(2014)A Theoretical Foundation for Scheduling and Designing Heterogeneous Processors for Interactive ApplicationsDistributed Computing10.1007/978-3-662-45174-8_11(152-166)Online publication date: 2014
https://doi.org/10.1007/978-3-662-45174-8_11
Ren SLan Cvan der Schaar M(2013)Energy-efficient design of real-time stream mining systems2013 IEEE International Conference on Acoustics, Speech and Signal Processing10.1109/ICASSP.2013.6638327(3592-3596)Online publication date: May-2013
https://doi.org/10.1109/ICASSP.2013.6638327
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents