满足双QoS约束的两阶段云工作流调度算法

武丽芬，严学勇

(1.晋中学院 信息技术与工程系，山西 晋中 030600；2.中国联通晋中分公司 信息支撑中心，山西 晋中 030600)

0 引 言

云计算环境中，资源可根据应用需求动态地分配至用户任务，而用户对资源的支付方式是即付即用的，这极大地区别于传统的网格等分布式计算环境。这种特有的使用特征使得云计算提供了对科学工作流调度的最好支持。每一种大规模的工作流应用均可建模为有向无循环图DAG结构，其中包含大量相互依赖和相互独立的任务，有些可同步执行，有些则需按照先后次序执行。为了满足用户应用的QoS需求，云工作流调度需要寻找有效的调度方案，实现任务与多资源间的映射与执行。

目前，云资源的使用特征导致已有调度算法拥有以下不足：①资源使用时间固定。本文中资源只要在空闲状态即可释放，资源获取是任意的，这样可节省资源使用代价；②资源定价未使用账单模型。本文应用Amazon EC2的资源账单定价模型，在已付账单中，先前任务的空闲时间片可被下一任务继续利用，以节省代价；③涉及多QoS参数时，已有搜索或元启发式算法复杂度过高。本文将设计时间复杂度更低的工作流调度算法，同步满足截止时间和预算约束，寻找调度可行解。

1 相关研究

对于工作流调度多目标优化问题，本文将调度算法分为两种类型：单工作流调度和多工作流调度。单工作流调度仅涉及一次从入口任务至出口任务的执行过程，而多工作流调度涉及入口任务与出口任务间的多次执行过程。目前多集中于单工作流调度，但多数不适用于云环境，原因在于云计算具有即付即用和按需提供的特征，这与传统资源提供方式具有极大不同。

单工作流调度的目标是寻找任务与资源间的合适映射以满足目标函数优化，具体包括：①代价最优，截止时间约束。文献[1]提出代价最优化算法，利用任务复制机制增加满足约束概率。文献[2]提出动态代价有效截止时间约束调度算法，实现单一工作流调度。除了以上启发式算法，文献[3,4]利用搜索和元启发式算法优化相同的目标；②时间最优，预算约束。文献[5-7]提出启发式算法最小化执行时间，同时满足预算约束。文献[8]提出安全与预算感知调度算法SABA，可在满足安全级的同时降低执行时间；③时间最优，代价最优。很多文献尝试均衡最小化时间和代价两种QoS。文献[9]提出关键路径优先算法，利用工作流的扩展与压缩机制优化时间和代价。文献[10]提出Pareto最优的代价-时间最优调度算法。同样地，利用Pareto最优，文献[11]通过设置反映用户对于时间和代价偏好的代价有效因子，提出执行时间和代价最小化调度算法；④截止时间约束，预算约束。文献[12]提出双约束健壮启发式算法实现调度优化，算法利用搜索策略对调度任务进行重分配，以满足时间和代价参数。以上工作的问题在于：采用的资源定价模型不同于当前云的帐单模型；调度过程中资源数量固定，不适应于云环境；VM资源没有设置释放/获取时间戳。

相比单工作流调度，多工作流调度研究相对较少。文献[13]提出两种分级工作流调度算法：宏观多工作流调度和微观单工作流调度。工作流基于QoS需求划分为时间敏感型和代价敏感型，算法采有不同的调度策略可保证对于每种工作流类型的时间QoS和代价QoS的满足。文献[14]提出多DAG最大化吞吐量调度算法MTMD，可保证多个DAG在截止时间内的完成比例。文献[15]提出在线多工作流调度算法OMPHC-PCPR和OPHC-TR，两种算法的不同在于资源分配的任务优先级机制。

2 系统模型

2.1 应用模型

