This paper analytically compares the performance of the SRPT (Shortest-Remaining-Processing-Time) and PS (Processor-Sharing) scheduling policies. SRPT scheduling has long been criticized for treating large jobs unfairly, whereas PS scheduling is by definition fair. We evaluate SRPT and PS under conditions where the unfairness under SRPT is believed to be most apparent: system overload. Specifically, we consider an single server with an alternating ON/OFF arrival process. During the ON periods the load at the server exceeds 1. During the OFF periods the load at the server is 0. We derive expressions for mean response time as a function of job size under PS and SRPT, for general job size distributions.

In comparing these expressions, we find that for our ON/OFF model:

1. The mean response time under SRPT scheduling is far lower than under PS scheduling.

2. When the job size distribution is exponential, the biggest jobs may have higher mean response time under SRPT scheduling as compared with PS scheduling. However, when the job size distribution is heavy-tailed jobs, including the very largest job, have lower (or only marginally higher) mean response times under SRPT scheduling as compared with PS scheduling. Heavy-tailed workloads are important because they arise naturally in many empirical computer workloads.

23 pages

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

This page maintained by reports@cs.cmu.edu