一种成本驱动的云计算任务调度策略

邓见光，赵跃龙，袁华强，刘 霖

(1.东莞理工学院工程技术研究院，广东东莞523808;2.华南理工大学计算机科学与工程学院，广东广州510006)

云计算技术是互联网迅速发展的必然结果.在云计算平台中，用户无需购买和部署IT基础设施，而只需按需租用各类硬件、软件、计算设备以及存储资源，并通过向云平台提交任务来实现计算任务与存储业务.在进行任务调度时，作为一种商业服务，云计算系统在满足用户QoS(quality of service)要求的同时，还应尽可能地最大化其服务收益.给定任务和计算资源集，云计算任务调度问题就是为了寻找一种调度策略，基于该策略，云平台将用户任务分别指派给不同的计算节点，以实现大量任务在计算资源之间的合理分配和高效执行.任务调度是一个NP完全问题，其不可能在多项式时间复杂度内求得全局最优解.目前，研究人员提出了多种方法来逼近其最优解，然而现有调度方法大多耗时过长且结果不可预测，很难应用于实际的云计算环境.遗传算法具有较好的全局搜索能力，可以快速遍历一个较大的搜索空间，并且能够避免陷入局部最优解，可以很好地应用于复杂的目标优化问题.

根据上述分析，从云服务提供方的角度出发，基于遗传算法，文中提出一种成本驱动的云计算任务调度策略.提出的方法充分考虑云服务的商业特性，在满足用户任务QoS要求的前提下，尽可能地最大化云环境单位计算开销的服务收益.

1 相关工作

近年来，任务调度问题吸引了大量研究人员参与其中，在提出的众多方法中，经典的Min-min［1］和Max-min［2］算法常被用来作为评价一个调度算法优劣的标准.

云计算基于虚拟化技术，将分布在不同位置的资源进行整合，形成统一的资源池，向广大用户提供各种计算或存储服务.云计算的服务器规模庞大，广大用户可按需购买任意规模的资源或服务，以处理各类计算密集型或数据密集型任务.根据不同的任务类型，目前有大量的调度方法被提出.对于计算密集型应用，文献［3］提出了一种高效的任务调度方法，该方法可并行处理分布于异构平台同时包含独立任务袋的多个应用.文献［4］提出了一种预算约束的调度器，对于QoS要求各异的任务，该调度器可分别为其分配相应性能指标的计算资源;相对于固定的任务预算，该调度器可以最小化总的任务完成时间.文献［5］提出了一种动态云环境下的工作流任务调度策略，该策略充分考虑了科学工作流的任务特征，并基于概率机制不断调整其调度定价模型以适应云计算环境的动态多变特性.考虑到在数据密集型应用中，数据存储之间往往相互关联，文献［6］开发了一个数据重用模型，并在此基础上提出了一个启发式的任务调度算法;文献［7］则通过同时考虑调度任务的数据需求和计算需求，提出了一种自适应的任务调度方案.前述两种方案均可以很好地应用于数据密集型的任务调度.

不仅如此，现有方法常常应用计算资源属性和调度任务的QoS参数来对任务的完成时间进行预测，以辅助调度决策.文献［8］基于统计分析的观点，通过对基准测试集和编译器进行分析，提出了一种任务完成时间的预测方法.文献［9］通过对一个时间序列内的历史数据进行统计建模，基于一个K近邻的方法来实现对任务完成时间的预测.文献［10］提出了一种多策略的协同预测模型，并引入一个预测精度保障的概念来对任务完成时间的预测精度进行定量评估.

云计算本质上是一种商业服务模型，其在满足广大用户任务调度QoS要求的同时，还应尽可能地增加其服务收益.因此，上述的调度策略虽能够满足用户调度的QoS要求，但并不太适应于云计算这一商业计算模式.文中基于云的商业特性，从云服务提供方的角度出发，提出一种成本驱动的云计算任务调度策略.

2 成本驱动的云计算任务调度策略

2.1 相关符号及约束条件

集合C={c1，c2，…，cn}表示云计算资源集，其中n表示计算节点数;集合T={t1，t2，…，tm}表示系统中待调度的任务集，m表示待调度的任务数.X是一个m×n的任务分配矩阵，若任务ti被分配给计算节点cj，则X中的元素xi，j=1，否则xi，j=0.文中假设一个任务只能被指派到一个计算节点上执行调度，且任务调度不能抢占执行.

