Fair and timely scheduling via cooperative polling

ABSTRACT

Advances in hardware capacity, especially I/O devices such as cameras and displays, are driving the development of applications like high-definition video conferencing that have tight timing and CPU requirements. Unfortunately, current operating systems do not adequately provide the timing response needed by these applications. In this paper, we present a hierarchical scheduling model that aims to provide these applications with tight timing response, while at the same time preserve the strengths of current schedulers, namely fairness and efficiency. Our approach, called cooperative polling, consists of an application-level event scheduler and a kernel thread scheduler that cooperate to dispatch time-constrained application events accurately and with minimal kernel preemption, while still ensuring rigorously that all applications share resources fairly. Fairness is enforced in a flexible manner, allowing sharing according to a mixture of both traditional resource-centric metrics and new application-centric metrics, the latter being critical to support graceful application-level adaptation in overload. Unlike traditional real-time systems, our model does not require specification or estimation of resource requirements, simplifying its usage dramatically. Our evaluation, using an adaptive video application and a graphics server, shows that our system has event dispatch accuracies that are one to two orders of magnitude smaller than are achieved by existing schedulers. At the same time, our scheduler still maintains fairness and has low overhead.

REFERENCES

• 1: Atul Adya , Jon Howell , Marvin Theimer , William J. Bolosky , John R. Douceur, Cooperative Task Management Without Manual Stack Management, Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, p.289-302, June 10-15, 2002
• 2: Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, Scheduler activations: effective kernel support for the user-level management of parallelism, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.53-79, Feb. 1992 [doi>10.1145/146941.146944]
• 3: Mohit Aron , Peter Druschel, Soft timers: efficient microsecond software timer support for network processing, ACM Transactions on Computer Systems (TOCS), v.18 n.3, p.197-228, Aug. 2000 [doi>10.1145/354871.354872]
• 4: Gérard Berry , Georges Gonthier, The ESTEREL synchronous programming language: design, semantics, implementation, Science of Computer Programming, v.19 n.2, p.87-152, Nov. 1992 [doi>10.1016/0167-6423(92)90005-V]
• 5: Fernando J. Corbató , Marjorie Merwin-Daggett , Robert C. Daley, An experimental time-sharing system, Proceedings of the May 1-3, 1962, spring joint computer conference, May 01-03, 1962, San Francisco, California [doi>10.1145/1460833.1460871]
• 6: 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
• 7: Ralf S. Engelschall. The GNU Portable Threads. http://www.gnu.org/software/pth/, 2006.
• 8: Tim Glauert, Dave Carver, Jim Gettys, and David P. Wiggins. X Synchronization Extension Library Version 3.0. X Consortium Standard, 1991. http://www.xfree86.org/current/synclib.pdf.
• 9: Ashvin Goel , Luca Abeni , Charles Krasic , Jim Snow , Jonathan Walpole, Supporting time-sensitive applications on a commodity OS, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060305]
• 10: Ramesh Govindan , David P. Anderson, Scheduling and IPC mechanisms for continuous media, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.68-80, October 13-16, 1991, Pacific Grove, California, United States
• 11: R. Jain, D. Chiu, and W. Hawe. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. Technical Report TR-301, DEC Research, September 1984. URL http://www.cse.wustl.edu/jain/papers/fairness.htm.
• 12: Stephen F. Jenks , Kane Kim , Yuqing Li , Sheng Liu , Liangchen Zheng , Moon H. Kim , Hee-Yong Youn , Kyung Hee Lee , Dong-Myung Seol, A middleware model supporting time-triggered message-triggered objects for standard Linux systems, Real-Time Systems, v.36 n.1-2, p.75-99, July 2007 [doi>10.1007/s11241-007-9018-1]
• 13: Michael B. Jones , Daniela Roşu , Marcel-Cătălin Roşu, CPU reservations and time constraints: efficient, predictable scheduling of independent activities, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.198-211, October 05-08, 1997, Saint Malo, France
• 14: Charles Krasic , Jean-Sébastien Légaré, Interactivity and scalability enhancements for quality-adaptive streaming, Proceeding of the 16th ACM international conference on Multimedia, October 26-31, 2008, Vancouver, British Columbia, Canada [doi>10.1145/1459359.1459478]
• 15: Charles Krasic, Anirban Sinha, and Lowell Kirsh. Priority-progress CPU adaptation for elastic real-time applications. In Proc. of the Multimedia Computing and Networking Conference (MMCN), January 2007.
• 16: Maxwell Krohn , Eddie Kohler , M. Frans Kaashoek, Events can make sense, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
• 17: Ian M. Leslie, Derek McAuley, Richard Black, Timothy Roscoe, Paul T. Barham, David Evers, Robin Fairbairns, and Eoin Hyden. The design and implementation of an operating system to support distributed multimedia applications. IEEE Journal of Selected Areas in Communications, 14 (7): 1280--1297, 1996.
• 18: C. Lu, J. A. Stankovic, T. F. Abdelzaher, G. Tao, S. H. Son, and M. Marley. Performance specifications and metrics for adaptive real-time systems. In Proc. of the RTSS, December 2000.
• 19: Larry McVoy , Carl Staelin, lmbench: portable tools for performance analysis, Proceedings of the 1996 annual conference on USENIX Annual Technical Conference, p.23-23, January 22-26, 1996, San Diego, CA
• 20: C. W. Mercer, S. Savage, and H. Tokuda. Processor capacity reserves: Operating system support for multimedia applications. In Proc. of the IEEE International Conference on Multimedia Computing and Systems, pages 90--99, May 1994.
• 21: Jason Nieh , Monica S. Lam, The design, implementation and evaluation of SMART: a scheduler for multimedia applications, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.184-197, October 05-08, 1997, Saint Malo, France
• 22: Keith Packard, Efficiently scheduling X clients, Proceedings of the annual conference on USENIX Annual Technical Conference, p.44-44, June 18-23, 2000, San Diego, California
• 23: Reza Rejaie , Mark Handley , Deborah Estrin, Quality adaptation for congestion controlled video playback over the Internet, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.189-200, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 24: Sergio Ruocco, User-Level Fine-Grained Adaptive Real-Time Scheduling via Temporal Reflection, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.246-256, December 05-08, 2006 [doi>10.1109/RTSS.2006.50]
• 25: Heiko Schwarz, Detlev Marpe, and Thomas Wiegand. Overview of the scalable video coding extension of the h.264/avc standard. IEEE Trans. Circuits Syst. Video Techn., 17 (9): 1103--1120, 2007.
• 26: 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
• 27: Jean-Marc Valin. On adjusting the learning rate in frequency domain echo cancellation with double-talk. IEEE Transactions on Audio,Speech, and Language Processing, 15 (3): 1030--1034, March 2007.
• 28: Dan Williams, Patrick Reynolds, Kevin Walsh, Emin Gun Sirer, and Fred B. Schneider. Device driver safety through a reference validation mechanism. In Proc. of the OSDI, 2008.
• 29: Ting Yang, Tongping Liu, Emery D. Berger, Scott F. Kaplan, and J. Eliot B. Moss. Redline: First class support for interactivity in commodity operating systems. In Proc. of the OSDI, 2008.
• 30: Zhenyu Yang , Wanmin Wu , Klara Nahrstedt , Gregorij Kurillo , Ruzena Bajcsy, ViewCast: view dissemination and management for multi-party 3d tele-immersive environments, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291434]
• 31: Nickolai Zeldovich, Alexander Yip, Frank Dabek, Robert T. Morris, David Mazières, and Frans Kaashoek. Multiprocessor support for event--driven programs. In Proc. of the USENIX Technical Conference, pages 239--252, June 2003.

INDEX TERMS

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

General Terms:
Design, Measurement, Performance

Keywords:
fairness, timeliness