工作流的建模方式为有向无循环图DAG，以三元组G=表示工作流应用DAG，T={t1,t2,…,tn}为有限任务集，n为工作流任务数量。边集E为任务间的依赖关系，该依赖关系确保只有所有父任务完成并发送需要的输入数据后，其子任务才开始执行。data表示数据传输量的n×n矩阵，data(ti,tj)表示tj执行前ti需要向tj发送的数据量。Tavg(ti,tj)表示ti与tj间的平均传输时间，其值取决于所有资源对间的平均带宽和延迟。对于给定的DAG，无前驱任务(父任务)的任务称为入口任务tentry，无后继任务(子任务)的任务称为出口任务texit。

2.2 资源模型

云环境由m个异构资源R={∪mj=1rj|rj∈VMtype}组成，可提供不同能力和代价的服务资源。假设所有计算和存储资源处于同一数据中心，资源间的平均带宽是相等的。执行于同一VM上的两个任务的传输时间为0。每个VM类型在其CPU能力、内存容量和代价方面拥有自身配置。假设工作流应用使用的资源VMs数量是不受限制的，且为了合理初始化以便于用户使用，租用VM时需要一个初始的启动时间boot_time。同时，资源定价是基于VM的间隔时间(interval time)数量的即付即用账单模型，用户将根据interval time的执行数量付费。

对于特定资源rj，其平均性能以每秒进行的浮点操作次数GFLOPs度量，其单位小时价格是已知的。表1给出了实验中使用的Amazon EC2所提供的4种VM资源类型的相关参数。

表1 Amazon EC2资源参数

令VMr/a表示每个VM在调度中更新的释放/获取时间戳排列，VMr/a={(S1,F1),(S2,F2),…}，(S,F)为目标VM连续执行的开始时间和完成时间。该时间戳在任务调度至目标VM时计算。

在为当前任务tcurr选择适当资源rsel之后，如果该任务无法从资源rsel的上一执行任务上降低其执行代价，即：使用资源rsel上的之前最后任务的剩余时间间隔，资源rsel的VMr/a则通过以下方式更新：①最后调度任务执行完后增加释放时间；②根据tcurr的开始时间增加获取时间。否则，资源rsel的释放时间将根据当前任务的完成时间进行更新。此外，令schedrj={ti|AR(ti)=rj}为资源rj上的调度任务集，AR(ti)为执行ti的分配资源。每个schedrj集合基于其任务完成时间进行排序。

2.3 问题定义

工作流调度即为寻找任务与资源间的映射关系，以满足用户定义的QoS参数。本文所讨论的调度问题的QoS参数主要包括工作流的总执行时间makespan和经济代价。

(1)执行时间makespan

为了计算给定工作流的执行时间，定义ti在资源rj上的处理时间TR为ti在资源rj上的执行时间ET(ti,rj)与其任意父任务tp∈pred(ri)传输的最大输入时间的要求时间之和，表示为

(1)

考虑到任务间的数据传输时间的存在性，对于每个在rj上执行的ti，资源rj需要在ti开始接收父任务传输数据之前进行部署，且仅在其完成和数据已传送至其子任务之后进行释放。令avail(tj)表示不考虑其父任务时ti在rj上的最早开始时间

(2)

其中，tl表示资源rj上的任务调度排序表schedrj中的最后一个任务，FT(tl,rj)表示tl在rj上的完成时间。基于avail(rj)，定义rj的释放时间RT(rj)为资源上最后调度任务的最后租用小时数

(3)

图1是简单调度，图1中t1、t2和t3已调度，t4是当前被选待调度任务。由式(3)及在3个资源上最后调度任务所使用的最后interval time可计算资源释放时间，此时，t4未被调度但已分配至目标资源。

图1 调度示例

ti在资源rj上的开始时间ST和完成时间FT可表示为

(4)

FT(ti,rj)=λ(ti,rj)+ST(ti,rj)+TR(ti,rj)

(5)

其中，λ(ti,rj)为资源rj的启动时间。如果ti可在rj的最后interval time上开始，则任务完成时不考虑启动时间；否则，需要启动目标资源rj，并将其启动时间考虑至任务完成时间中。例如，图1中，仅当t4调度至VM3时，启动时间才考虑至完成时间中，由于t4在VM3的当前释放时间之后才执行。λ(ti,rj)计算为

(6)

