张以利，杨万扣

0 引言

云计算是由分布式计算、并行计算、网格计算、虚拟技术等技术综发展起来的新型计算模型。云环境下不乏许多经典调度算法。R.Armstrong提出将长度最小的任务调度到最优资源上的调度算法，可使任务完成数最大化，但算法未考虑任务重要程度及任务预算等市场效益约束问题。R.Buyya提出在用户任务预算和期望完成时间约束下，优先调度在资源上执行时间较短的任务，算法充分考虑了任务预算等市场效益问题，但在任务预算不足或期望完成时间较短，云服务方无法保障任务全部完成的情况下，任务完成数会较小[1]。

针对用户任务预算不足或期望完成时间较短，云服务方无法保障任务全部完成的情况下，提出基于任务分类和线性规划优化模型调度算法（Scheduling Algorithm based on Task Classifying and Linear Pogramming Model in a Cloud Environment,SCLCE），使任务完成数最大化，同时考虑到任务的重要程度。SCLCE算法根据任务长短及重要性进行分类，然后建立任务计算资源关系矩阵及三个相关约束条件，以任务完成数最大化为目标函数，搭建线性规划优化模型，同时给出算法实现[2]。

1 基于任务分类和LPM优化模型的调度算法

云计算环境中，设 n个任务构成集合 T=（T1,T2,…Ti…,Tn）(i∈n)；设 p 台机器构成集合 M=（M1, M2,…M i…,M p）(i∈p)，这些机器提供m个计算资源，构成计算资源集合 R=（R1,R2,…Ri…,Rm）(i∈m)[3]。

1.1 相关概念定义及任务分类

定义1 计算资源

计算资源定义为一个三元组[4]，公式（1）计算资源的三个属性分别为资源号属性、资源计算性能属性、资源计算价格属性。

定义2 用户任务

用户任务定义为一个五元组，公式（2）

用户任务的五个属性分别为任务号属性、任务类型属性、任务长度属性、任务预算属性和用户任务期望完成时间属性。

用户任务预算属性budgT，为该任务按预期完成后所付给资源提供方的价格数[5],deadT为调度在某资源上的任务执行完成时间不得超过的时间值属性。

定义3 TH任务集合 TL任务集合

typeT为任务类型属性，分为High和Low两种类型。High类型任务为比较重要的用户任务或者是长度较短的任务，要求最迟要在时间deadT之前完成，这些任务构成TH任务集合,即 TH=(TH1,TH2,…THi。。。,THn) (i∈n)。而 Low类型任务为不是太重要的用户任务，用户期望完成时间也不是太高，可以延迟完成该任务，这些任务构成TL任务集合,即 TL=(TL1,TL2,…TLi…,TLm) (i∈m)。

SCLCE算法中，根据type属性的不同，将所有任务分为两个类型的集合TH和TL。将集合TH中任务调度到优秀的资源上，确保High类型任务优先完成，得到较高的用户任务完成数[6]。

1.2 线性规划优化模型调度策略

如果由于用户任务预算不足或者任务期望完成时间较短，TH集合任务未全部完成，则SCLCE算法将该集合中未完成的任务类型typeT由High更改为Low，即将TH集合中没有完成的任务加入到TL集合中。

在对TL集合任务进行调度时，采用基于LPM优化模型的调度算法，即通过一个线性规划数学模型优化策略，在满足三个约束条件下，以执行任务完成数最大化为目标，返回任务完成数及任务与资源的映射关系，从而得到资源分配最优解[7]

定义4 任务计算资源调度关系矩阵Anm

Anm定义为一个n´m的矩阵，公式（3）

其中，矩阵元素aij意义为：

该矩阵的元素值，反映任务Ti在计算资源Rj上的调度分配情况。

每个用户任务最多只能调度到一个计算资源上，而每个计算资源可以根据需要调度多个任务在其中执行[8]，于是，根据式3可得到下面的约束条件，公式（4）

执行TL类型的任务时，设第j个计算资源执行TH类型任务共花费时间timeRj, 任务期望完成时间deadT，全部计算资源在执行TH类型任务所获总成本为costSum，两种类型任务的总预算为 budgSum，则剩下执行时间为 deadT-timeRj, 剩下可用预算为budgSum-costSum，于是，根据式3和式4，可得到下面的两个约束条件[9]，公式（5）、（6）

其中，lengTi为第i任务Ti的长度，perfRj为第j个计算资源 Rj的计算性能，pricRj为第 j个计算资源 Rj的计算价格，Ti为第i个任务。式5是任务期望完成时间的约束条件，式6是用户任务预算约束条件。

在SCLCE调度算法中，完成任务数最大值为：

式7是任务完成数的最大值，是SCLCE算法调度所期望的目标，即数学中的目标函数，式3、式5和式6，分别是用户任务在资源上调度的约束条件、用户任务期望完成时间的约束条件和用户任务预算的约束条件。由此，线性规划数学模型(LPM)建立如下：

约束条件：

LPM 优化模型是运筹学中解决有限资源最佳分配问题的数学模型，即如何对有限资源作出最佳方式的调配和最有效的利用，以使最充分地发挥资源的效能去获取最佳的经济效益[10]。LPM 求解，即在约束条件下使目标最优的一组变量的取值。

求解该数学模型，即在满足三个约束条件下使得执行任务完成数最大化，返回任务完成数及任务与计算资源的映射情况，从而得到计算资源分配最优解。LMP优化模型调度算法策略，见算法1。

算法1 LPM优化模型调度算法

1.3 基于任务分类和线性规划模型的调度算法

