Grouped Distributed Queues: Distributed Queue, Proportional Share Multiprocessor Scheduling
- Grouped Distributed Queues: Distributed Queue, Proportional Share Multiprocessor Scheduling
- Caprita, Bogdan
Stein, Clifford S.
- Technical reports
- Computer Science
Industrial Engineering and Operations Research
- Persistent URL:
- Columbia University Computer Science Technical Reports
- Part Number:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- We present Grouped Distributed Queues (GDQ), the first proportional share scheduler for multiprocessor systems that, by using a distributed queue architecture, scales well with a large number of processors and processes. GDQ achieves accurate proportional fairness 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 similar 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 migrating processors among groups. The set of processors working on a group use simple, low-overhead round-robin queues, while processor reallocation among groups is achieved using a new multiprocessor adaptation of the well-known Weighted Fair Queuing algorithm. By commoditizing processors and decoupling their allocation from process scheduling, GDQ provides, with only constant scheduling cost, fairness 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.
- Computer science
- Item views
text | xml
- Suggested Citation:
- Bogdan Caprita, Jason Nieh, Clifford S. Stein, 2006, Grouped Distributed Queues: Distributed Queue, Proportional Share Multiprocessor Scheduling, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:29440.