|
OSDI 2000 Abstract
Surplus Fair Scheduling: A Proportional-Share CPU Scheduling
Algorithm for Symmetric Multiprocessors
Abhishek Chandra, Micah Adler,University of Massachusetts Amherst, Pawan Goyal, Ensim Corporation
and Prashant Shenoy, University of Massachusetts Amherst
Abstract
In this paper, we present surplus fair scheduling (SFS), a
proportional-share CPU scheduler designed for symmetric
multiprocessors. We first show that the infeasibility of certain
weight assignments in multiprocessor environments results in
unfairness or starvation in many existing proportional-share
schedulers. We present a novel weight readjustment algorithm to
translate infeasible weight assignments to a set of feasible
weights. We show that weight readjustment enables existing
proportional-share schedulers to significantly reduce, but not
eliminate, the unfairness in their allocations. We then present
surplus fair scheduling, a proportional-share scheduler that is
designed explicitly for multiprocessor environments. We implement our
scheduler in the Linux kernel and demonstrate its efficacy through an
experimental evaluation. Our results show that SFS can achieve
proportionate allocation, application isolation and good interactive
performance, albeit at a slight increase in scheduling overhead. We
conclude from our results that a proportional-share scheduler such as
SFS is not only practical but also desirable for server operating
systems.
|
Need help? Use our Contacts page.
