skip to main content
10.1145/1146381.1146396acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling

Published: 23 July 2006 Publication History

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.

References

[1]
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.
[2]
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.
[3]
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.
[4]
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.
[5]
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.
[6]
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.
[7]
S. J. Golestani. A Self-Clocked Fair Queueing Scheme for Broadband Applications. In Proceedings of IEEE INFOCOM '94, pages 636--646, april 1994.
[8]
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.
[9]
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.
[10]
L. Kleinrock. Computer Applications, volume II of Queueing Systems. John Wiley & Sons, New York, NY, 1976.
[11]
Robert Love. Linux Kernel Development. SAMS, Developmer Library Series, first edition, 2004.
[12]
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.
[13]
A. Srinivasan and J. Anderson. Fair scheduling of dynamic task systems on multiprocessors, 2003.
[14]
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.
[15]
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.
[16]
Uresh Vahalia. UNIX Internals: The New Frontiers. Prentice Hall, Upper Saddle River, NJ, 1996.
[17]
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.
[18]
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.

Cited By

View all
  • (2020)Balancing Fairness and Efficiency for Cache Sharing in Semi-external Memory SystemProceedings of the 49th International Conference on Parallel Processing10.1145/3404397.3404450(1-11)Online publication date: 17-Aug-2020
  • (2019)Towards Relaxed Concurrent Data Structures on Distributed Memory Computer Systems2019 International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon)10.1109/FarEastCon.2019.8934183(1-6)Online publication date: Oct-2019
  • (2018)A Markov-Chain Model Based Study of Distributed Weighted Round-Robin Scheduling for Data Centers2018 International Conference on Advanced Computation and Telecommunication (ICACAT)10.1109/ICACAT.2018.8933588(1-8)Online publication date: Dec-2018
  • Show More Cited By

Index Terms

  1. Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
    July 2006
    230 pages
    ISBN:1595933840
    DOI:10.1145/1146381
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 23 July 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. fair queuing
    2. multiprocessor scheduling
    3. proportional sharing
    4. quality of service
    5. resource management
    6. scheduling

    Qualifiers

    • Article

    Conference

    PODC06

    Acceptance Rates

    Overall Acceptance Rate 740 of 2,477 submissions, 30%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)7
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2020)Balancing Fairness and Efficiency for Cache Sharing in Semi-external Memory SystemProceedings of the 49th International Conference on Parallel Processing10.1145/3404397.3404450(1-11)Online publication date: 17-Aug-2020
    • (2019)Towards Relaxed Concurrent Data Structures on Distributed Memory Computer Systems2019 International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon)10.1109/FarEastCon.2019.8934183(1-6)Online publication date: Oct-2019
    • (2018)A Markov-Chain Model Based Study of Distributed Weighted Round-Robin Scheduling for Data Centers2018 International Conference on Advanced Computation and Telecommunication (ICACAT)10.1109/ICACAT.2018.8933588(1-8)Online publication date: Dec-2018
    • (2017)Analysis and Evaluation of Scheduling Policies for Consolidated I/O OperationsJournal of Grid Computing10.1007/s10723-017-9392-415:1(107-125)Online publication date: 1-Mar-2017
    • (2015)Fair-Share Scheduling for Performance-Asymmetric Multicore Architecture via Scaled Virtual RuntimeProceedings of the 2015 IEEE 21st International Conference on Embedded and Real-Time Computing Systems and Applications10.1109/RTCSA.2015.10(60-69)Online publication date: 19-Aug-2015
    • (2013)Uncovering CPU load balancing policies with harmonyProceedings of the ACM International Conference on Computing Frontiers10.1145/2482767.2482784(1-10)Online publication date: 14-May-2013
    • (2012)Providing Fair Share Scheduling on Multicore Cloud Servers via Virtual Runtime-based Task Migration AlgorithmProceedings of the 2012 IEEE 32nd International Conference on Distributed Computing Systems10.1109/ICDCS.2012.33(606-614)Online publication date: 18-Jun-2012
    • (2010)Fuzzy expert system for load balancing in symmetric multiprocessor systemsExpert Systems with Applications: An International Journal10.1016/j.eswa.2010.06.04937:12(8711-8720)Online publication date: 1-Dec-2010
    • (2009)Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robinACM SIGPLAN Notices10.1145/1594835.150418844:4(65-74)Online publication date: 14-Feb-2009
    • (2009)Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robinProceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/1504176.1504188(65-74)Online publication date: 14-Feb-2009
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media