一种CREDIT调度器中增量时间片调整架构及方法

摘要

本发明公开了一种CREDIT调度器中增量时间片调整架构及方法。其中，中断决策信息维护器负责维护历史中断决策信息；增量时间片自适应调整器定时采集中断决策信息维护器中维护的数据信息，结合增量时间片调整历史信息，动态计算出新的增量时间片。若新计算得到的增量时间片与原有的增量时间片有差异，则通知CREDIT调度器执行增量时间片的更新。作为原有时间片机制的扩展，增量时间片动态维护一个非负值来增加原有时间片的长度。增量时间片机制建立在虚拟中断自主决策机制之上，因此可以在不影响虚拟机I/O性能的前提下增加时间片的长度。

说明书

技术领域

本发明涉及系统虚拟化、虚拟中断处理、虚拟机调度器设计领域，具体地，涉 及一种CREDIT调度器中基于中断绑定决策支持的增量时间片调整架构及方法， 用于解决由调度器中时间片长度设置所引起的上下文切换频繁、物理计算资源损耗 及中断响应处理延迟较长的问题。

背景技术

系统虚拟化及其相关技术在业界发展迅速。虚拟化技术通过将一台或多台功能 相对比较强大的物理服务器虚拟化成多台性能上相对普通的中小型计算机，实现了 计算资源和存储资源的整合，在充分考虑现实情况和生产环境需求的前提下对整合 后的物理资源进行集中式的管理、再分配与维护，相比原有的物理实体设备系统而 言，具有易于把握全局资源利用情况，无需针对不断变化的计算规模和计算要求重 复的购置物理资源，便于系统迁移、灾备和重建等主要优点。

目前主流的系统虚拟化实现方案中，虚拟机监视器(Virtual Machine Monitor, VMM)扮演了一个重要的角色。虚拟机监视器被设计成这样一个软件中间层，他对 下层掌握实际的物理资源，包括物理系统的计算资源、存储资源、通信资源等，向 上对虚拟操作系统提供虚拟硬件接口，从而实现同一个物理资源在虚拟操作系统层 面上的复用。虚拟操作系统从虚拟机监视器中得到虚拟硬件的接口，认为自己独占 有一些或某些硬件资源，从而实现系统设备的虚拟化。

目前业界主流的虚拟机监视器主要有XEN、KVM、VIRTUAL-BOX、VMWARE 以及HYPER-V等。其中XEN作为主流的开源虚拟机监视器，为企业和研究机构研 究虚拟机监视器开发技术提供了一个非常好的技术平台。XEN默认使用CREDIT 调度器来调度VCPU（虚拟CPU）。CREDIT调度器是一种典型的常用调度器。在 CREDIT调度器中，每个调度对象即VCPU被分配一定数额的CREDIT值，调度 器以时间片为调度周期的考量，对VCPU进行调度。VCPU每运行一段时间，调 度器就扣除与运行时间对应的CREDIT值。若VCPU用完了所有的CREDIT值， 则在本调度周期中，该VCPU将不再被调度，即不再处于在线状态。

由于虚拟机监视器作为一种软件中间层插入到虚拟操作系统和底层物理硬件 中间，不可避免地在系统整体性能上带来一定程度的负面影响，其中，I/O事件处 理延时和VCPU切换性能浪费是两个典型的问题，而这两个问题都和调度器时间 片的设计有密切关系。对于I/O事件处理在虚拟化环境中的延时问题，学术界目前 采用的研究方法主要集中在设计抢占策略、缩短VCPU轮换的时间片长度、增加 VCPU切换频率这些方面。缩短VCPU轮换的时间片长度增加了VCPU在调度队 列中的分散度，在一定程度上能够缓解I/O事件处理的延时较长问题。但是，短时 间片直接导致了更加频繁的VCPU上下文切换，从而将宝贵的系统计算资源浪费 在VCPU切换上，降低了物理资源的实际利用率。进一步，对于CPU密集型任务， 由于其I/O事件不处于主要的性能开销瓶颈中，频繁的上下文切换不但不利于任务 的完成，反而会增加任务的时间开销。相反，较长的时间片有利于CPU密集型任 务的完成，但是在传统的虚拟中断处理平台中，较长的时间片意味着较长的VCPU 队列等待时间和更加不均匀的VCPU在线状态，从而导致I/O事件的响应延时进一 步增长。

