满足实时云任务需求的主动响应式工作流调度模型

王 旖 旎

(重庆商务职业学院 重庆 401331)

0 引 言

云计算是一种革新式的应用，可以以即付即用的计算模式提供按需形式的应用、平台、基础设施[1-3]。本质上，云提供者需要部署大量的虚拟机以满足广泛分布的用户需求，同步地为云提供方和用户方降低运营代价。此外，云提供方可以根据平台负载动态地调整可用的虚拟机资源，从而进一步做到代价的节省。有赖于云计算低代价、弹性应用、高可用性的特征，云计算平台可执行的应用领域也越来越广泛[4-6]。一种描述应用过程的典型模式即为工作流，它由多数量的具有数据相关性的任务图组成，通常以有向无环图的形式描述[6-8]。对于云平台而言，该类工作流应用拥有实时性的特征，主要体现在两个方面，一是广泛分布的用户的动态发送请求，其到达时间是无法预知的；二是其需要逻辑上和临时计算上的正确性，进而确保工作流处理的时效要求。

目前，大量工作集中在云平台上的工作流调度问题上。但是，多数已有工作流集中于单一工作流调度，且无法处理实时工作流调度问题。原因在于：首先，调度实时工作流任务时，由于工作流任务间的数据依赖性导致大量虚拟机的空闲时槽无法利用；其次，若按序调度实时工作流，通过合并不同资源上的工作流任务降低空闲时槽的方法可能增加算法的复杂性。更糟的是，合并工作流任务可能延迟任务的执行时间，从而导致工作流执行的截止时间无法得到保证。

如果来自不同工作流的任务可按序在相同虚拟机上执行，则由于数据依赖导致的空闲时槽可被充分利用，进而有助于改进执行代价和云平台的资源利用率。基于此，本文主要研究如何以混合形式调度不同工作流任务，为了提高效率，着眼于如何扩展和压缩可用的虚拟机资源，实现代价更高效的工作流调度。

1 相关研究工作

工作流应用是分布式计算环境中的普遍形式，如大数据分析应用、图像处理应用、科学工作流应用等，其中涉及大量相互依赖的任务执行需求。近年来，工作流调度问题越来越受到关注，大量的工作流调度算法被提出，而已有算法可以划分为三类：表调度算法、聚类调度算法、元启发式调度算法。表调度算法是工作流调度的常用形式，其主要过程包括两步：(1) 为每个工作流任务分配优先级；(2) 基于任务优先级调度工作流调度。例如：第一个基于表调度的工作流调度算法HEFT[9]，基于任务升秩值设置任务优先级之后，再将其调度至完成时间最小的处理器上执行。文献[10]扩展了HEFT算法，以改进执行跨度和能效为目标寻找工作流调度的Pareto解集合。文献[11]提出一种随机等级调度算法以随机运行时间调度工作流任务。但是，以上方法仅关注于单一工作流的调度问题，在满足截止时间下的云平台中的多工作流调度问题上显得效率较低。

部分工作通过对工作流任务进行聚类的方式实现工作流调度。文献[12]设计一种局部关键路径算法PCP进行网格中的工作流调度，可以实现满足截止时间下的代价最优。PCP算法的两个关键步骤是：首先进行截止时间的分配，即将总体截止时间在每个工作流任务间进行子划分；然后为调度阶段，即分配每个任务至满足子截止时间下执行代价最小的实例上。文献[13]扩展PCP算法得到了两种新的算法IC-PCP和IC-PCP2，实现了云环境中的工作流调度。文献[14]设计了云工作流调度算法RCT，主要步骤是：首先根据任务相关性将工作流任务聚类为多个局部关键路径，然后在满足时间和代价约束的基础上为每条关键路径生成一个可行调度解集合，最后对解集合进行优化，选择最优解。但是，以上方法没有云环境提供资源的动态性，对于调度实时工作流的效率显然不高。

元启发式调度算法是解决工作流调度的另一有效方法。文献[15]利用PSO降低了工作流调度的执行代价，同时可以确保时间约束。文献[16]同样利用PSO增强了调度的负载能力。文献[17]利用GA得到了云工作流调度的Pareto解集，在执行跨度和能效上均得到了优化。文献[18]设计了基于蜂群的工作流调度算法JDS-BC，同步降低了执行跨度和数据传输时间。文献[19]利用GA对工作流进行了分级，然后通过启发式方法对任务进行映射。文献[20]结合启发式方法和进化搜索方法求解了工作流调度问题。文献[21]设计了新的进化搜索方法对单一工作流调度的时间和代价进行均衡。文献[22]利用种群协作机制同步优化执行跨度、代价和调度能耗。但是，以上随机化搜索算法通常具有较高的时间复杂度，应用在云环境中的工作流调度问题上拥有诸多限制。

