Classifying scheduling policies wrt unfairness and performance

PEOPLE INVOLVED

FUNDING PROVIDED BY

SYNOPSIS

It is common to evaluate scheduling policies based on their mean response times. Another important, but sometimes opposing, performance metric is a scheduling policy's fairness. For example a policy that biases towards small job sizes so as to minimize mean response time may end up being unfair to large job sizes. In the SYNC project we examined the unfairness properties of the SRPT scheduling policy. In this project we look at all scheduling policies from the perspective of unfairness. We define a scheduling policy, P, as being fair if all jobs experience lower (or equal) expected response time under P as compared with their expected response time under Processor-Sharing. In [Sigmetrics 2003], we classify most scheduling policies into one of 3 categories: Always Fair, Sometimes Unfair, or Always Unfair, as shown below, where Always Fair policies are fair under all loads and all service distributions, and Always Unfair policies are unfair under all loads and all service distributions.

We also investigate which jobs are being treated unfairly and provide insight into designing more fair scheduling policies while still maintaining low response times.

In [Performance 2002], we consider a theoretical metric -- the performance of only the largest job (looking in the limit as job size goes to inifinity). Under this metric, we find, surprisingly, that all work conserving policies converge almost surely to the same value. We also find that the expected slowdown under any work conserving policy can be made arbitrarily close to that under Processor-Sharing, for all job sizes that are sufficiently large.

In [ORL 2003], we study the Feedback (FB) policy, which gives the processor to the job with the least attained service (lowest age). By biasing towards jobs with small ages, FB is, in a sense, attempting to complete the short jobs as quickly as possible. The fact that the FB policy does not need to know the size of a job, and yet can often achieve performance similar to policies which bias towards short jobs, makes FB a very practical policy. In [ORL 2003] we prove that the FB policy outperforms the PS (processor-sharing) policy if and only if the service distribution has a decreasing failure rate.

SOME OF OUR RELEVANT PAPERS

[Sigmetrics 2003] : Adam Wierman and Mor Harchol-Balter. "Classifying Scheduling Policies with respect to Unfairness in an M/GI/1." Proceedings of ACM Sigmetrics 2003 Conference on Measurement and Modeling of Computer Systems . San Diego, CA. June 2003. Winner of SIGMETRICS Best Student Paper Award . Postscript .

[Performance 2002] : Mor Harchol-Balter, Karl Sigman, and Adam Wierman. "Asymptotic Convergence of Scheduling Policies with respect to Slowdown." To appear in Performance 2002. IFIP WG 7.3 International Symposium on Computer Modeling, Measurement and Evaluation. Postscript and Abstract .

[ORL 2003] : Adam Wierman, Nikhil Bansal, and Mor Harchol-Balter "A note on comparing response times in M/GI/1/FB and M/GI/1/PS queues." To appear in Operations Research Letters 2003. Technical report: CMU-CS-02-177. Postscript.

[Sigmetrics 2001] : Nikhil Bansal and Mor Harchol-Balter "Analysis of SRPT Scheduling: Investigating Unfairness." Proceedings of ACM Sigmetrics 2001 Conference on Measurement and Modeling of Computer Systems. Postscript and Abstract.

Back to Mor's Home Page .