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

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