一种任务合并机制下的云工作流多阶段调度方法

2019-12-12黄志刚

计算机应用与软件 2019年12期

黄志刚刘峰

1(湖南科技职业学院湖南长沙 410004 )2(长沙理工大学计算机学院湖南长沙 410082)

0 引言

工作流是复杂计算问题的常用建模方式，云计算特有的按需提供和即付即用的资源定制模式使得云环境下进行调度工作流变得更为复杂[1]。工作流任务结构与传统批或包任务的调度方法极为不同，工作流任务通常拥有严格的执行次序，或称逻辑依赖，需要在满足用户指定的服务质量约束的前提下，对各任务实现与其对应虚拟机资源的映射。工作流调度过程中的调度任务选择与虚拟机实例提供决策对于是否能够满足给定约束和全局调度代价均具有重要影响[2]。传统的调度方法偏向于关注调度效率，忽略了资源利用费用，此时的调度问题在不同资源和不同调度方案下的执行时间和代价均有所不同。因此，云环境下需要同步考虑用调度时间和调度代价，这更符合云工作流的调度场景[3]。

有关研究中，文献[4]设计了基于执行时间和调度费用的多目标工作流调度算法，作者将多目标转化为单目标优化进行了优化方案的求解，但却忽略了云资源虚拟机的性能变化，仅讨论了同质资源的情形。文献[5]设计基于局部关键路径的调度算法IC-PCP，IC-PCP优先将处于局部关键路径上的任务调度至最低代价虚拟机上执行，避免了每个局部关键路径的通信代价，实现截止时间的约束，但算法却忽略了虚拟机的启动和部署时间，这在实际场景中占比较重。文献[6]中提出的RTC和RCT算法是分别针对执行时间优先和执行代价优先提出的工作流调度最优化算法，均是单目标无约束式优化，费用与时间只考虑了一种，不符合云工作流实际调度特征。与上文不同，文献[7]提出一种基于粒子群的工作流调度优化算法，虽然考虑了资源提供弹性与异构特征，但利用智能优化算法仍然无法摆脱时间复杂度过高和早熟问题。文献[8]在混合云中设计一种整数非线性规化方法求解工作流调度，其目标是满足截止时间约束最小化执行总代价。文献[9]提出一种动态规化方法处理多约束工作流调度问题，但没有考虑多类型异构虚拟机提供场景。

本文将设计时间复杂度更低的工作流调度算法，满足截止时间的同时寻找工作流调度优化最优可行解。本文设计了一种代价优化的工作流调度算法WSCO，算法着重考虑了云资源提供时虚拟机性能的动态性和异构性，最终实现在不同要求的截止时间约束程度下的工作流调度代价的最小化。

1 系统模型

1.1 应用模型

云计算工作流应用W=(T,E)可表示为有向无循环图DAG，T={t1,t2,…,tn}代表任务的图顶点集，E代表任务间数据传输关系的有向边集，边eij表示任务对(ti,tj)间的顺序约束关系，ti,tj∈T,ti≠tj，表明任务tj(子任务)只能在ti(父任务)完成并传输相关数据后才可以开始执行。换言之，子任务在其所有父任务完成且数据传输完成之前是无法执行的。截止时间D用于限定所有工作流任务完成的最后期限。工作流示例如图1所示，每个节点代表一个任务，边值代表任务间的数据传输时间。

图1 工作流示例

1.2 资源模型

云资源由IaaS云服务提供者提供的虚拟机资源构成，假设所有计算或存储资源处于同一数据中心内，则服务间的带宽是相同的。计算资源由不同类型的虚拟机VMs提供，各VMs类型拥有不同的CPU类型、内存大小和定价。假设应用任务租用的VM实例数量不受限制，且一个VM被租用时，需要有启动时间进行初始化。相应地，VM被释放时，需要有一定的关机时间停止服务。VM定价模型使用基于即付即用的帐单策略(与商业云Amazon EC2相似)，用户根据租用VM的时间间隔Tintervals进行付费，Tintervals由云提供商定义，如Amazon以一小时作为付费间隔。因此，即使VM利用不足一小时，也将以一小时付费。云资源模型中，将VM类型VMv定义为一个二元组{(ETti)v,Cv}，描述每个任务ti的估计计算时间和每个Tintervals的代价。任务ti执行于VMv类型的VM上的代价计算为：

