From: Greg Green (ggreen_at_cs.washington.edu)
Date: Wed Jan 28 2004 - 10:10:07 PST
The paper describes a novel scheduling system that schedules a process
based on whether it has the winning ticket in a lottery. Each thread
or process is awarded some share of tickets. This is determined by the
operator and can be adjusted with system calls. At each schedule call,
the winning ticket is determined with a random-number generator. This
determines the next process/kernel thread to be scheduled based on
whether it has the ticket or not. The implementation used in the paper
was built on top of Mach 3.0. The processes were in a linear list,
sorted by the number of tickets held, largest at the front of the
list.
Several means of ticket transfers are used. For instance a client
process that blocks on a server, can pass it's lottery tickets to that
server, thereby increasing it's chance of running. Also a process that
doesn't consume its quanta each time it runs, can be given an inflated
number of tickets, so that it gets an equal share of time as another
process that consumes it's entire quanta each time it runs. A system
of currencies is also used which divide up the tickets into logical
boundaries.
The paper then provides performance measurements for several different
types of computations using the scheduling system. Good results were
obtained from compute bound benchmarks, monte-carlo simulations (using
dynamic adjustment of priorities based on progression through the
simulation), client-server applications, and multi-media
applications. A test was run on mutex contention. This allowed 2
groups of threads to be given different priorities to the mutex and
therefore different mutex acquisition rates.
This was quite a novel idea. One of the colloquia last quarter talked
about using random algorithms in routers. It also had better
performance than the previous algorithms. It seems that probabilistic
algorithms can have widespread applications and one should look out
for the opportunities to try them out. This scheduling algorithm
seemed like it would be quite suitable for specialized tasks allowing
a much finer level of control.
The paper also alludes to an auction based system of schedulers. I
couldn't picture how that would work.
-- Greg Green
This archive was generated by hypermail 2.1.6 : Wed Jan 28 2004 - 10:12:38 PST