其中，boot_timerj表示VM的启动时间，实验中设置为97 s[16]。

工作流总执行时间makespan可定义为最后执行完成的任务(出口任务)的完成时间，即

DAGmakespan=FT(texit)

(7)

(2)执行代价cost

ti在资源rj上的执行代价根据任务完成的总资源使用时间计算，包括数据传输时间、执行时间和资源使用价格。对于Amazon EC2实例而言，不足一小时的资源使用仍支付整数小时代价，因此，如果任务能在已支付时间间隔内完成，则该任务无需支付费用。定义ti的总使用时间为需要支付的周期时间

(8)

如果ti在rj的当前释放时间RT(rj)之前开始且在其之后完成，则出现第3种情况。此时，RT(rj)之前的时间片需由之前的任务支付，且无需考虑在ti的当前使用时间之内。

对于第二种情况，如果任务在之前的支付时间间隔内执行(未完全利用)且未支付额外代价，则Ptime(ti,rj)=0。例如，图1中，如果当前t4被调度至资源VM2，则Ptime(t4,VM2)=0。通过式(8)，VM1的支付时间为Ptime(t4,VM1)=FT(t4,VM1)-RT(VM1)，对于VM3有Ptime(t4,VM3)=FT(t4,VM3)-ST(t4,VM3)。同时，通过式(5)，VM3的启动时间boot_time已考虑在FT(t4,VM3)内。

对于Ptime>0，任务ti在资源rj上的执行代价为

(9)

其中，Prj表示每个使用间隔中资源rj的使用代价，即表1中的价格。因此，工作流总执行代价可表示为

(10)

3 算法设计

本节设计截止时间与预算双QoS约束云工作流调度算法DBWS(deadline-budget constraint workflow scheduling)，旨在寻找满足双QoS约束的调度可行解。在满足截止时间约束的同时，如果执行代价也满足预算，则视为一种成功的可行调度，否则，视为调度失效。算法通过调度成功率进行评估。

为了便于算法描述，以下给出相关符号说明：

tcurr：表示当前调度任务，即所有就绪任务中在任务选择阶段中选择的目标任务；

rsel：表示执行任务tcurr的目标资源；

FTmin(tcurr)和FTmax(tcurr)：表示当前任务tcurr在所有测试资源上的最小和最大完成时间；

l(ti)：表示ti的分级，即从入口任务至ti间路径边的最大值。对于入口任务，其分级l(tentry)=1，对于其它任务

(11)

Costmin(tcurr)和Costmax(tcurr)：表示当前任务tcurr在所有测试资源上的最小和最大执行代价；

Costhigh(DAG)和Costlow(DAG)：表示将工作流调度至所有资源类型中代价最高和最低的异构VMs集合上的总执行代价。

算法分为两个阶段：任务选择阶段和资源选择阶段。

3.1 任务选择阶段

任务根据优先级进行选择。利用任务在工作流中的自顶向下分级值ranku赋予优先级，即：对于ti，其分级值为ti至出口任务texit间的最长路径的长度，包括ti的计算时间，表示为

ranku(tchild)}

(12)

其中，ETavg(ti)表示ti在所有资源上的平均执行时间，Tavg(ti,tchild)表示ti与其子任务tchild间的平均传输时间，succ(ti)表示ti的直接后继(子)任务集。对于出口任务则有：ranku(texit)=ETavg(texit)。

3.2 资源选择阶段

对于执行当前任务的目标VM资源的选择需要在双QoS的约束下同时考虑代价与时间的因素。为了选择最优资源，需要均衡时间与代价。定义SDL作为时间约束，表示总截止时间在每个任务的截止时间子分配。

首先，将任务根据其在工作流DAG中的深度进行不同的分级，定义Levelexe为对应分级中所有任务的最大执行长度

(13)

其中，ETmax(ti)表示ti在所有VM类型VMtype中的最大执行时间。

(14)

对于第一级，式(14)的前半部分为0。

最后，所有属于同一级的任务拥有相等子截止时间

(15)