调度于不同VM的任务间的数据传输时间TT(eij)计算为dti/β，其中，dti为ti与tj间的输出数据量，β为数据中心的带宽。当两个任务调度于同一VM时，TT(eij)=0。

1.3 问题定义

本文的目标是寻找工作流的调度方案，使得执行代价达到最小，并且满足用户定义的截止时间要求。为了得到截止时间限定下的调度方案，首先需要确定截止时间是否可达，若不可达，调度问题将没有可行解，需要修正截止时间。在截止时间内可完成的情况下，目标即是在截止时间约束下为每个任务寻找合适的调度决策，进而实现调度代价的最小，该过程涉及以下三个决策问题：

1)cheapesttask-VMmapping：代价最低映射，用于为等待调度的每个任务寻找代价最低的VM类型：

cheapesttask-VMmapping={(ti→VMv)}

2)ProvisioningPlan：用于基于运行任务的状态和等待任务的cheapesttask-VMmapping确定不同阶段工作流执行时每种VM类型的利用数量。定义资源池中的每一个VMvk均拥有类型type、开始时间stk及结束时间etk等属性：

VMPool={vk,type(vk),stk,etk}

3)SchedulingPlan：用于决定任务ti调度于资源池中的哪个VM类型vk及任务相应的估计开始时间tstart和结束时间tend：

Schedule={ti,vk,tstart,tend}

算法目标是寻找工作流应用W的调度方案S，使得工作流的调度总代价达到最小，并且总体执行时间TET不超过截止时间D的约束，可形式化为：

(1)

s.t.TET≤D，TET=maxti{AFT(ti)}

2 相关说明与定义

文中涉及的主要符号含义说明如表1所示。

表1 符号说明

续表1

1)MET(ti)：任务ti的最小执行时间定义为任务ti在所有可用VM类型中，在拥有最小执行时间ET(ti,VMv)的VM实例类型VMv∈VMset上执行时得到的时间，表示为：

(2)

2)EST(ti)：任务ti的最早开始时间定义为其所有前驱任务在最快VM类型上调度且关联数据已传送至ti时的开始执行时间，表示为：

(3)

3)EFT(ti)：任务ti的最早完成时间定义为：

EFT(ti)=EST(ti)+MET(ti)

(4)

4)XFT(ti)：任务ti调度至VMvk时的期望完成时间定义为：

(5)

5)XST(ti)：任务ti的期望开始时间定义为其所有前驱调度后ti开始执行的估计时间，表示为：

(6)

6)XIST(vk)：资源池中一个活动VMvk的期望空闲开始时间为vk期望完成其上调度的最近任务的时间。若tp为调度于vk的最近任务，则vk的期望空闲开始时间为：

(7)

7)LFT(ti)：任务ti的最迟完成时间定义为所有任务在工作流截止时间D之前完成时ti完成的最迟时间，表示为：

(8)

8)LST(ti)：任务ti的最迟开始时间定义为所有任务在工作流截止时间D之前完成时ti开始执行的最迟时间，表示为：

LST(ti)=LFT(ti)-MET(ti)

(9)

9)XET(ti,VMv)：VM类型VMv上从任务ti开始的关键路径(最长执行路径)的期望执行时间定义为从ti开始执行整个关键路径任务的总时间，表示为：

(10)

10)MET_W：工作流最小执行时间为所有任务均执行于最快VM时的关键路径长度(时间)，即最长的执行路径，表示为：

(11)

11)CLI(vk)：租用VMvk的当前租用间隔定义的是该VM被租用索价的时间跨度。给定vk提供的时间stk，帐单的时间单位Tintervals以及当前的Tintervals(n)，则CLI(vk)可表示为：

