基于Xen 的虚拟磁盘调度算法改进

刘可超，李小勇

0 引言

Xen[1][2]是一款开源的虚拟机监视器，最初由剑桥大学开发。它同时支持准虚拟化（Para-Virtualization，也称为半虚拟化或泛虚拟化）和全虚拟化（Full-Virtualization）。准虚拟化主要是通过修改客户操作系统内核完成的；而全虚拟化的实现有两种方式：动态二进制翻译；硬件虚拟化技术，如Intel VT和AMD-V技术。以前由于缺乏硬件支持，而基于动态二进制翻译的全虚拟化方式性能较差，因此 Xen只支持准虚拟化。但是准虚拟化需要修改客户操作系统的内核，非开源的操作系统难以实现准虚拟化。随着硬件虚拟化技术的出现，Xen开始支持全虚拟化，这种基于硬件的虚拟化（HVM，Hardware Virtual Machine）性能要更好。

Xen本身并没有集成各种设备的驱动程序，而是通过一个特殊的Linux内核实现的。这个Linux内核是经过修改的，开机之后就会运行，主要功能就是为各个虚拟机提供设备驱动以及实现虚拟机的管理功能。在 Xen中，运行的操作系统内核称为域（Domain），提供驱动的内核称为Domain 0，其它虚拟机称为Domain U。

1 存储虚拟化

1.1 存储虚拟化

存储的虚拟化可以通过以下几种不同的方式[3]：直接使用物理硬盘或其分区；通过网络存储协议，例如 NFS网络文件系统；基于逻辑卷（LVM，Logical Volume Manager）；基于文件的虚拟存储，也称为虚拟磁盘镜像（Virtual Disk Image）。本文主要研究的是基于文件的虚拟存储。

Xen使用 QEMU[4]来为虚拟机模拟各种设备，包括磁盘、网卡等。从虚拟机上发出的I/O请求的处理流程如图1所示（以全虚拟化为例）：

图1 全虚拟化环境下Xen虚拟机的I/O路径

首先 Domain U的内核执行磁盘读写访问指令，触发VMExit，处理器调用虚拟机监视器（VMM）设置的VMExit处理函数，从非根环境转入根环境。然后，将I/O指令的具体信息写入Domain U 内核与QEMU设备模型共享的I/O共享页中，并通过事件通道（Event Channel）机制通知Domain 0。接着虚拟机监视器阻塞Domain U，并且调用调度算法，把执行控制交给Domain 0。Domain 0负责收集这些虚拟机的I/O请求，并将执行控制从内核态返回用户态，处于用户态的QEMU设备模型通过读取I/O共享页，识别对于磁盘设备的访问，调用相应的回调函数，完成对磁盘的读写操作。

当硬盘读写操作完成后，磁盘控制器触发硬件中断，该中断首先由虚拟机监视器的处理函数接管，接着通知Domain 0，调用其中的中断处理函数。Domain 0的中断处理函数处理完后，唤醒正阻塞于I/O等待队列中的设备模型进程，当设备模型发现有虚拟硬件中断时，通过I/O共享页设置相应的中断位，同时把这个虚拟硬件中断通过事件通道通知虚拟机监视器。当虚拟机下次 VMEntry返回时，就可以唤醒被阻塞的Domain U，完成整个I/O操作。

1.2 I/O调度

Xen的Domain 0是基于改进后的Linux 2.6内核实现的，它支持四种 I/O调度算法[5]：完全公平队列（CFQ，Complete Fair Queuing）；最后期限调度（Deadline）；基于预期的调度（Anticipatory）；简单的先到先服务调度（NOOP）。而其中CFQ算法支持基于优先级的调度。CFQ算法根据同步和异步，对进程提交的I/O请求进行分类，优先处理同步的I/O请求。CFQ算法内部维护多个请求队列，它根据发出I/O请求的进程的标识号（PID），通过散列函数将该请求映射到相应的队列中。CFQ优先选择I/O优先级高的队列进行处理；在同优先级的队列之间，CFQ算法使用轮询调度（Round Robin）的机制处理各个活动队列，实现将I/O请求从CFQ队列传送到设备队列。

