ABSTRACT
We present Grouped Distributed Queues (GDQ), the first proportional share scheduler for multiprocessor systems that scales well with a large number of processors and processes. GDQ uses a distributed queue architecture, and 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 Weighted Fair Queuing. By commoditizing processors and decoupling their allocation from process scheduling, GDQ provides, with only constant scheduling overhead, 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 and processes.
- Jon C. R. Bennett and Hui Zhang. WF2Q: Worst-Case Fair Weighted Fair Queueing. In Proceedings of IEEE INFOCOM '96, pages 120--128, San Francisco, CA, Mar. 1996. Google ScholarDigital Library
- Josep M. Blanquer and Banu Ozden. Fair Queuing for Aggregated Multiple Links. In Proceedings of ACM SIGCOMM '01, pages 189--198, San Diego, CA, Aug. 2001. Google ScholarDigital Library
- Bogdan Caprita, Wong Chun Chan, Jason Nieh, Clifford Stein, and Haoqiang Zheng. Group Ratio Round-Robin: O(1) Proportional Share Scheduling for Uniprocessor and Multiprocessor Systems. In Proceedings of the 2005 USENIX Annual Technical Conference, pages 337--352, Anaheim, CA, April 2005. USENIX. Google ScholarDigital Library
- Abhishek Chandra, Micah Adler, Pawan Goyal, and Prashant J. Shenoy. Surplus Fair Scheduling: A Proportional-Share CPU Scheduling Algorithm for Symmetric Multiprocessors. In Proceedings of the 4th Symposium on Operating System Design & Implementation, pages 45--58, San Diego, CA, Oct. 2000. Google ScholarDigital Library
- Abhishek Chandra, Micah Adler, and Prashant Shenoy. Deadline fair scheduling: Bridging the theory and practice of proportionate fair scheduling in multiprocessor systems. In RTAS '01: Proceedings of the Seventh Real-Time Technology and Applications Symposium (RTAS '01), page 3, Washington, DC, USA, 2001. IEEE Computer Society. Google ScholarDigital Library
- A. Demers, S. Keshav, and S. Shenker. Analysis and Simulation of a Fair Queueing Algorithm. In Proceedings of ACM SIGCOMM '89, pages 1--12, Austin, TX, Sept. 1989. Google ScholarDigital Library
- S. J. Golestani. A Self-Clocked Fair Queueing Scheme for Broadband Applications. In Proceedings of IEEE INFOCOM '94, pages 636--646, april 1994.Google ScholarCross Ref
- P. Goyal, H. Vin, and H. Cheng. Start-Time Fair Queueing: A Scheduling Algorithm for Integrated Services Packet Switching Networks. IEEE/ACM Transactions on Networking, pages 690--704, Oct. 1997. Google ScholarDigital Library
- D.S. Hochbaum and D.B. Shmoys. Using dual approximation algorithms for scheduling problems: theoretical and practical results. Journal of the ACM, 34:144--162, 1987. Google ScholarDigital Library
- L. Kleinrock. Computer Applications, volume II of Queueing Systems. John Wiley & Sons, New York, NY, 1976. Google ScholarDigital Library
- Robert Love. Linux Kernel Development. SAMS, Developmer Library Series, first edition, 2004.Google Scholar
- A. Parekh and R. Gallager. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case. IEEE/ACM Transactions on Networking, 1(3):344--357, June 1993. Google ScholarDigital Library
- A. Srinivasan and J. Anderson. Fair scheduling of dynamic task systems on multiprocessors, 2003.Google Scholar
- A. Srinivasan, P. Holman, J. Anderson, S. Baruah, and J. Kaur. Network Processor Design: Issues and Practices Volume II, chapter Multiprocessor Scheduling in Processor-based Router Platforms: Issues and Ideas. Morgan Kaufamann Publishers, 2004.Google Scholar
- Josep Torrellas, Andrew Tucker, and Anoop Gupta. Evaluating the performance of cache-affinity scheduling in shared-memory multiprocessors. J. Parallel Distrib. Comput., 24(2):139--151, 1995. Google ScholarDigital Library
- Uresh Vahalia. UNIX Internals: The New Frontiers. Prentice Hall, Upper Saddle River, NJ, 1996. Google ScholarDigital Library
- T. Wolf and M. Franklin. Locality-aware predictive scheduling for network processors. In Proc. of IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 152--159, Tucson, AZ, Nov. 2001.Google ScholarCross Ref
- Yunkai Zhou and Harish Sethu. On Achieving Fairness in the Joint Allocation of Processing and Bandwidth Resources: Principles and Algorithms. Technical Report DU-CS-03-02, Drexel University, Jul. 2003.Google Scholar
Index Terms
- Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling
Recommendations
Multiprocessor Scheduling of Processes with Release Times, Deadlines, Precedence, and Exclusion Relations
The author presents a scheduling algorithm that solves the problem of finding a feasible nonpreemptive schedule whenever one exists on M identical processors for a given set of processes such that each process starts executing after its release time and ...
Global EDF-based scheduling with laxity-driven priority promotion
This paper presents an algorithm, called Earliest Deadline Critical Laxity (EDCL), for scheduling sporadic task systems on multiprocessors. EDCL is a derivative of the Earliest Deadline Zero Laxity (EDZL) algorithm. Each job is assigned a priority based ...
Interposed proportional sharing for a storage service utility
SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systemsThis paper develops and evaluates new share-based scheduling algorithms for differentiated service quality in network services, such as network storage servers. This form of resource control makes it possible to share a server among multiple request ...
Comments