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

Proportional share resource management provides a flexible and useful abstraction for multiplexing time-shared resources. However, previous proportional share mechanisms have either weak proportional sharing accuracy or high scheduling overhead. We present Group Ratio Round-Robin (GR3), a proportional share scheduler that can provide high proportional sharing accuracy with O(1) scheduling overhead. Unlike many other schedulers, a low-overhead GR3 implementation is easy to build 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 scheduling overhead and better scheduling accuracy in practice than these other approaches for large numbers of clients