From: Nathan Dire (ndire_at_cs.washington.edu)
Date: Wed Jan 28 2004 - 14:55:17 PST
In "Lottery Scheduling: Flexible Proportional-Share Resource Management",
Waldspurger and Weihl present a method of scheduling which exploits randomness
to implement proportional-share resource management. This mechanism is very
simple and flexible, and is able to provide allocations close to the assigned
proportion.
The implementation of the mechanism is very simple. The entities are given
"tickets" in ranges according to their assigned share of the resource. When
multiple entities request use of a resource, the scheduling algorithm
generates a random number and determines which entity "won" the lottery. This
eliminates the need for complex mechanisms to ensure proportional allocations.
This system is very flexible because it is easy to change the allocation of
the tickets. Clients can give tickets to another client that they are
waiting on via ticket transfers. Clients can be compensated for consuming
less than their share of the resource by being given additional tickets.
Tickets can be exchanged between resource domains to help with the problem of
priority inversions.
The first question that comes to mind in evaluating this idea is how well the
algorithm can perform, given that it generates random numbers and searches for
a winner. The authors implement the algorithm on the Mach microkernel. The
use the Park-Miller pseudo-random number generator, and use a binary tree to
find the winner. The result is that application can execute faster than with
the unmodified Mach scheduler, and the allocations are very close to the
assigned proportion.
Overall, I find it very difficult to find any flaws with this paper. The idea
is very simple and elegant, and the presentation is both complete and concise.
The results are clearly relevant and there are areas for future work.
This archive was generated by hypermail 2.1.6 : Wed Jan 28 2004 - 14:57:06 PST