Comparison of SRPT and PS Scheduling Under ON/OFF Load Conditions

摘要

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 a 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 all 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.