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

Department of Computer Science, Columbia University Technical Report , CUCS-028-04, July 2004


Proportional share resource management provides a flexi- ble and useful abstraction for multiplexing time-shared re- sources. We present Group Ratio Round-Robin (GR3 ), the first proportional share scheduler that combines accu- rate proportional fairness scheduling behavior with O(1) scheduling overhead on both uniprocessor and multipro- cessor systems. GR3 uses a novel client grouping strat- egy 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. GR3 can provide fairness within a constant factor of the ideal generalized processor shar- ing model for client weights with a fixed upper bound and preserves its fairness properties on multiprocessor systems. We have implemented GR3 in Linux and measured its per- formance against other schedulers commonly used in re- search and practice, including the standard Linux sched- uler, Weighted Fair Queueing, Virtual-Time Round-Robin, and Smoothed Round-Robin. Our experimental results demonstrate that GR3 can provide much lower scheduling overhead and much better scheduling accuracy in practice than these other approaches.



Columbia University Department of Computer Science