Date: June 3, 1999
Time: 1 PM
Place: Wean Hall 8220
Speaker: David Petrou, Carnegie Mellon University
Implementing Lottery Scheduling: Matching the Specializations in Traditional Schedulers
Abstract:
I will describe extensions to lottery scheduling, a proportional-share resource management algorithm, to provide the performance assurances present in traditional non-real time process schedulers. Lottery scheduling enables flexible control over relative process execution rates with a ticket abstraction and provides load insulation among groups of processes using currencies. I will first show that a straightforward implementation of lottery scheduling does not provide the responsiveness for a mixed interactive and CPU-bound workload offered by the decay usage priority scheduler of the FreeBSD operating system. Moreover, standard lottery scheduling ignores kernel priorities used in the FreeBSD scheduler to reduce kernel lock contention.
In this talk, I will show how to use dynamic ticket adjustments to incorporate into a lottery scheduler the specializations present in the FreeBSD scheduler to improve interactive response time and reduce kernel lock contention. This is achieved while maintaining lottery scheduling's flexible control over relative execution rates and load insulation. In spite of added scheduling overhead, the throughput of CPU-bound workloads under the scheduler is within one percent of the FreeBSD scheduler for all but one test. I will describe our design, evaluate our implementation, and relate our experience in deploying this hybrid lottery scheduler on production machines.
SDI / LCS Seminar Questions?
Karen Lindenfelser, 86716, or visit www.pdl.cmu.edu/SDI/