CMU-CS-02-187
Computer Science Department
School of Computer Science, Carnegie Mellon University


CMU-CS-02-187

Classifying Scheduling Policies
with Respect to Unfairness in an M/GI/1

Adam Wierman, Mor Harchol-Balter

October 2002

CMU-CS-02-187.ps
CMU-CS-02-187.pdf


Keywords: Scheduling; unfairness; M/G/1; FB; LAS; SET; feedback; least attained service; shortest elapsed time; PS; processor sharing; SRPT; shortest remaining processing time; slowdown.


It is common to classify 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 short jobs so as to minimize mean response time, may end up being unfair to long jobs. In this paper we define three types of unfairness and demonstrate large classes of scheduling policies that fall into each type. We end with a discussion on which jobs are the ones being treated unfairly.

26 pages

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

This page maintained by reports@cs.cmu.edu