Bounds on a fair policy with near optimal performance

Abstract: "Providing fairness and providing good response times are often viewed as conflicting goals in scheduling. Scheduling policies that provide low response times, such as Shortest Running Processing Time (SRPT), are sometimes not fair, while fair policies like Processor Sharing (PS) provide response times far worse than SRPT. This seemingly inevitable tension between providing fairness and providing good response times was eliminated at last year's ACM Sigmetrics conference with the introduction of a new scheduling policy, Fair Sojourn Protocol (FSP), that appears to provide both [9]. The FSP policy is provably fair, as seen directly from its definition, and simulations show that FSP has a very low mean response time, close to that of SRPT in many cases [9]. Unfortunately, analyzing the mean response time of the FSP policy has proven to be difficult, and thus the queueing performance of FSP has only be [sic] assessed via simulation. In this work, we present the first queueing analysis of FSP. This analysis yields close upper and lower bounds on the mean response time and mean slowdown of the M/GI/1/FSP queue. Our upper bound shows that the improvement of FSP over PS is substantial: for all job size distributions, the mean response time and mean slowdown under FSP are a fraction (1 - [rho]/2) of that under PS, where [rho] is the system load. For distributions with decreasing failure rate the improvement is even greater. We also prove that the mean response time of SRPT and FSP are quite close. Lastly, our bounds reveal that FSP has yet another desirable property: similarly to PS, the FSP policy is largely insensitive to the variability of the job size distribution.