GR3: O(1) Proportional Share Resource Management

Proportional share resource management provides a flexible and useful abstraction for multiplexing time-shared resources. We introduce a family of round-robin proportional share schedulers that combine accurate proportional fairness scheduling behavior with O(1) scheduling overhead. Group Ratio Round-Robin (GR3) is one such scheduler we have developed that 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 have analyzed the behavior of GR3 ane measured its performance against other schedulers commonly used in research and practice, including the standard Linux scheduler, Weighted Fair Queueing, 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.