research-article

Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin

Authors:

Dan Baumberger,

Scott HahnAuthors Info & Claims

ACM SIGPLAN Notices, Volume 44, Issue 4

Pages 65 - 74

https://doi.org/10.1145/1594835.1504188

Published: 14 February 2009 Publication History

Abstract

Fairness is an essential requirement of any operating system scheduler. Unfortunately, existing fair scheduling algorithms are either inaccurate or inefficient and non-scalable for multiprocessors. This problem is becoming increasingly severe as the hardware industry continues to produce larger scale multi-core processors. This paper presents Distributed Weighted Round-Robin (DWRR), a new scheduling algorithm that solves this problem. With distributed thread queues and small additional overhead to the underlying scheduler, DWRR achieves high efficiency and scalability. Besides conventional priorities, DWRR enables users to specify weights to threads and achieve accurate proportional CPU sharing with constant error bounds. DWRR operates in concert with existing scheduler policies targeting other system attributes, such as latency and throughput. As a result, it provides a practical solution for various production OSes. To demonstrate the versatility of DWRR,we have implemented it in Linux kernels 2.6.22.15 and 2.6.24, which represent two vastly different scheduler designs. Our evaluation shows that DWRR achieves accurate proportional fairness and high performance for a diverse set of workloads.

References

[1]

S. K. Baruah, N. K. Cohen, C. G. Plaxton, and D. A. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15(6):600--625, June 1996.

Digital Library

[2]

S. K. Baruah, J. E. Gehrke, C. G. Plaxton, I. Stoica, H. Abdel-Wahab, and K. Jeffay. Fair on-line scheduling of a dynamic set of tasks on a single resource. Information Processing Letters, 64(1):43--51, Oct. 1997.

[3]

J. C. R. Bennett and H. Zhang. WF 2 Q: Worst-case fair weighted fair queueing. In Proceedings of IEEE INFOCOM '96, pages 120--128, Mar. 1996.

Digital Library

[4]

J. M. Blanquer and B. Özden. Fair queuing for aggregated multiple links. In Proceedings of ACM SIGCOMM '01, pages 189--197, Aug. 2001.

Digital Library

[5]

J. Bruno, E. Gabber, B. Özden, and A. Silberschatz. The Eclipse operating system: Providing quality of service via reservation domains. In Proceedings of the 1998 USENIX Annual Technical Conference, pages 235--246, June 1998.

Digital Library

[6]

B. Caprita, W. C. Chan, J. Nieh, C. Stein, and H. 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, Apr. 2005.

Digital Library

[7]

B. Caprita, J. Nieh, and C. Stein. Grouped distributed queues: Distributed queue, proportional share multiprocessor scheduling. In Proceedings of the 25th ACM Symposium on Principles of Distributed Computing, pages 72--81, July 2006.

Digital Library

[8]

A. Chandra and P. Shenoy. Hierarchical scheduling for symmetric multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 19(3):418--431, Mar. 2008.

Digital Library

[9]

A. Chandra, M. Adler, P. Goyal, and P. Shenoy. Surplus fair scheduling: A proportional-share CPU scheduling algorithm for symmetric multiprocessors. In Proceedings of the 4th Symposium on Operating Systems Design and Implementation, pages 45--58, Oct. 2000.

Digital Library

[10]

A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. In Proceedings of ACM SIGCOMM '89, pages 1--12, Sept. 1989.

Digital Library

[11]

K. J. Duda and D. R. Cheriton. Borrowed-virtual-time (BVT) scheduling: Supporting latency-sensitive threads in a general-purpose scheduler. In Proceedings of the 17th ACM Symposium on Operating System Principles, pages 261--276, Dec. 1999.

Digital Library

[12]

D. H. J. Epema. Decay-usage scheduling in multiprocessors. ACM Transactions on Computer Systems, 16(4):367--415, Nov. 1998.

Digital Library

[13]

S. J. Golestani. A self-clocked fair queueing scheme for broadband applications. In Proceedings of IEEE INFOCOM '94, pages 636--646, June 1994.

[14]

P. Goyal, X. Guo, and H. M. Vin. A hierarchical CPU scheduler for multimedia operating systems. In Proceedings of the Second Symposium on Operating Systems Design and Implementation, pages 107--121, Oct. 1996.

Digital Library

[15]

P. Goyal, H. M. Vin, and H. Cheng. Start-time fair queueing: A scheduling algorithm for integrated services packet switching networks. IEEE/ACM Transactions on Networking, 5(5): 690--704, Oct. 1997.

Digital Library

[16]

