From: Ian King (iking_at_killthewabbit.org)
Date: Wed Jan 28 2004 - 09:30:15 PST
Waldspurger and Weihl describe a unique scheduling algorithm for fairly
balancing access to system resources - "fair" being decided by user input. This
algorithm allows for assignment of numerical weight to processes or other system
resources, which are then assigned based on a lottery, or random draw of a
number that corresponds to one choice of many. The authors describe various
features that enable this mechanism, compare it with other scheduling policies
including the commonly-implemented priority scheme, and provide empirical data
of an implementation on the Mach microkernel. A particularly important claim is
that this mechanism allows for dynamic response to changing system needs.
While this scheme is intriguing in many ways, I was distracted by the somewhat
forced allusions to monetary concepts. Nonetheless, after reading through it a
couple of times, I realized that implementing this effectively can be almost
sinfully trivial - which is good in a component such as the scheduler, which
impacts performance enormously if done poorly. This mechanism avoids protocol
inversion and starvation, because the probability of a given process being
scheduled to run is never zero; however, it is interesting that Ethernet was
still scheduled with a fixed high priority. Some devices simply cannot be
deferred with impunity, and Ethernet falls in that class because of the short
time in which the device accumulates large amounts of data - it is simply
imperative that it is serviced with regularity. This suggests that lottery
scheduling is inappropriate for any sort of real-time system, which is
intuitively apparent.
The scheme of ticket transfers to a server on which a client is blocked is quite
clever; I can envision an implementation in which the ready queue is a list of
(owner, value) pairs, and the owner is simply changed for the duration of the
call, again producing a simple and fast mechanism. The discussion of balancing
Monte Carlo simulations demonstrated the idea of weighting priority based on
some value calculated in the system, which allows for very adaptive scheduling
with little overhead; traditional priority schemes require more complex mapping
of need onto the arbitrary priority value, which nonetheless does not affect
other priority values that may be higher and still supercede the process at
issue.
Given my experience in a priority-based operating system, I am of the opinion
that application programmers would have a difficult time adapting to this
scheduling policy. Systems are often designed with careful tuning of relative
priorities, with decision processes that may degenerate into religious wars.
While modern hardware provides such fast processing that in most cases there
would not likely be any noticeable difference in responsiveness or throughput in
anything short of a true real-time application, programmers would find it
difficult to surrender that control to a probabilistic process. Nonetheless, I
find it fascinating.
This archive was generated by hypermail 2.1.6 : Wed Jan 28 2004 - 09:43:10 PST