CLI(vk)=[stk,stk+n×Tintervals]

(12)

3 算法设计

算法1给出了WSCO算法的伪代码。算法首先需要验证截止时间D的可达性。对于可达的截止时间，需要大于工作流的最小执行时间MET_W。因此，算法首先评估MET_W并将其与截止时间D作比较，若D大于MET_W，算法继续寻找合适的调度；否则，用户将修正截止时间D。一旦确定了截止时间的可达性，算法通过预处理步骤和控制循环过程确定所需的调度方案。预处理步骤通过合并管道任务为单个任务降低算法运行开销，控制循环过程维持运行任务的更新信息并相应为等待的未调度任务作出调度决策。以下对算法作详细描述。

算法1WSCO算法

输入: 工作流W(T,E) ，代价矩阵C，执行时间矩阵ET，传输时间TT，截止时间D以及作务请求间隔

1.开始

2. 以式(2)(3)(4)(11)计算MET_W

3. 若D>MET_W

4. 调用算法2进行管道任务合并

5. 计算MET,LFT和XET

6. 寻找工作流结构的根节点为{tentry}

7.for每个属于{tentry}中的任务te

8.To_Provision←CheapesttaskVMMap(te)

//调用算法4

9. 生成类型为To_Provision的虚拟机ve

10. 在时间XST(te)时将te调度至ve

11. 更新虚拟资源池VM_Pool_Status

12.结束for循环

13.whileT中所有任务未完成

14. 发送调度任务至执行管理器

15. 更新任务AST，XFT

16. 将任务ti的父任务集中被调度和正在运行的任务组成任务集合to_be_scheduled

17. 在任务集to_be_scheduled上调用算法3

18.结束while循环

19.结束

20. 在MET_W以内修正截止时间

21.结束if

22.结束

3.1 任务预处理

为了降低任务运行时开销，算法通过任务预处理过程将管道任务合并为单个任务执行，如图2所示。预处理可以节省任务间通信的数据传输时间，加快动态调度方案的生成。图3为预处理示例，任务t1和t2可合并为任务t1+t2，这使得t2可以在与t1相同的资源上执行并在本地直接利用t1的执行结果，避免t1与t2在不同资源上执行时的数据传输时间，降低循环控制过程中的运行开销。预处理步骤的执行过程如算法2所示。

图2 管道任务

图3 合并管道任务

算法2Pre-processing(W)

输入: 工作流W(T,E)

1. 开始

2. 入口任务{tentry}置入初始任务队列tksqueue

3.while任务队列tksqueue非空

4. 队首任务赋予tp

5.tp的子任务置入Sc

6.ifSc的基数为1且tc仅有一个父任务tp

7. 合并tp和tc为tp+c

8. 设置tp+c为tc子任务的父任务

9. 新任务执行时间ET(tp+c)

10. 添加合并任务tp+c至队首

11.else

12. 添加tp的子任务至队列tksqueue的队尾

13.结束if

14.结束while循环

15.end

3.2 循环控制过程

预处理后，算法提供代价最低的可用资源(cheapestapplicable)用于执行工作流入口任务，然后进入循环控制过程。由于入口任务是第一个调度任务，故入口任务的期望开始时间XST设置为期望VM获取时间(expectedVMacquisitiontime)。在每次循环控制中，算法更新调度运行任务的实际开始时间AST，确定父节点已被调度的任务及将运行(to-be-scheduled)的任务，然后利用PlanandSchedule算法作出合适的调度决策。循环控制过程直到所有工作流任务被调度时结束。在每一阶段中，任务的cheapestapplicableVM类型由CheapesttaskVMMap算法决定，若T时刻请求一个新的VM，则此时确保VM可用的expectedVMacquisitiontime也为T。

1) PlanandSchedule算法。PlanandSchedule算法接收一个任务集作为输入，并将其调度至合适(appropriate)VM实例上。与CheapesttaskVMmap算法一致，该算法寻找最小代价且拥有最小数据传输时间的调度方案。算法试图将一个任务调度至最后一个父节点(拥有最大期望完成时间XFT的父任务)相同的资源上，以避免调度在不同资源时的数据传输。PlanandSchedule如算法3所示。

