skip to main content
article

Nearly insensitive bounds on SMART scheduling

Published: 06 June 2005 Publication History

Abstract

We define the class of SMART scheduling policies. These are policies that bias towards jobs with small remaining service times, jobs with small original sizes, or both, with the motivation of minimizing mean response time and/or mean slowdown. Examples of SMART policies include PSJF, SRPT, and hybrid policies such as RS (which biases according to the product of the remaining size and the original size of a job).For many policies in the SMART class, the mean response time and mean slowdown are not known or have complex representations involving multiple nested integrals, making evaluation difficult. In this work, we prove three main results. First, for all policies in the SMART class, we prove simple upper and lower bounds on mean response time. Second, we show that all policies in the SMART class, surprisingly, have very similar mean response times. Third, we show that the response times of SMART policies are largely insensitive to the variability of the job size distribution. In particular, we focus on the SRPT and PSJF policies and prove insensitive bounds in these cases.

References

[1]
N. Bansal. On the average sojourn time under M/M/1/SRPT. Oper. Res. Letters, 22(2):195--200, 2005.
[2]
N. Bansal and M. Harchol-Balter. Analysis of SRPT scheduling: Investigating unfairness. In Proceedings of ACM Sigmetrics, 2001.
[3]
P. Barford and M. Crovella. Generating representative web workloads for network and server performance evaluation. In Proceedings of ACM Sigmetrics, 1998.
[4]
S. Borst, O. Boxma, and R. Nunez-Queija. Heavy tails: the effect of the service discipline. In Computer Performance Evaluation - Modelling Techniques and Tools (TOOLS), pages 1--30, 2002.
[5]
R. W. Conway, W. L. Maxwell, and L. W. Miller. Theory of Scheduling. Addison-Wesley Publishing Company, 1967.
[6]
A. B. Downey. Evidence for long-tailed distributions in the internet. In Proceedings of ACM SIGCOMM Internet Measurment Workshop, 2001.
[7]
H. Feng and V. Misra. Mixed scheduling disciplines for network flows (the optimality of FBPS). In Workshop on MAthematical performance Modeling and Analysis (MAMA), 2003.
[8]
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.
[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.
[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.
[11]
L. Kleinrock. Queueing Systems, volume II. Computer Applications. John Wiley & Sons, 1976.
[12]
W. Leland, M. Taqqu, W. Willinger, and D. Wilson. On the self-similar nature of ethernet traffic. In Proceedings of SIGCOMM '93, pages 183--193, September 1993.
[13]
R. Nunez-Queija. Queues with equally heavy sojourn time and service requirement distributions. Ann. Oper. Res, 113:101--117, 2002.
[14]
T. O'Donovan. Direct solutions of M/G/1 priority queueing models. Revue Francaise d'Automatique Informatique Recherche Operationnelle, 10:107--111, 1976.
[15]
A. Pechinkin, A. Solovyev, and S. Yashkov. A system with servicing discipline whereby the order of remaining length is serviced first. Tekhnicheskaya Kibernetika, 17:51--59, 1979.
[16]
D. L. Peterson. Data center I/O patterns and power laws. In CMG Proceedings, December 1996.
[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.
[18]
M. Rawat and A. Kshemkalyani. SWIFT: Scheduling in web servers for fast response time. In Symp. on Network Computing and App., 2003.
[19]
L. E. Schrage. A proof of the optimality of the shortest remaining processing time discipline. Operations Research, 16:678--690, 1968.
[20]
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.
[21]
D. Smith. A new proof of the optimality of the shortest remaining processing time discipline. Operations Research, 26:197--199, 1976.
[22]
A. Wierman, N. Bansal, and M. Harchol-Balter. A note comparing response times in the M/GI/1/FB and M/GI/1/PS queues. Operations Research Letters, 32:73--76, 2003.
[23]
A. Wierman and M. Harchol-Balter. Classifying scheduling policies with respect to unfairness in an M/GI/1. In Proceedings of ACM Sigmetrics, 2003.

Cited By

View all

Recommendations

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
  • cover image ACM Conferences
    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
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

  1. M/G/1
  2. PS
  3. PSJF
  4. SMART
  5. SRPT
  6. preemptive shortest job first
  7. processor sharing
  8. response time
  9. scheduling
  10. shortest remaining processing time

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)8
  • Downloads (Last 6 weeks)2
Reflects downloads up to 07 Jan 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media