Computer Science Department
School of Computer Science, Carnegie Mellon University
Analysis of SRPT Scheduling: Investigating Unfairness
Nikhil Bansal, Mor Harchol-Balter
Keywords: M/G/1, processor sharing, shortest, processing remaining
time, time-sharing, priortiy, unfiarness, starvation, slowdown,
heavy-tailed behavior, high variances, single server, job scheduling
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