黄漾

收稿日期：2013-10-18

基金项目：国家自然科学基金重点项目（61133005）； 湖南省科技厅课题项目（2011FJ3067）

作者简介：黄 漾（1974—），女，湖南株洲人，副教授，硕士，研究方向：分布式系统、并行计算。

通讯联系人，E-mail：543179572@qq.com

文章编号：1003-6199（2014）03-0084-04

摘 要：虚拟机调度算法对并行任务的执行效率考虑不够充分。现代处理器平台具备了多个可用的计算核心，使多个虚拟机并发执行成为了现实。针对多核平台下的并行虚拟机调度优化问题，提出一种基于任务特征虚拟机CON-Credit调度算法。该算法在调度并行任务时，使用动态方式对计算机核心进行分配，采用传统的虚拟机调度算法为执行普通任务的虚拟机进行分配；采用定制的同步算法给执行并行任务的虚拟机分进分配。相关实验显示，CON-Credit调度算法能显著提高并行任务的执行效率。

关键词：多核； 虚拟机； VMM； 调度；MapReduce

中图分类号：TP311 文献标识码：A

Dynamic Scheduling Model of XEN Virtual Machine in Multi-core System

HUANG Yang

（Hunan Vocational College of Railway Technology， Zhuzhou，Hunan 412000，China）

Abstract：The virtual machine scheduling algorithm doesnt fully consider the execution efficiency of parallel application. Modern processors have multiple available computing core， so that concurrent execution of multiple virtual machines become a reality. In this paper， a parallel multicore platform virtual machine scheduling problems， Presents a task-based Virtual Machine CON-Credit scheduling algorithm. The algorithm in the scheduling of parallel tasks， Dynamically allocated using a computer core， using the traditional virtual machine scheduling algorithm to perform common tasks allocated virtual machines； Using custom synchronization algorithm to perform parallel tasks assigned virtual machine. Related experiments show， CON-Credit scheduling algorithm can significantly improve the efficiency of the parallel task execution.

Key words：multi-core； virtual machine； VMM； scheduling； MapReduce

1 引 言

目前系统级虚拟机技术已成为云计算平台的重要基础设施，KVM、XEN、VMware等大批虚拟机平台已被广泛部署和应用。虚拟机调度由虚拟机管理器（VMM）实施，VMM采用了不同的虚拟化方法，为每一个虚拟机分配虚拟CPU，其虚拟机调度算法负责将所有虚拟机所使用的VCPU分配到物理CPU上。由于PCPU数量通常远小于VCPU，如何高效地在各虚拟机之间分配处理器是虚拟机调度的研究热点之一.目前VMM的调度算法，直接借鉴了操作系统的调度思路，并不能反映虚拟机自身的特点；虚拟机是硬件加软件的集合。根据不同的任务特征设计调度算法，满足多种任务类型需要。多核平台可同时运行多个虚拟机，调度算法已从纯粹的时分复用向时分复用与空分复用相结合的混合调度模式过度。当请求任务中包含并行任务时，VMM默认的调度算法性能无法适应底层硬件特点，导致并行任务的执行效率下降。以XEN为例设计应用于并行环境的调度算法——CON-Credit。该算法根据当前资源状态和任务特点动态调整资源，将CPU分配给不同类型任务，确保并行任务在空间上的分布执行和时间上的并发执行，提高多核平台的整体性能。

2 算法与实现

2.1 问题提出及算法分析

XEN中默认调度算法——Credit算法没有充分考虑虚拟机之间的协作关系及多核特点，单纯基于时间来划分和调度不同的处理器核，这不利于MapReduce型的并行编程框架。 MapReduce是由Google公司实现的分布式计算模型，该框架结构结合了早期的人工智能领域的Lisp语言的设计思想[1]。美国斯坦福大学设计了第一个面向共享内存系统的MapReduce计算框架[2]，而复旦大学则开发出原型系统Ostrich，采用一种分块MapReduce编程模型，以适用于NUMA系统的特点[3]

使用MapReduce模型时，其用户需要指定两个函数；Map和Reduce。 Map把一组键值对映射成一组新的键值对，Reduce接受一个键和相关的一组值，将这组值进行合并最后生成一组规模更小的值。Map是高度并行的，Reduce则依赖于Map的结果。且Map操作的并行性和均衡性决定MapReduce程序的整体效率。

例举MapReduce结构模型如图1所示，其中表示计算任务节点集合，设在同一层的所有节点的计算时间相同，令第i层任务的处理时间T（Vi）：

T（Vi）=T（Vi1）=T（Vi2）=…=T（Vij），i=1，2，3…，l

