Desktop scheduling: how can we know what the user wants?

ABSTRACT

Current desktop operating systems use CPU utilization (or lack thereof) to prioritize processes for scheduling. This was thought to be beneficial for interactive processes, under the assumption that they spend much of their time waiting for user input. This reasoning fails for modern multimedia applications. For example, playing a movie in parallel with a heavy background job usually leads to poor graphical results, as these jobs are indistinguishable in terms of CPU usage. Suggested solutions involve shifting the burden to the user or programmer, which we claim is unsatisfactory; instead, we seek an automatic solution. Our attempts using new metrics based on CPU usage failed. We therefore propose and implement a novel scheme of identifying interactive and multimedia applications by directly quantifying the I/O between an application and the user (keyboard, mouse, and screen activity). Preliminary results indicate that prioritizing processes according to this metric indeed solves the aforementioned problem, demonstrating that operating systems can indeed provide better support for multimedia and interactive applications. Additionally, once user I/O data is available, it opens intriguing new possibilities to system designers.

REFERENCES

• 1: Maurice J. Bach, The design of the UNIX operating system, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 2: Daniel Pierre Bovet , Marco Cassetti , Andy Oram, Understanding the Linux Kernel, O'Reilly & Associates, Inc., Sebastopol, CA, 2000
• 3: J. Bruno, E. Gabber, B. "Ozden, and A. Silberschatz, "The Eclipse operating system: providing quality of service via reservation domains". In it USENIX Technical Conf., pp. 235--246, 1998.
• 4: Stephen Childs , David Ingram, The Linux-SRT Integrated Multimedia Operating System: Bringing QoS to the Desktop, Proceedings of the Seventh Real-Time Technology and Applications Symposium (RTAS '01), p.135, May 30-June 01, 2001
• 5: 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
• 6: Yoav Etsion , Dan Tsafrir , Dror G. Feitelson, Effects of clock resolution on the scheduling of interactive and soft real-time processes, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 7: Y. Etsion, D. Tsafrir, and D. G. Feitelson, it Human-Centered Scheduling of Interactive and Multimedia Applications on a Loaded Desktop. Technical Report 2003-3, School of Comp. Sci. and Eng., The Hebrew University, Mar 2003.
• 8: 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
• 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: J. Mauro and R. McDougall, it Solaris Internals. Prentice Hall, Oct 2001.
• 11: Marshall Kirk McKusick , Keith Bostic , Michael J. Karels , John S. Quarterman, The design and implementation of the 4.4BSD operating system, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
• 12: 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
• 13: 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
• 14: B. Paul, it Introduction to the Direct Rendering Infrastructure. http://dri.sourceforge.net/doc/DRIintro.html, Aug 2000.
• 15: 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
• 16: Ben Shneiderman, Designing the user interface (videotape), University of Maryland at College Park, College Park, MD, 1987
• 17: Silicon Graphics Inc., "OpenGL". http://www.opengl.org/.
• 18: D. A. Solomon and M. E. Russinovich, it Inside Windows 2000. Microsoft Press, 3rd ed., 2000.
• 19: C. A. Waldspurger and W. E. Weihl, "Lottery scheduling: flexible proportional-share resource management" In it Symp. Operating System Design & Implementation, pp. 1--11, Nov 1994.
• 20: X Consortium, "X Windows System". www.X.org.

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

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human factors

General Terms:
Algorithms, Design, Human Factors

Keywords:
frame rate, human centered computing, interactive, multimedia, scheduling, user I/O