Budgeti表示任务ti的预算，即云服务方在约定时间内完成ti的调度时所获得的收益;Deadlinei表示任务ti的调度时间底线，当云服务方在该底线之前完成ti的调度时，无需支付赔偿金，否则需向用户支付赔偿金;I-counti表示任务ti的指令数，即任务规模，其由预处理模块估算获得;T-finii表示任务ti的预期完成时间;I-costj表示计算节点cj执行单条指令的开销成本;D-costi表示任务ti单位时间的延迟成本，即云服务方超过时间底线Deadlinei后，每延迟一个时间单位需向用户支付的赔偿金额;L-line表示任务ti所能接受的最迟完成时间，在该时间点，云服务方需要向用户支付的赔偿金达到最大值.不失一般性，文中约定任务的调度完成时间超过L-line时，云服务方的收益为0.

执行调度时，用户向云平台提交调度请求.云服务提供方根据任务预算及其QoS要求来估算收益情况，以判断是否接受该任务.接受调度请求之后，如云服务方未能在用户要求的时间内完成调度，则需根据其延迟时间向用户支付赔偿金.

就用户而言，其任务的预期完成时间T-fini最迟不能超过L-line，否则不仅其QoS得不到满足，云服务方也得不到任何收益.另一方面，在满足调度任务QoS要求的条件下，假设任务ti被指派给计算节点cj，即xi，j=1，则节点cj调度任务ti的计算开销为

相对于上述开销，节点cj调度任务ti取得的服务收益为，其中为节点cj调度任务ti的延迟赔偿金，具体为

进一步地，整个云系统调度任务集T={t1，t2，…，tm}的总收益为总的计算开销为

在满足用户QoS要求的前提下，云计算应以尽可能小的成本获得尽可能多的收益.因此，提出的成本驱动的云计算任务调度策略应尽可能地最大化其单位计算开销的服务收益，即其求解目标为

很显然，上述求解目标是一个NP完全问题，其不可能在多项式时间复杂度内求得全局最优解.

2.2 成本驱动的云计算任务调度模型

成本驱动的云计算任务调度模型如图1所示.

图1 成本驱动的云计算任务调度模型

用户首先发出任务调度请求，预处理单元根据任务属性及其QoS要求对任务规模进行估算.调度器接收到调度请求之后，将任务属性信息、QoS参数以及从云资源管理器获取的计算资源信息等一并发送至任务调度模块.调度模块根据任务及计算资源信息建立调度目标，并基于遗传算法进行目标优化，最后将优化的调度方案返回至调度器.调度器在获得调度方案之后，在云计算资源层执行调度操作.调度结束后，由云计算资源层将任务调度结果返回至调度器.

3 基于遗传算法的目标求解

应用遗传算法，在多项式时间复杂度内对前述调度目标进行近似求解，其求解过程如图2所示.

图2 基于遗传算法的目标求解过程

3.1 初始化种群

首先确定遗传算法的种群规模N和迭代计算器Count，Count的初始值为0.为了应用遗传算法对提出的任务调度策略进行全局求解，需要将每一种可能的调度方案编码成染色体.例如，对于m=7，n=4的云计算环境，根据其任务分配矩阵X，可采用下述方法进行染色体编码:

在上述变换中，用00，01，10，11依次表示相应的任务被指派到计算节点c1，c2，c3，c4.将用二进制表示的任务分配矩阵按行展开即得到相应调度方案的染色体编码.根据指定的种群规模N，将相应数量随机生成的调度策略基于上述方法进行染色体编码，即得到初始种群P(0).

3.2 适应度函数

适应度函数用于评价染色体的好坏，其函数值越大，相应的染色体在遗传算法的进化迭代中越有利于被保留下来.文中遗传算法以云计算单位计算开销的服务收益作为其适应度函数，表示如下:

对于一条染色体，其适应度函数值越大，则它对应的调度方案的单位计算开销的服务收益越多.

3.3 遗传迭代操作

获得初始种群P(0)之后，应用交叉、变异、选择等遗传操作算子对P(0)中的染色体进行迭代进化操作，重复上述过程，直至种群进化到一个可接受的解.首先确定交叉概率pc和变异概率pm.

