Grouped Distributed Queues: Distributed Queue, Proportional Share Multiprocessor Scheduling

Bogdan Caprita, Jason Nieh, Clifford Stein

Proceedings of the 25th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2006), Denver, CO, July 23-26, 2006, pp. 72-81


We present Grouped Distributed Queues (GDQ ), the first propor- tional share scheduler for multiprocessor systems that scales well with a large number of processors and processes. GDQ uses a dis- tributed queue architecture, and achieves accurate proportional fair- ness scheduling with only O(1) scheduling overhead. GDQ takes a novel approach to distributed queuing: instead of creating per- processor queues that need to be constantly balanced to achieve any measure of proportional sharing fairness, GDQ uses a simple grouping strategy to organize processes into groups based on sim- ilar processor time allocation rights, and then assigns processors to groups based on aggregate group shares. Group membership of processes is static, and fairness is achieved by dynamically migrat- ing processors among groups. The set of processors working on a group use simple, low-overhead round-robin queues, while proces- sor reallocation among groups is achieved using a new multipro- cessor adaptation of Weighted Fair Queuing. By commoditizing processors and decoupling their allocation from process schedul- ing, GDQ provides, with only constant scheduling overhead, fair- ness within a constant of the ideal generalized processor sharing model for process weights with a fixed upper bound. We have implemented GDQ in Linux and measured its performance. Our experimental results show that GDQ has low overhead and scales well with the number of processors and processes.



Columbia University Department of Computer Science