Lottery Scheduling

Big Issue
Simple priority schemes cannot describe large complex systems.
Their mechanism gives a modular way for applications to schedule their
constituent parts in ways that the OS too often does not have the
power to know about (if it should is another matter).
Their prototype resource is locks (mutexes) and their acquisition (to
help priority inversion).
Benefits: abstract, relative (can have many tickets to make a fine
grained scheme), probabilisticly fair.


Mechanism
Can transfer tickets based on dependencies (if waiting for someone,
you can give your tickets away) -- presumably this is just for this
particular resource.
Can use inflation amoung mutually trusting clients -- perhaps a
problem.
Currencies are backed by other, more primitive ones (with an exchange
rate).
Can get compensation tickets for not using all of a resource.
4.5 shows that compensation is a pretty fixed arbitrary policy.
Children take tickets from their parents.
Can use an inverse lottery to help share divisible resources like
memory.


Conclusions
They don't really show any tangible benefits.
However, OS is able to retain global picture of what should have
priority and leave micromanagement of a process's resources to itself.
Compare to multilevel feedback queues where long running jobs get
lower priority but longer time slices.
This paper brought back scheduling as an important idea.
Might not really benefit I/O bound jobs (often better to interleave
their requests).


Lottery Scheduling: Flexible Proportional-Share Resource Management
Carl Waldspurger, William Weihl

The authors present a simple scheduling scheme that differs from
widely deployed priority-based methods in allowing for intuitive,
proportional resource management, as well as naturally provides
other desirable properties missing from more complex scheduling
algorithms.  The central idea of their system is allocating each
consumer a number of tickets, which are placed in a lottery to
vie for a resource; when it becomes time to schedule the resource,
a random "ticket" is chosen, and a particular consumer's chance of
winning is proportional to its share of the total number of tickets
in the lottery.  Tickets behave much like money, and the paper
describes several constructs for lottery scheduling analogous to
market controls, including ticket transfers and currencies; the
former allow blocked processes to speed up another process they
are waiting for, while the latter allow for localized resource
management.  Another added feature of the authors' lottery system
is ensuring that resources are apportioned fairly (i.e., in
proportion to number of tickets owned) over time, through use of
compensation tickets.

This paper presents a novel approach to the scheduling problem
that makes use of non-determinacy to easily provide behavior that
is otherwise difficult to obtain.  The numerous applications the
authors give -- transfering tickets from clients to servers to give
some clients higher priority, fine-tuning QoS for media-based
applications at the OS level, separating resource management between
different groups of tasks through ticket currencies -- demonstrate
the fecundity of lottery scheduling.  However, while such information
may exist in the literature, comparisons between lottery scheduling
and other scheduling algorithms on the given tests would have been
quite helpful.  The results the authors provide are impressive, but
difficult to assess without knowledge of how other algorithms perform.