设处理器核4个，该MapReduce任务模型在Credit调度算法下，一旦任务在所分配的某一Credit值下不能完成该任务时，正在执行的任务会被迫中断，并调入另一任务运行，且处在同一层的其他任务可能不会在同一时间内得到处理器资源，已处理完毕的任务必须等待该层所有任务完成，才能进入下一层次的任务执行。等待时间往往不确定且不可忽视。如图2可能出现的调度情况，总的完成时间：

T=41T（V1）+21（V2）+T（V3）+T（V4）

对于并行计算任务，依据各自的任务权重来动态分配PCPU；时间上统一决定处理器核的启动时间和运行时间，对一个任务节点来说，下一层任务必须等待上一层任务全部完成后才开始执行。进一步考虑混合任务类型同时执行的情况，设该MapReduce模型和另外5个串行任务同时请求，物理处理器核数为6，预先分配3个为普通任务类型，分配3个为并行任务类型。运行时采用动态分配资源机制，对不同类型任务根据其任务量来动态调整资源分配。core3结束J3后一直处于空闲状态，若动态分配给V17，此时调度情况如图3所示：

分析可知，默认算法对并行任务存在缺陷，而针对多核的改进算法有更好的适应性。且对混合型任务的分析说明，动态调度更有利提高资源利用率和性能，减少总执行时间。

据上分析提出基于任务类型动态划分多核处理器的调度模型CON-Credit。在原结构基础上增加了任务状态监控和调度决策模块，前者通过读取事件通道中的数据来收集设备访问过程中的时间和任务状态信息；后者对收集到的信息实时处理，动态分配资源到各个VCPU处理相应类型的任务，条件满足时做出调度决策。整体结构如图4所示，实现包括；将处理器核动态划分为COM-Core和CON-Core， COM-Core对应串行任务，CON-Core对应并行任务；调度器根据应用类型在不同的集合内进行调度；任务状态监测与动态划分决策；实现虚拟机并行协作调度。

2.2 CON-Credit策略分析

考虑|P|个处理器核的系统，用P={P1，P2，…，Pp}；所有多核处理器，J={J1，J2，…，Jn} 为待处理的n个串行任务，代表任务i的处理时间。V={V11，V12，…，V21，V22，…，Vi1，…，Vij}共m个任务。令W=JV。设|D|个虚拟机CPU的集合为D={D1，D2，…，DD}。某一运行时刻，成立，其中分别表示该时刻正在运行的任务，VCPU及PCPU数。在多核VMM系统中，任务调度包括VCPU对任务的虚拟机分配，设Dk=λ（Wi），以及VMM对各个虚拟机的PCPU分配，设Pj=μ（Dk），于是Pj=μ（λ（Wi））表示将处理器核j分配给任务i。对|P|个核动态分配，令串行任务所需资源的比重为ω（Pj），并行任务所需资源的比重为ω（Pv），且ω（Pj）+ω（Pv）=1。

3 性能分析

3.1 实验环境与基准

本文所使用的实验平台硬件配置为Intel八核Xeon 7550处理器，主频为2。0MHz，18M缓存，Seagate 1TB IDE 硬盘，DDRII-800 8GB内存，RTL 8139D 200Mbps 以太网卡。实验中使用的XEN版本号为4。1。2，Domain0和所有的Domain U的操作系统都为Fedora16 64位，Linux 版本号为3.10.17。实验通过在XEN上搭建8个虚拟机来创建虚拟集群环境进行实验。为全面的研究算法的性能，比较分析CON-Credit调度算法；高效性，CON-Credit相对于传统Credit算法对并行任务调度性能的提升；适应性，混合任务模式下CON-Credit的算法性能。

为说明CON-Credit算法，构造四个MapReduce程序[4]；点乘；在MapReduce实现中，把乘法运算作为Map函数，把求和运算作为Reduce函数。π估算；采用蒙特卡罗概率算法，Map函数输出的是一连串的二进制值0或1，Reduce函数负责求和，最后再计算π的值。RC4密钥查找；标准的64bit无线加密协议。Map函数输入是一个指针指明开始探寻的位置，Reduce函数则检查返回值和输出正确的密钥。N-体问题[5]；是解一组已知初始值的常微分方程组。输入的Map函数是n个粒子当前的信息和计算颗粒指数，Reduce则负责计算各粒子的新状态。

3.2 实验结果及分析

