一种多核环境下的Xen虚拟机调度控制方法

摘要

本发明提出了一种多核架构下的Xen虚拟机调度控制方法，包括如下步骤：(一)调度初始化；(二)调度信息统计的初始化，即对管理域(domain0)中的虚拟cpu进行监控，并实时地向虚拟机监控器(VMM)发送监控结果；(三)创建虚拟机并分配虚拟cpu，同时将虚拟cpu依照优先级级别和credit值存放到相应cpu分组的红黑树上，并且启动初始化阶段设置的所有定时器；(四)虚拟机调度。本发明可以动态调整分组中逻辑cpu执行的时间片，有效地减少了调度方法在执行过程中所消耗的时间，并对io任务有较好的响应时间，能够适应对时间要求较高的任务类型中。

权利要求

1.一种多核架构下的Xen虚拟机调度控制方法，包括如下步骤：

（一）调度初始化

（1.1）首先，枚举所有逻辑cpu，将属于相同物理号并且核号相同的逻辑cpu分为一组，每个分组中的逻辑cpu共享同一个调度时间片长度；然后分配并初始化每个分组内各个cpu共享的用于组织和维护虚拟cpu的红黑树；

（1.2）数据结构和调度参数的初始化

首先，初始化cpu分组中所有逻辑cpu的时间片定时器，该时间片定时器用于控制相应逻辑cpu进行调度的时间间隔；

然后，初始化调度方法的调度参数，即设置虚拟机的默认权重、基准负载以及基准时间片的初始值；

（1.3）初始化每个cpu分组所拥有的定时器，该定时器用于根据负载情况动态调整相应cpu分组时间片的长度；

（二）调度信息统计的初始化，即对管理域（domain0）中的虚拟cpu进行监控，并实时地向虚拟机监控器（VMM）发送监控结果，具体过程为：（2.1）在向客户域（domainU）发送数据过程中，后端驱动判断正在执行的管理域（domain0）中的虚拟cpu编号，并且向虚拟机监控器传输该cpu编号；

（2.2）虚拟机监控器将收集的编号存储在cpu位图中；

（三）创建虚拟机并分配客户域（domainU）虚拟cpu，同时将所述客户域（domainU）虚拟cpu依照优先级级别和credit值存放到相应cpu分组的红黑树上，并且启动初始化阶段设置的所有定时器；

（四）虚拟机调度

首先查询cpu位图，判断cpu位图中当前逻辑cpu正在执行的虚拟cpu的编号所对应的位是否已经置位；如果已经置位，则取消此次调度，如果没有置位，就从该逻辑cpu所在分组的红黑树中取最高优先级的虚拟cpu进行切换，实施调度。

2.根据权利要求1所述的调度控制方法，其特征在于，所述的步骤（四）中，对于被切换出来的虚拟cpu需要重新插入红黑树中，该过程具体为：（4.1）对于under级和over级的虚拟cpu，根据优先级级别和credit值进行插入放回；

（4.2）对于boost级虚拟cpu，采用如下过程插入放回：

（I）将虚拟cpu放置到上一次所处的红黑树上；

（II）查询该红黑树对应的cpu分组中的所有逻辑cpu，判断是否所有的逻辑cpu正在执行boost级任务，如果所有的逻辑cpu都在执行boost级任务，就跳转到下一步，如果一旦找到一个逻辑cpu没有执行boost级任务，则停止查找，并触发该逻辑cpu的调度，完成插入放回；

（III）查询与该cpu分组具有相同物理号的其他cpu分组中的所有逻辑cpu，如果所有的逻辑cpu都在执行boost级任务，就跳转到下一步；如果找到某个逻辑cpu没有执行boost级任务，则将该虚拟cpu迁移到该逻辑cpu对应的红黑树结构中，并触发该逻辑cpu的调度，完成插入放回；

（IV）查询与该cpu分组具有不同物理号的所有其他cpu分组中的所有逻辑cpu，如果找到一个逻辑cpu没有执行boost级任务，则将虚拟cpu迁移到该逻辑cpu对应的红黑树结构中，并触发该逻辑cpu的调度，完成插入放回；如果没有找到，完成插入放回。

