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

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.
• 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.
• 4: Josep M. Blanquer , Banu Özden, Fair queuing for aggregated multiple links, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.189-197, August 2001, San Diego, California, United States
• 5: John Bruno , Eran Gabber , Banu Özden , Abraham Silberschatz, The eclipse operating system: providing quality of service via reservation domains, Proceedings of the annual conference on USENIX Annual Technical Conference, p.20-20, June 15-19, 1998, New Orleans, Louisiana
• 6: Bogdan Caprita , Wong Chun Chan , Jason Nieh , Clifford Stein , Haoqiang Zheng, Group ratio round-robin: O(1) proportional share scheduling for uniprocessor and multiprocessor systems, Proceedings of the annual conference on USENIX Annual Technical Conference, p.36-36, April 10-15, 2005, Anaheim, CA
• 7: Bogdan Caprita , Jason Nieh , Clifford Stein, Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146396]
• 8: Abhishek Chandra , Prashant Shenoy, Hierarchical Scheduling for Symmetric Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.19 n.3, p.418-431, March 2008 [doi>10.1109/TPDS.2007.70755]
• 9: Abhishek Chandra , Micah Adler , Pawan Goyal , Prashant Shenoy, Surplus fair scheduling: a proportional-share CPU scheduling algorithm for symmetric multiprocessors, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.4-4, October 22-25, 2000, San Diego, California
• 10: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 11: Kenneth J. Duda , David R. Cheriton, Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.261-276, December 12-15, 1999, Charleston, South Carolina, United States
• 12: D. H. J. Epema, Decay-usage scheduling in multiprocessors, ACM Transactions on Computer Systems (TOCS), v.16 n.4, p.367-415, Nov. 1998 [doi>10.1145/292523.292535]
• 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: Pawan Goyal , Xingang Guo , Harrick M. Vin, A hierarchial CPU scheduler for multimedia operating systems, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.107-121, October 29-November 01, 1996, Seattle, Washington, United States
• 15: Pawan Goyal , Harrick M. Vin , Haichen Cheng, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.690-704, Oct. 1997 [doi>10.1109/90.649569]
• 16: A. G. Greenberg , N. Madras, How fair is fair queuing, Journal of the ACM (JACM), v.39 n.3, p.568-598, July 1992 [doi>10.1145/146637.146658]
• 17: Chuanxiong Guo, SRR: an O(1) time-complexity packet scheduler for flows in multiservice packet networks, IEEE/ACM Transactions on Networking (TON), v.12 n.6, p.1144-1155, December 2004 [doi>10.1109/TNET.2004.838601]
• 18: J. L. Hellerstein, Achieving Service Rate Objectives with Decay Usage Scheduling, IEEE Transactions on Software Engineering, v.19 n.8, p.813-825, August 1993 [doi>10.1109/32.238584]
• 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.
• 20: Tong Li , Dan Baumberger , David A. Koufaty , Scott Hahn, Efficient operating system scheduling for performance-asymmetric multi-core architectures, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362694]
• 21: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 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: Jason Nieh , Monica S. Lam, A SMART scheduler for multimedia applications, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.117-163, May 2003 [doi>10.1145/762483.762484]
• 25: Jason Nieh , Christopher Vaill , Hua Zhong, Virtual-Time Round-Robin: An O(1) Proportional Share Scheduler, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.245-259, June 25-30, 2001
• 26: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 27: David Petrou , John W. Milford , Garth A. Gibson, Implementing lottery scheduling: matching the specializations in traditional schedulers, Proceedings of the annual conference on USENIX Annual Technical Conference, p.1-1, June 06-11, 1999, Monterey, California
• 28: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round-robin, IEEE/ACM Transactions on Networking (TON), v.4 n.3, p.375-385, June 1996 [doi>10.1109/90.502236]
• 29: Anand Srinivasan , James H. Anderson, Efficient and flexible fair scheduling of real-time tasks on multiprocessors, The University of North Carolina at Chapel Hill, 2003
• 30: David C. Steere , Ashvin Goel , Joshua Gruenberg , Dylan McNamee , Calton Pu , Jonathan Walpole, A feedback-driven proportion allocator for real-rate scheduling, Proceedings of the third symposium on Operating systems design and implementation, p.145-158, February 1999, New Orleans, Louisiana, United States
• 31: I. Stoica , H. Abdel-Wahab , K. Jeffay , S. K. Baruah , J. E. Gehrke , C. G. Plaxton, A proportional share resource allocation algorithm for real-time, time-shared systems, Proceedings of the 17th IEEE Real-Time Systems Symposium, p.288, December 04-06, 1996
• 32: Carl A. Waldspurger , William E. Weihl, Lottery and stride scheduling: flexible proportional-share resource management, Massachusetts Institute of Technology, 1995
• 33: Carl A. Waldspurger , William E. Weihl, Lottery scheduling: flexible proportional-share resource management, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.1-es, November 14-17, 1994, Monterey, California

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
distributed weighted round-robin, fair scheduling, lag, multiprocessor