实验中以MapReduce程序和串行程序（如排序算法及 .gcc）为例，验证并比较改进前后算法的性能。在8个Domains上混合调度虚拟集群测试，测试该环境下运行MapReduce应用与串行应用的性能。设置4个于并行MapReduce程序，4个于串行程序，取MapReduce迭代次数为109。两种算法下各任务的执行时间如图5（a）所示。得出CON-Credit算法性能相对于传统算法，点乘，π估算，RC4运算，N-体所需执行时间分别减少24.98%，24.06%，28.50%，25.31%。而排序算法，176.gcc所需执行时间分别增加5.43%，9.28%。

设置8个Domains中6个用于MapReduce程序，2个用于串行应用程序，取MapReduce应用迭代次数为109。两种算法下各程序的执行时间如图5（b）所示。并得出CON-Credit算法性能相对于传统算法，点乘，π估算，RC4运算所需执行时间分别减少25.33%，26.14%，28.91%。排序算法，176.gcc所需执行时间分别增加5.43%，6.19%。这由于改进后的VMM中，增加了决策模块，导致对于串行任务所需时间有少许增加，在大环境下是可接受的。综合分析，相较于实验二中两组数据，通过实验数据图5（a）和（b）验证了当串行任务比例较高时，改进后的算法效率降低。经实验验证，改进后的算法对于混合任务请求特别是对于并行任务具有极大意义。

4 相关工作

本小节对XEN VMM调度算法目前相关工作做简要介绍。Kim等人在2009年VEE上发表的文献[6]为了提高I/O任务的性能提出了任务特性感知的虚拟机调度算法，优先调度I/O-bounds的任务，在提高I/O任务性能的基础上不降低CPU-bounds任务的性能。Weng等人针对目前运行在VM中的负载可以分为高吞吐量和并发任务两种类型，在虚拟机系统中设计了一个混合调度框架，根据任务类型选择不同的调度策略[7]。Diego Ongaro等人分析了不同调度特性支持的情况下，XEN调度在面向I/O密集型应用时的性能表现，其研究工作主要针对Credit调度进行[8]。Hwanju Kim等人测试了XEN系统Credit调度算法中的boost机制，提出了一种Partial-Boost方法[9]，该方法通过检查I/O事件目标VCPU的CR3寄存器来判断当前是否处于I/O密集进行应用的上下文中，以决定是否执行boost操作。L Shi等人[10]提出了一个vCUDA框架，GPGPU的虚拟机的高性能计算解决方案。vCUDA允许应用程序在虚拟机上的执行，以充分利用硬件加速功能，对HPC应用程序的性能具有意义。

5 总结及展望

本文针对传统虚拟机调度算法不适应并行任务调度的缺陷，充分利用多核体系结构的内在特点，设计和实现了CON-Credit调度算法。该算法实现了物理CPU的动态分类和匹配，通过在普通任务和并行任务之间的协同调度提高了MapReduce等并行虚拟任务的执行效率。经实验验证，该算法在并行任务调度和混合任务调度中表现出良好的性能，具有较强的适应性和扩展性。CON-Credit目前仅部署于XEN虚拟机平台，未来将向KVM、Hyper-V等虚拟机体系移植以进一步证实其有效性。此外，云计算平台可能涉及大量异构处理器，如何将并行计算任务与异构虚拟计算环境相结合，设计具有更强适应性的虚拟机调度算法，是值得进一步深入研究的课题。

参考文献

[1] The Lisp Programming Language[EB/OL].http：//groups.engin.umd.umich.edu/CIS/coursedes/cis400/1isp/1isp. html.

[2] Colb Ranger. Ramanan Raghuraman. Arun Penmetsa. Gan Bradski. Christos Kozyrakis[M].Evaluating MapReducc for Multi-core and Multiprocessor Systems. In the processing of the HPCA. 2007.

[3] Rong Chen. Haibo Chen， and Binvu Zang.. iled-MapReduce： Optimizing Resource Usages of Data-parallel Applications on Multicore with Tiling[M].In Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques. 2010.

[4] JACKSON H C，YEUNG C C，TSANG K.H.Tsoi， et al. Map-reduce as a Programming Model for Custom Computing Machines[M].16th International Symposium on Field-Programmable Custom Computing Machines，2008：149-159.

[5] K.H.TSOI， C.H.HO， H.C.YEUNG，P.H.W.LEONG. An arithmetic library and its application to the n-body problem[J].in Proc.IEEE Symposium on Field-Programmable Custom Computing Machines （FCCM）， 2004：68-78.

[6] H.KIM， H.LIM， J.JEONG， H.JO， et al. Task-aware Virtual Machine Scheduling for I/O Performance[J].In Proceedings of the 4th international conference on Virtual Execution Environments （VEE）， 2009：101-111

