Lottery Scheduling: Flexible Proportional Share Resource Management

C. Waldspurger, and W. Weihl. Proceedings of the First Symposium on Operating Systems Design and Implementation. November 1994, pp. 1-12

Overall, a really good paper. Basically give tickets to apps and hold a lottery to do scheduling. This is probabilistically fair (borne out in testing) and avoids starvation.

Ticket transfer can eliminate priority inversion and allows cooperating processes to trade rights.

Local currencies allows sub-allocation of tickets at whatever granularity is desired.

Implementation is lightweight and effective.


Umesh Shankar
Last modified: Thu Jul 5 15:55:02 PDT 2001