Effects of clock resolution on the scheduling of interactive and soft real-time processes

ABSTRACT

It is commonly agreed that scheduling mechanisms in general purpose operating systems do not provide adequate support for modern interactive applications, notably multimedia applications. The common solution to this problem is to devise specialized scheduling mechanisms that take the specific needs of such applications into account. A much simpler alternative is to better tune existing systems. In particular, we show that conventional scheduling algorithms typically only have little and possibly misleading information regarding the CPU usage of processes, because increasing CPU rates have caused the common 100 Hz clock interrupt rate to be coarser than most application time quanta. We therefore conduct an experimental analysis of what happens if this rate is significantly increased. Results indicate that much higher clock interrupt rates are possible with acceptable overheads, and lead to much better information. In addition we show that increasing the clock rate can provide a measure of support for soft real time requirements, even when using a general-purpose operating system. For example, we achieve a sub-millisecond latency under heavily loaded conditions.

REFERENCES

• 1: B. Adelberg, H. Garcia-Molina, and B. Kao, "Emulating soft real-time scheduling using traditional operating system schedulers". In Real-Time System Symp., Oct 1994.
• 2: 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]
• 3: M. Barabanov and V. Yodaiken, "Introducing real-time Linux". Linux Journal 34, Feb 1997. http://www.linuxjournal.com/article.php?sid=0232.
• 4: Michael Beck , Harold Bohme , Ulrich Kunitz , Robert Magnus , Mirko Dziadzka , Dirk Verworner, Linux Kernel Internals, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 5: Daniel Bovet , Marco Cesati, Understanding The Linux Kernel, Oreilly & Associates Inc, 2005
• 6: J. Bradley Chen , Yasuhiro Endo , Kee Chan , David Mazières , Antonio Dias , Margo Seltzer , Michael D. Smith, The measured performance of personal computer operating systems, ACM Transactions on Computer Systems (TOCS), v.14 n.1, p.3-40, Feb. 1996 [doi>10.1145/225535.225536]
• 7: R. T. Dimpsey , R. K. Iyer, Modeling and measuring multiprogramming and system overheads on a shared-memory multiprocessor: case study, Journal of Parallel and Distributed Computing, v.12 n.4, p.402-414, Aug. 1991 [doi>10.1016/0743-7315(91)90009-X]
• 8: 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
• 9: Y. Etsion, D. Tsafrir, and D. G. Feitelson, Human-Centered Scheduling of Interactive and Multimedia Applications on a Loaded Desktop. Technical Report 2003-3, Hebrew University, Mar 2003.
• 10: Krisztián Flautner , Trevor Mudge, Vertigo: automatic performance-setting for Linux, 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.1060300]
• 11: Kristián Flautner , Rich Uhlig , Steve Reinhardt , Trevor Mudge, Thread-level parallelism and interactive performance of desktop applications, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.129-138, November 2000, Cambridge, Massachusetts, United States
• 12: FreeBSD Documentation Server, Thread on "clock granularity (kernel option HZ)". URL http://docs.freebsd.org/mail/archive/2002/freebsd-hackers/20020203.freebsd-hackers.html, Feb 2002.
• 13: 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]
• 14: Joe Gwinn, Some measurements of timeline gaps in VAX/VMS, ACM SIGOPS Operating Systems Review, v.28 n.2, p.92-96, April 1994 [doi>10.1145/198153.198167]
• 15: 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 J. Select Areas in Commun. 14(7), pp. 1280--1297, Sep 1996.
• 16: John Lions, Lions' commentary on UNIX 6th edition with source code, Peer-to-Peer Communications, Inc., San Jose, CA, 1996
• 17: Jim Mauro , Richard McDougall, Solaris Internals (2nd Edition), Prentice Hall PTR, Upper Saddle River, NJ, 2006
• 18: Jason Nieh , James G. Hanko , J. Duane Northcutt , Gerard A. Wall, SVR4UNIX Scheduler Unacceptable for Multimedia Applications, Proceedings of the 4th International Workshop on Network and Operating System Support for Digital Audio and Video, p.41-53, November 03-05, 1993
• 19: 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
• 20: J. K. Ousterhout, "Why aren't operating systems getting faster as fast as hardware?". In USENIX Summer Conf., pp. 247--256, Jun 1990.
• 21: B. Paul, "Introduction to the Direct Rendering Infrastructure". http://dri.sourceforge.net/doc/DRIintro.html, August 2000.
• 22: Melissa A. Rau , Evgenia Smirni, Adaptive CPU Scheduling Policies for Mixed Multimedia and Best-effort Workloads, Proceedings of the 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.252, March 24-28, 1999
• 23: R. Ronen, A. Mendelson, K. Lai, S-L. Lu, F. Pollack, and J. P. Shen, " Coming challenges in microarchitecture and architecture". Proc. IEEE 89(3), pp. 325--340, Mar 2001.
• 24: David A. Solomon , Mark Russinovich, Inside Microsoft Windows 2000, Microsoft Press, Redmond, WA, 2000
• 25: B. Srinivasan , S. Pather , R. Hill , F. Ansari , D. Niehaus, A Firm Real-Time System Implementation using Commercial Off-the-Shelf Hardware and Free Software, Proceedings of the Fourth IEEE Real-Time Technology and Applications Symposium, p.112, June 03-05, 1998
• 26: D. Tyrell, K. Severson, A. B. Perlman, B. Brickle, and C. Vaningen-Dunn, " Rail passenger equipment crashworthiness testing requirements and implementation". In Intl. Mechanical Engineering Congress & Exposition, Nov 2000.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Measurements

General Terms:
Measurement, Performance

Keywords:
Linux, clock interrupt rate, interactive process, overhead, scheduling, soft real-time, tuning