云环境中一种多阶段式工作流任务调度算法

张 扬 马 飞

1(广西工业职业技术学院 广西 南宁 530003) 2(广西大学计算机与电子信息学院 广西 南宁 530004)

0 引 言

通常，云计算环境中的工作流可表示为有向无循环图DAG的形式[1]。DAG中，节点即为待执行的任务，有向边即为任务间的次序约束或任务间的通信关系。相互独立的任务可分配至不同的虚拟机上同步执行，而相互依赖关系的任务则可以分配至同一虚拟机上执行以降低任务间的数据通信延时。调度问题即将DAG中的任务分配至一个虚拟机资源集合，并考虑改善系统的性能[2]。调度问题可以是静态的，即任务执行前发生调度；也可以是动态的，即任务执行过程中发生调度。多数情况下，以实现调度时间或代价最优为目标的工作流形式的任务调度问题是NP问题。而大多数算法也仅集中于考虑执行时间最小化的任务调度问题，而忽略了云计算环境中的调度代价问题。

本文设计一种基于代价的工作流任务调度算法(简称ICTS)。算法由层次排序、确定任务优先级、虚拟机选择三个阶段组成。通过三阶段式的任务调度过程，较好地均衡了调度长度和任务执行代价间的平衡问题，并且通过大规模随机化生成的任务有向图模型的仿真比较研究，证实了算法在调度长度和执行代价同步优化上的优势。

1 相关研究

为了解决工作流调度这一NP问题，很多文献提出了启发式调度算法。文献[3]提出两种算法LOSS和GAIN分别用来优化预算约束下的时间和代价，但仅涉及单目标优化。文献[4]讨论了IaaS云环境中的代价和截止时间约束工作流调度，但所考虑的资源仅为同质资源模型。文献[5]提出两种云工作流调度算法：一阶段算法IC-PCP和两阶段算法IC-PCPD2。两种算法可以在多项式时间内得到截止时间约束下的代价最小调度方案。文献[6]提出了在混合云中截止时间约束的代价最小化调度算法HEFT，利用子截止时间的概念进行资源的重调度，并实现了代价最小化。文献[7]则实现了包任务在截止时间约束下的代价最小化调度，但仅适用于独立任务调度。文献[8]利用粒子群搜索方法求解了用户截止时间约束下费用最小化的工作流调度方案。文献[9-11]提出了一种截止时间与预算约束时工作流调度遗传算法，但也仅是实现执行代价或执行时间的单一优化。文献[12]提出一种工作流调度算法Hybrid，基于帕累托占优技术将任务调度至代价最小的虚拟机上，有效降低非关键路径上任务的调度代价。但算法没有考虑关键路径上任务执行代价对于总体代价的关键影响，导致得到的最终代价并不一定是最优的。可以看出，以上启发式或元启式算法多数仅进行了垄断和单一目标优化。

鉴于此，本文设计了一种同步考虑执行时间与代价的工作流调度算法，通过定义任务的调度优先级以及最优调度资源的选择规则，实现工作流的均衡调度。

2 系统模型

表1给出与本文相关的所有符号含义说明。

表1 符号说明

表1 符号说明

2.1 工作流模型

科学工作流的常规建模方式即为有向无环图模型DAG，将工作流表示为G=(V,E)，V表示任务v的集合，E表示边e的集合也代表两个任务间的通信代价。节点vi∈V表示任务的计算时间，该值取决于任务所分配的虚拟机的计算能力。边(i,j)∈E的权重表示任务vi与任务vj间的通信时间，即任务间发送数据所需要的时间。若DAG中的一个任务不存在父节点(前驱节点)，则称之为入口任务ventry，若一个任务不存在子节点(后继节点)，则称之为出口任务vexit。若DAG中拥有多个入口或出口任务节点，可分配一个总的入口或出口任务节点，并将其所有先前入口或出口任务相连，且该总入口或出口节点的权重取0，边权重也取0。DAG的任务模型表明，一个任务只有在其所有父节点完成后，该任务才能开始执行。有向无环图模型下的工作流模型优势在于可以明确工作流各个子任务间的依赖关系，以及整个工作流的进出口位置，进而方便任务调度次序的选择和任务完成时间的计算。

图1为一个DAG模型示例。该DAG包括10个任务节点，节点v0为第一个执行任务，节点v1-v8仅能在任务v0完成关发送结果数据后才能开始执行，而节点v2-v4直到v1完成前也无法开始执行，节点v9是最后一个任务，该任务只有在其他所有任务均执行完成后才能开始执行。当两个任务被分配至同一虚拟机资源时，边上的通信代价值也可以忽略不计。

图1 DAG示例

2.2 云资源模型

假设云计算环境拥有m个异构虚拟机资源组成的集合M，由于每个任务可在不同虚拟机上执行，令t(vi,mj)表示任务vi在虚拟机vj上的执行时间，并假设每个任务是DAG的一个个体而不再分割。DAG中的所有任务调度至虚拟机上执行后，DAG的调度长度makespan即为出口任务vexit的实际完成时间。令TES(vi,mj)、TEF(vi,mj)、TLF(vi,mj)分别表示任务vi在虚拟机mj上的最早开始时间、最早完成时间、最迟完成时间。TES(vi,mj)可表示为：

