Lottery Scheduling: Flexible Proportional-Share Resource Management
(OSDI '94 Best Paper)
Carl A. Waldspurger, William E. Weihl
MIT Laboratory for Computer Science
Cambridge, MA 02139 USA
{carl,weihl}@lcs.mit.edu
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.