From: Justin Voskuhl (justinv_at_microsoft.com)
Date: Mon Jan 26 2004 - 14:53:01 PST
This paper presents an interesting approach to fairly sharing resources.
In the Lottery scheduling system, each time a shared resource becomes
free, a "lottery" is held to determine which party will get to use the
resource next. The lottery is run by picking a winning "ticket." Then
a search is done to find the owner of the winning ticket. They have
organized their system so that this search takes on average O(ln n).
The owner of the winning ticket is granted access to the resource.
The more interesting ideas come when they explore allowing different
parties to share lottery tickets. An example is given of a client
waiting on a server to complete an RPC. It can temporarily give its
tickets over to the server, giving the server a "boost" to complete the
work at hand. Another example of this is for threads waiting on a mutex
to give their tickets temporarily to the thread current in the mutex.
This causes the thread in the mutex to potentially complete its work
faster and unblock.
The authors introduce the idea of currency, which is a multiplier on the
value of lottery tickets. It can be used to give more weight to the
tickets of some parties in the system. This idea seems somewhat tacked
on, although I can see how it might be a useful extension in some cases.
The system is fair over long periods of time, although for short periods
of time it can temporarily be unfair. The authors argue that on the
computers they were building the system on that the scheduler was fair
after about a second of time. They have another way of handling
scheduling fairness, which is to adjust the weight of lottery tickets if
a time-slice isn't completely used. If the user is using only f
fraction of their time slice, at the next lottery their tickets have
weight 1/f so they are in effect boosted to preserve fairness.
The authors finally discuss other applications, like using another
lottery system to find victims for page faults. In this lottery system,
having more tickets makes you more likely to NOT win the lottery, and
therefore be less likely to have your memory paged out.
This archive was generated by hypermail 2.1.6 : Mon Jan 26 2004 - 14:53:09 PST