From: Prasanna Kumar Jayapal (prasak_at_winse.microsoft.com)
Date: Wed Jan 28 2004 - 17:33:29 PST
This paper ("Lottery Scheduling") presents a very nice mechanism for
scheduling and allocation of resources with in a system. It further goes
on to say that this logic can be generalized to be used to manage any
resources. Then it talks about the implementation details and the
prototype lottery scheduler that was implemented for Mach 3.0
microkernel and summaries the results of several quantitative
experiments.
As the name indicates, the whole idea is based on the "lottery".
Resource rights are represented by lottery tickets. Each task that
needs to use a resource holds a lottery ticket. Resource allocation is
determined by a lottery (using a random number generator). The winner of
the lottery gets the resource. The expected allocation of resources to
tasks
is proportional to the number of tickets that they hold. The authors
claim that this method is probabilistically fair and give a nice
explanation. They further go on to say that startvation does not exist
as any client with atleast 1 ticket will eventually win a lottery.
A client can acquire tickets in many ways. Tickets can be transferred
from one client to another or a client can escalate its resource rights
by creating more tickets (ticket inflation). Componensation tickets are
granted to clients that uses only a fraction of its alocated resource.
Currencies were not very clear initially. However, I got a better
picture in the implementation section while going through the examples.
The experiments that talk about fairness and flexible control were nice
to read through. In general, the experiments seem to convice that the
lottery scheduler provides fair execution time with respect to the
number of tickets each of the clients hold. In the end, the authors
mention that this could be used for other resources like memory
management, IO, multiple resources, etc.
Overall, I thought it was an interesting algorithm and the authors do a
good job of presenting this novel approach to the scheduling problem.
This archive was generated by hypermail 2.1.6 : Wed Jan 28 2004 - 17:33:26 PST