TES(vi,mj)=

(1)

若前驱任务vp调度至虚拟机mj，则ctvp,vi等于0。TEF(vi,mj)可表示为：

TEF(vi,mj)=TES(vi,mj)+t(vi,mj)

(2)

TLF(vi,mj)可表示为：

(3)

DAG的调度长度makespan定义为DAG的完成时间，等于出口任务vexit的实际完成时间，表示为：

MS=TAF(vexit)

(4)

云计算中，多个虚拟机均可以执行每个任务。则任务vi在虚拟机mj上的执行时间可表示为：

(5)

若现有n个虚拟同可执行任务vi，则vi的平均执行时间可表示为：

(6)

该资源模型利用异构的虚拟机集群建立了执行工作流任务的通用模型，使得不同处理能力和不同价格的虚拟机均是工作流任务的可选目标，这样可以在调度算法设计上仅关注于任务与资源间满足目标函数的匹配与映射求解问题。

2.3 价格模型

云计算拥有不同的价格模型，如Amazon EC2按照虚拟机的数量和类型收费，而Google App Engine则按照所请求的CPU周期数收费。本文利用后一种虚拟机的代价模型，其优势在于在单个已付费周期的CPU租用过程中，若付费任务已经在单个CPU周期内完成，则后续继续利用CPU的任务可以不支付费用，从而降低工作流整体的执行代价。价格越高，则表明虚拟机计算能力越强，反之亦然。令mc(vi,mj)表示任务vi在虚拟机mj上执行的代价：

(7)

3 算法设计

本文设计一种基于代价的工作流任务调度算法，目标是将DAG中的任务调度至虚拟机上执行，并确保得到最小化的调度长度和执行代价。算法基本流程如算法1所示。

算法1ICTS算法

输入：DAG G(V,E)，虚拟机集合。

输出：任务调度解，即任务与虚拟机间的映射关系。

1. partition G into levles according to tasks dependency

2. sort levels based on dependency order

3. for each level do

4. for each taskvido

5. computeRank(vi)

6. end for

7. end for

8. create new tasks list

9. sort all tasks in the new list in decreasing order of Rank(vi)

10. for each taskviin the task list do

11. for each VMmjin the VMs set do

12. compute MKCR(vi,mj)

13. end for

14. end for

15. assign taskvito the VMmjthat has the maximum value of MKCR(vi,mj)

16. end

ICTS算法由三个阶段组成：层次排序阶段(工作流任务分级)、确定任务优先级阶段、虚拟机选择阶段。第一阶段的目标是尽可能提高任务并行执行度，具体方式是以自顶向下的方式遍历工作流结构的有向无环图，以拓扑排序的形式将处于同一层次的相互独立的任务划分为群组。分组后的任务将形成任务包的形式，在同一任务包中的任务不具备相关性，从而提高任务的并行执行程度。第二阶段中，算法根据每个任务的秩值，对每个层次中的任务进行排序，任务vi的秩值计算方式为：

(8)

(9)

Rank(vexit)=MCP(vexit)

(10)

由此可见，第二阶段计算任务的秩值决定了任务被调度的优先级次序，且任务秩值需要以递归方式从出口任务往入口任务进行计算。

最后，在虚拟机选择阶段，任务vi在虚拟机mj上的调度长度/代价比率MKCR(vi,mj)计算为：

MKCR(vi,mj)=[(1-β)×Min_Cost(vi)/

Cost(vi,mj)]+[β×Min_TEF(vi)/TEF(vi,mj)]

(11)

式中：β表示代价因子，用于描述用户对于调度长度与执行代价间的偏好；Cost(vi)表示任务vi在虚拟机mj上的执行代价。

第三阶段使得每个任务将被调度至拥有最大MKCR(vi,mj)值的虚拟机上，该策略可以充分利用在每个虚拟机上相邻两个调度任务间的空闲时间槽，不仅最小化整个DAG的完成时间，并且可以通过目标虚拟机的选择时参考调度长度/代价比率MKCR的方式均衡任务执行的时间和代价。

算法时间复杂度分析。ICTS算法的时间复杂度与传统的HEFT算法是相似的，同为O(e×m)，其中：e表示DAG中有向边的数量，m表示虚拟机数量。若有向边的数量正比于v2(v为任务数量)，则算法时间复杂度可达到O(v2×m)。

图2展示了以图1为例的任务DAG利用混合算法Hybrid[12]和本文算法ICTS得到的调度结果。算例的场景中拥有3个虚拟机资源，任务在虚拟机上的执行时间和执行代价如表2和表3所示。图2(a)显示混合算法的调度长度为1 000.94 s，调度代价为822＄。图2(b)显示ICTS算法的调度长度为874.19 s，调度代价为793＄。本文提出的算法降低了约12.66%的调度长度，调度代价约节省了3.52%。

图2 调度结果对比