交叉:从当前种群P(g)中随机选取两个染色体，然后对选取的两个染色体的部分基因座以某种特定的方式进行交换，即实现染色体的交叉繁殖.其中，g表示种群的代数，对于初始种群，g=0;每条染色体均以概率pc的几率被选取参与交叉操作.经交叉操作生成的新染色体集合记作Scrossover.

变异:以变异概率pm从当前种群P(g)中随机选取一定数量的染色体，对选取染色体的个别基因座以某种特定方式进行变异，即生成新的染色体.经变异操作生成的新染色体集合记作Smutation.

选择:对经交叉和变异操作生成的新染色体集合以及当前种群进行合并，得到集合Scrossover∪Smutation∪P(g)，对于该集合中的元素，分别计算其适应度函数值，并选择适应度函数值最大的前N个染色体作为下一代种群保留下来，记作P(g+1)，并令Count=Count+1.

3.4 算法终止

经过上述迭代操作，可得到新一代种群P(g+1)，接下来根据调度策略的求解目标，即公式(3)来对新一代种群进行评估.若算法迭代次数超过预先设置的最大迭代次数iteration，或者在连续的多代种群中，适应性最好的染色体的适应度函数值没有改进，则终止条件得到满足，算法终止;否则令g=g+1，并继续上述遗传迭代操作，直至算法的终止条件得到满足.

4 试验测试与分析

为验证成本驱动的云计算任务调度策略的性能，作者对该策略进行了模拟测试，同时将测试结果与传统Min-min算法［1］以及改进的QoS约束的Minmin 算法［11］分别进行比较.

4.1 试验环境与参数设置

基于Cloudsim［12］对提出的任务调度策略、Minmin算法以及改进的QoS约束的Min-min算法分别进行模拟测试.整个云计算仿真环境共有10个计算节点，各节点拥有的处理单元数量、处理单元的计算效率以及单位时间的计算成本如表1所示.

表1 云计算环境计算资源列表

请求调度的任务属性包括I-count，Budget，Deadline，L-line，D-cost.试验共用到 10 组一共 100个任务，各组任务的数量及参数设置见表2.

表2 请求调度的任务列表

在应用遗传算法对提出的调度目标进行优化求解时，设定初始种群规模为100，交叉概率为0.7，变异概率为0.15，最大迭代次数为300，连续3次迭代种群的最小进化速率为0.3%.

4.2 测试结果与分析

基于上述试验环境及参数设置，依次对成本驱动的云计算任务调度策略、传统的Min-min算法以及改进的QoS约束的Min-min算法分别进行测试，并对测试结果进行比较分析.在每组测试中，参与调度的用户任务数量依次为10，20，…，100，它们均从表2所示的任务列表中随机选取，每组测试结果均通过多次试验并取平均值获得.

任务的调度完成时间与参与调度的任务数量之间的关系如图3所示.

图3 不同任务数量下的调度完成时间

由图3可见，随着调度任务数量的增加，3种方法的调度完成时间均呈上升趋势.相比之下，QoS约束的Min-min算法优于传统的Min-min，这是由于前者的调度决策兼顾了任务的Deadline约束.进一步地，成本驱动的调度方法明显优于前两类方法，这是由于成本驱动的方法将计算开销作为调度决策的关键因素，其以最大化单位计算开销的服务收益作为调度目标，使得其总是从全局出发，尽可能地将全部任务均指派给最为合适的计算资源;另一方面，Min-min及QoS约束的Min-min算法总是趋向于将任务指派给具有最小最早完成时间的计算资源，导致负载不均，增大了部分任务的等待时间，最终延迟了任务的调度完成时间.

随着参与调度的任务数量的增加，调度完成时间超过其Deadline的任务数占全部任务数比例的变化趋势如图4所示.

图4 不同任务数量下调度完成时间超越Deadline的比例

由图4可见，成本驱动的调度方法优于另外两种方法.如前所述，成本驱动的方法总是从全局出发，尽可能地将任务指派给最为合适的计算资源;而Min-min及其改进算法容易导致负载不均，增大了部分任务的等待时间，从而使得调度的完成时间超过其Deadline的任务数量增多.改进的QoS约束的Min-min算法由于更多地考虑了调度任务的Deadline约束，也使得其调度完成时间超过Deadline的任务比例明显低于传统的Min-min算法.就3种算法而言，由于任务之间的资源竞争，调度完成时间超过Deadline的任务比例随着参与调度的任务数量的增加均呈上升趋势.