3.根据权利要求2所述的调度控制方法，其特征在于，所述步骤（一）中，调整每个cpu分组时间片的长度的具体原则如下：当定时器到期后，计算每个cpu分组的负载信息，然后按照如下公式计算新的每个cpu分组调度时间片：其中，每个cpu分组负载为每个cpu分组中所有cpu负载之和的平均值。

4.根据权利要求3所述的调度控制方法，其特征在于，所述步骤（4.1）中，具体插入放回的过程为：如果待插入的当前节点的优先级低于红黑树根节点的优先级，则插入左子树中，否则，就插入右子树中；其中，所述优先级的比较原则为：首先对虚拟cpu的优先级级别进行比较，如果两者不等，可以直接找出高优先级者，如果相等，继续对credit值按大小进行比较。

说明书

一种多核环境下的Xen虚拟机调度控制方法

技术领域

[0001] 本发明属于计算机虚拟化方向，尤其涉及一种在多核架构下的调度方法，属于计算机操作系统与虚拟化技术领域。

背景技术

[0002] 目前系统虚拟化技术在企业中的应用越来越广泛，虚拟化技术主要有灵活、高效两大优点。通过虚拟化技术，企业可以迅捷地搭建基础IT设施，如操作系统，数据库，Web服务器等；采用虚拟化迁移技术与对虚拟机硬件的动态调整技术，可以满足当前服务器对硬件资源动态变化的需求，从而大大提高了对硬件等资源分配的灵活性。通过虚拟化技术，企业可以提高对硬件等资源的利用率，用更少的硬件资源就可以完成原企业级应用的要求，从而使资源的利用更加高效。目前也出现了许多的虚拟机技术以及相关的虚拟机应用程序，目前比较流行的有，VMware，Virtual PC，Xen等。Xen是由剑桥大学计算机实验室系统研究组开发的虚拟机监视器，以其高效性和灵活性而著称。

[0003] 多任务是Xen的关键特性。从外部看来，有多个专用的Guest操作系统“同时”运行在一台物理机器上。因此，在一段固定的时间内，Xen需要在这段时间内把各个CPU时间片合理高效地分配给在其上运行的各个Guest的虚拟CPU，从而达到了多任务的目的。这个分配CPU时间片的方法就是我们通常所说的调度方法。

[0004] 基于Xen的虚拟机计算环境的CPU调度分三级：虚拟机监视器将物理CPU时间片分配给各个虚拟CPU；虚拟CPU将其时间片分配给各个Guest操作系统中的核心线程；Guest操作系统中的核心线程将其时间片分配给应用程序的各个用户态线程。虚拟机调度方法位于三级调度中的最底层，因此虚拟机调度方法性能的高低将直接决定整个Xen虚拟机计算环境性能的高低。

[0005] Credit调度方法是xen虚拟机中的默认调度方法，对于计算型任务，它可以将CPU时间公平高效的分配给各个虚拟CPU，而对于io型任务，其会产生一定量的延时，并且现存的credit调度方法在处理io数据分发的时候总是频繁的发生虚拟CPU切换，导致domain0中虚拟cpu不停的被切换出去，严重影响系统的性能。与此同时，随着计算机系统的发展，在每个逻辑cpu上运行的虚拟cpu数量会激增，这时仅仅通过线性表对所有的虚拟cpu进行组织和管理，性能是比较低的。除此之外，该调度方法对系统中所有的逻辑cpu采用一个固定的时间片，这样有时会造成虚拟cpu频繁切换，导致cache失效，cache命中率下降；并且有时会导致其他任务的饥饿。这些问题都会严重影响整个xen系统的性能。

发明内容

[0006] 本发明的目的在于提出一种多核环境下的Xen虚拟机调度控制方法，通过对逻辑cpu进行分组，并让每个分组结合红黑树来组织和维护这些虚拟cpu，再根据每个cpu分组中的负载情况进行时间片的动态调整，从而避免频繁的虚拟CPU切换，有效地提升系统的性能。

[0007] 为实现本发明的目的所采用的具体技术方案为：