A. G. Greenberg and N. Madras. How fair is fair queuing. Journal of the ACM, 39(3):568--598, July 1992.

Digital Library

[17]

C. Guo. SRR: An O(1) time complexity packet scheduler for flows in multi-service packet networks. IEEE/ACM Transactions on Networking, 12(6):1144--1155, Dec. 2004.

Digital Library

[18]

J. L. Hellerstein. Achieving service rate objectives with decay usage scheduling. IEEE Transactions on Software Engineering, 19(8):813--825, Aug. 1993.

Digital Library

[19]

I. Leslie, D. McAuley, R. Black, T. Roscoe, P. Barham, D. Evers, R. Fairbairns, and E. Hyden. The design and implementation of an operating system to support distributed multimedia applications. IEEE Journal on Selected Areas in Communications, 14(7):1280--1297, Sept. 1996.

Digital Library

[20]

T. Li, D. Baumberger, D. A. Koufaty, and S. Hahn. Efficient operating system scheduling for performance-asymmetric multi-core architectures. In Proceedings of the 2007 ACM/IEEE Conference on Supercomputing, Nov. 2007.

Digital Library

[21]

C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM, 20(1):46--61, Jan. 1973.

Digital Library

[22]

C. W. Mercer, S. Savage, and H. Tokuda. Processor capacity reserves: Operating system support for multimedia applications. In Proceedings of the First IEEE International Conference on Multimedia Computing and Systems, pages 90--99, May 1994.

[23]

J. B. Nagle. On packet switches with infinite storage. IEEE Transactions on Communications, 35(4):435--438, Apr. 1987.

[24]

J. Nieh and M. S. Lam. A SMART scheduler for multimedia applications. ACM Transactions on Computer Systems, 21(2): 117--163, May 2003.

Digital Library

[25]

J. Nieh, C. Vaill, and H. Zhong. Virtual-time round-robin: An O(1) proportional share scheduler. In Proceedings of the 2001 USENIX Annual Technical Conference, pages 245--259, June 2001.

Digital Library

[26]

A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated services net-works: The single-node case. IEEE/ACM Transactions on Networking, 1(3):344--357, June 1993.

Digital Library

[27]

D. Petrou, J. W. Milford, and G. A. Gibson. Implementing lottery scheduling: Matching the specializations in traditional schedulers. In Proceedings of the 1999 USENIX Annual Technical Conference, pages 1--14, June 1999.

Digital Library

[28]

M. Shreedhar and G. Varghese. Efficient fair queueing using deficit round robin. IEEE/ACM Transactions on Networking, 4(3):375--385, June 1996.

Digital Library

[29]

A. Srinivasan. Efficient and Flexible Fair Scheduling of Real-time Tasks on Multiprocessors. PhD thesis, University of North Carolina at Chapel Hill, 2003.

Digital Library

[30]

D. C. Steere, A. Goel, J. Gruenberg, D. McNamee, C. Pu, and J. Walpole. A feedback-driven proportion allocator for real-rate scheduling. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, pages 145--158, Feb. 1999.

Digital Library

[31]

I. Stoica, H. Abdel-Wahab, K. Jeffay, S. K. Baruah, J. E. Gehrke, and C. G. Plaxton. A proportional share resource allocation algorithm for real-time, time-shared systems. In Proceedings of the 17th IEEE Real-Time Systems Symposium, pages 288--299, Dec. 1996.

Digital Library

[32]

C. A. Waldspurger. Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management. PhD thesis, Massachusetts Institute of Technology, Sept. 1995.

Digital Library

[33]

C. A. Waldspurger and W. E. Weihl. Lottery scheduling: Flexible proportional-share resource management. In Proceedings of the First Symposium on Operating Systems Design and Implementation, pages 1--12, Nov. 1994.

Digital Library

Cited By

Wang WLiu ZZhang SLiu G(2024)Trust Score-Based Malicious Vehicle Detection Scheme in Vehicular Network EnvironmentsComputers, Materials & Continua10.32604/cmc.2024.05518481:2(2517-2545)Online publication date: 2024
https://doi.org/10.32604/cmc.2024.055184
Manna SMudigonda K(2024)Revitalizing the single batch environment: a ‘Quest’ to achieve fairness and efficiencyInternational Journal of Computers and Applications10.1080/1206212X.2024.238066046:8(651-665)Online publication date: 25-Jul-2024
https://doi.org/10.1080/1206212X.2024.2380660
Zhao YRao HLe KWang WXu YJia G(2024)RCFS: rate and cost fair CPU scheduling strategy in edge nodesThe Journal of Supercomputing10.1007/s11227-024-05997-y80:10(14000-14028)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11227-024-05997-y
Show More Cited By

