一种基于M/M/n模型的虚拟机调度策略

申秋慧，郭丽萍，张文娟

(周口师范学院 计算机科学与技术学院 ，河南 周口 466000)

云计算的核心技术是如何合理地将虚拟机调度到物理机上，调度算法的优劣直接影响云计算系统的性能及收益.目前国内外的研究成果中，采用的方法可总结为两类：简单调度策略和基于启发式算法的全局寻优策略.

简单的调度策略易于实现，比如Amazon EC2采用的以负载均衡为目标的轮转调度(RR)[1]，HP采用的以公平分配为目标的先来先服务(FIFS)策略[2]，但执行效率较低. 基于启发式算法的调度策略只从单方面考虑，或者考虑的只是单个方面的多个目标而已，比如基于博弈论的算法，能保证负载均衡，但算法复杂，无法充分保证用户服务质量(QoS)；基于遗传算法的策略(MOGA)能保证资源充分利用，但忽略了资源过载对任务执行效率的影响[3]；基于内存感知的服务器整合算法(BCSF)以节能为目的，但物理机性能会因负载不均衡而降低[4].

为了解决上述问题，本文基于M/M/n理论建模云计算系统并提出了一种虚拟机调度策略，不仅能动态分配虚拟机以满足用户对资源的需求，还能进行虚拟机的迁移达到负载均衡，关闭空闲的物理机降低能耗.

1 问题描述

本文基于M/M/n理论，把物理机可容纳的虚拟机数量比作服务窗口，把待分配的虚拟机比作队列中等待服务的客户. 设云数据中心有x个物理主机，物理主机的集合是H={h1，h2，…，hx}，对于任一物理主机hj，用每秒百万指令数(MIPS)描述他的CPU性能，则hj={cj，rj，wj}，其中cj表示hj的CPU能力，rj表示hj的存储容量，wj表示hj的网络带宽，hjr表示hj的剩余可用资源.

云数据中心根据类型把任务分为计算密集型、存储密集型、传输密集型和混合型4类，每个类型又分为大、中、小3种规模. 为每一类型的不同规模的任务创建一个虚拟机，也就是说云计算中心一共需要建立12个不同配置的虚拟机模板.当任务到达时，调度中心先根据任务的类型和规模参照模板为它初始化一个虚拟机，虚拟机模板集合V={v1，v2，…，v12}，对于每一类虚拟机用vir={c(vi)，r(vi)，n(vi)}表示虚拟机所占资源，其中c(vi)，r(vi)，n(vi)分别表示虚拟机的CPU性能、存储容量和网络带宽. 用n表示当前系统中物理机可容纳的最大虚拟机数量，也就是M/M/n模型中服务窗口的大小，可取容纳最小虚拟机个数和最大虚拟机个数的均值，即

(1)

设到达云数据中心的任务ti是相互独立的，服从λ的泊松分布，即与任务匹配的虚拟机的创建间隔也服从λ的泊松分布，虚拟机调度到物理机上后即开始运行，由于任务的多样性，物理机对虚拟机的服务时间st是随机的，假设该服务时间st服从参数为μ的负指数分布.

2 基于M/M/n的云数据中心系统模型

2.1 模型设计

根据第1部分的描述可以建立基于M/M/n的云数据中心系统模型，如图1所示.

图1 基于M/M/n的云数据中心系统模型

任务到达后，由初始化模块分析任务的类型和规模，然后从模板库中选择一个合适的模板为任务初始化一个虚拟机. 所有任务的虚拟机按照初始化完成的先后顺序排成一个全局虚拟机队列，用Nd表示全局队列中虚拟机的数量，用t(vi)表示在能够满足用户QoS的情况下虚拟机vi的最大等待时间，等于虚拟机开始运行的时间减去初始化完成的时间. 如果调度策略判断当前系统无法在保证服务质量的情况下完成虚拟机调度，就开启新的物理机；若判断到物理机资源空闲较多，则进行虚拟机的迁移，关闭空闲物理机，以达到节能的目的.

若任务运行完成，与之对应的虚拟机就被撤销，对应物理机hj被虚拟机vi占用的资源就释放了，hj可以接纳新的虚拟机.

2.2 模型分析

综上所述，可用λ表示虚拟机的初始化完成速率，μ表示各虚拟机在物理机上运行的服务速率，所以nμ表示整个系统的平均服务率. 记ρ1=λ/μ，ρ=λ/(nμ)表示服务强度，用Pi表示系统中存在第i个需要调度的虚拟机的定态概率. 根据Little公式可知，当ρ<1时，整个系统处于稳定状态，即云计算系统处于负载均衡的稳定状态.

对于云计算系统来说，任务数量是无限的，因此需要分配的虚拟机也是无限的，所以整个云计算系统可以看成是一个不断进行状态变换的生灭系统，系统可能的状态集可写为Φ={0,1,2,3,…}，其状态流图如图2所示.

图2 基于M/M/n的云数据中心状态流图

其中状态k(n≥k≥0)表示系统中有k个虚拟机已经分配到了物理机上运行，物理机还可以接纳n-k个虚拟机，当状态k>n时，表示待分配的虚拟机数量超过了系统中物理机所能容纳的虚拟机数量，物理机已达到饱和状态，剩余的k-n个虚拟机必须排队等待. 当云计算系统处于平衡状态时，可以得到K氏代数方程[5]：

(2)

(3)

由此，可得

(4)

根据上述分析，可知

(5)

由Little公式可知

(6)

根据上述公式，只要确定了云计算系统当前开机的物理机的参数，就能计算出系统处于平稳状态时的Nw及Tw.

3 虚拟机调度策略

基于上文所建立云数据中心模型，提出了虚拟机调度策略，该策略包括一个全局调度算法，M/M/n调度算法；3个处理不同情况的子算法：检测算法、迁移算法和分配算法.

3.1 M/M/n调度算法

首先选取一个排在全局虚拟机队列队首的虚拟机vi，然后从物理机集合H中选择一个可用资源满足vi的物理机hj，把vi分配给hj，完成虚拟机vi的调度，然后调用检测算法，检测是否有大量空闲物理机，如果有，调用迁移算法，集中虚拟机，把空闲物理机关闭. 否则，如果找不到一个满足vi的物理机hj，就计算物理机集合H中所有可用资源的总和Hr，如果Hr>vir，调用迁移算法，进行虚拟机的迁移，把可用资源集中到一台物理机上hj，把vi分配给它. 如果迁移失败，就表示当前物理机已达到饱和，此时，需调用分配算法，判断vi是继续等待还是新启动一台物理机，然后把vi分配给它. 算法伪代码如表1所示.

表1 M/M/n算法伪代码

3.2 子调度算法

检测算法的思路是首先假设关闭一台物理机，然后根据公式(1)计算服务窗口n，根据公式(5)计算等待分配的虚拟机的平均个数Nw.如果当前全局队列中虚拟机的数量Nd

分配算法的步骤是先计算Nw，再根据公式(6)计算虚拟机的平均等待时间Tw. 若全局队列中虚拟机数量Nd小于平均等待数量Nw，且vi的允许等待时间t(vi)大于平均等待时间Tw，则vi继续等待，下一轮再分配. 否则，为了保证用户满意度，开启新的物理机并把vi分配给它.

4 实验与性能分析

本文使用CloudSim云仿真平台运行在真实云环境中进行实验. 选择了来自不同科学领域的四个真实任务Montage，LIGO，SIPHT和CyberShake作为实验输入[6]. 这四个任务按大、中、小规模可对应本文提出的12个虚拟机模板. 用提出的M/M/n调度算法与RR算法、MOGA算法、BGT算法和BCSF算法在系统能耗、活跃物理机数量和任务完成率三个方面进行比较.

4.1 实验配置

实验运行在一台IBM高性能服务器上，模拟了400台物理机，物理机的配置是10 000 MIPS的CPU计算能力，2 TB的存储和10 G的带宽. 虚拟机类型及配置如表2所示：

表2 虚拟机类型及配置

将工作流分为平均50，200，400，500，600，800，1 000个任务，每个任务配置一个虚拟机，也就是说系统中虚拟机的数量分别是50，200，400，500，600，800，1 000，每种虚拟机数量运行20次，将20次实验结果的平均数据作为最终评估数据.

4.2 结果分析

在实验中，假设初始有20台物理机处于开机状态，可估算出n=178，取λ=250[7]，即虚拟机到达间隔是0.004 s，取服务强度ρ=0.85. 活跃物理机数量如图3所示，活跃物理机数量与虚拟机规模存在正比关系，虚拟机数量变大，活跃物理机数量也随之增加，系统能耗明显提升，如图4所示. 在同一数量的虚拟机请求规模下，M/M/n算法在活跃物理机数量上明显少于RR算法、MOGA算法和BGT算法，相比与这三种算法活跃的物理机数量分别减少了约14.5%，9.4%，6.5%，但高于以节能为目的的BCSF算法2.75%.

图3 活跃物理机数量比较

图4 系统能耗比较

M/M/n算法在任务完成率方面高于RR算法、MOGA算法、BGT算法和BCSF算法，如图5所示.原因是M/M/n算法在调度虚拟机时不仅考虑了待分配物理机的数量，还考虑了虚拟机允许的最大等待时间，若不满足最大等待时间立即开启新的物理机以满足虚拟机的调度. 而对于整个云计算系统还考虑了物理机空闲的情况，根据Nw动态检测系统负载，若负载轻，立即运行迁移算法，腾出轻载物理机并关闭，以降低系统能耗.

图5 任务完成率比较

5 结论

本文分析了典型的虚拟机调度策略及其存在的问题，基于排队理论对云计算系统进行建模，提出了M/M/n虚拟机调度策略.该策略不仅考虑了全局虚拟机的分配，还动态地对物理机的负载情况进行检测，结合动态阈值进行虚拟机的迁移和物理机的开关机，在保证任务完成率的情况下，也达到了节能的目的. 实验验证了M/M/n调度策略的优越性，虽然能耗方面略高于以节能为优化目标的BCSF算法，但任务完成率方面M/M/n调度策略效果最好.

M/M/n调度策略的关键是动态计算Nw和Tw，Nw和Tw的计算都用到λ，实验时λ的取值用的是大多数研究者在M/M/n排队理论中的取值. 此未来的工作会研究与任务类型最匹配的λ取值，让不同类型的虚拟机使用不同的λ值，对M/M/n调度策略做进一步地优化和验证.