图1是虚拟机监视器中原有虚拟中断处理框架。可以看到，在原有的虚拟机监 视器设计架构中，调度器的设计和虚拟中断处理平台在结构上是完全独立、互不联 系的。以SMP虚拟机为例，在虚拟中断处理平台中，虚拟设备产生虚拟中断请求， 发送给虚拟I/O APIC（输入/输出高级可编程中断控制器），虚拟I/O APIC进一步 将此中断请求绑定至该虚拟机的某一个确定的VCPU，并且将中断发送给该VCPU 的虚拟Local APIC（本地高级可编程中断控制器），完成中断注入。而另一方面， VMM中的调度器则负责调度VCPU，以每一个物理CPU为单位维护该物理CPU 对应的VCPU队列，基于一定的管理方式，例如CREDIT管理等进行VCPU的调 度。

综上所述，在系统虚拟化技术中，调度器时间片的设计从系统性能和物理资源 利用率角度来说，存在这样一个自我矛盾、需要分析和进行权衡、取舍的问题。短 时间片有利于I/O事件和中断的响应，长时间片则有利于CPU密集型任务的执行， 并且减少了不必要的VCPU上下文切换所带来的计算资源的浪费。这种权衡的局 面使得时间片的长度在设计上存在一定的争议，不能同时满足快速中断响应和高资 源利用率的要求。

因此，本领域的技术人员致力于开发一种兼顾快速中断响应和高资源利用率的 时间片长度调整架构及方法。

发明内容

有鉴于现有技术的上述缺陷，本发明所要解决的技术问题是提供一种CREDIT 调度器中增量时间片调整架构及方法，在保证系统虚拟中断得到及时处理的同时， 根据历史中断处理情况分析，合理增加了时间片长度，从而有效降低了由VCPU 上下文切换而引起的系统计算资源的浪费，提高了物理资源的利用率。

为实现上述目的，本发明提供了一种CREDIT调度器中基于中断绑定决策支 持的增量时间片调整架构及方法。

调整架构包括以下模块：

（1）调度信息维护器：负责接收CREDIT调度器通知，维护及提供虚拟机的 调度状态；

（2）中断自主决策器：负责拦截虚拟I/O APIC发送出的虚拟中断，读取调度 信息维护器中的调度状态，选取VCPU进行虚拟中断的应答；

（3）中断决策信息维护器：负责维护及提供所述虚拟中断的信息；

（4）时间片自适应调整器：负责监视和分析中断决策信息维护器中的信息， 通知CREDIT调度器执行对增量时间片的调整，维护增量值和增量时间片调整历 史信息。

采用以上调整架构的调整方法包括以下步骤：

步骤1、当虚拟机监视器接收到物理I/O发送的中断后，CREDIT调度器通知 调度信息维护器对当前虚拟机的调度状态，其包括1.各个物理队列中的VCPU的 在线状态，即当前是否在线，2.在各自队列中所处的位置，即在队列中排第几，3. 每个VPCU所拥有的剩余信用值，4.VCPU是否处于空闲状态，进行实时的增量维 护，为进一步的方案实施准备充分、有序、可用的调度信息；

步骤2、当虚拟机监视器需要处理由物理I/O设备发送的中断而生成的虚拟中 断时，中断自主决策器在虚拟I/O APIC发送出虚拟中断之前进行拦截，并且从调 度信息维护器中取得当前虚拟机的调度状态，选取VCPU进行虚拟中断的应答， 并在中断决策信息维护器中维护虚拟中断的信息；

步骤3、时间片自适应调整器实时监视和分析中断决策信息维护器中的信息， 通知CREDIT调度器中的增量时间片调整执行器执行对当前虚拟机的所有VCPU 的增量时间片的调整。

进一步地，步骤2中，选取VCPU进行虚拟中断的应答前，需判断当前虚拟 机的所有VCPU在CREDIT调度器中是否都不处于在线状态：

如当前虚拟机没有任何一个VCPU处于在线状态，即中断决策意外，则中断 决策器随机选取当前虚拟机中的一个VCPU进行虚拟中断的应答；

如当前虚拟机有一个或多个VCPU处于在线状态，即中断决策成功，则中断 决策器随机选取当前虚拟机中处于在线状态中的一个VCPU进行虚拟中断的应答。

进一步地，步骤2中，中断决策信息维护器维护中断决策意外和中断决策成功 的信息，包括当前时间、当事VM的ID、当事的中断向量号、最后被选取的VCPU 的ID、本条中断决策信息是否成功。

进一步地，步骤3中，对于当前虚拟机，时间片自适应调整器从中断决策信息 维护器中读取预设数量的信息来计算中断决策意外/中断决策成功的比例，并将该 比例与预设门限范围进行比较：

