|
Measuring the Fairness of Scheduling
Policies
for Web Servers and Beyond
People
Adam Wierman
Motivation Within
modern computer systems, the question of how to allocate resources to process
incoming requests is paramount. Applications across domains are all faced with
this task. Within traditional networking, web servers are constantly being
barraged with incoming requests, and must decide how best to allocate resources
to respond. Even within the network, routers are placed under the same demands.
Outside of networks, the foundations of operating systems depend on the ability
to allocate the processor in response to requests made by active processes. Even
database queries can be viewed in the same light - memory resources must be
allocated to fulfill user requests.
Our work in
this area began with a simple question: What is the experience of large job
sizes under policies that prioritize small jobs, e.g. SRPT? We proved that,
surprisingly, the largest jobs do not receive worse performance under SRPT than
they do under traditional timesharing policies like Processor Sharing (PS),
which is intuitively fair because it shares the server evenly among all jobs in
the system at all times. In fact, in many cases using SRPT can provide
smaller response times (in expectation) for all job sizes than PS. However,
under heavy load SRPT can be unfair to some jobs, it is just not the largest
jobs. Instead, it is the medium-large jobs that are treated unfairly.
Our work on fairness has been cited over 50 times, has been used for many applications including web servers, routers, operating systems, and wireless networks, and has served to jumpstart a new focus on fairness in the Sigmetrics community. Many researchers, e.g. Rai, Biersack, et al. and Gong & Williamson, have analyzed other policies with respect to the fairness measure we introduced. Still others, including Friedman & Henderson, have invented new policies that perform well with respect to this fairness measure. In addition, many researchers, such as Levy & Raz and Sandmann, have developed new fairness measures for use in other applications.
The impact of prioritization on conditional response time
Under preparation.
Asymptotic cumulants of scheduling policies
Under preparation.
Fairness and classifications
To appear in Performance Evaluation Review.
Proceedings of ACM Sigmetrics, 2005.
Thesis Proposal, 2005.
Proceedings of ACM Sigmetrics, Best Student Paper Award recipient, 2003.
Performance Evaluation Review, 2002. 30(3):9-11.
Performance Evaluation, 2002. 49(1-4):241-256.
Proceedings of ACM Sigmetrics, 2001
|
|
Figure 1. A summary of the classification of common policies and scheduling techniques based
on fairness
Figure 2.
A comparison of the response time for a job of size x, T(x), under PS and
SRPT. Notice that under low load SRPT outperforms PS for all job sizes,
but that under high load SRPT is unfair to medium-large job sizes.