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.