From: Richard Jackson (richja_at_expedia.com)
Date: Wed Jan 28 2004 - 14:05:58 PST
This late-1994 paper by Waldspurger and Weihl discusses lottery
scheduling, which they claim is a novel scheduling method that provides
better fairness and control than existing schedulers.
The paper is comprised of three parts: 1) lottery scheduling, 2)
performance of prototype, 3) applications of this scheduler
First, the paper talked about the general concept of lottery scheduling.
The concept is pretty straightforward, with definitions very similar to
traditional lottery and currency systems. The base idea is a lottery
ticket, which is essentially a chance to win a virtual lottery. Each
process has one or more tickets, and the periodic lottery decides which
process gets to execute. An underlying notion of tickets is that of a
currency, which means that some tickets may have more relative value
than other tickets, and are therefore more likely to win a lottery. The
currency scheme is hierarchical, so groups of processes could be
controlled independently of others. Supposedly, the scheme could also
be used to control access, which seems to be orthogonal to the purpose
of this system.
Performance was discussed, and it was shown that the lottery scheduler
has similar overhead to the native Mach scheduler. Also, the configured
lottery proportions are generally maintained during actual tests. They
noted that the overall fairness of the lottery will be increased for
longer run-times. For shorter run-times, the results may vary somewhat.
The key consideration is the size of your runtime versus the size of the
scheduling strata(time slices).
Regarding applications, they noted a database application where each
client could have different lottery ticket proportions. Another example
used a Monte Carlo statistical task, which used the ticket scheduler to
adaptively change scheduling during algorithm iteration. These two
examples show how the lottery scheduler can be very powerful in specific
situations. Other possible applications are discussed, such as the
management of shared locks or virtual memory.
The largest problem I see with this scheduler is that the ticket
proportions seem very difficult to manage. Each application would need
to be tuned relative to all other applications running on the machine.
While a very fine level of control is possible, I think that this method
would be reduced to the equivalent of priorities in many applications.
That is, some default ticket settings would be used for all applications
of the same class, and therefore the lottery scheduler wouldn't provide
any benefit.
Overall, I was impressed by this scheme. The provided examples
demonstrated the power of this approach for such things as a graphics
rendering or distributed database application. In the database
application, I could definitely see this feature being useful to
constrain the relative scheduling of different types of queries and/or
users. Then again, this problem could also be solved by using
traditional priorities.
This archive was generated by hypermail 2.1.6 : Wed Jan 28 2004 - 14:08:43 PST