算法3PlanandSchedule算法

1. 将虚拟机池中的活跃虚拟机列表赋予Active_VMs

2.for任务列表中的每个任务t

3.vmmap←CheapesttaskVMMap(ti)

4. 寻找满足约束条件的目标虚拟机集合

5.if{vk}存在

6. 寻找XIST(vk)与XST(ti)差值最小的虚拟机vk

7. 在vk调度任务ti并更新XST(ti)

8. 更新虚拟机资源池VM_Pool_Status

9.else

10. 寻找满足约束条件的目标虚拟机集合

11.if{vj}存在

12. 寻找XIST(vj)与XST(ti)间差值最小的虚拟机vj

13. 在vj上调度任务ti并更新XST(ti)

14. 更新虚拟机资源池VM_Pool_Status

15.else

16. 生成新虚拟机

17. 按XST在v上调度任务ti

18. 更新虚拟机资源池VM_Pool_Status

19. 结束if

20.结束if

21.结束for循环

22. 撤销关闭空闲虚拟机

23.返回

对于任务列表中的任务ti，PlanandSchedule算法调用CheapesttaskVMmap算法(即步骤3)得到调度ti的cheapestapplicableVM类型vmmap。由于VM按完整的时间间隔Tintervals收取费用，因此为了尽可能密集地利用VM，PlanandSchedule算法试图决策是否ti能够在当前租用间隔CLI结束前调度于已经租用的VM上。为了完成这个目标，算法首先寻找与vmmap同类型且满足以下条件的活动VMs {vk}：

(1) 若ti调度于vk，ti仅利用CLI(vk)的剩余时间部分；

(2)ti的期望完成时间小于或等于ti的最迟完成时间；

(3) 若ti调度于vk，不存在任一ti的子任务tc，使得tc的期望开始时间大于tc的最迟开始时间。

若该活动VM集合存在，则从该集合中选择拥有最小期望空闲开始时间XIST与期望开始时间之差的VMvk用于调度ti。XST(ti)与VM_Pool_Status通过步骤4-步骤8进行更新；否则，PlanandSchedule算法试图寻找活动VMs{vj}，使得type(vj)≥vmmap且以下条件得到满足：

(1) 若ti调度于vj，ti可在CLI(vj)的剩余时间内完成；

(2)ti的期望完成时间小于或等于ti的最迟完成时间；

(3) 若ti调度于vj，不存在任一ti的子任务tc，使得tc的期望开始时间大于tc的最迟开始时间。

若该活动VM集合存在，则从该集合中选择拥有最小期望空闲开始时间XIST与期望开始时间之差的VMvj用于调度ti。XST(ti)与VM_Pool_Status通过步骤10-步骤14进行更新；若不存在活动VMs可利用于调度ti，则需要从云端生成新的VM类型vmmap调度ti，即步骤16-步骤18。任务列表中的所有任务调度后，PlanandSchedule算法需要查证无任务调度的空闲VMs及已完成任务的VMs，即步骤22。

2) CheapesttaskVMmap算法。CheapesttaskVMmap算法接收一个任务t作为输入，并返回其cheapestapplicable的VM类型taskvmmap。尽管cheapestapplicable的VM类型可以在任务的最迟完成时间内完成任务，但可能不是最优选择，这是因为选择代价最小的VM类型并未考虑对其子任务的影响，即可能迫使子任务执行于更快的VM而增加了总代价。因此，算法将任务的cheapestapplicable的VM类型定义为代价最小类型的单个VM，若利用该VM类型调度关键路径上从t开始的所有任务，则可在截止时间D内完成全部关键路径任务的执行，即所讨论的目标是利用最小的可能数据传输时间寻找最小代价的调度方案。因此，若任务t无需等待即可得到VM上一个空闲(免费)的时间间隔，则算法将确认任务t是否能够调度于其最后的父任务(拥有最大期望完成时间的父任务)相同的VMvp上。若t调度于vp，XST(t)将被首次评估并与XIST(vp)比较。若XIST(vp)小于XST(t)(表明vp在t的期望开始时间上是空闲的，可用于调度t)，调度于vp上可确保在截止时间D前完成执行，然后可将taskvmmap设置为type(vp)，并更新XST(t)，即步骤4-步骤10。然后，PlanandSchedule算法将任务t调度于vp。否则，利用以下规则(步骤12-步骤18)更新XST(t)和对于t的taskvmmap：