在云计算环境中，设有 n个计算资源的集合 R=（R1,R2,…Ri…,Rn）(i∈n)，m个任务的集合T=（T1,T2,…Ti…,Tm）(i∈m)。针对用户任务预算不足或者用户任务期望完成时间较短，资源提供方无法保障全部任务的顺利完成，SCLCE算法采用基于任务分类和LPM优化模型的调度算法，确保重要类型任务优先完成并最大化用户任务的完成数[11]。

假设任务在执行过程中是不可抢占的，并且对于任务类型typeT相同的任务，执行的优先级顺序相同，则基于任务分类和LPM优化模型的调度策略，如算法2所示。

算法2 基于任务分类和LPM优化模型调度算法

2.仿真实验及结果分析

仿真实验：采用R.Buyya的CloudSim模拟平台，这是一个使用云计算环境来模拟经济模型的实验平台。本实验使用5台机器，M=（M1, M2, M3,M4,M5），每台机器提供20个计算资源，这20个计算资源的计算性能、价格都相同，共有 100 个计算资源，R=（R1,R2,…Ri…,R100）(i∈100)，计算性能参数perfR用机器每秒执行指令数描述，预算及价格参数均用相对值描述。实验设立100个任务，T=(T1,T2,…Ti。。。,Tn) (i∈100)[12]。

对比实验：采用同 R.Buyya提出的经典调度算法作对比，记录两个算法实验数据并图示，通过对比分析 SCLCE算法的优劣。

共设计两组实验如下：

第一组实验：验证基于LPM优化模型的调度算法，实验数据记录如图1所示。任务不分类，即只有HL任务。以任务预算和期望完成时间参数组合分 8个组且各组的组合参数数据逐渐增加：G1（20000,1000），G2（40000,2000），G3（60000,3000），G4（80000,4000），G5（100000,5000），G6（120000,6000），G7（140000,7000），G8（160000,8000）。

任务预算和期望完成时间参数组合与任务完成数的关系，如图1所示：

图1 基于LPM优化模型的调度算法验证模拟实验

实验分析：由图1可看出，SCLCE算法的数据线总是在经典算法的上方。这是因为前者采用LPM优化模型调度策略，即在任务预算不足或期望完成时间较短而云服务方无法保障任务全部完成条件下，以任务完成数最大化为目标函数，所以会得到最大化的任务完成数；而后者虽然充分考虑了任务预算等市场效益问题，但在同样约束条件下，任务完成数会较小。

第二组实验：验证基于任务分类的SCLCE算法，实验数据记录如图2和图3所示。用户任务根据typeT类型属性的High和Low分为TH集合和TL集合，不断变化的TH集合任务数为横轴， TH任务完成数或总任务完成数为纵轴。

TH集合中的任务数随TH任务完成数的变化情况，如图2所示。

实验分析：由图2所示：

图2 TH集合任务数随TH任务完成数的变化情况

可看出，SCLCE算法数据线总在经典算法的上方，这是因为前者采用任务分类并优先考虑的策略，根据任务长短及重要程度分成TH和TL集合，对TH集合中的任务优先调度，而后者则对任务重要性未做充分考虑。

TH集合中的任务数随总任务完成数的变化情况，如图3所示：

图3 TH集合任务数随总任务完成数的变化情况

实验分析：由图3可看出，SCLCE算法数据线在50之前始终处于经典算法数据线上方，而在50之后则明显放缓甚至有的数据点还在经典算法线的下方。这是因为，SCLCE算法采用任务分类且优先调度TH任务的策略，在50之后，随着TH任务占有率的快速增加，TH任务会占用大量优质资源，严重影响用户任务全局优化。所以，SCLCE算法的任务分类时，TH任务数在整个任务中的百分数要适中，一般不要超过50%。

3.结束语

云环境下基于任务分类和线性规划优化模型调度算法，是对R.Armstrong和R.Buyya提出的经典算法的有效改进。该算法充分考虑到用户任务预算不足或期望完成时间较短，资源提供方未能全部完成的情况下，如何最大化用户任务完成数的问题。同时还充分考虑到了用户任务的重要程度及用户任务预算等市场效益约束问题。

[1]刘晓茜.云计算数据中心结构及其调度机制研究[D].合肥:中国科学技术大学,2011.

[2]师雪霖，徐恪.云虚拟机资源分配的效用最大化模型[J].计算机学报, 2013 Vol.36 (02): 252—262.

[3]祝家钰，肖丹，王飞.云计算下负载均衡的多维QoS约束任务调度机制 [J].计算机工程与应用, 2012 Vol.38 (14): 38-40.

[4]朱锦雷, 刘俊鹏.面向云计算的虚拟进程调度算法[J].计算机工程, 2012 Vol.38 (14): 38-40.

[5]左利云, 曹志波.云计算中调度问题研究综述 [J].计算机应用研究, 2012,29(11):4023-4027.

[6]张春艳,刘清林,孟珂.基于蚁群优化算法的云计算任务分配[J].计算机应用, 2012,32(05): 1418-1420.

[7]景波,刘莹,黄兵.基于遗传算法的Job Shop调度问题研究[J].计算应用研究, 2013,30(3):688-691.

[8]白露 晏立.多处理器固定优先级算法的可调度性分析[J].计算机应用,2012 Vol.32 (03): 603-605.

[9]任丰玲, 于炯, 杨兴耀.基于最小化传输和完成时间的多DAG调度[J].计算机工程, 2012 Vol.38 (23):287-290.

[10]邹伟明,于炯,英昌甜,胡丹.基于动态等待时间阈值的延迟调度算法[J].计算机应用研究,2012,29(11):4073-4078.

[11]胡志刚, 刘艳.云环境下基于组合双向拍卖的动态资源定价[J].计算机工程, 2012 Vol.38 (08): 19-21.

[12]王鹏 张磊 任超 郭又铭.云计算系统相空间分析模型及仿真研究[J].计算机学报,2013，Vol.36 (02): 286—296.