From: Chuck Reeves (creeves_at_windows.microsoft.com)
Date: Wed Jan 28 2004 - 13:59:03 PST
The paper "Lottery Scheduling: Flexible Proportional-Share Resource
Management" was written by a number of researchers at MIT. The document
describes the design, benefits and performance of using weighted
elections to grant (and potentially deny) access to constrained
resources. This algorithm is proposed for use in managing access to a
diverse set of resources including CPU allocation, I/O bandwidth, memory
and mutexes. The use of currency as an abstraction of proportion made
the description of the algorithm simple to understand. I appreciated how
the ticket transfer mechanism is used to proportionately increase the
"priority" of threads with waiting on I/O and blocking activities. Given
the simplicity of this algorithm, the outcomes described in section 5 of
the document were not much of a surprise. One topic not discussed in
this paper was the impact of ignoring any sense of sequencing that
exists in the creation of a set of tasks.
Chuck Reeves, creeves_at_microsoft.com
Microsoft | Windows | Directory Services
This archive was generated by hypermail 2.1.6 : Wed Jan 28 2004 - 13:59:11 PST