Index Terms

Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Scheduling

Recommendations

Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin
PPoPP '09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming

Fairness is an essential requirement of any operating system scheduler. Unfortunately, existing fair scheduling algorithms are either inaccurate or inefficient and non-scalable for multiprocessors. This problem is becoming increasingly severe as the ...
The Case for Fair Multiprocessor Scheduling
IPDPS '03: Proceedings of the 17th International Symposium on Parallel and Distributed Processing

In this paper, we compare the PD2 Pfair algorithm to the EDF-FF partitioning scheme, which uses "first fit" (FF) as a partitioning heuristic and the earliest-deadline-first (EDF) algorithm for per-processor scheduling. We present experimental results ...
Minimizing migrations in fair multiprocessor scheduling of persistent tasks

Suppose that we are given n persistent tasks (jobs) that need to be executed in an equitable way on m processors (machines). Each machine is capable of performing one unit of work in each integral time unit and each job may be executed on at most ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 44, Issue 4

PPoPP '09

April 2009

294 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1594835

Issue’s Table of Contents

PPoPP '09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming
February 2009
322 pages
ISBN:9781605583976
DOI:10.1145/1504176
General Chair:
Daniel Reed
Microsoft Research, USA
,
Program Chair:
Vivek Sarkar
Rice University, USA

Copyright © 2009 ACM.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 February 2009

Published in SIGPLAN Volume 44, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

80
Total Citations
View Citations
1,524
Total Downloads

Downloads (Last 12 months)66
Downloads (Last 6 weeks)4

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang WLiu ZZhang SLiu G(2024)Trust Score-Based Malicious Vehicle Detection Scheme in Vehicular Network EnvironmentsComputers, Materials & Continua10.32604/cmc.2024.05518481:2(2517-2545)Online publication date: 2024
https://doi.org/10.32604/cmc.2024.055184
Manna SMudigonda K(2024)Revitalizing the single batch environment: a ‘Quest’ to achieve fairness and efficiencyInternational Journal of Computers and Applications10.1080/1206212X.2024.238066046:8(651-665)Online publication date: 25-Jul-2024
https://doi.org/10.1080/1206212X.2024.2380660
Zhao YRao HLe KWang WXu YJia G(2024)RCFS: rate and cost fair CPU scheduling strategy in edge nodesThe Journal of Supercomputing10.1007/s11227-024-05997-y80:10(14000-14028)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11227-024-05997-y
Dai MJiang Z(2023)Multiprocessor Fair Scheduling Based on an Improved Slime Mold AlgorithmAlgorithms10.3390/a1610047316:10(473)Online publication date: 7-Oct-2023
https://doi.org/10.3390/a16100473
Jiang HDai XXiao ZIyengar A(2023)Joint Task Offloading and Resource Allocation for Energy-Constrained Mobile Edge ComputingIEEE Transactions on Mobile Computing10.1109/TMC.2022.315043222:7(4000-4015)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1109/TMC.2022.3150432
Dai XXiao ZJiang HChen HMin GDustdar SCao J(2023)A Learning-Based Approach for Vehicle-to-Vehicle Computation OffloadingIEEE Internet of Things Journal10.1109/JIOT.2022.322881110:8(7244-7258)Online publication date: 15-Apr-2023
https://doi.org/10.1109/JIOT.2022.3228811
Pereberina AKostyushko ATormasov A(2023)An algorithm for scheduling of threads for system and application code split approach in dynamic malware analysisJournal of Computer Virology and Hacking Techniques10.1007/s11416-023-00473-219:3(459-468)Online publication date: 5-Apr-2023
https://doi.org/10.1007/s11416-023-00473-2
Patro GJana PChakraborty AGummadi KGanguly N(2022)Scheduling Virtual Conferences Fairly: Achieving Equitable Participant and Speaker SatisfactionProceedings of the ACM Web Conference 202210.1145/3485447.3512136(2646-2656)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3485447.3512136
Yang FZhan KDu JHuang ZXie G(2022)Multiple Objective Fairness Scheduling Optimization Algorithms Based on Multiple DAGs in Heterogeneous Edge ComputingJournal of Circuits, Systems and Computers10.1142/S021812662350141432:08Online publication date: 19-Dec-2022
https://doi.org/10.1142/S0218126623501414
Mehrabi ASorin DLee B(2022)Spatiotemporal Strategies for Long-Term FPGA Resource Management2022 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)10.1109/ISPASS55109.2022.00026(198-209)Online publication date: May-2022
https://doi.org/10.1109/ISPASS55109.2022.00026
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents