Implementing lottery scheduling: matching the specializations in traditional schedulers
David Petrou, John W. Milford, Garth A. Gibson · 1999
This paper extends lottery scheduling, a proportional-share resource management algorithm, to provide the performance assurances present in traditional non-real time process schedulers. Proportional-share scheduling enables flexible control over relative process execution rates and provides load insulation among groups of processes using a ticket abstraction. We 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 paper, we 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. We achieve this while maintaining lottery schedu...