任务VM0VM1VM2v0191.98132.6499.31v1220.01152.01113.81v2177.37122.5591.75v3270.97187.22140.18v4204.71141.44105.90

续表2 s

表3 任务在不同虚拟机上的执行代价 ＄

4 仿真实验

利用WorkFlowSim平台[13]进行云环境中工作流调度的仿真实验，并利用一种特定的工作流结构类型Montage作为云工作流的拓扑结构进行测试，Montage工作流是一种应用于天文学领域的科学工作流结构，其任务组成以I/O密集型为主，对CPU处理能力要求相对较低，串行任务较少，其结构如图3所示。表4是实验中的相关参数配置情况。

图3 Montage工作流结构

表4 参数配置

4.1 性能指标

1) 调度长度比率和代价比率。系统调度效率可以通过标准化的调度长度和代价进行衡量，即调度长度比率SLR和代价比率MCR，分别定义为：

(12)

(13)

式(12)的分母部分表示处于关键路径CP上的任务的最小执行时间之和，式(13)的分母部分表示处于关键路径CP上的任务的最小执行代价之和。

2) 代价因子β。为了度量SLR和MCR，需要使用不同的代价因子β取值。图4为针对不同的代价因子取值在不同的DAG规模下得到SLR和MCR取值情况。图中，x轴代表代价因子，y轴同时代表SLR和MCR，即标准化的调度长度和代价。DAG中的任务数量随机生成于80～400个任务之间。图4表明，代价因子与MCR成正比，而与SLR成反比。对于较小的代价因子β，如β=0.1、0.2、0.3，MCR和SLR的变化比例略小于β>0.3的变化。总体来看，在β<0.4的情况下，算法在两个指标上能够拥有较好的性能表现。而β>0.4后，SLR的变化比例较慢，而MCR变化较快。因此，在后续仿真测试中代价因子β可取值为0.1、0.2和0.3。

图4 不同规模不同代价因子对性能的影响

4.2 结果分析

本节对ICTS算法和对比算法Hybrid进行实验对比分析，利用前文引入的标准化调度长度比率和标准化代价比率作为性能指标。在相同的虚拟机资源配置下，利用不同的DAG规模(不同的任务数量)进行实验仿真。图4为在不同的任务数量和CCR取值情况下两个指标的性能比较情况，其中，柱状图的取值对应于左侧纵坐标值，折线图的取值对应于右侧坐标值。算法的SLR指标均会随着任务数量和CCR取值的增加而增加，而ICTS算法在不同DAG规模下也可以得到更优的SLR性能。表5给出本文算法ICTS对比Hybrid算法在任务调度长度和代价上得到的增益比例(即在调度长度和代价上的节省程度)，在确定的任务规模下，ICTS算法在选择目标虚拟机时有效参考了调度效率与代价的均衡，使得两个指标均得到改善。

表5 ICTS算法比较对比算法Hybrid得到的增益

图5和图6显示了在不同的DAG任务规模下算法得到的SLR和MCR指标性能情况。可以看到，ICTS算法在两项指标上是优于Hybrid算法的，这是因为ICTS算法考虑了任务父节点与自身的通信时间以及任务子节点与自身的通信时间(如式(8)所示)。因此，在DAG中最复杂任务将处于分级队列的队首而被优先进行调度。而Hybrid算法在计算每个任务的分级时仅仅考虑了任务与其后继之间的通信时间。

图5 不同任务组成(CCR度量)及不同任务数量对SLR的影响

图6 不同任务组成(CCR度量)及不同任务数量对MCR的影响

利用式(11)选择任务调度的虚拟机，ICTS算法同时考虑了Min_Cost(vi)和Min_TEF(vi)。此外，还可以看到，改变工作流中任务的通信/计算比率(改变计算密集型和通信密集型任务的比例)的情况下，ICTS算法在SLR指标上依然具有较好的适应性，仿真结果并没有出现反转式的结果，而仅仅是指标值出现比较缓和的增加。

对于算法而言，MCR指标会随着任务数量和CCR取值的增加而增加。图6结果表明ICTS算法在不同的任务规模下提供了比Hybrid算法更好的MCR性能。另一方面，Hybrid算法过多依赖于时间与代价的比例，这些比例在选取调度任务时仅考虑了执行代价与执行时间的最小值和最大值，而本文算法对相关参数的依赖性则远弱于Hybrid算法，使其在不同规模和不同任务组成的情况下依然可能得到比较稳定的性能表现。

5 结 语

为了实现云计算环境中的工作流任务调度，本文以最小化调度长度和执行代价为目标，提出一种基于代价的工作流调度算法。通过任务分级排序、确定任务优先级以及虚拟机资源选择三个阶段的优化，实现了不同规模任务下对工作流调度长度和执行代价的同步优化。仿真实验结果表明，对于选取的SLR和MCR两个性能指标，本文算法均表现出比对比算法更好的性能。下一步可选择将云资源提供方的能耗问题考虑到优化目标中，即在执行效率与执行能效之间取得更好的平衡，以此为目标设计工作流调度算法。