(1) 确定VM类型集合{VMk}，使得从t开始的关键路径若调度于类型VMk的单个VM上，可以D内完成执行；

(2) 从集合{VMk}中确定VM类型VMj，可使得该关键路径的总执行代价最小。

算法4CheapesttaskVMMap(t)算法

1. 开始

2. 映射集合taskvmmap置空

3. ift不是入口任务

5. 将正在运行最后一个父任务的虚拟机赋予vp

7. if((temp≥XIST(vp))且(temp+XET(t,type(vp)))≤D)

8.XST(t) ←temp

9.taskvmmap←type(vp)

10. 返回映射集合taskvmmap

11.else

13.结束if

14.else

15.XST(t) ←acquisitiondelay

16.结束if

17. 寻找满足(XST(t)+XET(t,VMk))≤D的集合{VMk}

19. 将虚拟机VMj置入映射集合taskvmmap

20. 返回映射集合taskvmmap

3.3 算例说明

本节通过一个算例说明算法的执行过程。以图4作为工作流示例，包括9个任务t1-t9，边上的数值表示任务间的数据传输时间。设有三种VM类型{VMs,VMm,VMl}(s-small,m-medium,l-large)用于工作流任务的执行。图5是任务在各VM上的执行时间矩阵和数据传输时间矩阵,图6是合并管道任务后的工作流结构。最小租用时间间隔设置为10 min，VM获取延时acquisitiondelay设置为1 min，每个时间间隔的代价设置为：smalle类型VM为＄0.01，medium类型VM为＄0.02，large类型VM为＄0.04，截止时间设置为50 min。

图4 工作流示例

(a) 执行时间矩阵 (b) 数据传输时间矩阵图5 执行时间矩阵和数据传输时间矩阵

图6 预处理后的工作流结构

算法首先需要通过式(2)、式(3)、式(4)计算每个任务的最小执行时间MET、最早开始时间EST和最迟完成时间EFT，计算结果如表2所示。然后，比较工作流的最小执行时间MET_W(max(EFT(ti)=49))与截止时间D(D=50)，由于MET_W小于D，表明截止时间是可达的，算法需要继续寻找调度方案。

表2 图4中工作流各任务的MET、LFT和XET

首先，通过算法2进行任务预处理。算法2通过合并管道任务t4、t7和t8、t9为单个任务t4+7和t8+9，预处理后的工作流结构如图6所示，预处理后的执行时间矩阵和数据传输时间矩阵如图7所示。

(a) 执行时间矩阵 (b) 数据传输时间矩阵图7 预处理后的矩阵

预处理后，WSCO算法通过式(2)、式(8)、式(10)计算每个任务的最小执行时间MET、最迟完成时间LFT和期望执行时间XET，结果如表3所示。

表3 图6中各个任务的MET、LFT和XET(D=50)

然后，算法调用CheapesttaskVMmap算法寻找代价最低的VM类型调度入口任务t1。CheapesttaskVMmap算法设置XST(t1)为acquisitiondelay，并寻找执行代价最小的VM类型。由于三种VM类型中，XET(t1,VMm)和XET(t1,VMl)均小于D，算法比较在这两种VM类型上执行从t1开始的关键路径得到的代价，并确定VMm为调度t1的cheapestapplicableVM。然后，算法获得VMm类型的一个VM进行调度t1，并更新VM池状态。算法在步骤13输入while循环，并执行循环过程直到所有任务调度完成。表4-表7列出了算法执行过程中任务不同参数的取值变化。

表4 初始状态

表5 第1次迭代结果

表6 第2次迭代结果

表7 第3次迭代结果

4 仿真实验

4.1 实验配置

利用WorkFlowSim[10]构建仿真实验评估工作流调度算法性能，选取四种不同领域的现实科学工作流作为测试工作流结构，包括：Montage、CyberShake、LIGO和Epigenomics工作流，不同工作流在执行结构和计算特征上均有所不同，具体可参见文献[1]。每种工作流均配置三种规模的任务，小规模为30个任务，中规模为100个任务，大规模为1 000个任务。

云服务商提供五种类型VM，其配置与处理能力参考Amazon EC2进行设置[11]，具体见表8，其中，一个ECU等同于1.0～1.2 GHz的Xecon CPU计算能力，VM间的平均带宽设置为20 Mbit/s，接近于Amazon web service的平均带宽能力。VM的启动时间设置为97 s[12]，账单间隔时间设置为10 min。

表8 VMs类型配置

设置三种截止时间类型评估算法性能，包括严格型、适度型和宽松型，截止时间D=(1+μ)×MET_W。对于严格型截止时间约束，0≤μ<1;对于适度型截止时间，1≤μ<2;对于宽松型截止时间，2≤μ≤3。且μ可视为约束因子，μ的变化步长为0.25。选择基于部分关键路径算法IC-PCP[5]、健壮代价时间算法RCT[6]和健壮时间代价算法RTC[6]作为基准算法进行性能比较。

4.2 结果说明

1) 截止时间约束的评估。表9给出了算法满足截止时间比例的情况。对于严格型约束，IC-PCP在所有工作流中均无法满足截止时间约束，RCT在四种工作流中按从高到低的满足率分别为52.5%、47.5%、40%和37.5%，RTC则比RCT的约束满足率更高，而WSCO是所有算法中对截止时间约束满足最好的。对于适度型约束，IC-PCP的性能并未得到改善，RCT在先前的基础上得到了轻微改善，RTC和WSCO则均达到了对截止时间100%的约束满足。对于宽松型约束，IC-PCP性能不变，RCT继续提高。可以看出，IC-PCP性能最差，这源于此算法并未预测VM的性能改变，且未考虑VM的启动时间，RCT和RTC基于资源选择策略，一定程度上忽略了VMs的性能变化，WSCO同时考虑了以上因素，能够估算单个任务的开始时间和完成时间，可以尽可能地确保截止时间内完成任务调度。

表9 截止时间满足比例

续表9

2) 执行时间与执行代价评估。图8同步观察了平均执行时间和平均执行代价情况，由于为了产生更加经济的调度方案需要以更长的调度时间作为代价，故需同步观察这两个性能表现。可以看到，IC-PCP产生了最便宜的调度方案，但其执行时间长于截止时间，无法满足截止时间约束。由于算法设计的目标是生成更高低价的调度且满足截止时间，因此，以对截止时间违例得到的经济调度方案也是无效的。另外三种算法中，RCT在所有约束因子上均产生了最经济的调度方案，且调度时间也最长，但约束满足率平均仅为50%。对于0～0.25间的严格型约束，WSCO产生了最高代价调度但其调度时间最短，且其约束满足率也高于其他算法，这是由于该算法通过适应VM的性能变化能以可接受的代价降低截止时间的违例。同时，在同样的条件下，RTC以最小的调度时间产生了最高代价的调度。比较来说，随着约束因子的增加，WSCO可以充分利用增加的VM空闲时间在满足截止时间约束的同时得到最低价的调度。进一步，对于所有的截止时间约束因子，平均来说，WSCO相比RTC可以降低34%的代价和增加46%的调度时间，相比RCT可以降低28%的代价和降低16%的调度时间。因此，综合评价，WSCO可以降低代价并满足截止时间来交付，比对比算法有着更好的性能表现。对于严格型约束，算法可交付最高的约束满意率，代价也更高。然而，随着约束变得宽松，WSCO也可充分利用增加的空闲时槽进而降低执行代价。