面向云工作流的两阶段资源调度方法*

王岩 汪晋宽 韩英华

(1. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819; 2. 东北大学秦皇岛分校 控制工程学院, 河北 秦皇岛 066004)

面向云工作流的两阶段资源调度方法*

王岩1汪晋宽1韩英华2

(1. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819; 2. 东北大学秦皇岛分校 控制工程学院, 河北 秦皇岛 066004)

为提高云计算系统的资源利用率,优化系统性能,同时兼顾用户的服务质量(QoS)需求约束,文中结合云计算和工作流建立了云工作流系统,给出了具有两个调度阶段的系统资源调度模型.在第1阶段中,考虑了QoS的时间及价格约束、工作流内各个任务之间的依赖关系以及各个任务所产生的中间数据的处理,提出了改进的粒子群优化(MPSO)算法,并利用Pareto获得最优解,以提高调度效率;在第2阶段中,考虑了资源在主机上的分配情况,提出了具有负载感知的调度策略,根据系统的负载情况进行资源调度,以提高系统的资源利用率.实验结果表明:在云工作流系统的资源优化调度中,与经典的异构最早完成时间算法、单目标优化的遗传算法相比,MPSO算法的任务执行速度更快、资源利用率更高,能满足用户的QoS需求;具有负载感知的调度策略能更有效地根据负载情况进行调度,提高任务执行的效率和资源利用率.

云计算;工作流;粒子群算法;负载感知

随着云计算技术的不断发展,分布式工作流系统逐步发展到云工作流系统.云工作流系统充分结合了云计算和工作流的优点,克服了分布式工作流系统在资源管理和作业调度方面的缺陷.

实例密集型工作流[1-3]应用的特点是工作流系统中存在大量的实例,虽然实例本身较简单,但数量巨大,因此对调度算法要求较高,如何合理调度资源并提高服务质量(QoS)是系统调度策略的衡量指标.Liu等[4]提出了一种针对实例密集型应用的、使得系统吞吐量最大化的调度策略,该策略在实例层的调度算法提高了任务调度的系统吞吐量;在任务层的调度算法通过扩展等待时间,减少了资源调度所需时间,提高了资源利用率,但仅考虑扩展了极小(Min-Min)算法,会因迭代计算少、非迭代计算的时间收敛性较差而导致负载不均衡的情况发生.Javadi等[5]提出了一种适用于实例密集型应用的工作流调度算法,该算法首先对工作流实例进行分类,将用户指定的最后期限分配到各个任务中,在调度执行时动态地调整后续子任务的调度时间,进而优化任务总的执行时间.该算法能够在一定程度上减少资源竞争,提高资源利用率,但算法本身没有考虑子任务的执行时间.考虑任务的优先执行顺序,Jrad等[6]针对实例密集型工作流调度问题提出了基于预演算的调度算法,能够在调度前根据任务的优先级排序,按照优先级从高到低的顺序提供空闲的资源执行.以上研究均是针对实例密集型工作流而提出的不同调度策略,但云计算环境下的工作流作为一项服务,关键问题是如何满足用户的QoS需求,提供高水平的QoS服务[7-10].

QoS主要包括时间、费用、可靠性、安全性等因素.人们针对用户QoS保障提出了动态地为用户提供资源，并采用服务资源迁移的方法进行资源管理[11-12].Buyya等[13]提出的最后期限分配算法根据不同的任务分类,将用户指定的QoS限制进行划分并分配给流程任务,然后进行分类调度,但此算法是面向单实例任务的调度,不适合实例密集型任务的调度;文献[14-15]提出的资源混合调度算法修正了单一调度算法的问题,更好地平衡了云计算环境中用户任务对性能和价格的约束,但其将运行时间作为调度评价的标准,对于另一个用户关心的费用标准未予以考虑.

云计算中具有大量的工作流任务,如果没有整体调度策略来保障,将会严重影响整个系统的性能,导致任务的QoS冲突.同时,针对云计算的面向市场机制的服务特征,云计算环境中的工作流系统应当根据当前的资源分配情况、系统负载情况进行流程处理,以提高资源利用率.

因此,文中针对实例密集型工作流的任务调度,基于QoS性能优化,考虑了子任务的执行顺序,建立了符合任务特点的预调度模型,提出了具有两个调度阶段的系统资源调度模型.首先考虑基于QoS性能优化的工作流预调度,提出了改进的粒子群优化(MPSO)算法,从整体角度对云工作流系统的执行性能进行调度优化;然后考虑系统中的负载,提出了具有负载感知的任务调度策略,从局部角度对云工作流系统的性能进行优化.