在已有的多工作流调度研究中，文献[23]设计了一种收益感知算法，在满足预算和时间约束的情况下可以提高工作流调度的收益。文献[24]在公平和优先原则的基础上设计了一种均衡策略，可以确保工作流调度的截止期限。文献[25]在考虑时间和费用约束的基础上实现了并行任务的完成率提升。文献[26]则充分利用虚拟机之间的空闲时槽降低工作流执行代价。但是，以上方法没有不同工作流中并行任务的到达，没有充分利用计算资源的空闲时间。

2 问题描述

云平台下的工作流可建立模型为WS={w1,w2,…,wn}。对于每一个工作流wi∈WS又可以建立为一个三元组模型wi={Gi,ai,Di}，Gi代表工作流wi的任务结构，ai代表工作流的到达时间，Di代表工作流完成的截止时间。工作流的结构Gi可以建立模型为有向无循环图结构，表示为DAGGi=(Ti,Ei)，其中：Ti={t1,i,t2,i,…,ti,|Ti|}代表有向图中的顶点集合，表示任务节点，ti,j代表工作流wi中的任务j；|Ti|代表集合Ti中的顶点数，即任务数；Ei⊆Ti×Ti代表任务节点间的有向边集合。一条有向边ei,p,j∈Ei代表任务ti,j开始执行取决于执行任务ti,p的输出数据，而ti,p是任务ti,j的直接前驱任务之一，ti,j是任务ti,p的直接后继任务之一。集合pred(ti,j)代表所有ti,j的直接前驱任务组成的集合，succ(ti,j)代表所有ti,j的直接后继任务组成的集合。

云平台可以提供不同类型不同数量的虚拟机VM服务，令m代表云平台中可用的虚拟机类型的数量，u∈{1,2,…,m}代表VM类型的标识号，每种虚拟机类型对应一个使用代价p(u)，则VMu,k代表类型为u的第k个虚拟机，再令ck,l代表虚拟机su,k与虚拟机su′,h间的通信带宽。

云平台下的虚拟机可在任意时刻进行租用和释放，本文假设当一台虚拟机空闲时，即该虚拟机已经完成所有映射任务和数据传输后，即可被释放。进一步，虚拟机按其租用的时间单位按整数进行付费，单位时间内的部分时间租用也按整数单位时间付费，即若付费时间单位为1小时，若虚拟机租用时间为1小时1分钟，也将按2小时付费。由于任务只有在接收完其所有前驱任务的数据后才能开始执行，则存在如下约束：

FTi,p,k+TTi,p,j≤STi,j,k

(1)

式中：FTi,p,k代表任务ti,p在虚拟机VMu,k上的完成时间；TTi,p,j代表任务ti,p与ti,j间的数据传输时间；STi,j,k为任务ti,j在虚拟机VMu,k上的开始时间。

在工作流wi的所有任务被调度至虚拟机执行后，wi的完成时间FTi可定义为所有任务中的最大完成时间，即：

(2)

为了确保工作流执行的截止时间，工作流wi中的所有任务必须在其期限Di内完成，即存在以下约束：

FTi≤Di∀wi∈WS

(3)

结合式(1)的数据依赖约束和式(3)的截止时间约束，云平台下的多工作流调度问题的第一个目标是降低完成工作流集WS的总体执行代价TC，可形式化为：

(4)

式中:|VM|代表处理工作流集合WS时租用的虚拟机量；Pk代表租用虚拟机VMu,k的时间单位数量。

对于云资源提供方而言，其目标是追求尽量高的资源利用率AU。虚拟机资源的利用率定义为虚拟机执行工作流任务的有效工作时间与虚拟机完整运行时间的比例，虚拟机完整运行时间包括虚拟机有效工作时间和无任务执行空闲时的等待时间。基于此，多工作流调度问题的另一个目标是最大化虚拟机的平均资源利用率，可形式化为：

(5)

式中：wtk代表处理工作流WS时虚拟机VMu,k的有效工作时间；TTk代表虚拟机VMu,k的完整运行时间，包括工作时间和空闲等待时间。

