The hybrid scheduling framework for virtual machine systems

ABSTRACT

The virtualization technology makes it feasible that multiple guest operating systems run on a single physical machine. It is the virtual machine monitor that dynamically maps the virtual CPU of virtual machines to physical CPUs according to the scheduling strategy. The scheduling strategy in Xen schedules virtual CPUs of a virtual machines asynchronously while guarantees the proportion of the CPU time corresponding to its weight, maximizing the throughput of the system. However, this scheduling strategy may deteriorate the performance when the virtual machine is used to execute the concurrent applications such as parallel programs or multithreaded programs. In this paper, we analyze the CPU scheduling problem in the virtual machine monitor theoretically, and the result is that the asynchronous CPU scheduling strategy will waste considerable physical CPU time when the system workload is the concurrent application. Then, we present a hybrid scheduling framework for the CPU scheduling in the virtual machine monitor. There are two types of virtual machines in the system: the high-throughput type and the concurrent type. The virtual machine can be set as the concurrent type when the majority of its workload is concurrent applications in order to reduce the cost of synchronization. Otherwise, it is set as the high-throughput type as the default. Moreover, we implement the hybrid scheduling framework based on Xen, and we will give a description of our implementation in details. At last, we test the performance of the presented scheduling framework and strategy based on the multi-core platform, and the experiment result indicates that the scheduling framework and strategy is feasible to improve the performance of the virtual machine system.

REFERENCES