[7] Chulianq Wenq， Zhiqang Wanq， Minqlu Li et al. The Hybrid Scheduling Framework for Virtual Machine Systems[J]. In Proceedings of 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environment Washington ，DC， USA， 2009：156-168.

[8] Ludmila Cherkasova and Rob Gardner. Measuring CPU overhead for I/O processing in the xen virtual machine monitor[J]. In USENIX Annual Technical Conference， General Track， 2005：387-390

[9] H.KIM，H.LIM and et al. Task-aware Virtual Machine Scheduling for I/O Performance[C]. VEE， 2009； 101-110

[10]L SHI， H CHEN， J.H SUN， K.L.Li.VCUDA； GPU-Accelerated High-Performance Computing in Virtual Machines[J].IEEE Transaction on Computers doi/10.1109/TC.2011.112.

4 相关工作

本小节对XEN VMM调度算法目前相关工作做简要介绍。Kim等人在2009年VEE上发表的文献[6]为了提高I/O任务的性能提出了任务特性感知的虚拟机调度算法，优先调度I/O-bounds的任务，在提高I/O任务性能的基础上不降低CPU-bounds任务的性能。Weng等人针对目前运行在VM中的负载可以分为高吞吐量和并发任务两种类型，在虚拟机系统中设计了一个混合调度框架，根据任务类型选择不同的调度策略[7]。Diego Ongaro等人分析了不同调度特性支持的情况下，XEN调度在面向I/O密集型应用时的性能表现，其研究工作主要针对Credit调度进行[8]。Hwanju Kim等人测试了XEN系统Credit调度算法中的boost机制，提出了一种Partial-Boost方法[9]，该方法通过检查I/O事件目标VCPU的CR3寄存器来判断当前是否处于I/O密集进行应用的上下文中，以决定是否执行boost操作。L Shi等人[10]提出了一个vCUDA框架，GPGPU的虚拟机的高性能计算解决方案。vCUDA允许应用程序在虚拟机上的执行，以充分利用硬件加速功能，对HPC应用程序的性能具有意义。

5 总结及展望

本文针对传统虚拟机调度算法不适应并行任务调度的缺陷，充分利用多核体系结构的内在特点，设计和实现了CON-Credit调度算法。该算法实现了物理CPU的动态分类和匹配，通过在普通任务和并行任务之间的协同调度提高了MapReduce等并行虚拟任务的执行效率。经实验验证，该算法在并行任务调度和混合任务调度中表现出良好的性能，具有较强的适应性和扩展性。CON-Credit目前仅部署于XEN虚拟机平台，未来将向KVM、Hyper-V等虚拟机体系移植以进一步证实其有效性。此外，云计算平台可能涉及大量异构处理器，如何将并行计算任务与异构虚拟计算环境相结合，设计具有更强适应性的虚拟机调度算法，是值得进一步深入研究的课题。

参考文献

[1] The Lisp Programming Language[EB/OL].http：//groups.engin.umd.umich.edu/CIS/coursedes/cis400/1isp/1isp. html.

[2] Colb Ranger. Ramanan Raghuraman. Arun Penmetsa. Gan Bradski. Christos Kozyrakis[M].Evaluating MapReducc for Multi-core and Multiprocessor Systems. In the processing of the HPCA. 2007.

[3] Rong Chen. Haibo Chen， and Binvu Zang.. iled-MapReduce： Optimizing Resource Usages of Data-parallel Applications on Multicore with Tiling[M].In Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques. 2010.

[4] JACKSON H C，YEUNG C C，TSANG K.H.Tsoi， et al. Map-reduce as a Programming Model for Custom Computing Machines[M].16th International Symposium on Field-Programmable Custom Computing Machines，2008：149-159.

[5] K.H.TSOI， C.H.HO， H.C.YEUNG，P.H.W.LEONG. An arithmetic library and its application to the n-body problem[J].in Proc.IEEE Symposium on Field-Programmable Custom Computing Machines （FCCM）， 2004：68-78.

[6] H.KIM， H.LIM， J.JEONG， H.JO， et al. Task-aware Virtual Machine Scheduling for I/O Performance[J].In Proceedings of the 4th international conference on Virtual Execution Environments （VEE）， 2009：101-111

[7] Chulianq Wenq， Zhiqang Wanq， Minqlu Li et al. The Hybrid Scheduling Framework for Virtual Machine Systems[J]. In Proceedings of 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environment Washington ，DC， USA， 2009：156-168.

[8] Ludmila Cherkasova and Rob Gardner. Measuring CPU overhead for I/O processing in the xen virtual machine monitor[J]. In USENIX Annual Technical Conference， General Track， 2005：387-390

