From: Jeff Duzak (jduzak_at_exchange.microsoft.com)
Date: Tue Jan 27 2004 - 00:38:39 PST
This paper describes the lottery scheduling system. The system accomplishes proportional-share resource allocation by assigning each potential user of a resource a certain number of tickets. Then, when selecting a user to schedule, one ticket out of the total allocated is selected, and the owner of the ticket gets to use the resource.
The paper then talks about a method by which a thread can relinquish control of a resource early and yet still be allocated its proper proportion of the resource over time. Further, the paper talks about further subdividing resource allocation within a given task. The analogies with currency markets are amusing.
The idea is very simple, yet it leads to some cool features. First of all, because it is proportional rather than priority-based, the system prevents the possibility of thread starvation. Second, the system allows fair distribution of resources even when one thread makes an RPC to another thread to perform some task on its behalf. The caller can transfer its share of resources to the callee in order that the callee can complete the RPC faster, and return to the caller sooner. Likewise, when threads are waiting on a mutex, those threads can transfer their share of resources to the mutex holder, so that it can release the mutex sooner.
Another really cool feature of the system is that it maps well onto the users notions of relative importance of threads. In particular, the paper describes using the lottery mechanism on a server. A thread processing a caller's request can be given resources proportional to the credits the caller provides. Hence, a customer who pays for the right to call a server can be given access to the server proportional to the money paid for that access.
This archive was generated by hypermail 2.1.6 : Tue Jan 27 2004 - 00:38:30 PST