From: Manish Mittal (manishm_at_microsoft.com)
Date: Wed Jan 28 2004 - 15:10:07 PST
The authors present a simple scheduling scheme that differs from widely
deployed priority-based methods. One of the problems with the priority
based systems is that highest priority always wins. Lottery scheduling
provides intuitive proportional resource management, dynamic flexibility
as well as other desirable properties missing from more complex
scheduling algorithms. Lottery scheduling also provides excellent
support for modular resource management. Lottery scheduling can be
generalized to manage many diverse resources, such as I/O bandwidth,
memory, and access to locks.
The central idea of this system is simple. Resource rights are
represented by lottery tickets. Priority is determined by the relative
percentage of all of the tickets competing for this resource. Tickets
are uniform and can be used to compete for different kinds of resources.
Scheduler picks winning ticket randomly, and grants resource to client
holding winning ticket. The expected allocation of resources to clients
is proportional to the number of tickets that they hold. Response time
is inversely proportional to ticket allocation.
Tickets behave much like money, and the paper describes several
constructs for lottery scheduling analogous to market controls,
including ticket transfers and currencies. The ticket transfers allow
blocked processes to speed up another process they are waiting for,
while the currencies allow for localized resource management. Another
added feature of the authors' lottery system is ensuring that resources
are allocated fairly, i.e. in proportion to number of tickets owned,
over time through use of compensation tickets. Basic idea behind
compensation tickets is that if you complete fraction f of the quantum,
your tickets are inflated by 1/f until the next time you win.
Several experiments are conducted to test fairness and flexible control.
The experiments shows that the lottery scheduler is accurate in
providing fair execution time with respect to the number of tickets each
of the clients hold. In addition, the flexibility of the scheduler
displayed with the Monte-Carlo experiment helps supports the scheduler
exhibiting dynamic control. The authors also talk about ways in which
the scheduler could be used for other resources such as IO, networks and
memory.
This paper presents a novel approach to the scheduling problem that
makes use of probability to easily provide behavior that is otherwise
difficult to obtain. The numerous applications the authors refers to
such as transferring tickets from clients to servers to give some
clients higher priority, fine-tuning quality of service for media-based
applications at the OS level and separating resource management between
different groups of tasks through ticket currencies clearly demonstrate
the productiveness of lottery scheduling.
I think this paper does an excellent job of proving its points. The
small case studies are clear and easy to follow. The mathematical
reasoning behind their claims is also convincing. However, comparisons
between lottery scheduling and other scheduling algorithms on the given
tests would have been quite helpful. The results the authors provide
are impressive, but difficult to assess without knowledge of the working
of other algorithms.
This archive was generated by hypermail 2.1.6 : Wed Jan 28 2004 - 15:10:13 PST