为了便于云计算环境中的工作流任务调度仿真，本文将应用工作流仿真平台WorkFlowSim实现算法仿真。该平台在既有云任务仿真平台CloudSim的基础上扩展而来，支持本文所构建的有向无环图模型的工作流调度。同时，为了实现多工作流调度模型，平台中可通过触发器生成多类型不同结构的工作流，支持实时多工作流调度需求。而为了统计调度算法优化目标中的任务总体执行代价和虚拟机资源利用率，实验过程中调度器会实时统计运行状态的虚拟机资源量、虚拟机被租用的时间单位数量、虚拟机的完整运行时间，以便衡量工作流调度算法的执行效果。

3 调度模型与算法设计

3.1 调度模型

本节设计了云平台下的响应式工作流调度模型，如图1所示。调度模型由三个部分构成：用户方、调度器、云资源提供方。云平台可向广泛分布的用户提供服务，用户方则可以在任意时间向云平台发送其工作流任务的执行请求。调度器作为用户方与资源方的连接桥梁，可以动态地将工作流执行请求调度至虚拟机资源上，并根据云平台的负载状况动态调整资源方所提供的可用虚拟机资源，形成可扩展可收缩的资源池。

图1 响应式工作流调度模型

任务就绪状态。若一个任务的所有前驱任务均已在虚拟机上完成，或任务不存在任一前驱任务，即pred(ti,j)=∅，则该工作流任务视为就绪状态。

为了以混合方式调度来自不同工作流的任务，每台虚拟机至多仅有一个等待任务，而其他等待任务将临时放置在工作流任务队列中。当工作流任务就绪后，它们将被移动至就绪任务队列。由于就绪任务队列中的就绪任务来自于不同的工作流，且它们之间不存在数据依赖关系，调度这些就绪任务可以改进代价和资源利用率。调度算法的主要目标是生成适应于可用数量虚拟机资源的调度策略，并调度工作流任务队列中的等待任务至虚拟机上执行。调度算法部分包括三个对工作流的调度响应策略：1) 新到达工作流的响应调度策略；2) 任务完成的响应策略；3) 紧迫任务的响应调度策略。调度响应策略不仅可以满足多工作流的执行需求，而且可以实时响应紧迫型工作流任务的执行需求，充分利用虚拟机资源的空闲时槽和更大化的任务并行程度，以混合形式调度来自不同工作流的任务，在确保截止期限约束的同时，有效满足实时云任务的调度需求。

当进行工作流调度时，若某些工作流在队列中的等待时间过长，则会导致无法满足工作流的截止时间约束。为了解决这一问题，需要定义每个任务的最迟开始时间LSTi,j，必须使每个工作流任务在该时间前开始执行，如此，工作流wi的完成时间即可在其截止时间之前。由于云平台下的虚拟机资源是异构的，当任务调度至不同虚拟机时得到的任务运行时间也是不一样的。类似地，工作流任务间的数据传输时间同样取决于所调度的虚拟机之间的带宽。因此，对于任务ti,j而言，无法准确计算其最迟开始时间LSTi,j。本文中，在调度工作流之前需要利用最小执行时间。定义任务的最小执行时间为METi,j，数据依赖ei,p,j的最小数据传输时间为MTTi,p,j，并定义如下：

(6)

(7)

式中：VM代表云平台中的虚拟机集合；ETi,j,k代表任务ti,j在虚拟机VMu,k上的执行时间；r(ti,j)代表任务ti,j所选的虚拟机索引。

结合以上定义，工作流任务ti,j的最迟开始时间可定义为：

(8)

式中：succ(ti,j)代表任务ti,j的所有直接后继任务集合；DTvm代表部署一台新虚拟机的延时。

则任务ti,j的最迟完成时间LFTi,j可定义为：

LFTi,j=LSTi,j+METi,j

(9)

3.2 算法详细设计

结合前文给出的工作流调度模型，本节设计一种启发式算法，整合三种响应调度策略，以较小的计算开销获取最优的调度方案。引入两种约束：1) 一旦一台虚拟机上的执行任务完成，且其所有前驱任务也已完成，则该虚拟机上的等待任务立即开始执行。2) 当满足以下两个条件时，一台虚拟机可被释放：(1) 为空闲虚拟机，即该虚拟机已经完成映射至其上的所有任务以及数据传输任务；(2) 该虚拟机的租用时间为整数个时间单位。

已有调度算法当有新的工作流到达时，所有工作流任务将被直接调度至虚拟机。不同于这种方法，本文算法保留部分等待任务在工作流任务队列中，仅有就绪任务被映射至虚拟机上执行。随着时间的推移，对于等待任务的新的调度方案随之生成，同时调整可用虚拟机资源应对新的任务调度。主动响应工作流调度算法的主要步骤如算法1所示。

