From: Steve Arnold (steve.arnold4_at_verizon.net)
Date: Tue Jan 27 2004 - 21:27:40 PST
This relatively short paper describes basically an algorithm for scheduling
within an operating system. The authors leave it fairly open-ended for what
resources are scheduled. The whole thing is based on a lotter metaphor,
where each task contending for resources holds lottery tickets with a preset
value. A random number generator then "picks the winner." The winner gets a
certain number of quantums on the resource. It is possible to have a number
of currencies on the system. Each currency runs its own lottery, as I
understand it.
In their testing, they show that the lottery is quite fair, despite the
random aspect of it. It also has about the same overhead (slightly less) as
competing scheduling systems. The authors really do a lot of tests to
basically demonstrate the design of the system (which could have as easily
been done mathematically as experimentally).
This was one of the more straight-forward papers we have read to date. It
basically shows that a random algorithm, in most cases, is just as good as
much more complicated systems. They do complain that priorities are rarely
used properly in other systems; I wonder if it will be the same with this
one. I would like to know where they took this research and if it has been
implemented in any production systems.
This archive was generated by hypermail 2.1.6 : Tue Jan 27 2004 - 21:27:35 PST