1 云工作流系统的第1阶段调度

图1给出了一个工作流的例子.图中的di(i=1,2,…,5)表示数据集,rij(i=1,2,…,5;j=2,3,4,5)表示任务节点之间任务数据的关联关系.

图1 工作流示例图

定理1 设a1、a2是工作流中两个具有相同深度的任务,并且a2晚于a1执行,当且仅当a2的执行时间大于a1的执行时间时,a2才有意义.

定理1的证明见文献[16].由此得出如下推论.

推论1 在任务等待执行时,若具有相同深度的任务在执行时出现死锁,则其等待时间不能小于同深度任务的执行时间,以保证整个工作流的执行.

对于一个给定的云工作流应用,每个任务的执行都是非抢占的.每个应用任务ai都需要在一个云节点pj上执行,云节点集合为P={p1,p2,…,pj,…,pm},其执行时间表示为tij,该时间与任务的大小及节点的计算速度相关,tij表示任务ai的数据到达云节点pj的时间,即任务ai的父任务产生并发送到任务ai的所有数据的时间之和.

定义3 任务的平均执行时间为

(1)

定义4 任务的平均通信量为

(2)

(3)

1.1 云工作流模型

在云工作流系统中,调度问题的关键在于运用合理的调度策略,使得服务时间、服务费用最少.因此,文中提出的云工作流的任务调度模型由资源及应用中心、监控中心、处理器、调度器组成,如图2所示.

资源及应用中心主要管理云计算环境下的资源和服务;监控中心负责对系统的负载情况进行监控;处理器负责对任务进行预调度,预调度根据用户QoS约束,采用合理的调度算法对任务和资源之间的关系进行优化,为调度预留资源;调度器感知资源当前的负载情况,预计任务在当前调度中的耗费,保证任务在最佳的时机被调度执行.云工作流系统在第1阶段的调度步骤如下:

(1)根据工作流定义搜索资源;

(2)将用户的QoS目标要求分配到任务中;

(3)选择最优调度算法;

(4)将工作流任务调度到调度器准备执行.

图2 云工作流系统任务调度模型

调度的完成时间表示为用户提交一个工作流应用的开始时间到获得运算结果的时间间隔,即

(4)

调度的完成时间包括整个工作流的执行时间、网络传输时间,而执行时间与所使用的调度策略、系统负载情况和性能相关,网络传输时间则取决于系统中的网络时延和任务的数据大小.

一个云工作流应用的价格表示为

Ctotal=Cdeal+Ctr

(5)

若两个任务ai、aj之间有数据依赖性,则这两者之间的传输价格计入总价格中,对于在同一云节点上执行的任务,其间的传输价格忽略不计.

(6)

调度策略在执行任务前,根据任务的优先级提供一个保持任务之间优先级约束的线性顺序.工作流调度问题就是构建任务到云节点的二元组Q,该二元组由时间、价格构成,表示为Q=[ttotal,Ctotal],则相应的优化问题表示为Q′=[minttotal,minCtotal].

1.2Pareto优化

文中引入Pareto多目标进化方法,通过求得变量可行域,再根据不同的约束条件获得调度策略的最优解.一般根据云工作流调度中两个相互影响的调度目标(完成时间和价格)的最小化进行求解.求解策略倾向于尽最大程度对两个参数进行优化,符合该标准的求解策略组成的集合为Pareto最优解集合.

在MPSO算法中,根据优化目标而确定的优化原则如下:

(1)工作流调度中的变量为离散型,故在定义粒子的位置和速度时,要保证其特征,并且要保持算法搜索的趋优性,即进行映射关系的解码,求得该映射的时间效用和价格效用值.

(2)在求解优化解的过程中,要求具有满足不同目标的Pareto最优解集.每次更新微粒,必须保持上一次寻优中搜索到的是比较好的分配方案,这样才能使得算法收敛到全局最优解.因此,文中参考了遗传算法中染色体的交叉和变异特性,在每次更新分配方案时,与当前搜索到的个体最优映射和全局最优映射进行交叉、变异,这样就能保存目前搜索到的较优分配,使得算法朝更优的方向运行.

1.3MPSO算法

粒子群优化算法是一种随机全局优化算法,通常能够得到较优的结果,但随着问题规模的增加,计算量和资源使用量迅速增加.因此,文中提出的MPSO算法从以下几个方面进行改进:重新定义经典PSO算法中的粒子速度、位置的更新,并在利用算法进行问题优化求解过程引入了Pareto方法.