为了避免引起其它活动队列的饥饿现象，CFQ算法同时还引入了时间片（Time Slice）的概念，对请求设置截止期限（Deadline）。当请求在超过截止期限之后还没有得到服务时，它们就会在下一个调度周期被优先处理。处理过的请求被移出活动队列并插入到底层设备的队列中，该插入操作可以按照I/O请求的磁盘扇区顺序进行排列，目的是减少磁盘寻道时间。

CFQ算法可以保证公平性，但是对于很多应用场合来说（如服务器整合），除了公平性，还应该合理的分配带宽。因为不同的应用所需的带宽是不一样的，对带宽稳定性的要求也是不一样的，如果单纯的在应用之间平均分配，可能会导致有的应用所获得的带宽超过了它所需的最低带宽，而其它应用的带宽需求则没有得到满足。虽然CFQ调度算法中支持优先级调度，通过设置I/O优先级可以使服务得到不同的磁盘带宽；但是它并不能够提供定量的带宽保证。

2 动态优先级实现模型

基于反馈机制的动态优先级调度的结构如图2所示：

图2 基于反馈的动态优先级调度

主要包括三个模块：性能实时统计模块、动态优先级模块以及控制模块：

2.1 性能实时统计

由于虚拟机对于磁盘的访问，都是通过QEMU设备模型来完成的，因此，通过改进 QEMU，可以实现实时的磁盘性能信息统计。而统计的时间间隔就显得非常重要，因为如果间隔太短，则无法正确的得到实际的性能数据；相反，如果间隔太长，则会影响到优先级调整的速度，使得性能达不到预期的目的。目前，采用的时间间隔默认是5秒钟，实时统计模块会记录每个虚拟机在每5秒钟之内的I/O请求的大小，并将得到的带宽传给控制模块。带宽数据的传递是通过QEMU与控制模块之间的消息队列完成的。

2.2 动态优先级

Linux 2.6内核中从低到高支持3个I/O优先级类型，分别是：空闲（Idle）、最大有效度（Best Effort）和实时（Real Time）。而每个优先级类型中有分别包含8个优先级，从低到高依次为7，6，…，0。在进行调度的时候，优先的处理实时类型的请求，根据具体的优先级，从0到7进行处理；当优先处理完实时优先级的I/O请求之后，便会接着处理最大有效度类型的请求；最后当系统中没有其它类型的请求时，才会处理空闲类型的请求。而如果同一类型的多个进程同时发出I/O请求，那么优先级较高（数值较低）的进程会得到更多的磁盘服务。但是，优先级低的进程并不是完全得不到服务，而只是所占的比例较小。因此，可以通过调整I/O优先级，使得磁盘带宽在多个虚拟机之间，按照预先设定的目标带宽进行分配。

动态优先级模块负责通过系统调用动态的升高或降低各个虚拟机的QEMU设备模型进程的I/O优先级。具体如何调整是由控制模块进行控制的。在实际进行调整的过程中，首先，将所有的虚拟机对应的I/O优先级都设置为Best Effort，优先级为 4，这样就处于一个居中的优先级，便于灵活调整。然后，根据控制模块传来的控制信息，如果目前某个虚拟机的带宽没有达到预期，则升高它的I/O优先级，如变为3，隔一定时间后，再根据控制信息进行增减。如果增加到Best Effort 0还是达不到要求，则调整为Real Time 7；反之亦然。

2.3 控制模块

每隔一定的时间间隔（5秒钟），性能统计模块就会将信息反馈给控制模块。控制模块通过实时的性能参数和预设的目标参数来控制I/O优先级的调整。如果虚拟机当前的磁盘带宽没有达到它的目标带宽，就需要对该虚拟机所对应的设备模型进程的I/O优先级进行调整。这样就可以通过反馈的机制来不断进行优先级调整，以便使得各个虚拟机都能够达到目标带宽。如果系统总体的性能无法满足所有虚拟机的需求，则尝试满足尽量多的虚拟机。

