一种基于QOS约束简化的云计算资源调度策略研究

彭红姣　李安南　曹新欣

摘要：该文对基于QoS约束的资源调度策略进行了研究：根据用户对QoS的偏好，建立资源调度模型。实现了基于QoS约束的资源调度算法。通过实验，扩展了CloudSim中的基础类，在CloudSim平台上对本文MMPS算法算法进行模拟验证。实验结果表明，该文策略能更好地满足服务质量。

关键词：云计算；任务调度；QoS；资源；cloudsim

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）30-7027-02

近年来，互联网需要处理的业务量快速增长，如何处理海量数据成为互联网未来发展的关键。在这种背景下，基于分布式计算特别是网格技术的发展，产生了一种新型服务计算模型：云计算[1]，即将计算任务分布在大量计算机构成的资源池上，使各种应用系统能够根据需要获取计算力、存储空间和信息服务，其核心问题是资源调度管理[2]。云计算资源调度是指在特定的云环境中，根据一定的资源使用规则，在不同的资源使用者之间进行的资源调整过程。现有的资源调度策略大多是通过虚拟机级别上的调度技术结合一定的调度策略来为虚拟机内部应用做资源调度，调度算法过于简单，判断需要进行推测执行任务的算法造成过多任务需要推测执行，降低了整个任务的性能。所以在虚拟机级别上采用什么算法实现资源调度是暨待解决的一个难题。

目前，对于云计算资源调度资源分配的研究仍存在许多问题，各大云计算厂商关注的问题主要集中在虚拟机资源管理、任务调度、系统负载均衡上。而每个云计算厂商都以自己的基础设施架构来构建，缺乏统一的规范和标准，使得云环境下的资源调度和资源管理呈现出多样化的特点。云计算由分布式计算和网格计算发展而来，两者的资源调度和分配经过多年的研究已相当成熟，对于云计算环境下的资源调度资源分配有一定的可借鉴性和相通性。但是以虚拟化技术为基础，并侧重于商业化模式的应用理念使得云计算的资源调度资源分配具有自己的特点不能生搬硬套网格计算中的任务调度策略。

1 一种基于QOS约束简化的资源调度策略

1.1 任务描述

用户提交服务请求是一个随机过程，任务到达云计算系统的时间应服从随机分布。从任务对计算资源需求角度看，任务类型具有多样性，常见的包括计算密集型、通信密集型、数据密集型和I/O密集型等等[3]。

1.2 资源描述

云计算以一种简化机制调度作业，把任务所需资源用虚拟机来表现，所谓的资源搜索从本质上看就是搜索虚拟机，作业调度就是一种以优化的方式将任务与资源进行映射匹配。物理资源性能参数一般包括CPU、内存、存储空间、带宽、I/O存取率、故障率等等，虚拟机也是一种物理资源。该文对虚拟机性能参数的选取包括：CPU、内存、存储空间以及带宽。

1.3 Qos参数选取

云计算目的是为不同用户提供应用服务，在资源需求方面各类用户的期望不一样，如：实时性，低费用，稳定的网络等。QoS作为衡量服务满意度的一个重要标准，云计算对用户的服务可以通过QoS来评价，该文主要考虑三个QoS参数：完成时间、网络带宽、费用。

1.4 负载均衡策略

负载均衡是把系统中的资源按性能进行负载分配。目前主流操作系统在任务分配方面使用了一种简单方案：根据物理机CPU性能按比例分摊。常用的负载指标（Index）包括CPU就绪队列长度、进程响应时间、内存使用情况、磁盘访问频度，CPU和I/O利用率等，以及异构节点处理能力上的差别。

1.5 任务与资源映射模型

云计算环境下资源优化分配可描述为：当任务随机到达计算节点时，根据任务的类型、长度和计算节点的执行状态（主要是负载量），从任务开始执行到结束期间，当云计算系统总代价最小时，最大限度地满足QoS。该文云计算系统总代价包括两个部分：节点负载量和任务计算代价。因此，该文所研究的问题就转化为——基于多目标约束的最优解问题。基于QoS约束的任务计算代价粗粒度综合评价表达式如（1） 所示：

[Costvm=（Jft-eiF）2+（Jbw-eiB）2+（Jcs-eiS）2] （1）

当Costvm值越小，任务与虚拟机的匹配度越高，任务得到的服务质量越高；当Costvm值越大，任务与虚拟机的匹配度越低，任务得到的服务质量越低；当Costvm=0时，任务与虚拟机匹配度最高，即完全匹配。

2 实验仿真与结果分析

2.1 实验仿真数据

云计算系统调度模型，物理环境不变条件下，调度系统性能优劣主要取决于资源映射和调度规则，是整个调度系统核心。该文实现了一种基于QoS简单约束的最小代价最大服务概率算法（Minimum cost and Maximum Probability of Service， MMPS）算法。

本文MMPS算法仿真实验在CloudSim上进行，根据任务执行成本、虚拟机负载量和任务分配带宽进行了实验对比，选取5个虚拟机、9个任务，实验环境涉及的相关参数见表1。

2.2 实验结果分析

为验证MMPS算法有效性和进一步增加实验的对比性，该文选择顺序分配策略，贪心策略和随机分配策略作为对比实验，全部任务总执行时间实验结果如表2所示。

MMPS算法的任务总执行时间最短，贪心策略算法任务总执行时间略长于MMPS算法，顺序分配算法的任务总执行时间最长。MMPS算法比贪心策略算法节省了约8.55%的时间，MMPS算法比顺序分配算法节省了约30.31%的时间。随机分配策略每一次执行结果都会有所不同，但都会比MMPS算法和贪心策略算法执行时间长。

全部任务执行时间分布图1所示，MMPS算法的0号任务与其他几种算法时间大致相同，1号任务花费的时间比其他的任务都多，2号任务少于顺序分配策略，从3号任务开始，执行时间都少于或者接近其他几种调度算法，该文的MMPS调度算法在执行时间上比其他三种算法更高效。endprint

2.3 算法时间复杂度分析

设系统中共有m台虚拟机和n个任务，小堆排序的时间复杂度为O（nlogn）；VM归一化的时间复杂度为O（m）；VM计算任务负载量的时间复杂度为O（mn）；任务计算代价的时间复杂度为O（mn）。

资源匹配过程最好情况是任务一次就匹配成功，时间复杂度为 O（1）；最坏情况下每个任务都需要匹配m次，n个任务共需要匹配m×n次，时间复杂度为O（mn）。因此，整个资源匹配过程最好情况下时间复杂度为O（l），最坏情况下时间复杂度为O（mn）。

3 结束语

云计算系统是一个特殊的超大规模集群系统，资源调度策略和负载均衡策略可作为影响云计算系统性能的重要因素之一。该文研究了云计算环境下基于QoS简单约束的资源调度策略，借鉴作业调度的基本思想，建立资源调度模型。再根据物理资源与QoS参数的映射关系，建立云计算环境下的资源分配模型，深入研究了云计算仿真平台CloudSim体系结构，对CloudSim中基础类：ExtendedExample2类和DatacenterBorker类等进行相应的扩展，重新对源代码进行编译，在CloudSim平台上实现了MMPS算法的仿真，实验结果表明MMPS算法效果较为显著，能较好地满足用户服务质量。

参考文献：

[1] 刘鹏.云计算 [J].2版.北京：电子工业出版社，2011.

[2] 陈全，邓倩妮.云计算及其关键技术[J].计算机应用，2009，29（9）：2562-2567.

[3] 秦勇，肖文俊，黄翰，等.一种基于QoS度量的Pareto并行路由寻优方法[J].计算机学报，2009，32（3）：463-472.

[4] 罗作民，张景，李军怀，等.网格计算及其关键技术综述[J].计算机工程与应用，2004，39（30）：18-22.

[5] 宋杰，李甜甜，闫振兴，等.一种云计算环境下的能效模型和度量方法[J].软件学报， 2012，23（2）：200-214.

[6] 雷炳翰，何军，何翔，等.基于QoS的网格负载调度算法[J].计算机工程，2009，35（24）：96-98.

[7] 宴婧.云环境下基于QoS约束的工作流任务调度算法研究与实现[D].重庆：重庆大学，2011.endprint

2.3 算法时间复杂度分析

设系统中共有m台虚拟机和n个任务，小堆排序的时间复杂度为O（nlogn）；VM归一化的时间复杂度为O（m）；VM计算任务负载量的时间复杂度为O（mn）；任务计算代价的时间复杂度为O（mn）。

