Comparison of the three CPU schedulers in Xen

ABSTRACT

The primary motivation for enterprises to adopt virtualization technologies is to create a more agile and dynamic IT infrastructure -- with server consolidation, high resource utilization, the ability to quickly add and adjust capacity on demand -- while lowering total cost of ownership and responding more effectively to changing business conditions. However, effective management of virtualized IT environments introduces new and unique requirements, such as dynamically resizing and migrating virtual machines (VMs) in response to changing application demands. Such capacity management methods should work in conjunction with the underlying resource management mechanisms. In general, resource multiplexing and scheduling among virtual machines is poorly understood. CPU scheduling for virtual machines, for instance, has largely been borrowed from the process scheduling research in operating systems. However, it is not clear whether a straight-forward port of process schedulers to VM schedulers would perform just as well. We use the open source Xen virtual machine monitor to perform a comparative evaluation of three different CPU schedulers for virtual machines. We analyze the impact of the choice of scheduler and its parameters on application performance, and discuss challenges in estimating the application resource requirements in virtualized environments.

REFERENCES

• 1: Credit Scheduler, http://wiki.xensource.com/xenwiki/CreditScheduler.
• 2: HP-UX Workload Manager, http://www.hp.com/products1/unix/operating/wlm/.
• 3: Httperf. http://www.hpl.hp.com/research/linux/httperf/. Last accessed 1/17/2006.
• 4: IBM Enterprise Workload Manager, http://www.ibm.com/developerworks/autonomic/ewlm/.
• 5: Iperf: The TCP/UDP Bandwidth Measurement Tool. http://dast.nlanr.net/Projects/Iperf.
• 6: Paul Barham , Boris Dragovic , Keir Fraser , Steven Hand , Tim Harris , Alex Ho , Rolf Neugebauer , Ian Pratt , Andrew Warfield, Xen and the art of virtualization, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 7: Ludmila Cherkasova , Rob Gardner, Measuring CPU overhead for I/O processing in the Xen virtual machine monitor, Proceedings of the annual conference on USENIX Annual Technical Conference, p.24-24, April 10-15, 2005, Anaheim, CA
• 8: Harvey M. Deitel, An Introduction to Operating Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 9: 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
• 10: R. B. Essick. An event based fair share scheduler. In Proceedings of the Winter USENIX Conference, 1990.
• 11: K. Fraser, S. Hand, R. Neugebauer, I. Pratt, A. Warfield, and M. Williamson. Reconstructing I/O. Technical report, 2004.
• 12: Tal Garfinkel , Mendel Rosenblum, When virtual is harder than real: security challenges in virtual machine based computing environments, Proceedings of the 10th conference on Hot Topics in Operating Systems, p.20-20, June 12-15, 2005, Santa Fe, NM
• 13: 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
• 14: D. Gupta, L. Cherkasova, R. Gardner, and A. Vahdat. Enforcing Performance Isolation Across Virtual Machines in Xen. In Proceedings of the 7th International Middleware Conference, 2006.
• 15: D. Gupta, R. Gardner, and L. Cherkasova. XenMon: QoS Monitoring and Performance Profiling Tool. Technical report, HPL-2005-187, 2005.
• 16: 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]
• 17: G. J. Henry. The fair share scheduler. AT&T Bell Labs Technical Journal, 63(8):1945--1957, 1984.
• 18: J. Kay , P. Lauder, A fair share scheduler, Communications of the ACM, v.31 n.1, p.44-55, Jan. 1988 [doi>10.1145/35043.35047]
• 19: S. J. Leffler, M. K. McKusick, and M. J. Karels. The Design and Implementation of the 4.3 BSD Unix Operating System. Addison-Wesley, 1988.
• 20: I. M. Leslie, D. Mcauley, R. Black, T. Roscoe, P. T. Barham, D. Evers, R. Fairbairns, and E. Hyden. The Design and Implementation of an Operating System to Support Distributed Multimedia Applications. IEEE Journal of Selected Areas in Communications, 1996.
• 21: 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]
• 22: I. Pratt. Xen Roadmap. http://wiki.xensource.com/xenwiki/XenRoadMap.
• 23: 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 (RTSS '96), p.288, December 04-06, 1996
• 24: C. A. Waldspurger, Lottery and Stride Scheduling: Flexible Proportional-share Resource Management, Massachusetts Institute of Technology, Cambridge, MA, 1995

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Measurements; Operational analysis

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance