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. Acurrency 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.
Authors: Carl A. Waldspurger and William E. Weihl
Date: 1994|||||http://www.usenix.org/publications/library/proceedings/osdi/full_papers/waldspur ger.pdf