当然，实际带宽不可能完全和目标带宽一致，应该允许一定的误差范围；同时由于目前的I/O调度算法中优先级划分的粒度较大，调整一个优先级别就会使带宽发生很大变化，频繁调整优先级会导致虚拟机的磁盘带宽波动严重。因此，在实际实现中，只有当有某个虚拟机的实际带宽低于目标带宽超过 1MB/s时，才会向动态优先级模块发出控制信息，进行优先级调整。而如果某个虚拟机的实际带宽超过了它的目标带宽，但是其它虚拟机的带宽需求也能得到满足，为了避免波动，不会进行优先级调整。

3 性能评估

3.1 实验环境

实验机器配置如下：CPU：Intel Pentium 4 3.0GHz（支持VT-x），内存：1GB，磁盘：80G B。使用的Xen版本为：Xen-Unstable：Change Set 20128， Xen Linux内核版本：2.6.18.8。在其上运行两个Red Hat Enterprise Linux 5.2（内核2.6.18）的虚拟机，分配给虚拟机的内存大小都是为256 MB，两个虚拟机的虚拟磁盘文件大小均为4 GB。

3.2 结果对比

分别在两个虚拟机之上运行测试程序（使用dd命令进行读测试：dd if=/dev/hda1 of=/dev/null）。假定虚拟机2对带宽的要求较高，其目标带宽为30MB/s；而虚拟机1则没有这么高的要求，它只需要10MB/s左右的带宽。对加入基于反馈的动态优先级调度前后两个虚拟机的平均磁盘带宽进行比较，结果如图3所示：

图3 改进前后对比

在改进之前，由于CFQ算法能保证较好的公平性，因此，两个虚拟机的磁盘带宽基本相等，都为22MB/s左右，总的系统吞吐量约为44MB/s。但是存在的问题是，虚拟机2的实际带宽并没有达到目标的30MB/s，虚拟机1并不需要20多MB/s的带宽，也就是说带宽的分配不够合理。

增加了基于反馈的动态I/O优先级调度之后，可以看到虚拟机2的带宽约为31MB/s，达到了预期的30MB/s。这种情况下，虚拟机1的带宽约为15MB/s，满足了它本身的需要。总的系统吞吐量约为46MB/s，与改进之前相比，并没有减少。结果表明，动态优先级的引入达到带宽按需分配的预期目标，而且对系统整体性能的影响很小。加入动态优先级调度之后，两个虚拟机的带宽变化过程如图4所示（以5秒钟为单位测得）：

图4 改进后带宽变化过程

从结果中可以看出，两个虚拟机在第2个5秒钟就达到了目标带宽，后面基本都保持在目标带宽之上。当然，结果中的带宽还是有一些波动，但是都是在目标带宽之上的波动，也就是说达到了预期的目标。

4 结束语

本文通过研究Xen中的存储虚拟化以及I/O调度算法原理，提出了一种基于反馈的动态优先级调度机制，以此来实现磁盘带宽的动态调整，为运行于多个虚拟机之上的各种服务提供存储带宽的保证。而通过测试也可以看出，改进之后，磁盘带宽能够在多个虚拟机之间按照需要进行分配。

[1]Barham P, Dragovic B, Fraser K, Hand S, Harris T, Ho A,Neugebauer R, Pratt I.and A Warfield. Xen and the art of virtualization. In 19th ACM Symposium on Operating Systems Principles, Oct 2003.

[2]Pratt I, Fraser K, Hand S, Limpach C, Warfield A,Magenheimer D, Nakajima J, and Malick A. Xen 3.0 and the art of virtualization. In Proceedings of the 2005 Ottawa Linux Symposium, Ottawa, Canada, July 2005.

[3]Xen 3.3 User Manual, http://bits.xensource.com/Xen/docs/user.pdf

[4]Bellard F.QEMU, a Fast and Portable Dynamic Translator.In Proceedings of the USENIX Annual Technical Conference, 2005.

[5]Pratt S, Heger D.Workload Dependent Performance Evaluation of the Linux 2.6 I/O Schedulers.In Proceedings of the Ottawa Linux Symposium, 2004.