From: David Coleman \(Roxio Inc\) (v-davcol_at_windows.microsoft.com)
Date: Wed Jan 28 2004 - 12:24:33 PST
The Lottery Scheduling approach was interesting and seems to be a unique
mechanism for dealing somewhat fairly with resource contention. It
allows very fine-grained prioritization which can be tuned to a given
applications needs. It is also flexible enough that it can change the
prioritization during different phases of application execution based on
the needs of the application.
The overall concept is that each entity contending for a resource gets
one or more tickets for that resource. When the resource comes
available, a lottery is held. The lottery consists of generating a
random number between 1 and the number of tickets outstanding. The list
of waiters is then traversed summing the number of tickets held by each
waiter. When the number is reaches the random number chosen, that
waiter acquires the resource. There are several optimizations available
that produce good performance.
Ticket transfers are also possible. This allows a general purpose
process to receive resource allocations (such as processor time) on
behalf of the client. This allows tickets to actually be allocated to
tasks or computations (in the Multics terminology) instead of processes
or threads. This seems to be a more useful approach.
I take issue with the statement in section 2.2 that states: "Since any
client with a non-zero number of tickets will eventually win a
lottery,...". I understand that probabilistically that is true, but it
is possible to have a situation where better funded clients are
continually being created and a random number sequence is produced that
always selects the first client in the list thus starving the original
client.
This is another case where a generalized mechanism in the kernel isn't
good enough for demanding applications and is thus some control is
transferred to user mode for finer tuning when necessary. It appears in
this case that substantially more work is needed to understand the
implications of using this concept in the wild. Users probably don't
care or understand these concepts in most cases. However, application
programmers will and I suspect this ability might be misused if exposed
to general purpose applications.
This archive was generated by hypermail 2.1.6 : Wed Jan 28 2004 - 12:24:39 PST