From: Gail Rahn (grahn_at_cs.washington.edu)
Date: Wed Jan 28 2004 - 12:18:13 PST
Review of "Lottery Scheduling" paper by Waldspurger and Weihl
This paper introduces a resource-scheduling system called "lottery
scheduling". It is a proportional-share scheduling mechanism that provides
efficient control over relative execution rates of computations, and is
said to better accomodate the needs of client/server and interactive
computing than traditional priority-based scheduling systems. The
lottery-scheduling algorithm can also be applied to lock-sharing,
mutex-acquisition and memory-management.
Lottery scheduling is simply described as a ticket-based system where
resources are allocated according to the ratio of tickets held by each
competing client. Clients request tickets for access to a resource. A
lottery is held, and the winning ticket is granted the resource. The next
lottery allocates the resource among all clients losing the previous
lottery.
Clients hold tickets of various values, multiples of some base currency
value. (Much like there are $10 and $1 bills in my wallet, one client's
ticket can be worth 10 units while another's ticket is worth 1 unit.)
Tickets are converted into base values when the lottery is run, so that the
winner is selected according to the proportion of provided tickets. Tickets
can be transferred between clients (a blocking thread transfers its
tickets, for example, to related running thread). The authors present two
simple mechanisms for efficiently discovering the lottery winner. Lottery
scheduling also prevents resource starvation. Because a client holds a
ticket for the resource lottery, that client is assured of eventually
winning the lottery and always (eventually) gaining access to the resource.
The lottery-scheduling algorithm seems to rely on well-behaved clients. The
paper reveals that a client can inflate its own ticket value, effectively
increasing their odds of being granted access to a resource. In their
tests, clients requested lottery tickets using some proportion. The
researchers showed that when tickets were requested with some ratio of
currency values, resources were allocated consistently with the ratios.
It's unclear to me what part of the operating system is the ticket
arbitrator - ensuring that clients compete in the correct proportion for
resources. Which operating system component decides the ratios of resource
allocation between competing clients? What protections would be in place to
manage a misbehaving client - one who always requests too many tickets?
Also, under waht conditions would allocated currency ratios between clients
change, and what OS behavior would prompt such a change? Resource hogging?
-------------
Gail Rahn
grahn_at_cs.washington.edu
This archive was generated by hypermail 2.1.6 : Wed Jan 28 2004 - 12:18:20 PST