[0008] 一种多核架构下的虚拟机调度方法，是对虚拟机中的虚拟cpu进行调度，每个虚拟cpu有一个代表优先级和运行时间的属性值-credit，系统会根据credit值将虚拟cpu分成两个级别，值大于0的成为under级，值小于0的成为over级别，系统为了提高io任务的优先级，对于那些被唤醒的虚拟cpu的优先级，系统将其设置为boost级。其中boost级高于under级，under级高于over级。具体包括以下步骤：

[0009] 步骤一：调度初始化，这是调度方法能够运行之前所必须进行的一项操作，本步骤包含以下执行步骤：

[0010] (1.1)枚举所有逻辑cpu，将属于同一物理cpu并且核号相同的逻辑cpu分为一组，并且每个分组中的逻辑cpu共享同一个调度时间片长度，然后分配并初始化每个分组共享的用于组织和维护虚拟cpu的数据结构-红黑树，其中所有的cpu分组可以根据物理cpu编号再进行分组，这些分组之间以链表的形式组织起来。

[0011] (1.2)初始化调度方法所需的数据结构和调度参数，主要包括以下几个方面：

[0012] 初始化cpu分组中所有逻辑cpu的时间片定时器，这个定时器用于控制每个逻辑cpu每隔一段时间进行一次调度。

[0013] 初始化调度方法的调度参数，具体包括虚拟机的默认权重，基准负载，基准时间片等。

[0014] 初始化控制整个系统调度的全局数据结构，这个数据结构管理系统中所有处于激活状态的虚拟机，负责统计系统中逻辑cpu的个数，维护空闲逻辑cpu的位图，以及启动整个调度系统中的定时器，该定时器用于每隔一段时间重新计算系统中所有虚拟cpu的credit值。此外，这个全局数据结构还包含了系统中所有虚拟机的权重之和以及所有虚拟cpu的creidt值之和。

[0015] (1.3)初始化每个cpu分组所拥有的一个定时器，该定时器的作用是根据负载情况动态调整每个cpu分组时间片的长度。调整的原则如下：

[0016] 当定时器到期后，计算每个cpu分组的负载信息，然后按照下面的公式计算新的每个cpu分组调度时间片：

[0017]

[0018] 其中每个cpu分组负载为每个cpu分组中所有cpu负载之和的平均值。

[0019] 步骤二：调度信息统计的初始化，即对管理域(domain0)中的虚拟cpu进行监控，并实时地向虚拟机监控器(VMM)发送监控结果。本步骤包含以下具体过程：

[0020] (2.1)在设备的后端驱动向客户域(domainU)发送数据过程中，后端驱动判断正在执行的虚拟cpu编号，并且向虚拟机监控器传输该cpu编号。

[0021] (2.2)虚拟机监控器将收集的编号存储在cpu位图中。

[0022] 步骤三：创建虚拟机，分配虚拟cpu，将虚拟cpu依照优先级级别和credit值存放到某个cpu分组的红黑树上，并且启动初始化阶段设置的所有定时器。

[0023] 步骤四：虚拟机调度，每个逻辑cpu在执行调度程序时，首先需要查询cpu位图，判断位图中当前逻辑cpu正在执行的虚拟cpu的编号所对应的位是否已经置位，如果已经置位，则取消此次调度。如果没有置位，就从该逻辑cpu所在分组的红黑树中取最高优先级的虚拟cpu进行切换。

[0024] 被切换出来的虚拟cpu是需要重新放入红黑树中的，对于像under级和over级的虚拟cpu是结合优先级级别和credit值进行插入放回的，而boost级虚拟cpu对时间的要求较高，对于这类虚拟cpu的插入需要采用下面的原则：

[0025] 1.将虚拟cpu放置到上一次所处的红黑树上；

[0026] 2.查询该红黑树对应的cpu分组中的所有逻辑cpu，判断是否所有的逻辑cpu正在执行boost级任务，如果所有的逻辑cpu都在执行boost级任务，就跳转到下一步，如果一旦找到一个逻辑cpu没有执行boost级任务，则停止查找，并触发该逻辑cpu的调度，完成插入放回；

