Carnegie Mellon University
Browse
file.pdf (1.81 MB)

Simple bounds on SMART scheduling

Download (1.81 MB)
journal contribution
posted on 2009-12-01, 00:00 authored by Adam Wierman, Mor Harchol-Balter
Abstract: "We define the class of SMART scheduling policies. These are policies that bias towards jobs with short 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 response time and 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. In particular, we focus on the SRPT and PSJF policies and prove even tighter bounds in these cases. 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 invariant to the variability of the job size distribution."

History

Publisher Statement

All Rights Reserved

Date

2009-12-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC