陈 亮，王江勇，彭 舰

（四川大学计算机学院，四川成都610065）

0 引 言

云计算是继分布式计算、网格计算、效用计算之后的一种新的计算模式［1］，并在商业上取得巨大的成功，将计算资源作为基础设施供应，并采用“即付即使用”支付方式，使得计算资源可以像水电那样购买。而服务等级协议（service level agreement，SLA）是云计算服务商和客户之间对服务质量（quality of service，QoS）的一种协商［2，3］。云计算服务商需要管理不同客户的SLAs，并监测QoS以满足不同用户的SLAs。通常SLA针对不同的应用而采用不同的衡量标准，例如Web应用一般采用响应时间来作为SLA，而对主机资源（CPU、RAM、IO等）需要一定时间持有的应用，SLA则需要考虑主机的资源利用率［4］。尽管不同客户的SLA不同，但是云计算服务商的主机资源是统一的，如何利用有限的资源，实现云系统中任务或虚拟机的分配和调度，以最大限度满足不同的SLA，是云计算中广泛研究的热点之一［5］。

为了给用户提供高度可用性、高度伸缩性的云服务［6］，数据中心一般都采用负载均衡机制［7］。当创建大量虚拟机得不到满足时，多队列系统应运而生用于解决任务排队的问题。同时，多个任务分布在大量主机上，显然没有有效利用资源，常见的办法是通过虚拟机迁移将多个虚拟机聚集在同一台主机以提高资源利用率和节约能耗［8］。文献［9］提出一个负载均衡下的随机模型，并定义了吞吐量最优的概念，根据该概念提出两个吞吐量最优的算法，但没有考虑SLA约束。文献［10］提出基于资源预算条件下的动态调整自适应应用程序的参数，以满足资源动态变化的供应。文献［11］提出虚拟机复用技术，将多个虚拟机整合在同一主机上，本文将整合的思想扩展到多队列系统中。

本文采用文献［9］提到的基于时间片的分时系统，将资源SLA考虑在内，给出资源SLA违反模型，并提出一个多维资源SLA感知的优化算法，该算法减少了SLA违反率，并加快了任务的执行速度。

1 模型描述

1.1 多队列系统

基于多队列系统，本文作出以下几点假设:

（1）采用分时系统，系统的最小时间单位，即一个时间片t；

（2）用户请求的任务是非长期的计算密集型任务，不存在类似Web应用的任务长期驻留在服务器上；

（3）用户向系统发出的请求，描述了所需虚拟机（virtual machine，VM）的类型和大小，分别记为m和S。虚拟机类型一共有1…m种，而VM的大小是该VM执行完任务所需要的时间片数量。

根据以上假设，当有大量的用户请求时，系统为用户请求的任务创建对应类型的VM，同一类型的VM进入同一队列排队，因此产生m个队列。在每一个时间片t时，分别从m个队列中取出一个m维的VM向量N（简称“向量N”），它的每一维是对应每种类型的VM数量。系统将这些VM派发给特定的服务器（physical machine，PM）去执行，当VM所需时间片（即VM的大小）用完时，用户请求的任务完成，该VM从主机上销毁。

在时间片t的起始时刻，到达系统的m类型VM的集合记为m（t），其数量是Am（t）＝｜m（t）｜。有如下队列模型［8］，即

式（1）和式（2）中，在时间片t时刻时，Wm（t）是达到的m类型任务的总大小，Qm（t）是当前队列中未处理完的m类型任务的总大小，Dm（t）是能被系统处理的任务总量。

系统将m个队列分布在每个服务器s上，但是逻辑上可以看作系统只存在m个队列，如图1所示。

图1 多队列系统

每个服务器从自己的m个队列中选择最优的配置向量N＊，因此式（2）可以进一步写成

文献［9］给出了两种优于JSQ（Join－the－shortestqueue）算法的路由算法，分别是Power－of－two算法和Pick－and－Compare算法。这两种算法减少了集中维护队列长度信息的开销，提高了系统负载性能，但是对减少系统的SLA冲突没有帮助。本文以简单的JSQ算法（算法在1.2节中描述）作为VM派发阶段的路由算法，集中讨论主机PM上资源SLA违反情况和资源利用率。

1.2 JSQ算法

JSQ算法是一种针对服务器集群的常用路由策略［12］，该算法集中维护所有队列的长度，将需要分发的任务分配给当前具有最短长度队列的服务器。JSQ算法分配任务的基本思想是，根据每个服务器上队列的长度，决定每个服务器的处理能力，即队列越短，该服务器处理能力越强。由于队列的长度是动态变化的，因此主机的处理能力也是动态确定的，不存在某一个队列的长度很长的情况。

在1.1节中提到的多队列系统中，虚拟机类型有m种，而这m种虚拟机对主机资源的需求不同，因此多队列系统中的m队列，相对于某一个主机来说，被处理的速度不同，具体体现在队列的长度不同。本文将JSQ算法扩展到所有主机上的m个队列，当系统收到用户的虚拟机请求时，根据虚拟机的类型，确定当前所有主机上对应该虚拟机类型的最短队列，并将请求的虚拟机分配给具有该最短队列的主机。根据JSQ算法的思想，显然具有该最短队列的主机更有能力处理此类型的虚拟机。

1.3 SLA冲突检测模型

假设每台服务器有i种不同的资源（例如CPU、内存、磁盘等），每种资源记为Ri，其总量为Ti，则由m种类型VM组成的可行配置向量N，应满足如下公式

显然，N取值有很多，这些可行配置向量N构成可行配置向量集合，每次达到服务器的工作量λ为这些可行配置向量N的组合。

由文献［11］启发，本文给出如下SLA模型，在［1，L］个时间片内，有

上述公式中符号的含义，见表1。

显然，上述SLA模型针对i种资源有i种约束，Pi和βi这两个参数是根据不同应用性能设定的，也受不同资源特点的影响。在Pi时间段内，是资源i的平均量，当它大于当前服务器剩余资源i时，说明资源i存在SLA违反。这时，需要考虑检查当前最优可行配置向量中存在SLA违反的VM类型，在文中第2节给出了具体算法。

表1 主要符号及其含义

2 多维资源SLA冲突优化算法

2.1 优先队列

在1.1节描述的系统模型中，从VM类型划分了m个队列，但是没有考虑任务SLA违反的情况，即存在一些任务可能占用某种资源（CPU密集型任务、IO密集型任务、Network密集型任务等），但是由于虚拟机预定配置造成某种资源的瓶颈，延长了任务的执行时间。本文提出为每台服务器增加一个优先队列，通过SBP（select by priority）算法（算法在2.2节中描述）将存在资源SLA违反的VM，放入优先队列中。当服务器在每个时间片t的开始时，先从优先队列中读取最优可行配置VM向量，然后再根据服务器的当前容量，从m个队列中选择一个最优可行配置向量。采用优先队列的队列模型，如图2所示。

图2 采用优先队列的队列模型

在时间片L时，将资源违反SLA的VM放入优先队列中。很明显，当L足够长时，收集SLA冲突的信息更多，更能准确地预测出当前VM向量中存在那类资源SLA违反。下面通过SBP算法将预测出的资源SLA违反的VM选择出来放入优先队列中，该VM可以得到优先执行，因此可以满足该VM对资源较高的需求。

2.2 SBP算法

SBP算法采用贪心策略，当资源i发生SLA违反时，根据式（5）可以检测出SLA违反，从当前可行配置向量N（s）（t）中选择对资源i需求最大的VM，放入优先队列中；如果资源i仍然不符合SLA，则重复上述步骤，直至N（s）（t）不存在SLA违反。这时，优先队列中的配置向量是可行配置向量，因为

根据SBP算法，服务器s先从优先队列中读取最优可行配置向量，再从m个队列读取最优可行配置向量，则根据Myopic Max Weight分配算法的思想［9］，推导出如下公式

采用SQP算法的负载均衡调度策略，描述如下:

调度过程（1）VM分派阶段（JSQ算法）对于所有在时间片t时达到的m类型任务，路由到对应m类型VM的最短队列中，即s＊m（t）＝arg min多队列系统VM s Q ms（t）为选出的具有最短队列的服务器。此时，该服务器上达到的负载量，如下W ms（t）＝W m（t），s＝s＊m（t）0，s｛为其他服务器（2）VM执行阶段（SBP算法）if（每台服务器s采用SLA模型检查到i类型资源发生SLA违反）｛1）从当前可行配置向量N（s）（t）中选择对资源i需求最大的VM，放入优先队列中；如果资源i仍然不符合SLA，则重复上述步骤，直至N（s）（t）不存在SLA违反。这时，优先队列中存在配置向量＾N（s）（t）2）服务器先读取＾N（s）（t），再根据Myopic Max Weight分配算法，即公式珦N（s）（t）∈arg max Q m（t）N m求出珡N（s）m（t），并将该可行配置向量读入服务器。｝else｛采用Myopic Max Weight分配算法，求出珡N（s）m（t），并将该可行配置向量读入服务器。N:珡N（s）（t）＋N（s）（t－）＋＾N（s）（t）∈s∑m｝

3 实验与分析

本文采用CloudSim Toolkit工具［13］进行模拟实验，实验平台如下:Intel Core2 Duo CPU T5800 2.00GHz，RAM 2GB，Windows 7 SP1。CloudSim的基本模拟参数见表2。

表2 模拟实验基本参数

实验将Round Robin算法和采用SBP算法的Round Robin算法进行对比分析。

图3给出了CPU、RAM、IO资源的利用率的情况（VM数量为710时）。由于采用了资源SLA冲突模型，检测出可能存在资源瓶颈的VM，并优先执行这一类VM，SBP算法明显提高各项资源的利用率，优于一般的Round Robin算法。

图3 资源利用率（710 VMs）

图4给出了当VM数量为710至960时，CPU、RAM、IO资源的平均冲突率。显然，各个任务对RAM资源竞争程度强于CPU资源和IO资源，而SBP算法对CPU、RAM和IO资源冲突有不同程度的改善，较明显的是SBP算法将Round Robin算法的RAM冲突率减少了26%。总体上SBP算法较Round Robin算法，减少了各种资源的SLA冲突。

图5给出了VM总的执行时间。当VM数量小于200时，系统无论采用Round Robin算法，还是结合了SBP算法，系统都能在较短时间内执行完成VM。当用户请求的VM配置过多时，系统的排队时间延迟加大，而且每种资源（CPU、RAM和IO）的冲突明显增加。这时基于资源SLA冲突检测的SBP算法，尽可能将对资源需求大的任务优先执行，有效减缓了排队时间，VM的总执行时间在一定程度下没有剧增，VM的平均执行时间比采用Round Robin算法要短很多。

图4 平均SLA冲突率（710～960 VMs）

图5 执行时间

4 结束语

本文基于多队列系统，提出一个检测资源SLA的冲突模型和基于该模型的SBP算法，通过增加一个优先队列，将对资源需求大的VM放入优先队列并优先执行，最大化提高资源利用率和减少资源冲突情况，以减少系统的排队时间和VM的执行时间。仿真结果表明，采用SBP算法的Round Robin算法，有效减少各种资源（CPU、RAM和IO）的SLA冲突率，在提高资源利用率和缩短VM执行时间方面，明显优于一般的Round Robin算法。

［1］Qi Zhang，Lu Cheng，Raouf Boutaba.Cloud computing:State－of－the－art and research challenges［J］.Journal of Internet Services and Applications，2010，1（1）:7－18.

［2］Pankesh Patel，Ajith Ranabahu，Amit Sheth.Service level agreement in cloud computing［R］.Ohio:Kno.e.sis Publications，2009:1－2.

［3］Philipp Wieder，Joe M Butler，Wolfgang Theilmann，et al.Service level agreements for cloud computing［M］.New York:Springer，2011:13－26.

［4］Inigo Goiri，Josep Ll Berral，J Oriol Fito，et al.Energy－efficient and multifaceted resource management for profit－driven virtualized data centers［J］.Future Generation Computer Sys－tems，2012，28（5）:718－731.

［5］Vladimir Stantchev，Christian Schropfer.Negotiating and enforcing QoS and SLAs in grid and cloud computing［G］.LNCS 5529:Advances in Grid and Pervasive Computing.Berlin:Springer Berlin Heidelberg，2009:25－35.

［6］Peter Mell，Timothy Grance.The NIST definition of cloud computing（draft）［R］.USA:NIST Special Publication，2011.

［7］Randles M，Lamb D，Taleb－Bendiab A.A comparative study into distributed load balancing algorithms for cloud computing［C］//IEEE 24th International Conference on Advanced Information Networking and Applications Workshops，2010:551－556.

［8］Sallam A，Li K.A multi－objective virtual machine migration policy in cloud systems［J］.The Computer Journal，2013，3（1）:1－10.

［9］Maguluri S T，Srikant R，Ying L.Stochastic models of load balancing and scheduling in cloud computing clusters［C］//IN－FOCOM.IEEE，2012:702－710.

［10］Zhu Q，Agrawal G.Resource provisioning with budget constraints for adaptive applications in cloud environments［C］//Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing.ACM，2010:304－307.

［11］Meng X，Isci C，Kephart J，et al.Efficient resource provisioning in compute clouds via VM multiplexing［C］//Proceedings of the 7th International Conference on Autonomic Computing.ACM，2010:11－20.

［12］Gupta V，Harchol Balter M，Sigman K，et al.Analysis of join－the－shortest－queue routing for Web server farms［J］.Performance Evaluation，2007，64（9）:1062－1081.

［13］Calheiros R N，Ranjan R，Beloglazov A，et al.CloudSim:A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms［J］.Software:Practice and Experience，2011，41（1）:23－50.