[0027] 3.查询与该cpu分组具有相同物理号的其他cpu分组中的所有逻辑cpu，如果所有的逻辑cpu都在执行boost级任务，就跳转到下一步；如果找到某个逻辑cpu没有执行boost级任务，则将该虚拟cpu迁移到该某个逻辑cpu对应的红黑树结构中，并触发该某个逻辑cpu的调度，完成插入放回；

[0028] 4.查询与该cpu分组具有不同物理号的所有其他cpu分组中的所有逻辑cpu，如果找到一个逻辑cpu没有执行boost级任务，则将虚拟cpu迁移到该逻辑cpu对应的红黑树结构中，并触发该逻辑cpu的调度，完成插入放回；如果没有找到，则返回。

[0029] 本发明提出一种多核环境下的xen虚拟机调度方法，其优点是：

[0030] 1.方法将所有的逻辑cpu分组，因为同一物理cpu中具有相同核号的逻辑cpu之间共享大部分资源，实际上几乎没有什么区别，因此没有必要为每个逻辑cpu分配一个存储虚拟cpu的“容器”，并且为每个分组配置红黑树进行组织和维护虚拟cpu，较之以前的运行队列，执行速度有明显提升，尤其随着虚拟机中虚拟cpu数量的激增，这种性能上的优化将表现地更加明显。

[0031] 2.该方法除了沿用了credit调度方法适用于计算型任务的公平调度思想，还对唤醒后的io型虚拟cpu进行了策略放置，这样即使在对io型任务响应时间有要求较高的环境中，也能很好的满足要求。

[0032] 3.该方法根据每个分组的负载情况，动态调整分组中逻辑cpu执行的时间片，这样在负载较轻时，增加执行的时间片，可以减少固定时间片带来的频繁切换开销，有效的减少cache失效，从而提高虚拟cpu执行性能；在负载较重时，减少执行的时间片，这样可以避免“容器”中的任务因长期等待而导致“饥饿”。

附图说明

[0033] 图1为本发明流程示意图；

[0034] 图2为本发明的调度对象重新放置策略示意图；

[0035] 图3为虚拟机调度示意图；

具体实施方式

[0036] 下面结合附图对本发明进行更进一步详细说明。

[0037] 本发明提出了一种多核架构下的xen虚拟机调度方法，该方法针对现存调度方法执行效率不高和适用范围单一等缺陷，提出了一种能够在复杂环境下高效执行的虚拟机调度方法。具体过程如下：

[0038] 步骤一：调度初始化，这是调度方法能够运行之前所必须进行的一项操作，本步骤包含以下执行步骤：

[0039] (1.1)枚举所有逻辑cpu，将属于同一物理cpu并且核号相同的逻辑cpu分为一组，并且每个分组中的逻辑cpu共享同一个调度时间片长度，然后分配并初始化每个分组共享的用于组织和维护虚拟cpu的数据结构-红黑树，其中所有的cpu分组可以根据物理cpu编号再进行分组，各个分组之间以链表的形式组织起来。

[0040] (1.2)初始化调度方法所需的数据结构和调度参数，主要包括以下几个方面：

[0041] 初始化cpu分组中所有逻辑cpu对应的时间片定时器。

[0042] 初始化调度方法的调度参数，具体包括每个虚拟机的权重，基准负载，基准时间片。其中，初始化每个虚拟机的权重，基准负载、基准时间片属于本领域的常规手段，本领域技术人员可以根据实际情况进行具体选择和确定。

[0043] 初始化控制整个系统调度的全局数据结构，这个结构管理系统中所有处于激活状态的虚拟机，负责统计系统中逻辑cpu的个数，维护空闲逻辑cpu的位图，以及启动整个调度系统中的定时器，该定时器用于每隔一段时间重新计算系统中所有虚拟cpu的credit值。此外，这个全局数据结构还包含了系统中所有虚拟机的权重之和以及所有虚拟cpu的creidt值之和。

[0044] 对于系统中credit值的计算，本方法采用与已存的credit方法相同的步骤，根据系统中虚拟机的权重进行分配。

[0045] (1.3)初始化每个cpu分组所拥有的一个定时器，该定时器的作用是根据负载情况动态调整每个cpu分组时间片的长度。调整的原则如下：

[0046] 当定时器到期后，计算每个cpu分组的负载信息，然后按照下面的公式计算新的每cpu分组调度时间片：

