The Shortest-Remaining-Processing-Time (SRPT) scheduling policy has long been known to be optimal for minimizing mean response time. Despite this fact, SRPT scheduling is rarely used in practice. It is believed that the performance improvements of SRPT over other scheduling policies with respect to mean response time stem from the fact that SRPT unfairly penalizes the large jobs in order to help the small jobs. This belief has caused 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 via analysis the problem of unfairness in SRPT. The analysis assumes an M/G/1 model, but emphasizes heavy tailed job size distributions, as are characteristic of empirical workloads. We end with a trace-driven simulation experiment which agrees with the analysis, even though arrivals are no longer Poisson.

25 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]