基于Xen的多处理器负载均衡调度算法
|
摘要
虚拟化技术是创建灵活动态的企业级设施架构的关键机制。随着多处理器技术的发展,计算能力有了很大提高,也加速了虚拟化技术这一关键机制的发展。虚拟化技术可以屏蔽底层复杂的物理环境,允许多个虚拟机之间共享物理机资源,另外,正在运行的虚拟机可以无间断地在两台物理机之间进行迁移。所以对于大多数企业来说,基于虚拟化技术的企业架构能够提供更多的安全稳定性能,并且也是合并服务器资源和应用的理想解决方案之一。
Xen是目前应用比较广泛的开源虚拟化软件之一,它能够使多个客户操作系统以接近物理系统的性能同时运行在相互隔离的环境中,并对底层物理硬件实现共享访问,包括处理器资源。在虚拟化环境中,虚拟机上的CPU调度是以虚拟CPU作为调度单位进行分时调度。SEDF是Xen中缺省的CPU调度算法之一,该算法支持实时性较强的应用,但是缺少SMP架构中多处理器之间负载均衡的控制。
本文考虑到SMP架构中处理器和cache的关系,提出一种虚拟机环境中的CPU调度算法,该算法设计了一个共享等待队列,各个处理器根据自身负载情况,共享等待队列动态调整VCPU的调度顺序,不仅能够选择最优处理器来执行,并且可以避免处理器空闲。仿真测试结果表明,本文提出的调度算法具有较高的系统吞吐量和任务完成率,也能够降低任务执行的平均周转时间和平均响应时间。本文提出的算法不仅减少了cache和内存数据同步带来的性能损耗,而且支持较好的全局负载均衡,能够充分合理利用处理器资源。
Virtualization is a key mechanism of creating a flexible and dynamic enterprise infrastructure. With the development of more powerful multi-processors, the availability of computing power increased. Also it accelerates the trend of virtualization. It can shield the complicated underlying physical environment easily, and allow sharing of the physical machine resource among different virtual machines. Moreover, virtualization could dynamically migrate virtual machine from the running physical machine to another one without interrupting. So it can provide more security and steady for enterprise infrastructure, and it is also an ideal solution to consolidate server and application for most enterprises.
Xen is one of the most popular open source software. It could make several guest OS running with the similar performance in the isolated environment and sharing the physical resource such as processor. In the virtual environment, the CPU scheduling of virtual machine is based on the virtual CPU and is time-shared. SEDF is one of the default CPU schedulers in the Xen. It supports the real time application well, but doesn't have the ability of balancing the load among multi-processors in the SMP architecture.
Considering the relationship between SMP architecture and cache, this paper illustrates a new scheduler. This scheduler contains a share waiting queue, and according to the loading status of each CPU, it dynamically adjusts the scheduling order of the virtual CPU. It can choose a optimal CPU for the scheduling virtual CPU, and avoid the free of processor.
The simulation results demonstrate that the improved algorithm could get better performance than SEDF under several test standard. The system throughput and completed tasks are well, and the average turnaround time and average response time are get smaller. The improved algorithm can not only decrease the performance loss of multi-processor, but also support global loading balance better and make the processor resource more fully and reasonable.
Xen是目前应用比较广泛的开源虚拟化软件之一,它能够使多个客户操作系统以接近物理系统的性能同时运行在相互隔离的环境中,并对底层物理硬件实现共享访问,包括处理器资源。在虚拟化环境中,虚拟机上的CPU调度是以虚拟CPU作为调度单位进行分时调度。SEDF是Xen中缺省的CPU调度算法之一,该算法支持实时性较强的应用,但是缺少SMP架构中多处理器之间负载均衡的控制。
本文考虑到SMP架构中处理器和cache的关系,提出一种虚拟机环境中的CPU调度算法,该算法设计了一个共享等待队列,各个处理器根据自身负载情况,共享等待队列动态调整VCPU的调度顺序,不仅能够选择最优处理器来执行,并且可以避免处理器空闲。仿真测试结果表明,本文提出的调度算法具有较高的系统吞吐量和任务完成率,也能够降低任务执行的平均周转时间和平均响应时间。本文提出的算法不仅减少了cache和内存数据同步带来的性能损耗,而且支持较好的全局负载均衡,能够充分合理利用处理器资源。
Virtualization is a key mechanism of creating a flexible and dynamic enterprise infrastructure. With the development of more powerful multi-processors, the availability of computing power increased. Also it accelerates the trend of virtualization. It can shield the complicated underlying physical environment easily, and allow sharing of the physical machine resource among different virtual machines. Moreover, virtualization could dynamically migrate virtual machine from the running physical machine to another one without interrupting. So it can provide more security and steady for enterprise infrastructure, and it is also an ideal solution to consolidate server and application for most enterprises.
Xen is one of the most popular open source software. It could make several guest OS running with the similar performance in the isolated environment and sharing the physical resource such as processor. In the virtual environment, the CPU scheduling of virtual machine is based on the virtual CPU and is time-shared. SEDF is one of the default CPU schedulers in the Xen. It supports the real time application well, but doesn't have the ability of balancing the load among multi-processors in the SMP architecture.
Considering the relationship between SMP architecture and cache, this paper illustrates a new scheduler. This scheduler contains a share waiting queue, and according to the loading status of each CPU, it dynamically adjusts the scheduling order of the virtual CPU. It can choose a optimal CPU for the scheduling virtual CPU, and avoid the free of processor.
The simulation results demonstrate that the improved algorithm could get better performance than SEDF under several test standard. The system throughput and completed tasks are well, and the average turnaround time and average response time are get smaller. The improved algorithm can not only decrease the performance loss of multi-processor, but also support global loading balance better and make the processor resource more fully and reasonable.
引文
[1]金海等.计算系统虚拟化--原理与应用[M].北京：清华大学出版社,2008.34-35
[2]怀进鹏,李沁,胡春明.基于虚拟机的虚拟计算环境研究与发展[J].软件学报,2007,18(8)：2016-1026
[3]K. Adams and O. Agesen. A comparison of software and hardware techniques for x86 virtualization. In ASPLOSXII:Proceedings of the 12th international conference on Architectural support for programming languages and operating systems. New York: ACM,2006.2-13
[4]阮敏,Xen环境下实时迁移结构和算法研究[D],大连：大连海事大学,2009
[5]J.Liu, W.Huang, B.Abali, et al. High performance VMM-bypass I/O in virtual machines[C]. Proceedings of the 17th annual international conference on Supercomputing. San Francisco:CA,2006.23-26
[6]Intel(?)64 and IA-32 Architectures Software Developer's Manual Volume 3A:System Programming Guide[EB/OL].2012.01. http://download.intel.com/products/processor/ manual/325462.pdf
[7]Mangnusson P, Christensson M, Eskilson J, et al. Simics:A full system simulation platform[J]. Computer,2002,35(2):50-58
[8]Clark.C, Fraser.K, Hand.S, et al. Live Migration of Virtual Machines[C]. In NSDI'05 Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation. USA:USENIX,2005.273-286
[9]百度百科 CPU[EB/OL].2012.03.14. http://baike.baidu.com/view/2089.htm
[10]时光,郭玉东,王晓睿等.Xen中VCPU调度算法分析[J].计算机工程与设计,2010,31(18)：4116-4119
[11]A.Menon, J.R.Santos, Y.Turner, et al. Diagnosing performance overheads in the Xen virtual machine environment[C]. In VEE'05:Proceedings of the 1st ACM/USENIX International Conference on Virtual executin environments. New York:ACM,2005. 13-23
[12]P.Apparao, R.Iyer. X.Zhang, et al. Characterization & analysis of a server consolidation benchmark[C]. In VEE '08:Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments. New York:ACM,2008. 21-30
[13]A.menon, A.L.Cox, and W.Zwaenepoel. Optimizing network virtualization in Xen[C]. In ATEC '06 Proceedings of the annual conference on USENIX '06 Annual Technical Conference. USA:USENIX,2006.2-2
[14]D.Ongaro, A.L.Cox, and S.Rixner. Scheduling I/O in virtual machine monitors[C], In VEE'08:Proceedings of the Fourth ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, New York:ACM,2008. 1-10
[15]GLiao, D.Guo, L.Bhuyan, et al. Software techniques to improve virtualized IO performance on multicore systems[C], In ANCS'08:Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, New York: ACM,2008.161-170
[16]S.Govindan, A.R.Nath, A.Das, et al. Xen and co:communication-aware CPU scheduling for consolidated Xen-based hosting platforms[C], In VEE'07:Proceedings of the 3rd International Conference on Virtual Execution Environments, New York:ACM,2007. 126-136
[17]Min Lee, A. S. Krishnakumar. Supporting Soft Real-Time Tasks in the Xen Hypervisor[C]. In VEE'10:Proceedings of the 6th ACM SIGPLAN/SIGOPS international conference on Virtual execution environments. New York:ACM,2010. 97-108
[18]H.Kim, H.Lim, J.Jeong, et al. Task-aware virtual machine scheduling for I/O performance[C]. In VEE '09 Proceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual execution environments. New York, ACM,2009. 101-110
[19]金海,吴松,石宣化等.一种虚拟CPU调度方法[P].中国专利,102053858,2011.05.11
[20]Huacai Chen, Hai Jin, Kan Hu et al. Adaptive audio-aware scheduling in Xen virtual environment[C]. Proc of the ACS/IEEE International Conference on Computer Systems and Applications-AICCSA 2010. USA:IEEE Computer Society Washington,2010.1-8
[21]沈霆,多核虚拟化的性能分析和改进[D].上海：上海交通大学,2010
[22]孟江涛,Xen虚拟机研究[D].成都：电子科技大学,2003
[23]石磊,邹德清,金海.Xen虚拟化技术[M].武汉：华中科技大学出版社,2009
[24]曹欣,半虚拟化技术分析与研究[D].杭州：浙江大学,2008
[25]Paul Barham, Ian Pratt, Keir Fraser et al. Xen and the art of virtualization[C]. Proc of the nineteenth ACM symposium on Operating systems principles, New York:ACM,2003. 164-177
[26]David Chisnall. The Definitive Guide to the Xen Hypervisor, Prentice hall.2007
[27]Xen4.1维基百科[EB/OL].2011.5.14,http://wiki.Xen.org/wiki/Xen_4.1_Release_Notes
[28]D.Chisnall.The Definitive Guide to The Xen Hypervisor[M]. USA:Prentice Hall, 2008. 231-235
[29]VMware百度百科[EB/OL].2012.01.12. http://baike.baidu.com/view/301083.htm
[30]KIVITY.A, KAMAY.Y, LAOR.D, et al. A kvm:the Linux virtual machine monitor[C]. In Proceedings of the Linux Symposium.1(12), Canada,2007.225-230
[31]htm Virtualbox百度百科[EB/OL].2012.02.15. http://baike.baidu.com/view/1047853
[32]NEIGER.G, SANTONI.A, LEUNG.F, et al. R.Intel virtualization technology:Hardware support for efficient processor virtualization[J]. Intel Technology Journal.2006,10(3): 167-178
[33]A.Whitaker, M.Shaw, S.D.Gribble. Denali:Lightweight Virtual Machines for Distributed and Networked Applications[C]. Technical Report 02-02-01, University of Washington, 2002
[34]A.Whitaker, R.S.Cox, M.Shwa, S.D. Constructing Services with Interposable Virtual Hardware[C]. In NSDI'04 Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation. USA:USENIX,2004.13-13
[35]孟江涛,卢显良,虚拟机监控器Xen的可靠性优化[J].计算机应用,2010,30(9)：2358-2361
[36]宋振华,杨亚军.Xen虚拟机间的磁盘I/O性能隔离[J].小型微型计算机系统,2011,32(8)：1674-1678
[37]Xinjie Zhang, Dongsheng Yin. Real-time Improvement of VCPU Scheduling Algorithm on Xen[C]. Proc of the nineteenth ACM symposium on Operating systems principles, New York:ACM,2003.112-116
[38]David Chisnall. The Definitive Guide to the Xen Hypervisor[M]. USA:Prentice hall. 2007.341-347
[39]L.Cherkasova, D.Gupta, A.Vahdat. Comparison of the Three CPU Schedulers in Xen[C]. Proc of the ACM 2006 International Conference on Middleware. New York:ACM,2006, 42-51
[40]K.J.Duda and D.R.Cheriton. Borrowed-virtual-time(BVT) scheduling:supporting atency-sensitive threads in a general-purpose scheduler[C]. In SOSP '99 Proceedings of the seventeenth ACM symposium on Operating systems principles. New York:ACM, 1999.261-276
[41]Peijie Yu, Mingyuan Xia, Qian Lin, et al. Real-time Enhancement for Xen hypervisor[C], Contemporary Computing Third International Conference:Communications in Computer and Information Science. India:Springer,2010.61-65
[42]Xen sourcecode:sched_credit.c[EBOL].2007.07.12. http://lxr.Xen-source.com/Lxr/source/Xen/common/sched_credit. C
[43]LEE.M., KRISHNAKUMAR.A., KRISHNAN, et al. Supporting soft real-time tasks in the Xen hypervisor[C]. In Proceedings of the 6th ACM SIGPLAN/SIGOPS international conference on Virtual execution environments. USA:ACM,2010.97-108
[44]Sisu Xi, Justin Wilson, Chenyang Lu et al. RT-Xen:Towards real-time hypervisor scheduling in Xen[C]. Proc of the ninth ACM international conference on Embedded software. New York:ACM,2011.39-48
[45]顾振宇.Xen体系结构的虚拟机调度算法的研究[D].上海：上海交通大学,2008
[46]姚文斌,郑兴杰,一种改进的SEDF调度算法[J].小型微型计算机系统,2010,31(3)：446-450
[47]Xen sourcecode:sched_sedf.c[EBOL].2007.06.01. http: //lxr.Xen-source.com/Lxr/source/Xen/common/sched_sedf.c
[48]Gaurav Somani, Sanjay Chaudhary. Load Balancing in Xen Virtual Machine Monitor[C]. Contemporary Computing Third International Conference:Communications in Computer and Information Science. India:Springer,2010.62-70
[49]SMP百度百科[EB/OL]http://baike.baidu.com/view/9016.htm.
[2]怀进鹏,李沁,胡春明.基于虚拟机的虚拟计算环境研究与发展[J].软件学报,2007,18(8)：2016-1026
[3]K. Adams and O. Agesen. A comparison of software and hardware techniques for x86 virtualization. In ASPLOSXII:Proceedings of the 12th international conference on Architectural support for programming languages and operating systems. New York: ACM,2006.2-13
[4]阮敏,Xen环境下实时迁移结构和算法研究[D],大连：大连海事大学,2009
[5]J.Liu, W.Huang, B.Abali, et al. High performance VMM-bypass I/O in virtual machines[C]. Proceedings of the 17th annual international conference on Supercomputing. San Francisco:CA,2006.23-26
[6]Intel(?)64 and IA-32 Architectures Software Developer's Manual Volume 3A:System Programming Guide[EB/OL].2012.01. http://download.intel.com/products/processor/ manual/325462.pdf
[7]Mangnusson P, Christensson M, Eskilson J, et al. Simics:A full system simulation platform[J]. Computer,2002,35(2):50-58
[8]Clark.C, Fraser.K, Hand.S, et al. Live Migration of Virtual Machines[C]. In NSDI'05 Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation. USA:USENIX,2005.273-286
[9]百度百科 CPU[EB/OL].2012.03.14. http://baike.baidu.com/view/2089.htm
[10]时光,郭玉东,王晓睿等.Xen中VCPU调度算法分析[J].计算机工程与设计,2010,31(18)：4116-4119
[11]A.Menon, J.R.Santos, Y.Turner, et al. Diagnosing performance overheads in the Xen virtual machine environment[C]. In VEE'05:Proceedings of the 1st ACM/USENIX International Conference on Virtual executin environments. New York:ACM,2005. 13-23
[12]P.Apparao, R.Iyer. X.Zhang, et al. Characterization & analysis of a server consolidation benchmark[C]. In VEE '08:Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments. New York:ACM,2008. 21-30
[13]A.menon, A.L.Cox, and W.Zwaenepoel. Optimizing network virtualization in Xen[C]. In ATEC '06 Proceedings of the annual conference on USENIX '06 Annual Technical Conference. USA:USENIX,2006.2-2
[14]D.Ongaro, A.L.Cox, and S.Rixner. Scheduling I/O in virtual machine monitors[C], In VEE'08:Proceedings of the Fourth ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, New York:ACM,2008. 1-10
[15]GLiao, D.Guo, L.Bhuyan, et al. Software techniques to improve virtualized IO performance on multicore systems[C], In ANCS'08:Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, New York: ACM,2008.161-170
[16]S.Govindan, A.R.Nath, A.Das, et al. Xen and co:communication-aware CPU scheduling for consolidated Xen-based hosting platforms[C], In VEE'07:Proceedings of the 3rd International Conference on Virtual Execution Environments, New York:ACM,2007. 126-136
[17]Min Lee, A. S. Krishnakumar. Supporting Soft Real-Time Tasks in the Xen Hypervisor[C]. In VEE'10:Proceedings of the 6th ACM SIGPLAN/SIGOPS international conference on Virtual execution environments. New York:ACM,2010. 97-108
[18]H.Kim, H.Lim, J.Jeong, et al. Task-aware virtual machine scheduling for I/O performance[C]. In VEE '09 Proceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual execution environments. New York, ACM,2009. 101-110
[19]金海,吴松,石宣化等.一种虚拟CPU调度方法[P].中国专利,102053858,2011.05.11
[20]Huacai Chen, Hai Jin, Kan Hu et al. Adaptive audio-aware scheduling in Xen virtual environment[C]. Proc of the ACS/IEEE International Conference on Computer Systems and Applications-AICCSA 2010. USA:IEEE Computer Society Washington,2010.1-8
[21]沈霆,多核虚拟化的性能分析和改进[D].上海：上海交通大学,2010
[22]孟江涛,Xen虚拟机研究[D].成都：电子科技大学,2003
[23]石磊,邹德清,金海.Xen虚拟化技术[M].武汉：华中科技大学出版社,2009
[24]曹欣,半虚拟化技术分析与研究[D].杭州：浙江大学,2008
[25]Paul Barham, Ian Pratt, Keir Fraser et al. Xen and the art of virtualization[C]. Proc of the nineteenth ACM symposium on Operating systems principles, New York:ACM,2003. 164-177
[26]David Chisnall. The Definitive Guide to the Xen Hypervisor, Prentice hall.2007
[27]Xen4.1维基百科[EB/OL].2011.5.14,http://wiki.Xen.org/wiki/Xen_4.1_Release_Notes
[28]D.Chisnall.The Definitive Guide to The Xen Hypervisor[M]. USA:Prentice Hall, 2008. 231-235
[29]VMware百度百科[EB/OL].2012.01.12. http://baike.baidu.com/view/301083.htm
[30]KIVITY.A, KAMAY.Y, LAOR.D, et al. A kvm:the Linux virtual machine monitor[C]. In Proceedings of the Linux Symposium.1(12), Canada,2007.225-230
[31]htm Virtualbox百度百科[EB/OL].2012.02.15. http://baike.baidu.com/view/1047853
[32]NEIGER.G, SANTONI.A, LEUNG.F, et al. R.Intel virtualization technology:Hardware support for efficient processor virtualization[J]. Intel Technology Journal.2006,10(3): 167-178
[33]A.Whitaker, M.Shaw, S.D.Gribble. Denali:Lightweight Virtual Machines for Distributed and Networked Applications[C]. Technical Report 02-02-01, University of Washington, 2002
[34]A.Whitaker, R.S.Cox, M.Shwa, S.D. Constructing Services with Interposable Virtual Hardware[C]. In NSDI'04 Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation. USA:USENIX,2004.13-13
[35]孟江涛,卢显良,虚拟机监控器Xen的可靠性优化[J].计算机应用,2010,30(9)：2358-2361
[36]宋振华,杨亚军.Xen虚拟机间的磁盘I/O性能隔离[J].小型微型计算机系统,2011,32(8)：1674-1678
[37]Xinjie Zhang, Dongsheng Yin. Real-time Improvement of VCPU Scheduling Algorithm on Xen[C]. Proc of the nineteenth ACM symposium on Operating systems principles, New York:ACM,2003.112-116
[38]David Chisnall. The Definitive Guide to the Xen Hypervisor[M]. USA:Prentice hall. 2007.341-347
[39]L.Cherkasova, D.Gupta, A.Vahdat. Comparison of the Three CPU Schedulers in Xen[C]. Proc of the ACM 2006 International Conference on Middleware. New York:ACM,2006, 42-51
[40]K.J.Duda and D.R.Cheriton. Borrowed-virtual-time(BVT) scheduling:supporting atency-sensitive threads in a general-purpose scheduler[C]. In SOSP '99 Proceedings of the seventeenth ACM symposium on Operating systems principles. New York:ACM, 1999.261-276
[41]Peijie Yu, Mingyuan Xia, Qian Lin, et al. Real-time Enhancement for Xen hypervisor[C], Contemporary Computing Third International Conference:Communications in Computer and Information Science. India:Springer,2010.61-65
[42]Xen sourcecode:sched_credit.c[EBOL].2007.07.12. http://lxr.Xen-source.com/Lxr/source/Xen/common/sched_credit. C
[43]LEE.M., KRISHNAKUMAR.A., KRISHNAN, et al. Supporting soft real-time tasks in the Xen hypervisor[C]. In Proceedings of the 6th ACM SIGPLAN/SIGOPS international conference on Virtual execution environments. USA:ACM,2010.97-108
[44]Sisu Xi, Justin Wilson, Chenyang Lu et al. RT-Xen:Towards real-time hypervisor scheduling in Xen[C]. Proc of the ninth ACM international conference on Embedded software. New York:ACM,2011.39-48
[45]顾振宇.Xen体系结构的虚拟机调度算法的研究[D].上海：上海交通大学,2008
[46]姚文斌,郑兴杰,一种改进的SEDF调度算法[J].小型微型计算机系统,2010,31(3)：446-450
[47]Xen sourcecode:sched_sedf.c[EBOL].2007.06.01. http: //lxr.Xen-source.com/Lxr/source/Xen/common/sched_sedf.c
[48]Gaurav Somani, Sanjay Chaudhary. Load Balancing in Xen Virtual Machine Monitor[C]. Contemporary Computing Third International Conference:Communications in Computer and Information Science. India:Springer,2010.62-70
[49]SMP百度百科[EB/OL]http://baike.baidu.com/view/9016.htm.