From: Praveen Rao (psrao_at_windows.microsoft.com)
Date: Tue Jan 27 2004 - 22:03:20 PST
Lottery scheduling is a resource allocation mechanism. It provides
efficient, responsive control over the relative execution rates of
computations. It also provides modular resource management by enabling
concurrent modules to isolate their resource allocation policies from
each other. Lottery scheduling can be use to manage resources other than
CPU as well.
Lottery scheduling efficiently implements proportional-share resource
management, wherein the resource consumption rates of active
computations are proportional to relative shares they are allocated.
Basic idea is that resource rights are represented by tickets. Each
allocation is determined by a lottery - the winning ticket is granted
the resource. The probability of a client winning a lottery is
proportional to the number of tickets it holds.
Modular resource management is easily incorporated by concepts like
ticket transfers, ticket inflation, ticket currencies and compensation
tickets. For example, a client calling a server can transfer its tickets
increasing the chances of server getting the resource. Ticket inflation
implies that a client can allocate or deallocate more tickets. As such
this would be unfair but it provides flexibility in case of mutually
trusting clients. Ticket currencies allow expressing of resource rights
in units that are local to a group of mutually trusting clients. Each
currency has to be backed by base currency, which represents the actual
shares of resources. The currencies can actually form an arbitrary
acyclic graph. The currencies would have exchange rate wrt to the base
currencies and that will represent the actual "worth" of the currency to
get favored in resource allocation. A client that consumed only fraction
of its allocated time quantum is granted compensation tickets that will
increase its favorability during the next allocation. This can be useful
for I/O bound tasks and make them responsive.
In my opinion, this modularity is very powerful and can't be easily
achieved by the conventional resource allocation policies.
The paper argues that this scheme would never lead to starvation as any
client holding any tickets would eventually win a lottery. I am not
convinced of this. The probabilistic distribution can only
asymptotically guarantee this and in the most pathological case
starvation can happen even of a higher priority computation.
The paper then discusses implementation of these concepts in Mach 3.0
kernel.
Authors discuss the experiment done to validate the ability of lottery
scheduling to flexibly, responsively and efficiently control relative
rates of computations. Authors take the example of Monte Carlo
simulations to validate the flexibility - the intent in this case being
- increasing resource allocation to new simulations and lowering
resource allocation to the running the existing simulations that are
converging towards a smaller error. Authors discuss using ticket tansfer
in client-server scenarios and ticket allocation for QoS in multimedia
application. All these highlight the flexibility that this algorithm
provides. Authors discuss load insulation to highlight the modularity
possible with this algorithm - a set of computations inflate their
currencies when they allow more computations to join in but this has no
effect of another set of computations that use different currency.
Authors argue that lottery scheduling is very lightweight since a
tree-based lottery need only generate a random number and perform log(n)
addition and comparisons to select a winner amongst n clients.
Authors discuss that lottery scheduling can also be use to manage other
resources. One interesting example was using it for lock access. Similar
to client server example waiting threads transfer their tickets to the
thread holding the lock resulting in effectively boosting prioritization
of the thread holding the lock. When the thread releases the lock, it
again hold lottery to pick the thread to which to transfer the lock
ownership.
Lottery scheduling can be used not only for time-shared resources but
also for the space shared resources, e.g. memory. In this case the
notion is inverted - loser of the lottery is chosen to given up a unit
of resource it holds.
Overall it sounds like a powerful idea, though managing sets of mutually
trusting computations (which can form currency domains) seems
challenging for the OS.
This archive was generated by hypermail 2.1.6 : Tue Jan 27 2004 - 22:04:14 PST