定义7MPSO算法中粒子i的位置L=[ai,pj],表示任务ai在云节点pj上.

定义8MPSO算法中粒子i的速度vi=[w(a),a],权值w(a)表示任务分配的可能概率.

定义9 粒子i的速度、位置更新公式如下:

(7)

(8)

在每一次迭代过程中,粒子会通过追踪以上两个位置来更新自己,并且根据式(7)、(8)更新速度和位置.

具有目标约束的调度策略中时间目标函数、价格目标函数表示如下:

objt(Q)=ttotal(Q)

(9)

objC(Q)=Ctotal(Q)

(10)

由此,将MPSO优化算法中的适应度函数表示为

F(Q)=wTttotal(Q)+wCCtotal(Q)

(11)

式中,wT、wC分别为任务对于时间、价格的期望权值.

对于求解具有目标约束的粒子群优化算法,在尽可能找到被其他解所支配的最优解的前提下,MPSO算法对Pareto最优解集中的解进行比较,但为了防止陷入局部最优而影响全局求解的情况,一般随机选择最优解,以加大粒子的全局搜索能力.MPSO算法优化求解步骤如下:

(1)随机生成一个初始种群,对种群中的粒子设置初始速度,检验各粒子是否满足约束条件,若不满足则对其重新初始化.

(2)计算该种群每一个个体粒子的多目标适应度并检查其Pareto占优情况,将非劣解粒子存储于Pareto解集存储区f中. f中至少需要有两个粒子,若不足则随机产生.

(3)计算粒子群中各个体粒子的每个目标适应度,并以矢量形式存储.

(4)更新粒子群中个体粒子的速度和位置,从当前Pareto解集中随机选取一个值作为整个种群的最优解.如果更新后的粒子不满足约束条件,则删除该粒子后重新随机产生.

(5)检查粒子群中每一个粒子的Pareto占优情况,若某个占优粒子是非劣解,则将该粒子存入f中作为当前获得粒子的一个Pareto解.

(6)如果f中某个粒子受控于新存入的粒子,则从f中删除该粒子.

(7)若未达到最大迭代次数,则返回步骤(3)继续搜索,否则输出满足约束要求的映射方案,赋给调度模型.

MPSO算法描述如下.

输入:各个任务队列

输出:调度策略

CalculatePriority();∥计算任务优先级

SortByPriority();∥任务优先级排列

Fori= 1ToNum∥Num为粒子的数目

InitializeParticle();

∥初始化粒子,即将任务映射到云节点

InitializeVelocity();∥初始化粒子速度

Lbest[i];∥初始化粒子的个体极值

EndFor

CalculateObjectValue();

∥计算粒子的目标函数值

AddPareto();

Fort=lToIterationNum

Fori=lToSNum

CalculateVelocity();∥更新粒子速度

CalculatePosition();∥更新粒子位置

CalculateObjectValue();

∥计算粒子目标函数值

CalculateFitness(S[i]*);

∥通过适应度函数计算粒子的当前适应度值

IfS[i]*BetterThenLbest[i]

UpdateLbest[i];

EndIf

AddPareto();

EndFor

FndFor

ReturnPareto();∥返回调度策略集合

1.4MPSO算法复杂度分析

对于包含n个任务的工作流在m个云计算实例资源上运行的工作流调度问题,其算法的复杂度因任务之间的相互关联情况不同而不同:

(1)对于包含n个串行任务的工作流在m个云计算实例资源上运行的云工作流调度问题,则有分配矩阵n·m·T,其算法复杂度为O(nmT);若任务数量增加,云节点保持不变,则算法的复杂度为O(n).

(2)对于动态任务尤其是价格动态变化的调度中,若任务均为并行任务,则算法复杂度为O(mn);若任务数量增加,其中单个任务的执行复杂度为O(m),云节点保持不变,则算法的复杂度为O(2n).

(3)对于应用了优化搜索算法的云工作流调度系统,n个任务的工作流在m个云计算实例资源上运行时,任务执行的复杂度为O(m),进行最优解搜索的复杂度为O(m2q),其中q为搜索的价格复杂度,则一个任务完整执行的复杂度为O(m)+O(m2q),整个工作流的复杂度为n(O(m)+O(m2q)).若工作流中任务数不断增加,云节点保持不变,价格为常数,则算法的复杂度为O(n).