[9] H.KIM，H.LIM and et al. Task-aware Virtual Machine Scheduling for I/O Performance[C]. VEE， 2009； 101-110

[10]L SHI， H CHEN， J.H SUN， K.L.Li.VCUDA； GPU-Accelerated High-Performance Computing in Virtual Machines[J].IEEE Transaction on Computers doi/10.1109/TC.2011.112.

4 相关工作

本小节对XEN VMM调度算法目前相关工作做简要介绍。Kim等人在2009年VEE上发表的文献[6]为了提高I/O任务的性能提出了任务特性感知的虚拟机调度算法，优先调度I/O-bounds的任务，在提高I/O任务性能的基础上不降低CPU-bounds任务的性能。Weng等人针对目前运行在VM中的负载可以分为高吞吐量和并发任务两种类型，在虚拟机系统中设计了一个混合调度框架，根据任务类型选择不同的调度策略[7]。Diego Ongaro等人分析了不同调度特性支持的情况下，XEN调度在面向I/O密集型应用时的性能表现，其研究工作主要针对Credit调度进行[8]。Hwanju Kim等人测试了XEN系统Credit调度算法中的boost机制，提出了一种Partial-Boost方法[9]，该方法通过检查I/O事件目标VCPU的CR3寄存器来判断当前是否处于I/O密集进行应用的上下文中，以决定是否执行boost操作。L Shi等人[10]提出了一个vCUDA框架，GPGPU的虚拟机的高性能计算解决方案。vCUDA允许应用程序在虚拟机上的执行，以充分利用硬件加速功能，对HPC应用程序的性能具有意义。

5 总结及展望

本文针对传统虚拟机调度算法不适应并行任务调度的缺陷，充分利用多核体系结构的内在特点，设计和实现了CON-Credit调度算法。该算法实现了物理CPU的动态分类和匹配，通过在普通任务和并行任务之间的协同调度提高了MapReduce等并行虚拟任务的执行效率。经实验验证，该算法在并行任务调度和混合任务调度中表现出良好的性能，具有较强的适应性和扩展性。CON-Credit目前仅部署于XEN虚拟机平台，未来将向KVM、Hyper-V等虚拟机体系移植以进一步证实其有效性。此外，云计算平台可能涉及大量异构处理器，如何将并行计算任务与异构虚拟计算环境相结合，设计具有更强适应性的虚拟机调度算法，是值得进一步深入研究的课题。

参考文献

[1] The Lisp Programming Language[EB/OL].http：//groups.engin.umd.umich.edu/CIS/coursedes/cis400/1isp/1isp. html.

[2] Colb Ranger. Ramanan Raghuraman. Arun Penmetsa. Gan Bradski. Christos Kozyrakis[M].Evaluating MapReducc for Multi-core and Multiprocessor Systems. In the processing of the HPCA. 2007.

[3] Rong Chen. Haibo Chen， and Binvu Zang.. iled-MapReduce： Optimizing Resource Usages of Data-parallel Applications on Multicore with Tiling[M].In Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques. 2010.

[4] JACKSON H C，YEUNG C C，TSANG K.H.Tsoi， et al. Map-reduce as a Programming Model for Custom Computing Machines[M].16th International Symposium on Field-Programmable Custom Computing Machines，2008：149-159.

[5] K.H.TSOI， C.H.HO， H.C.YEUNG，P.H.W.LEONG. An arithmetic library and its application to the n-body problem[J].in Proc.IEEE Symposium on Field-Programmable Custom Computing Machines （FCCM）， 2004：68-78.

[6] H.KIM， H.LIM， J.JEONG， H.JO， et al. Task-aware Virtual Machine Scheduling for I/O Performance[J].In Proceedings of the 4th international conference on Virtual Execution Environments （VEE）， 2009：101-111

[7] Chulianq Wenq， Zhiqang Wanq， Minqlu Li et al. The Hybrid Scheduling Framework for Virtual Machine Systems[J]. In Proceedings of 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environment Washington ，DC， USA， 2009：156-168.

[8] Ludmila Cherkasova and Rob Gardner. Measuring CPU overhead for I/O processing in the xen virtual machine monitor[J]. In USENIX Annual Technical Conference， General Track， 2005：387-390

[9] H.KIM，H.LIM and et al. Task-aware Virtual Machine Scheduling for I/O Performance[C]. VEE， 2009； 101-110

[10]L SHI， H CHEN， J.H SUN， K.L.Li.VCUDA； GPU-Accelerated High-Performance Computing in Virtual Machines[J].IEEE Transaction on Computers doi/10.1109/TC.2011.112.