需要说明的是，如果当前任务无法找到满足其子截止时间约束的执行资源，则选择能够最早完成该任务的资源执行。

为了在时间和代价同步最小上取得均衡，资源选择阶段需要考虑时间和代价两个QoS。定义TimeQ和CostQ分别为当前任务tcurr的时间质量和代价质量，对于资源rj∈R∪R’上的当前任务tcurr，R为调度前一步中使用的资源集，R’表示来自于可用VMtype中的一个临时资源集。在为任务tcurr选择了合适资源rsel之后的每一步中，R通过R={R∪rsel|rsel∉R}的方式进行更新。

通过式(16)和式(17)对时间质量和代价质量进行标准化处理

(16)

(17)

其中

(18)

TimeQ用来度量当前任务在rj上的完成时间与任务子截止时间SDL的接近程度。子截止时间定义了任务完成时间的最大限度。通常，资源的TimeQ值越高，则完成时间与子截止时间距离越大，该资源被选择的概率也越大。如果当前任务在rj上的完成时间高于其子截止时间，则rj的TimeQ值为负值，表明降低了该资源被选择的概率。类似地，CostQ用来度量当前任务在rj上的实际执行代价与最大执行代价的相差程度。

如果没有任一资源可确保当前任务的子截止时间SDL(tcurr)，则对于所有资源CostQ=0，对于每个rj的TimeQ值为负值，表明在rj上得到的相对完成时间，即：更低的完成时间导致更小负值。同时，资源的TimeQ值越高，被选概率也越大。

最后，为了选择最优目标资源，将两种QoS质量综合考虑，资源rj的质量Q表示为

Q(tcurr,rj)=TimeQ(tcurr,rj)×(1-CF)+CostQ(tcurr,rj)×CF

(19)

其中，CF表示代价均衡因子，定义为

(20)

可以看出，CF越低，表明用户越倾向于更快的执行工作流，时间质量TimeQ将在资源质量Q中占更大比重。同理，CF越高，表明用户可用预算更接近于最低执行代价，因此，时间质量TimeQ将被相对忽视，而代价质量CostQ将成为主要影响因素，并允许选择更低价的资源为执行tcurr确保更低的执行代价。

3.3 算法流程与时间复杂度

算法1给出DBWS算法的执行流程。

Input: workflow DAG with two QoS parameters,DuserandBuser

Output: schedule mapping

(1)compute and sort all tasks based on their upward rank

(2) compute schedule cost on the resources with cheapest (Costlow) and most expensive (Costhigh) cost fromVMtype

(3) ifBuser

(4) return no possible schedule map

(5) else ifBuser>Costhigh(DAG)

(6) return PEFT scheduled map on most expen-siveVMtype

(7) end if

(8) compute the Sub-Deadline value (SDL) for each task

(9) while there is an unscheduled task do

(10)tcurr=the next ready task with highestrankuvalue

(11) for allrj∈R∪R’

(12) calculate QualityQ(tcurr,rj) by Eq.(19)

(13) end for

(14)rsel=resourcerjwith highest Quality (Q)

(15) assign current tasktcurrto resourcersel

(16) updateR={R∪rsel|rsel∉R}

(17) updateVMr/a(rsel)

(18) end while

(19) return schedule map

算法详细说明：步骤(1)、步骤(2)进行初始化，步骤(3)检测是否存在预算约束内的调度映射解。步骤(8)通过式(15)计算每个任务的子截止时间，然后，通过重复执行步骤(9)～步骤(18)映射工作流任务。步骤(10)中，选择所有就绪任务中拥有最高优先级(ranku)的任务作为当前调度任务tcurr。步骤(11)～步骤(13)中，计算tcurr的调度资源rj的质量Q(tcurr,rj)。此时，首先计算当前任务的完成时间FT和执行代价，然后计算所有资源的质量，步骤(14)选择所有资源中拥有最高质量的作为被选资源rsel。最后，分配当前任务至所选资源后，更新资源rsel的释放/获取时间戳。

