Citation: Waldspurger, C.A and Weihl, W.E., "Lottery Scheduling: Flexible Proportional- Share Resource Management", Proceedings of the First Symposium on Operating Systems Design and Implementation, Monterey CA, November 1994, pp. 1-11. * Summary Lottery scheduling provides efficient, responsive control over the relative execution rates of computations. It can be used to enable concurrent modules to insulate their resource allocation policies from on another through the use of currencies. The technique can also be generalized to manage diverse resources such as I/O bandwidth, memory, and access to locks. * Why We Need Lottery Scheduling - accurate control over the quality of service provided to users and apps requires support for specifying relative computation rate - priority based scheduling does not provide the encapsulation and modularity properties required for engineering large software systems - fair share and microeconomic schedulers are limited to relatively coarse control over long-running computations, and are ineffective for interactive systems which require rapid, dynamic control on the time scale of ms to s * Lottery Scheduling Lottery scheduling is a randomized resource allocation mechanism. Resource rights are represented by lottery tickets, and allocations are determined by holding lotteries with the resource granted to the winner. The chance of winning the lottery is proportional to the share of tickets held by a client, and thus scheduling by lottery is probabilistically fair. Tickets encapsulate resource rights that are abstract, relative, and uniform. They are abstract in that they are independent of machine details. They are relative in that the fraction of a resource represented varies dynamically in proportion to the contention for the resource. Finally, they are uniform because rights for heterogeneous resources can be homogeneously represented. Two advantages to lottery scheduling are that starvation cannot occur (it is statistically impossible) and changes to relative ticket allocations are immediately reflected in the next allocation decision (so its extremely responsive). One major requirement for a good implementation of lottery scheduling is a fast way to generate uniformly-distributed random numbers. The one used in the paper is based on the Park-Miller algorithm and is implemented in 10 RISC instructions. * Statistical Properties of Lotteries - number of lotteries won by a client has a binomial distribution, the number of lotteries until the first win has a geometric distribution - probability that client w/ t tickets will win a lottery w/ T total tickets is t/T - a client's throughput is proportional to its ticket allocation, with accuracy that improves with the square root of the number of lotteries - a client's average response time is inversely proportional to its ticket allocation * Modular Resource Management Ticket transfers may be performed whenever a client blocks due to some dependency, whether it be waiting on a server process or waiting for some lock. This conveniently solves the priority inversion problem similarly to priority inheritance. Ticket inflation/deflation can be used among mutually trusting clients to escalate/decrease a client's resource rights by creating/deleting tickets. This avoids the communication necessary with ticket transfers. Ticket currencies can be used to denominate tickets within a trust boundary. In this case, each ticket is backed by a more primitive currency. Effects of inflation can be locally contained by maintaining an exchange rate between each local currency and a base currency that is conserved. Compensation tickets can be issued to clients that only use a fraction f of their allocated resource quantum. Each compensation ticket inflates the client's value by 1/f until the client starts its next quantum. * Managing Diverse Resources Contention due to synchronization can substantially affect computation rates. Lottery scheduling can be used to control the relative waiting times of threads competing for lock access. This can be accomplished using a mutex currency and an inheritance ticket issued in that currency. As each thread attempts to obtain a lock, it transfers its tickets to fund the mutex currency. The mutex transfers the inheritance ticket to the current holder of the lock, effectively granting it the funding of all waiting threads. Lottery scheduling is typically used for time-shared resources such as the processor. However, it can also be used to provide proportional-share guarantuess for space-shared resources such as memory. In order to do so, an inverse lottery can be used to select a loser who must relinquish a unit of the resource. Since inverse probabilities are used, the more tickets a client has, the more likely it is to avoid having a unit of its resource revoked.