• 1: P. Gum. System/370 extended architecture: Facilities for virtual machines. IBM Journal of Research and Development, 27(6):530--544, 1983.
• 2: Jim Smith , Ravi Nair, Virtual Machines: Versatile Platforms for Systems and Processes (The Morgan Kaufmann Series in Computer Architecture and Design), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 3: Carl A. Waldspurger, Memory resource management in VMware ESX server, 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.1060307]
• 4: 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
• 5: Microsoft Corporation. Microsoft virtual server 2005. http://www.microsoft.com/windowsserversystem/virtualserver/default.mspx.
• 6: Andrew Whitaker , Marianne Shaw , Steven D. Gribble, Scale and performance in the Denali isolation kernel, 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.1060308]
• 7: A. Whitaker, M. Shaw, and S. Gribble. Denali: Lightweight virtual machines for distributed and networked applications. In Proceedings of the USENIX Annual Technical Conference, October 2002.
• 8: Jeff Dike, User-mode Linux, Proceedings of the 5th annual Linux Showcase & Conference, p.2-2, November 05-10, 2001, Oakland, California
• 9: Volkmar Uhlig , Joshua LeVasseur , Espen Skoglund , Uwe Dannowski, Towards scalable multiprocessor virtual machines, Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, p.4-4, May 06-07, 2004, San Jose, California
• 10: 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
• 11: 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 of Selected Areas in Communications, 14(7):1280--1297, 1996.
• 12: Credit Scheduler. http://wiki.xensource.com/xenwiki/credit scheduler.
• 13: Stanford Parallel Applications for Shared Memory (SPLASH). http://www-flash.stanford.edu/splash/.
• 14: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 15: httperf. http://www.hpl.hp.com/research/linux/httperf/.
• 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: S. Leffler, M. McKusick, and M. Karels. The Design and Implementation of the 4.3 BSD Unix Operating System. Addison-Wesley, 1988.
• 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: G. Henry. The fair share scheduler. AT&T Bell Labs Technical Journal, 63(8):1945--1957, 1984.
• 20: R. Essick. An event based fair share scheduler. In Proceedings of the Winter USENIX Conference, pages 147--161, 1990.
• 21: 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
• 22: D. Feitelson, L. Rudolph and U. Schwiegelshohn. Parallel job scheduling -- a status report. In Proceedings of the 10th Workshop on Job Scheduling Strategies for Parallel Processing, pages 1--16, 2004.
• 23: Barry G. Lawson , Evgenia Smirni , Daniela Puiu, Self-Adapting Backfilling Scheduling for Parallel Systems, Proceedings of the 2002 International Conference on Parallel Processing, p.583, August 18-21, 2002
• 24: E. Shmueli and D. Feitelson. Backfilling with lookahead to optimize the performance of parallel job scheduling. In Proceedings of the 9th Workshop on Job Scheduling Strategies for Parallel Processing, pages 228--251, 2003.
• 25: J. Ousterhout. Scheduling techniques for concurrent systems. In Proceedings of Third International Conference on Distributed Computing Systems (ICDCS), pages 22--30, 1982.
• 26: D. Feitelson and L. Rudolph. Gang scheduling performance benefits for fine-grain synchronization. Journal of Parallel and Distributed Computing, 16(4):306--318, 1992.
• 27: Anat Batat, Gang Scheduling with Memory Considerations, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.109, May 01-05, 2000
• 28: Yair Wiseman , Dror G. Feitelson, Paired Gang Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.14 n.6, p.581-592, June 2003 [doi>10.1109/TPDS.2003.1206505]
• 29: Improving Parallel Job Scheduling by Combining Gang Scheduling and Backfilling Techniques, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.133, May 01-05, 2000
• 30: VMWARE. Performance tuning best practices for ESX server 3, 2007. http://www.vmware.com/pdf/vi_performance_tuning.pdf.
• 31: VMWARE. Best practices using vmware virtual SMP, 2005. http://www.vmware.com/pdf/vsmp_best_practices.pdf.
• 32: Ludmila Cherkasova , Diwaker Gupta , Amin Vahdat, Comparison of the three CPU schedulers in Xen, ACM SIGMETRICS Performance Evaluation Review, v.35 n.2, p.42-51, September 2007 [doi>10.1145/1330555.1330556]
• 33: Sriram Govindan , Arjun R. Nath , Amitayu Das , Bhuvan Urgaonkar , Anand Sivasubramaniam, Xen and co.: communication-aware CPU scheduling for consolidated xen-based hosting platforms, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA [doi>10.1145/1254810.1254828]
• 34: Diego Ongaro , Alan L. Cox , Scott Rixner, Scheduling I/O in virtual machine monitors, Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, March 05-07, 2008, Seattle, WA, USA [doi>10.1145/1346256.1346258]
• 35: Jiuxing Liu , Wei Huang , Bulent Abali , Dhabaleswar K. Panda, High performance VMM-bypass I/O in virtual machines, Proceedings of the annual conference on USENIX '06 Annual Technical Conference, p.3-3, May 30-June 03, 2006, Boston, MA
• 36: H. Raj and K. Schwan. Implementing a scalable self-virtualizing network interface on an embedded multicore platform. In Proceedings of the Workshop on the Interaction between Operating Systems and Computer Architecture, 2005.
• 37: Paul Willmann , Jeffrey Shafer , David Carr , Aravind Menon , Scott Rixner , Alan L. Cox , Willy Zwaenepoel, Concurrent Direct Network Access for Virtual Machine Monitors, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.306-317, February 10-14, 2007 [doi>10.1109/HPCA.2007.346208]
• 38: Himanshu Raj , Karsten Schwan, High performance and scalable I/O virtualization via self-virtualized devices, Proceedings of the 16th international symposium on High performance distributed computing, June 25-29, 2007, Monterey, California, USA [doi>10.1145/1272366.1272390]
• 39: 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
• 40: Aravind Menon , Jose Renato Santos , Yoshio Turner , G. (John) Janakiraman , Willy Zwaenepoel, Diagnosing performance overheads in the xen virtual machine environment, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064984]
• 41: D. Gupta, R. Gardner, and L. Cherkasovah. Xen\Mon: Qo\Smonitoring and performance profiling tool. Technical Report HPL-2005-187, HP Labs, 2005.
• 42: Stephen T. Jones , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Antfarm: tracking processes in a virtual machine environment, Proceedings of the annual conference on USENIX '06 Annual Technical Conference, p.1-1, May 30-June 03, 2006, Boston, MA

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
hybrid scheduling, scheduling strategy, virtualization