2 云工作流系统的第2阶段调度

在云计算系统任务执行的密集期,大量任务使用一个服务资源,这样会严重影响系统的整体性能,导致冲突发生.因此在第2阶段,文中采用延迟调度策略,根据系统中机器的负载情况选择合适的时机将应用任务调度到机器上执行.

云工作流系统在第2阶段的调度步骤如下:

(1)通过监控中心获得系统的负载信息;

(2)计算调度所消耗的通信量;

(3)按照调度消耗的通信量确定调度时机;

(4)继续监控任务调度,并处理冲突.

(12)

定义11 设A中下一个任务的开始时间间隔Δtstart为

(13)

(14)

第2阶段调度考虑了系统负载参数,因此在第1阶段调度的基础上,文中建立如下的负载模型:

设op为CPU负载率,om为内存负载率,则系统资源负载率o为

o=opom

(15)

相应地,任务a发出请求等待时的资源负载率为owait=opwaitomwait,任务a开始执行时的资源负载率为ostart=opstartomstart.

此负载模型作为第2阶段调度机制的参数模型,为整个系统的第2阶段调度提供调度算法的参数选择标准.

根据以上定义,第2阶段调度算法描述如下.

输入:任务列表

输出:任务调度完成列表

SearchTask();∥搜索工作流中有请求的任务

SearchResource();

∥搜索处于预备状态的服务资源

CalculateΔtA;

If ΔtA≥0

Wait for delay;∥等待延迟

Else

ExecuteSchedulingPolicy;

AllocateResource;∥执行调度策略,分配资源

End If

3 仿真实验与结果分析

整个实验系统共有10台服务器,服务器设置为Pentium(R)Dual-Core E5300 2.60 GHz、2.0 GB RAM, Windows 7;系统提供4～15个资源节点,每个节点配置为2.0 GB内存及1 TB硬盘空间,另配置空载机器,仅运行操作系统等必要软件;由于目前数据中心局域网所使用的交换机和路由器基本上能够实现传输速率不受影响,因此假设传输速率为1 Gb/s.利用CloudSim进行仿真实验,并对此开源工具进行了修改:创建工作流生成器,可以生成一系列具有依赖关系的任务;将原工具中的数据中心分代理分为任务调度器和工作流执行引擎两个部分.调度器根据数据中心信息和任务信息制定调度方案,工作流执行引擎根据调度方案将任务提交到数据中心.

首先,CloudSim中的工作流生成器生成工作流,并将工作流提交给任务调度器,任务调度器通过查询数据中心信息生成一个调度方案,并将调度方案提供给工作流引擎,工作流引擎按照提供的调度方案申请虚拟机并将工作流的子任务提交给数据中心.

工作流定义中所设定流程任务数为30,在第1阶段调度中,不失一般性,粒子群操作中的选择概率分别设为40%和60%,以综合考虑小于、大于对应种群选择折中即50%时的变化情况,去除折中时的选择无关性.

3.1 优化调度结果分析

文中采用经典的HEFT算法、只针对单一目标优化的局部优化遗传算法(GA)与文中改进的MPSO算法进行对比.HEFT算法没有进行优化,而GA算法实现局部最优调度,MPSO则通过改进适应度函数实现全局随机优化.

表1为HEFT算法、遗传算法、MPSO算法(种群选择概率分别为40%和60%)的工作流任务执行时间情况,其中任务执行时间为整个工作流的分任务执行时间,整个表的数据表示工作流在一个数据库的不同节点执行完毕的总时间.

由表中可知,虽然在算法的复杂程度上,MPSO算法比HEFT算法和GA算法复杂,但由于云计算技术的使用,调度过程中计算能力的增强使算法的复杂度影响降低,而算法本身为资源调度效率的提高带来了较大的影响.

在实验中,采用改进的MPSO算法时云计算中的工作任务最早完成,即该算法进行全局调度优化的结果优于没有优化调度的HEFT算法和具有局部优化的遗传算法.

采用HEFT算法、GA算法及文中改进的MPSO算法(选择概率分别为40%和60%)时,云工作流系统的总费用对比如图3所示.

表1 4种算法的任务执行时间比较

图3 不同资源数下几种算法的任务执行费用

Fig.3 Task execution cost of several algorithms with different numbers of resources

由图3可知,由于改进MPSO算法的优化效率高,对资源的调度更有效,从而提升工作流中任务的执行效率,因此,在相同条件下对资源的消耗会降低.

