From: Joanna Muench (joannam_at_spro.net)
Date: Tue Jan 27 2004 - 21:17:02 PST
Waldspurger and Weihl (1994) present an interesting solution to resource
allocation via a lottery system. The authors successful demonstrate the
current paucity of mechanisms to distribute resources flexibly but
fairly. They primarily position their work as a solution to
computational resources, but illustrate how to apply the mechanism to
I/O bandwidth, memory and access to locks. The authors argue that their
allocation algorithm is both fair and considerably simpler than
previously proposed mechanisms. The later claim is easy to believe given
how readable this paper is.
The central idea to the lottery schedule is the allocation of tickets
among clients, with each ticket within the ticket pool or list
representing an equal chance of winning the resource. Tickets can be
apportioned among the competing clients according to a prioritization
scheme. The authors don't explicitly state that once used a ticket is
returned to the ticket list, but that seems to be implicit in their
argument. I believe this makes their mechanism equivalent to
sampling-with-replacement, a well-established statistical method.
I found the initial lottery mechanism quite interesting, but especially
appreciated their discussions of topics such as ticket transfers and
compensation tickets. The ticket transfer idea seemed particularly
slick, as a way for a high priority task to transfer its priority to a
service. The compensation ticket concept is a little clunky, but
obviously necessary for processes that only run briefly.
I would have liked to see more discussion about the problem of ticket
inflation and protection mechanisms to prevent clients from generating
extra tickets. The mechanism would need to be very flexible since
inflation/deflation could be useful as an allocation tool, but could
also unbalance the system if utilized improperly.
Overall this paper did an excellent job of covering the concept of
lottery scheduling from the abstract to several concrete examples. The
authors provide an elegant and flexible mechanism to allocate resources
preferentially with low-overhead.
This archive was generated by hypermail 2.1.6 : Tue Jan 27 2004 - 21:13:27 PST