Lottery Scheduling: Flexible Proportional-Share Resource Management
Carl A. Waldspurger (carl@lcs.mit.edu)
William E. Weihl (weihl@lcs.mit.edu)
MIT Laboratory for Computer Science
Cambridge, MA 02139 USA
Abstract
This paper presents lottery scheduling, a novel randomized resource
allocation mechanism. Lottery scheduling provides efficient,
responsive control over the relative execution rates of computations.
Such control is beyond the capabilities of conventional schedulers,
and is desirable in systems that service requests of varying
importance, such as databases, media-based applications, and networks.
Lottery scheduling also supports modular resource management by
enabling concurrent modules to insulate their resource allocation
policies from one another. A currency abstraction is introduced to
flexibly name, share, and protect resource rights. We also show that
lottery scheduling can be generalized to manage many diverse
resources, such as I/O bandwidth, memory, and access to locks. We
have implemented a prototype lottery scheduler for the Mach 3.0
microkernel, and found that it provides flexible and responsive
control over the relative execution rates of a wide range of
applications. The overhead imposed by our unoptimized prototype is
comparable to that of the standard Mach timesharing policy.
Download the full text of this paper in PDF,
ASCII (50,882 bytes) and
POSTSCRIPT (504,442 bytes) form.
To Become a USENIX Member, please see our
Membership Information.