Analysis of SRPT scheduling: investigating unfairness

N. Bansal, M. Harchol-Balter

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    129 Citations (Scopus)

    Abstract

    The Shortest-Remaining-Processing-Time (SRPT) scheduling policy has long been known to be optimal for minimizing mean response time (sojourn time). Despite this fact, SRPT scheduling is rarely used in practice. It is believed that the performance improvements of SRPT over other scheduling policies stem from the fact that SRPT unfairly penalizes the large jobs in order to help the small jobs. This belief has led people to instead adopt "fair" scheduling policies such as Processor-Sharing (PS), which produces the same expected slowdown for jobs of all sizes.This paper investigates formally the problem of unfairness in SRPT scheduling as compared with PS scheduling. The analysis assumes an M/G/1 model, and emphasizes job size distributions with a heavy-tailed property, as are characteristic of empirical workloads. The analysis shows that the degree of unfairness under SRPT is surprisingly small.The M/G/1/SRPT and M/G/1/PS queues are also analyzed under overload and closed-form expressions for mean response time as a function of job size are proved in this setting.
    Original languageEnglish
    Title of host publicationProceedings of the Joint International Conference on Measurements and Modeling of Computer Systems (SIGMETRICS 2001, Cambridge, MA, USA, June 16-20, 2011)
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery, Inc
    Pages279-290
    DOIs
    Publication statusPublished - 2001

    Fingerprint

    Dive into the research topics of 'Analysis of SRPT scheduling: investigating unfairness'. Together they form a unique fingerprint.

    Cite this