[0047]

[0048] 其中每个cpu分组负载为每个cpu分组中所有cpu负载之和的平均值，并且本调度方法将基准负载设置为50％，基准时间片设置为15ms，即表示当cpu分组的负载为50％的时候，调度方法为该cpu分组中的所有逻辑cpu设置15ms的调度时间片。

[0049] 步骤二：调度信息统计的初始化，即对管理域(domain0)中的虚拟cpu进行监控，并实时地向虚拟机监控器(VMM)发送监控结果。本步骤包含以下具体过程：

[0050] (2.1)在设备的后端驱动向客户域(domainU)发送数据过程中，后端驱动判断正在执行的虚拟cpu编号，并且向虚拟机监控器传输该cpu编号。

[0051] (2.2)虚拟机监控器将收集的编号存储在cpu位图中。

[0052] 因为后端驱动向客户域发送数据的过程是io任务执行过程中关键的一步，确保在这个过程中虚拟cpu不会被切换，对io性能的提升是非常有效率的。

[0053] 步骤三：创建虚拟机，分配虚拟cpu，将虚拟cpu依照优先级级别和credit值存放到某个cpu分组的红黑树上，并且启动初始化阶段设置的所有定时器。

[0054] 红黑树是一种部分平衡的二叉查找树，将虚拟cpu插入到红黑树过程中需要对节点的优先级进行比较，比较的原则如下：

[0055] 首先对虚拟cpu的优先级级别进行比较，其中boost级大于under级，under级大于over级，如果两个虚拟cpu的优先级级别不同，则已经判断出优先级的高低，如果优先级级别相同，则根据虚拟cpu的credit值按照大小再次进行比较，值大的，优先级高，值小的，优先级低。

[0056] 步骤四：虚拟机调度，每个逻辑cpu在执行调度程序时，首先需要查询cpu位图，判断位图中当前逻辑cpu正在执行的虚拟cpu的编号所对应的位是否已经置位，如果已经置位，则取消此次调度。如果没有置位，就从该逻辑cpu所在分组的红黑树中取最高优先级的虚拟cpu进行切换。

[0057] 被切换出来的虚拟cpu是需要重新放入红黑树中的，对于像under级和over级的虚拟cpu是结合优先级级别和credit值进行插入放回的。具体如下：

[0058] 系统将虚拟cpu作为红黑树中的一个节点进行插入的。

[0059] 当插入一个虚拟cpu时，需要将当前虚拟cpu的优先级和树中根节点中虚拟cpu的优先级进行比较，如果当前虚拟cpu的优先级低些，就插入左子树中，否则，就插入右子树中。

[0060] 其中，优先级的比较原则为：首先对虚拟cpu的优先级级别进行比较，如果两者不等，可以直接找出高优先级者，如果相等，继续对credit值按大小进行比较。

[0061] 而boost级虚拟cpu对时间的要求较高，对于这类虚拟cpu的插入需要采用下面的原则：

[0062] 1.将虚拟cpu放置到上一次所处的红黑树上；

[0063] 2.查询该红黑树对应的cpu分组中的所有逻辑cpu，判断是否所有的逻辑cpu正在执行boost级任务，如果所有的逻辑cpu都在执行boost级任务，就跳转到下一步，如果一旦找到一个逻辑cpu没有执行boost级任务，则停止查找，并触发该逻辑cpu的调度，完成插入放回；

[0064] 3.查询与该cpu分组具有相同物理号的其他cpu分组中的所有逻辑cpu，如果所有的逻辑cpu都在执行boost级任务，就跳转到下一步；如果找到某个逻辑cpu没有执行boost级任务，则将该虚拟cpu迁移到该某个逻辑cpu对应的红黑树结构中，并触发该某个逻辑cpu的调度，完成插入放回；

[0065] 4.查询与该cpu分组具有不同物理号的所有其他cpu分组中的所有逻辑cpu，如果找到一个逻辑cpu没有执行boost级任务，则将虚拟cpu迁移到该逻辑cpu对应的红黑树结构中，并触发该逻辑cpu的调度，完成插入放回；如果没有找到，则返回。