设定不同资源数,比较HEFT算法、GA算法、改进MPSO算法的工作流任务运行时间情况,结果如图4所示.

图4 不同资源数下几种算法的任务执行时间

Fig.4 Task execution time of several algorithms with different numbers of resources

由图4可以看出,在服务资源比较少的情况下,各算法的调度结果具有一定的差别,随着资源数的增加,改进MPSO算法虽然因为粒子群优化算法具有的不确定性而发生抖动,但并未产生强烈的影响,相对其他两种算法仍具有一定的优势,使资源调度更加优化,执行时间更短.

3.2 具有负载感知调度结果分析

实验将基于有、无负载感知机制的PSO算法分别应用于云工作流系统中,PSO算法的适应度随代数的变化如图5所示.衡量系统负载状况的内存利用率、CPU利用率的实验结果如图6所示.

图5 有、无负载感知机制的PSO算法的适应度随代数的变化Fig.5 Change of fitness with iteration number of PSO algorithm with or without load-aware

从图5可知,使用负载感知机制后,系统的调度算法在执行时能较早地趋于稳定,因此也保证了在系统中进行资源调度时负载的平衡性.

图6 内存利用率和CPU利用率对比

从图6可知,在系统工作流任务执行18、30、42 s左右的时间段内,选用有负载感知的调度策略时,系统的内存利用率和CPU利用率降低,这表明在该时间段内,任务在调度器中等待调度,故内存利用率下降,后续调度迅速安排任务执行,所以在以上时间段后CPU利用率迅速上升,符合工作流中任务调度的特点.在同样的时间段,选取无负载感知的调度策略时,系统的内存利用率处于增长状态,CPU利用率同样有所变化,并且变化幅度较大.

综合考虑内存、CPU利用率可知,在截取的60 s任务执行时间内,有负载感知的调度策略在任务请求调度中由于任务调度时机合适,使资源利用率没有发生大的波动,一直处于平稳状态,并没有因为请求服务数的突增而加大调度器的负担,因此,利用具有负载感知的调度策略能更好地保证云工作流系统的资源利用率,提高系统性能.

4 结论

根据用户的QoS需求,考虑系统的资源利用率对云计算资源进行有效调度,以实现效益最大化是当前云计算的资源分配所遇到的挑战.文中将云计算与工作流相结合,建立了云工作流系统,给出了具有两个调度阶段的系统调度模型.针对整体优化及对用户QoS的需求,文中提出了改进的MPSO算法,通过整体的优化策略进行预调度;为了保证系统任务在高负载时正常执行,保证系统的执行能力,将文中提出的考虑负载感知的调度策略应用于局部的调度中,根据调度策略求解负载情况,给出调度的恰当时机进行资源调度,以提高系统的资源利用率.实验结果表明:改进的MPSO算法应用于云工作流系统的资源优化调度中,相较于HEFT算法和GA算法,任务响应时间更快,能够高效地利用资源,满足用户一定的QoS需求;具有负载感知的调度策略能有效平衡系统负载,提升资源利用率.今后拟考虑QoS的综合约束条件,提出相应的资源调度策略.

[1] SINGH L,SINGH S.A genetic algorithm for scheduling workflow applications in unreliable cloud environment [C]∥Recent Rends in Computer Networks and Distributed Systems Security.Berlin/Heidelberg:Springer,2014:139-150.

[2] CHEN W N,ZHANG J.A set-based discrete PSO for cloud workflow scheduling with user-defined QoS constraints [C]∥Proceedings of 2012 IEEE International Conference on Systems,Man,and Cybernetics.Seoul: IEEE,2012:773-778.[3] TORDSSON J,MONTERO R S,MORENO-VOZMEDIA-NO R,et al.Cloud brokering mechanisms for optimized placement of virtual machines across multiple providers [J].Future Generation Computer Systems,2012,28(2):358-367.

[4] LIU Ke,GHAREHCHOPOGH F S,AHADI M,et al.Ana-lysis of scheduling algorithms in grid computing environment [J].International Journal of Innovation and Applied Studies,2013,4(3):560-567.

[5] JAVADI B,THULASIRAM R K,BUYYA R.Characterizing spot price dynamics in public cloud environments [J].Future Generation Computer Systems,2013,29(4):988-999.

[6] JRAD F,TAO J,BRANDIC I,et al.SLA enactment for large-scale healthcare workflows on multi-cloud [J].Future Generation Computer Systems,2015,43(4):135-148.

