Group Ratio Round-Robin: An O(1) Proportional Share Scheduler

Wong Chun Chan

Ph.D. Thesis, Department of Computer Science, Columbia University, June 2004


Proportional share resource management provides a flexible and useful abstraction for multiplexing time-shared resources. We present Group Ratio Round-Robin (GR3), a proportional share scheduler that combines accurate proportional fairness scheduling behavior with O(1) scheduling overhead. GR3 uses a novel client grouping strategy to organize clients into groups of similar processor allocations which can be more easily scheduled. Using this grouping strategy, GR3 combines the benefits of low overhead round-robin execution with a novel ratio-based scheduling algorithm. We analyze the behavior of GR3 and show that it can provide fairness within a constant factor of the ideal generalized processor sharing model for client weights with a fixed upper bound. GR3 can be easily implemented using simple data structures. We have implemented GR3 in Linux and measured its performance against other schedulers commonly used in research and practice, including the standard Linux scheduler, Weighted Fair Queueing, Virtual-Time Round-Robin, and Smoothed Round-Robin. Our experimental results demonstrate that GR3 can provide much lower schedul- ing overhead and much better scheduling accuracy in practice than these other ap- proaches.



Columbia University Department of Computer Science