资源匹配过程最好情况是任务一次就匹配成功，时间复杂度为 O（1）；最坏情况下每个任务都需要匹配m次，n个任务共需要匹配m×n次，时间复杂度为O（mn）。因此，整个资源匹配过程最好情况下时间复杂度为O（l），最坏情况下时间复杂度为O（mn）。

3 结束语

云计算系统是一个特殊的超大规模集群系统，资源调度策略和负载均衡策略可作为影响云计算系统性能的重要因素之一。该文研究了云计算环境下基于QoS简单约束的资源调度策略，借鉴作业调度的基本思想，建立资源调度模型。再根据物理资源与QoS参数的映射关系，建立云计算环境下的资源分配模型，深入研究了云计算仿真平台CloudSim体系结构，对CloudSim中基础类：ExtendedExample2类和DatacenterBorker类等进行相应的扩展，重新对源代码进行编译，在CloudSim平台上实现了MMPS算法的仿真，实验结果表明MMPS算法效果较为显著，能较好地满足用户服务质量。

参考文献：

[1] 刘鹏.云计算 [J].2版.北京：电子工业出版社，2011.

[2] 陈全，邓倩妮.云计算及其关键技术[J].计算机应用，2009，29（9）：2562-2567.

[3] 秦勇，肖文俊，黄翰，等.一种基于QoS度量的Pareto并行路由寻优方法[J].计算机学报，2009，32（3）：463-472.

[4] 罗作民，张景，李军怀，等.网格计算及其关键技术综述[J].计算机工程与应用，2004，39（30）：18-22.

[5] 宋杰，李甜甜，闫振兴，等.一种云计算环境下的能效模型和度量方法[J].软件学报， 2012，23（2）：200-214.

[6] 雷炳翰，何军，何翔，等.基于QoS的网格负载调度算法[J].计算机工程，2009，35（24）：96-98.

[7] 宴婧.云环境下基于QoS约束的工作流任务调度算法研究与实现[D].重庆：重庆大学，2011.endprint

2.3 算法时间复杂度分析

设系统中共有m台虚拟机和n个任务，小堆排序的时间复杂度为O（nlogn）；VM归一化的时间复杂度为O（m）；VM计算任务负载量的时间复杂度为O（mn）；任务计算代价的时间复杂度为O（mn）。

资源匹配过程最好情况是任务一次就匹配成功，时间复杂度为 O（1）；最坏情况下每个任务都需要匹配m次，n个任务共需要匹配m×n次，时间复杂度为O（mn）。因此，整个资源匹配过程最好情况下时间复杂度为O（l），最坏情况下时间复杂度为O（mn）。

3 结束语

云计算系统是一个特殊的超大规模集群系统，资源调度策略和负载均衡策略可作为影响云计算系统性能的重要因素之一。该文研究了云计算环境下基于QoS简单约束的资源调度策略，借鉴作业调度的基本思想，建立资源调度模型。再根据物理资源与QoS参数的映射关系，建立云计算环境下的资源分配模型，深入研究了云计算仿真平台CloudSim体系结构，对CloudSim中基础类：ExtendedExample2类和DatacenterBorker类等进行相应的扩展，重新对源代码进行编译，在CloudSim平台上实现了MMPS算法的仿真，实验结果表明MMPS算法效果较为显著，能较好地满足用户服务质量。

参考文献：

[1] 刘鹏.云计算 [J].2版.北京：电子工业出版社，2011.

[2] 陈全，邓倩妮.云计算及其关键技术[J].计算机应用，2009，29（9）：2562-2567.

[3] 秦勇，肖文俊，黄翰，等.一种基于QoS度量的Pareto并行路由寻优方法[J].计算机学报，2009，32（3）：463-472.

[4] 罗作民，张景，李军怀，等.网格计算及其关键技术综述[J].计算机工程与应用，2004，39（30）：18-22.

[5] 宋杰，李甜甜，闫振兴，等.一种云计算环境下的能效模型和度量方法[J].软件学报， 2012，23（2）：200-214.

[6] 雷炳翰，何军，何翔，等.基于QoS的网格负载调度算法[J].计算机工程，2009，35（24）：96-98.

[7] 宴婧.云环境下基于QoS约束的工作流任务调度算法研究与实现[D].重庆：重庆大学，2011.endprint