[7] IOSUP A.Performance analysis of cloud computing ser-vices for many-tasks scientific computing [J].IEEE Tran-sactions on Parallel Distributed System,2010,22(6):931-945.[8] 郭禾,陈征,于玉龙,等.带通信开销的DAG工作流费用优化模型与算法 [J].计算机研究与发展,2015,52(6):1400-1408.

GUO He,CHEN Zheng,YU Yu-long et al.A communication aware DAG workflow cost optimization model and algorithm [J].Journal of Computer Research and Development,2015,52(6):1400-1408.

[9] 张鹏,王桂玲,徐学辉.云计算环境下适于工作流的数据布局方法 [J].计算机研究与发展,2013,50(3):636-647.

ZHANG Peng,WANG Gui-ling,XU Xue-hui.A data placement approach for workflow in cloud [J].Journal of Computer Research and Development,2013,50(3):636-647.[10] 朱勇,罗军舟,李伟.一种工作流环境下能耗感知的多路径服务组合方法 [J].计算机学报,2012,35(3):627-638.

ZHU Yong,LUO Jun-zhou,LI Wei.An approach for energy aware multipath service composition based on workflow [J].Chinese Journal of Computers,2012,35(3):627-638.

[11] WU Zhangjun,LIU Xiao,NI Zhiwei,et al.A market-oriented hierarchical scheduling strategy in cloud workflow systems [J].The Journal of Supercomputing,2013,63(1):256-293.

[12] YANG Bo,TAN Feng,DAI Yuanshun,et al.Performance evaluation of cloud service considering fault recovery [J]. The Journal of Supercomputing,2013,65(1):426-444.

[13] BUYYA R,VENUGOPAL S.The gridbus toolkit for ser-vice oriented grid and utility computing:an overview and status report [C]∥Proceedings of the 1st IEEE International Workshop on Grid Economics and Business Mo-dels.Seoul:IEEE,2008:19-36.

[14] LIU Xiao,YANG Yun,JIANG Yuan-chun,et al.Preventing temporal violations in scientific workflows:where and how [J].IEEE Transactions on Software Enginee-ring,2011,37(6):805-825.

[15] YUAN Dong,YANG Yun,LIU Xiao.A data dependency based strategy for intermediate data storage in scientific cloud workflow systems [J].Concurrency and Computation:Practice and Experience,2012,24(9):956-976.

[16] LIU Jun-xiang,WANG Yong-ji,CARTMELL Matthew.An improved rate monotonic schedulability test algorithm [J].Journal of Software,2005,16(1):89-100.

A Two-Stage Resource Scheduling Method for Workflow Cloud Computing System

WANGYan1WANGJin-kuan1HANYing-hua2

(1. College of Information Science and Engineering, Northeastern University, Shenyang 110819, Liaoning, China;2. School of Control Engineering, Northeastern University at Qinhuangdao, Qinhuangdao 066004, Hebei, China)

In order to improve the resource utilization of cloud computing systems and optimize the system perfor-mance, by taking into account the users’ QoS demand, a workflow cloud computing system is established by integrating cloud computing with workflow, and a two-stage resource scheduling model is constructed for the cloud computing workflow system. In the first stage, by considering the time and cost constraints of QoS, the dependencies among the tasks in the workflow, and the processing of the intermediate data from each task, a modified particle swarm optimization algorithm (MPSO) is proposed, and the Pareto is used to obtain an optimal solution so as to improve scheduling efficiency. In the second stage, by considering the resource allocation on hosts, a scheduling stra-tegy with load-aware is proposed to perform resource scheduling according to system loads, so as to improve the resource utilization of the system. Experimental results show that, in the resource scheduling process of the workflow cloud computing system, the modified MPSO algorithm is superior to the earliest heterogeneous finish-time algorithm and single-objective optimization genetic algorithm in terms of execution speed, resource utilization and users’ satisfaction with QoS, and that, the proposed scheduling strategy with load-aware can schedule more efficiently accor-ding to the system loads, and the task execution efficiency and the resource utilizationare are thus improved.

cloud computing; workflow; particle swarm optimization; load-aware

1000-565X(2017)01- 0080- 08

2016- 03- 18

国家自然科学基金资助项目(61300194)

Foundation item： Supported by the National Natural Science Foundation of China(61300194)

王岩(1981-),女,博士生,讲师,主要从事云计算资源调度研究.E-mail:wangyan3215931@163.com

TP 393

10.3969/j.issn.1000-565X.2017.01.012