若比例在预设门限范围，维持当前虚拟机中所有VCPU的增量时间片不变， 即无操作；

若比例小于预设门限范围的下限值，则当前虚拟机中所有VCPU的增量时间 片加上增量值，即增加操作；

若比例大于预设门限范围的上限值，则当前虚拟机中所有VCPU的增量时间 片减去增量值，即减小操作；

在无操作或增加操作或减小操作完成后，将当前时间、当前虚拟机的ID、决 策类型作为一条增量时间片调整历史信息，决策类型记录的内容是无操作或增加操 作或减小操作。

进一步地，步骤3中，若从前一次开始并向前统计的增量时间片调整历史信息 中，增加操作和减少操作连续交替出现的次数大于预设次数，则将增量值乘以预设 百分比的结果作为后续计算中的增量值。

进一步地，增量时间片是非负值。

CREDIT调度器中基于中断绑定决策支持的增量时间片调整方法具有以下有 益的技术效果：

（1）中断自主决策器取代了传统的虚拟I/O APIC进行中断的发送，在选取 VCPU的决策过程中增加了对调度器调度现状信息的综合考虑，使得虚拟中断请求 尽可能的由在线VCPU处理，避免了不必要的中断处理等待用时，提高了虚拟中 断的响应速率。此外，当存在多个待选VCPU时，通过随机选取的方式，保证了 一定程度上的负载均衡性。

（2）基于中断决策信息维护的增量时间片自适应调整方案，在原有调度器的 时间片基础上提供了另一种额外的时间片-增量时间片，与原有的时间片一起协同 参与调度器时间片长度的管理，提高了调度器本身的灵活性，提高了调度器的管理 和优化能力。

（3）相比原有的单一、固定时间片策略，增量时间片基于中断决策信息动态 地给出了可以增加的时间片长度，延长了VCPU调度的时间片，减少了VCPU之 间的切换频率，有效降低了频繁的上下文切换带来的物理机计算性能的损耗。

（4）由于时间片的延长机制建立在自主中断决策机制上，延长时间片之后的 调度器不会对中断请求的及时应答造成负面影响，保证了虚拟中断及I/O事件的及 时处理。

（5）在确定时间片的增量大小的决策过程中考虑了增量时间片变动的历史操 作，根本上避免了不必要的增量值震荡波动现象，保证了增量时间片设置的稳定性、 合理性，从而提升了虚拟系统整体的稳定性和可用性。

以下将结合附图对本发明的构思、具体结构及产生的技术效果作进一步说明， 以充分地了解本发明的目的、特征和效果。

附图说明

图1是虚拟机监视器中原有虚拟中断处理示意图；

图2是本发明中加入增量时间片调整模块后的VMM虚拟中断处理示意图；

图3是本发明中基于中断自主决策的增量时间片调整架构的内部结构示意图。

具体实施方式

以下将结合附图对本发明的构思、具体结构及产生的技术效果作进一步说明， 以充分地了解本发明的目的、特征和效果。

图2是本发明中加入增量时间片调整模块后的VMM虚拟中断处理框架。其中， VCPU0～VCPU N表示多个VCPU，同样地，虚拟Local APIC0～虚拟Local APIC N 和物理CPU0～物理CPU M分别表示多个虚拟Local APIC和物理CPU。在本发明 中，虚拟机监视器的调度器模块和虚拟中断处理平台之间不再是孤立的状态，其中 引进了基于中断自主决策的增量时间片调整模块进行两边信息的接收、传递和处 理。新加入的模块从功能上将主要负责两方面的功能实现：1.截获原有虚拟I/O  APIC处理完毕的中断请求，根据调度信息实行动态的自主中断绑定。2.在中断历 史信息的支持下，结合增量时间片历史操作信息计算出新的增量时间片，通过消息 推送使得调度器中进行相应的更新操作。

图3是本发明中基于中断自主决策的增量时间片调整架构的内部设计结构。可 以看到，基于中断自主决策的增量时间片调整模块有四个主要的实现子模块，分别 是调度信息维护器、中断自主决策器、中断决策信息维护器和时间片自适应调整器。 调度信息维护器负责维护由调度器产生的调度信息，每当调度器发生一次调度事 件，就以增量的形式维护调度信息。调度信息维护器中维护的调度信息主要用于中 断自主决策器进行中断决策。中断自主决策器根据截获的中断请求信息，结合调度 信息考虑得出合适的接收者VCPU。若该接受者不处于在线状态，则称发生了一次 中断决策意外，否则认为此次中断决策成功。所有的中断决策信息都发送到中断决 策信息维护器中进行保存和处理。为了节省空间需求，信息维护器中都设置了一个 历史门限，超过历史门限的信息将被自动删除。最后，时间片自适应调整器从中断 决策信息维护器中得到必要的中断决策信息，综合历史增量时间片浮动信息以及中 断的处理情况、负载情况等，做出最终的增量时间片计算，通过消息推送使调度器 进行相应的时间片的更新。