算法1主动响应工作流调度算法

1. WTQ←∅

2. RTQ←∅

3.fornewwiarrivesdo

4.foreachti,j∈wido

5.computeLSTi,jandLFTi,jforti,j

6.ifpred(ti,j)=∅

7.ifLSTi,j-ct<△t

8.callAlgorithm2toscheduleti,jtoaVM

9.else

10. RTQ←RTQ∪{ti,j}

11.endif

12.else

13. WTQ←WTQ∪{ti,j}

14.endif

15.endfor

16.sortRTQbytask’sLSTinanincreasingorder

17.endfor

算法1中，WTQ和RTQ分别代表工作流任务队列和就绪任务队列，步骤1-步骤2将两个队列初始化为空集。一旦新的工作流wi到达后，算法立即计算工作流中所有任务的最迟开始时间LSTi,j和最迟完成时间LFTi,j，如步骤5。然后，所有工作流任务被划分为就绪任务和非就绪任务，如步骤6-步骤14。参数ct和△t分别代表当前时间和预设时间阈值，而△t可设置为新的虚拟机的开始时间。对于就绪的工作流任务，若任务为紧迫类任务，即其LSTi,j小于△t对应的当前时间(步骤7)，则通过步骤8中的紧迫任务调度功能算法2将其调度至虚拟机上。若任务为非紧迫任务，则在步骤10中将其添加至就绪任务队列中。对于在新工作流wi中的所有非就绪任务，它们将在工作流任务队列WTQ中等待，即步骤13。最后，步骤16对RTQ中的所有就绪任务按照最迟开始时间的递增方式进行排序。任务ti,j在虚拟机VMu,k上的执行代价ci,j,k为：

ci,j,k=p(u)×(FTi,j,k-rtk)

(10)

式中：rtk代表对于任务ti,j虚拟机su,k的就绪时间。rtk计算方法如下：1) 如果虚拟机VMu,k为空闲，即其执行和等待任务均为空，则rtk为当前时间；2) 如果虚拟机VMu,k为非空闲状态，其rtk为虚拟机VMu,k上最后一个任务的完成时间；3) 如果虚拟机VMu,k才被租用，则其rtk为租用的开始时间。

当算法调度紧迫工作流任务ti,j时，算法将选择拥有最小执行代价的虚拟机，同时确保其最迟完成时间。紧迫任务调度功能的具体过程如算法2所示。

算法2紧迫任务调度策略

1. minCost←∞

2. selectedVM←∅

3. for each availableVMu,kdo

4. ifwtk=∅ do

5. computeFTi,j,kofti,jonVMu,k

6. compute the costci,j,kofti,jonVMu,k

7. ifFTi,j,k≤LFTi,jandci,j,k

8. selectedVM←VMu,k

9. minCost←ci,j,k

10. end if

11. end if

12. end for

13.u←null

14. for each availableVMtypel∈{1,2,…,m} do

15. computeFTi,j,kofti,jon a newVMl,kwith typel

16. computeci,j,kofti,jon a newVMl,kwith typel

17. ifFTi,j≤LFTi,jandci,j,k

18.u←l

19. minCost←ci,j,k

20. end if

21. end for

22. ifu!=∅ then

23. rent a newVMwith typeuand scheduleti,jto thisVM

24. call Algorithm 3 to search a waiting task for newVM

25. else

26. scheduleti,jto the selectedVMselectedVM

27. end if

该算法接收任务ti,j作为输入，执行目标是为其寻找拥有最小执行代价，且在其最迟完成时间LFTi,j以内完成任务的虚拟机。首先，算法将检测云平台中等待任务wtk为空的所有可用虚拟机，即步骤3-步骤12。拥有最小执行代价且能在LFTi,j之前完成任务ti,j的虚拟机得以选择，即步骤7-步骤10。然后，所有可用虚拟机类型被检测(步骤13-步骤21)，以寻找一种虚拟机类型，使得该类型的新的虚拟机能够产生更低的执行代价，且能够满足任务的最迟完成时间，即步骤17-步骤20。之后，如果所选虚拟机类型为空(步骤22)，则表明租用所选类型的新的虚拟机可以产生最小执行代价，新的虚拟机将被租用以执行该紧迫任务，即步骤23。最后，第三种响应调度策略将寻找等待任务，即步骤24中调用算法3。如果所选虚拟机类型为空，则紧迫任务将被调度至相应可用虚拟机上执行，即步骤26。