在不同数量的调度任务下，3种算法单位计算开销的服务收益情况如图5所示.

图5 不同任务数量下单位计算开销的服务收益

由图5可见，成本驱动的方法优于另外两种方法，这是因为成本驱动的方法以最大化单位计算开销的服务收益为求解目标，负载较为均衡，调度更为合理.Min-min算法容易导致系统负载不均，增大了部分任务的等待时间，最终导致系统单位计算开销的服务收益受损.相比之下，QoS约束的Min-min算法在调度决策时兼顾了任务的Deadline要求，这使得其单位计算开销的服务收益情况要优于传统Min-min算法.随着参与调度的任务数量增多，任务之间的资源竞争加剧，3种算法单位计算开销的服务收益均呈下降趋势.

5 结论

从云服务提供方的角度出发，提出了一种成本驱动的云计算任务调度策略，并在Cloudsim模拟器上做了一系列仿真测试，结论如下:

1)提出的策略在任务完成时间上优于传统的Min-min算法和改进的QoS约束的Min-min算法.

2)相比于另外两种算法，提出的调度策略调度完成时间超越截止时间底线的任务比例总体上更低，这一优势在任务数量较多时更为明显.

3)提出的调度策略系统负载更为均衡，其单位计算开销的服务收益明显优于另外两种方法.

References)

［1］Braun T D，Siegel H J，Beck N，et al.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems［J］.Journal of Parallel and Distributed Computing，2001，61(6):810-837.

［2］Bhoi U，Ramanuj P N.Enhanced Max-min task scheduling algorithm in cloud computing［J］.International Journal of Application or Innovation in Engineering and Management，2013，2(4):259-264.

［3］Benoit A，Marchal L，Pineau J F，et al.Scheduling concurrent bag-of-tasks applications on heterogeneous platforms［J］.IEEE Transactions on Computers，2010，59(2):202-217.

［4］Oprescu A M，Kielmann T.Bag-of-tasks scheduling under budget constraints［C］∥Proceedings of2nd IEEE International Conference on Cloud Computing Technology and Science.Indianapolis，USA:IEEE Computer Society，2010:351-359.

［5］Zhou Amelie Chi，He Bingsheng，Liu Cheng.Probabilistic scheduling of scientific workflows in dynamic cloud environments［R］.Singapore:Nanyang Technological University，2013.

［6］Santos-Neto E，Cirne W，Brasileiro F，et al.Exploiting replication and data reuse to efficiently schedule data-intensive applications on grids［C］∥Proceedings of the10th International Workshop on Job Scheduling Strategies for Parallel Processing.New York:Springer Verlag，2005:210-232.

［7］Liu Wantao，Kettimuthu R，Li Bo，et al.An adaptive strategy for scheduling data-intensive applications in grid environments［C］∥Proceedings of2010 17th International Conference on Telecommunications.Doha，Qatar:IEEE Computer Society，2010:642-649.

［8］Kiran M，Hashim A-H A，Kuan L M，et al.Execution time prediction of imperative paradigm tasks for grid scheduling optimization［J］.International Journal of Computer Science and Network Security，2009，9(2):155-163.

［9］Phinjaroenphan P，Bevinakoppa S，Zeephongsekul P.A method for estimating the execution time of a parallel task on a grid node［J］.Lecture Notes in Computer Science，2005，3470:226-236.

［10］Tao Ming，Dong Shoubin，Zhang Liping.A multi-strategy collaborative prediction model for the runtime of online tasks in computing cluster/grid［J］.Cluster Computing，2011，14(2):199-210.

［11］Liu Juefu，Li Gang.An improved MIN-MIN grid tasks scheduling algorithm based on Qos constraints［C］∥Proceeding of2010International Conference on Optics，Photonics and Energy Engineering. Wuhan， China:IEEE Computer Society，2010:281-283.

［12］Calheiros R N，Ranjan R，de Rose C A F，et al.CloudSim:a novel framework for modeling and simulation of cloud computing infrastructures and services［R］.Australia:Grid Computing and Distributed Systems Laboratory，University of Melbourne，2009.