调整方法的具体实现步骤主要分为三个部分，其中第一部分步骤如下：

步骤1、当虚拟机监视器接收到物理I/O发送的中断后，就在调度信息维护器 中对当前的调度状态，其包括1.各个物理队列中的VCPU的在线状态，即当前是 否在线，2.在各自队列中所处的位置，即在队列中排第几，3.每个VPCU所拥有 的剩余信用值，4.VCPU是否处于空闲状态，进行实时的增量维护，为进一步的方 案实施准备充分、有序、可用的调度信息。

该部分的主要代码实现如下：

具体实现步骤的第二部分主要实现中断自主决策以及维护中断决策历史信息， 为第三部分增量时间片的调整计算做数据准备，具体步骤如下：

步骤1、当虚拟机监视器需要处理由物理I/O设备发送的中断而生成的虚拟中 断时，中断自主决策器在虚拟I/O APIC发送出此虚拟中断之前对其进行拦截，并 且从调度信息维护器中取得当前虚拟机各个VCPU的调度状态，根据处于在线状 态的VCPU的统计信息来进行VCPU-虚拟终端之间的匹配。若此时没有任何该虚 拟机的VCPU在调度器中处于在线状态，转操作1，否则转操作2。

操作1、当前虚拟机没有任何一个VCPU在虚拟中断请求到来的时候处于在线 状态，此时随机选取此虚拟机的某个VCPU作为中断的接收VCPU，称发生了一 个中断决策意外，并在中断决策信息维护器中维护这次中断决策意外的信息，包括 当前时间、当事VM的ID、当事的中断向量号、最后被选取的VCPU的ID、本条 中断决策信息不成功。

操作2、当前虚拟机有一个或多个VCPU处于在线状态，即能进行中断应答， 则随机选取能进行中断应答的在线VCPU为该中断的接收VCPU，称发生了一个 中断决策成功，并在中断决策信息维护器中维护这次中断决策成功的信息，包括当 前时间、当事VM的ID、当事的中断向量号、最后被选取的VCPU的ID、本条中 断决策信息成功。

该部分的主要代码实现如下：

具体实现步骤的第三部分，时间片自适应调整器收集充足的中断决策信息，结 合增量时间片自身的历史计算信息，通过增量时间片决策算法得出新的增量时间片 并通知调度器进行变更，其具体步骤如下：

步骤1、时间片自适应调整器实时监视和分析中断决策信息维护器中维护的中 断决策信息，根据中断决策意外、中断决策成功等一定历史范围内的虚拟中断处理 情况，结合一定时间范围内的增量时间片调整历史信息，动态计算是否应当重置当 前增量时间片的大小。若需要重置增量时间片的大小，则通过调用调度器中的增量 时间片动作器重置增量时间片大小，并且维护相应的增量时间片调整历史信息。

该部分的主要代码实现如下：

具体的增量时间片决策算法如下：

对于每个虚拟机，时间片自适应调整器从中断决策信息维护器中读取与其相关 的最近的M条记录，计算中断决策意外/中断决策成功的比例R，若R0≤R≤R1 则判断结果为不需要调整，若R1<R则该虚拟机的所有VCPU的增量时间片减少 一个小量T，若R<R0则该虚拟机的所有的VCPU的增量时间片增加一个小量T。 若结果是需要调整，则读取历史调整信息，进一步判断是否产生了调整操作的震荡， 即是否出现了增加、减少操作交替出现大于K次的情况，若出现，则将T缩小为 原来的a%，即T=T*a%。其中，R1、R0分别是预设门限范围的上限和下限，M、 T、K、a、R1、R0是需结合实际系统状况预定义的参数。

做出决策后，将“当前时间、当前VM的ID、决策类型(+、-或不变)”记录 为一条增量时间片调整历史信息。

以上详细描述了本发明的较佳具体实施例。应当理解，本领域的普通技术无需 创造性劳动就可以根据本发明的构思作出诸多修改和变化。因此，凡本技术领域中 技术人员依本发明的构思在现有技术的基础上通过逻辑分析、推理或者有限的实验 可以得到的技术方案，皆应在由权利要求书所确定的保护范围内。