当一个任务在虚拟机上完成或一个新的虚拟机被租用时，算法中的第三种响应调度策略将被触发，其过程如算法3所示。

算法3搜索新虚拟机的等待任务

1. for eachti,s∈succ(ti,j) do

2. ifti,sis ready then

3.ti,s→RTQ

4. end if

5. end for

6. sort all tasks inRTQbyLSTin a non-descending order

7.ti,j←get the task at the head inRTQ

8. whileti,j!=∅ do

9. computeFTi,jofti,jonVMu,k

10. ifFTi,j≤LFTi,jthen

11. scheduleti,jtoVMu,k

12. break

13. else

14.ti,j←get the next task inRTQ

15. end if

16. end while

当一个任务完成时，根据算法1，其后继任务可能变为就绪状态。令ti,j为虚拟机VMu,k刚刚完成的任务。如算法3所示，第三种响应策略首先寻找所有刚刚变为就绪状态的任务，然后将这些就绪任务添加至就绪任务队列RTQ中，即步骤1-步骤5。步骤6对RTQ中的所有任务按照其最迟开始时间进行非降序排列。步骤7获取队列RTQ中队首的任务。步骤9计算该任务在虚拟机VMu,k上的完成时间。步骤10比较该时间与任务的最迟完成时间的大小关系，若满足小于，则进行任务调度。需要注意的是，若策略被算法2调用以为虚拟机寻找新的等待任务(算法2中的步骤24)，则此时步骤1-步骤6将被抛弃不予执行。拥有较小的最近开始时间LSTi,j的任务将被优先考虑为确保为最迟完成时间而寻找调度虚拟机的任务，即步骤7-步骤16。

4 性能评测

在工作流仿真平台WorkFlowSim[27]下进行仿真实验对算法性能进行评测。选择五种工作流调度算法进行性能比较，包括：WSMT算法[26]，MER算法[28]，OMWSA算法[29]，IC-PCPD2算法[13]和HEFT算法[9]。WSMT算法是一种在线调度算法，当有新工作流到达时，该算法首先按计算资源的非升序对虚拟机进行排列；然后，为了降低任务执行代价，算法将工作流任务插入虚拟机的时间槽。若无法执行以上步骤，则再应用最小完成时间策略进行调度。MER算法首先利用最早完成时间策略生成工作流任务的基准调度方案；然后，通过合并轻型负载资源上的任务以填充至其他资源上的空闲时间槽来进一步优化调度方案。OMWSA算法在有新工作流到达时，为每个任务分配一个等级，然后根据等级对任务进行排序。当调度一个任务时，能够在任务最迟完成时间内完成的虚拟机被选择为目标。若无法找到以上步骤的可行解，算法将租用新的具有最小执行代价的虚拟机，并在其最迟完成时间内完成任务。IC-PCPD2算法的执行分为截止时间分配和调度两个阶段。第一阶段分配给每个任务一个子期限，然后将任务调度至代价最小的虚拟机上，并满足该子期限。算法评测指标上选择式(4)的总体执行代价和式(5)的资源利用率进行性能比较。

4.1 实验搭建

选择四种类型的虚拟机进行实验，每种类型的虚拟机数量可以扩展，虚拟机的主要参数包括使用代价、CPU内核数、内存量和类型因子，具体如表1所示。由于每个任务在不同类型的虚拟机上拥有不同的运行时间，类型因子参数Type(u)用于描述该不同。若该类型虚拟机拥有最强的计算能力，能最小化任务的执行时间，则类型u的Type(u)等于1。对于虚拟机类型u，其参数Type(u)定义为任务在该类型虚拟机上的执行时间与任务的最小执行时间之比。

表1 虚拟机配置

选取四种经典科学工作流结构Montage、SIPHT、CyberShake和LIGO工作流[5]作为实时工作流应用进行仿真测试。每种工作流设置不同的规模：小规模为30个任务组成，中等规模为100个任务组成，大规模为500个任务组成。同时，为了仿真云平台下工作流应用的动态属性，假设工作流的到达服从λ的泊松分布，1/λ为两个连接工作流到达的平均时间长度。

考虑到多种可用的虚拟机类型，工作流任务在不同类型的虚拟机上的执行时间是不同的。对于任务ti,j，其在类型为u的虚拟机上的执行时间计算为：

ETi,j,k=METi,j×Type(u)

(11)

式中：k代表虚拟机的索引；u代表虚拟机类型的索引。

