Group Ratio Round-Robin: O(1) Proportional Share Scheduling for Uniprocessor and Multiprocessor Systems

Bogdan Caprita, Wong Chun Chan, Jason Nieh, Clifford Stein, Haoqiang Zheng

Proceedings of the 2005 USENIX Annual Technical Conference, Anaheim, CA, April 10-15, 2005, pp. 337-352


We present Group Ratio Round-Robin (GR3 ), the first pro- portional share scheduler that combines accurate propor- tional fairness scheduling behavior with O(1) scheduling overhead on both uniprocessor and multiprocessor systems. GR3 uses a simple grouping strategy to organize clients into groups of similar processor allocations which can be more easily scheduled. Using this strategy, GR3 combines the benefits of low overhead round-robin execution with a novel ratio-based scheduling algorithm. GR3 introduces a novel frontlog mechanism and weight readjustment algo- rithm to operate effectively on multiprocessors. GR3 pro- vides fairness within a constant factor of the ideal general- ized processor sharing model for client weights with a fixed upper bound and preserves its fairness properties on multi- processor systems. We have implemented GR3 in Linux and measured its performance. Our experimental results show that GR3 provides much lower scheduling overhead and much better scheduling accuracy than other schedulers commonly used in research and practice.



Columbia University Department of Computer Science