时间复杂度分析。DBWS算法需要计算每个任务的自顶向下分级ranku和子截止时间SDL，该步骤的时间复杂度为O(n×p)，其中，p为可用资源数量，n为任务数量。在资源选择阶段，为了给当前任务寻找和分配资源，在所有资源间计算当前任务的ST和FT的时间复杂度为O(n×p)，计算资源质量的时间复杂度为O(p)，则总时间复杂度为O(n×p+n×(n×p+p))=O(n2×p)。

4 仿真实验

本节通过WorkflowSim的仿真实验评估算法性能，选择4种调度算法进行性能比较，包括：HYBIRD算法[11]、MTCT算法[17]、CWFT算法[18]和SABA算法[8]。选择4种常见科学工作流作为测试数据结构[19]，包括：CyberShake、Epigenomic、LIGO和Montage，CyberShake和LIGO存储需求更大，Epigenomic属于CPU-bound型工作流，Montage属于I/O-bound型工作流，同时CyberShake还属于数据密集型工作流。基于数据多样性，为每种工作流随机产生100个工作流DAG，每种工作流的任务数量设置为100、200和300。

4.1 截止时间和预算约束设置

定义截止时间和预算为

Duser=minD+αD×(maxD-minD)

(21)

Buser=minB+αB×(maxB-minB)

(22)

其中，minD和maxD分别表示将工作流调度至代价最小和最大的资源集合上执行时得到的总执行时间makespan，而此时对应的工作流执行代价则分别为maxB和minB。通过这种设置截止时间和预算的上下限方式，可以确保两种QoS约束的实际可行。

公式中，αD和αB分别表示截止时间因子和预算因子，αD、αB∈[0,1]。为了观察算法寻找有效调度解的性能，设置αD、αB为{0.1,0.3,0.5}进行了测试。

4.2 性能指标

选择调度成功率SR作为指标，该指标给出实验中算法进行有效调度的百分比，成功调度的衡量方式为同时满足截止时间与预算约束的一次工作流调度过程

(23)

此外，分别选择截止时间与完成时间makespan的比例、预算与工作流调度代价的比例作为另一性能指标，分别表示为

NM=Duser/DAGmakespan

(24)

NB=Buser/DAGcost

(25)

NM和NB比较1越小，则表明调度方案越无法满足约束。

4.3 结果分析

图2～图5是算法的平均调度成功率结果。DBWS比较其它算法得到更高的成功率。同时，通过增加预算因子αB，对于工作流将拥有更多的可用预算，导致DBWS的平均SR会进一步增加。而在较短的截止时间内(αD=0.1)，在4种工作流的大多数情况中，仅有DBWS可以完成调度工作流(图3～图5)。

图2 CyberShake工作流

图3 Epigenomic工作流

图4 LIGO工作流

图5 Montage工作流

图6和图7是算法的NM和NB情况。如果NM>1，表明算法可以得到makespan低于截止时间的调度解，反之亦然。NB也是同理。图6中，DBWS得到的调度解makespan在所有预算因子下总可以满足截止时间约束。然而，对于图7中的总执行代价，通过降低截止时间因子，DBWS的调度解执行代价会高于预算约束。图2～图5中的SR指标所表示的是同时满足时间和代价约束的调度工作流的比例。例如：尽管图7中的CWFT算法极大降低了执行代价，但在图6中却无法满足截止时间约束，其SR指标是所有算法中最差的。SABA的SR指标上则在大多数情况下均无法得到成功调度。主要是该算法没有考虑执行代价的控制，因此，图6～图7显示出SABA算法在降低总执行时间上拥有最好的性能，而代价方面则是最差的。

图6 NM指标

图7 NB指标

5 结束语

为了满足截止时间和预算的双QoS约束，提出了一种云工作流调度算法DBWS。算法将工作流调度划分为任务选择和资源选择两个阶段。任务选择阶段中利用任务的自项向下分级值为任务分配调度优先级。然后，在资源选择阶段中，将用户定义的截止时间在不同分级任务上进行子截止时间分配，并通过时间质量和代价质量寻找最优的目标资源。实验结果表明，DBWS算法在调度成功率和同步满足两种QoS约束上性能是更优的。