令基准调度方案为将每个任务调度至能力最强的虚拟机上执行得到的方案，此时虚拟机间的最大带宽可用于计算数据传输时间。参数MF代表该基准方案下工作流的执行跨度。设置参数β用于控制工作流的截止时间的缩放范围，表示截止时间因子，工作流wi的截止时间设置为：

Di=ai+β×MF

(12)

实验中将分析截止时间因子β、工作流到达率λ和工作流数量对性能的影响。分析一个参数的影响时，另两个参数固定。具体如表2所示。

表2 参数配置

4.2 结果对比

图2是期限因子β对性能的影响。图2(a)显示，随着β的增加，六种算法的总体执行代价有轻微下降的趋势，原因是处于长截止时间可以使得工作流的时效需求更加宽松，使得更多的并行任务可以调度至同一虚拟机上执行，从而减少虚拟机使用量。此外，更多低代价的虚拟机可以满足截止时间约束需求，也进一步降低了执行代价。本文算法相比WSMT、MER、OMWSA、IC-PCPD2和HEFT分别降低了8.1%、10.5%、16.8%、17.9%和24.1%的代价。原因是：首先，本文算法仅在任务就绪时才调度至虚拟机上，大量压缩上虚拟机的等待时间；其次，由算法1可知，当虚拟机执行其他任务时，虚拟机上的等待任务可以接收其前驱任务的数据，这样可以使等待任务直接开始执行而进一步降低虚拟机的空闲时槽和租用时间，也有助于降低执行代价。图2(b)显示，资源利用率在β增加时具有明显上升的趋势，原因是越大的β值则有越长的截止时间，这有助于在相同虚拟机资源上执行并行任务，尽可能避免虚拟机空闲时间。本文算法相比WSMT、MER、OMWSA、IC-PCPD2和HEFT分别提高了7.3百分点、14.1百分点、19.1百分点、30百分点和35.7百分点的资源利用率。原因在于，本文算法在调度就绪任务时不存在数据依赖，这些任务可以混合方式分配至虚拟机上执行，因此压缩了虚拟机的空闲时间。而其他五种算法在有新的工作流到达时即调度至虚拟机。

(a) 对执行代价的影响

图3是工作流到达率对性能的影响。图3(a)显示，本文算法和WSMT算法的总体执行代价随着到达率λ的增加而轻微下降，其他四种算法基本保持不变。工作流越高的到达率表明越多的任务在工作流任务队列中等待，尤其在就绪任务队列中会更多等待。当就绪任务增多时，对于虚拟机而言寻找等待任务更加容易，虚拟机的空闲时间也将进一步降低。因此，本文算法在增加到达率时代价更小。MER、IC-PCPD2和HEFT三种算法涉及单一工作流的调度，是轮流调度方式，并无先前工作流调度带来的空闲时槽问题。因此，基本维持不变的代价。WSMT将任务插入虚拟机的时槽中，高到达率也有利于增加任务插入的成功率。图3(b)显示，到达率从0.01增加至0.1，本文算法的资源利用率从78%增加至87%，而MER、IC-PCPD2和HEFT则仅有66%、53%和49%左右，原因同上。

(a) 对执行代价的影响

图4是工作流数量对性能的影响。图4(a)显示，六种算法的执行代价随工作流数量呈线性递增，原因是越多的工作流带来越多虚拟机上越长的等待时间，进而影响到越高的执行代价。本文算法的代价要小于WSMT、MER、OMWSA、IC-PCPD2和HEFT算法约8.6%、9.3%、14.3%、20.2%和28.4%。图4(b)显示，本文算法、WSMT、MER、OMWSA、IC-PCPD2和HEFT算法的资源利用率分别稳定在78.4%、72.2%、66.1%、62.9%、53.5%和49.8%，与工作流到达量无关。这些结果充分地展示出本文算法在改善资源利用率和降低执行代价方面具有预期的优势。

(a) 对执行代价的影响

5 结 语

云平台下的工作流调度问题必须同步地注重资源提供方的资源利用率提升和资源使用方进行任务调度的代价优化问题。为了改善云平台下多工作流的执行代价和资源利用率，提出一种代价有效的工作流调度算法。该算法可以充分利用虚拟机资源的空闲时槽，以混合形式调度来自不同工作流的任务，在确保截止期限约束的同时，降低任务执行代价，并提高资源利用率。仿真实验结果表明，与其他几种工作流调度算法相比，本文的调度方法可以达到更好的预期效果。