多云环境下带截止日期约束工作流的基于代价驱动调度方法

技术领域

本发明属于并行和分布式高性能计算领域的工作流调度方法，具体涉及一种 多云环境下带截止日期约束工作流基于代价驱动和局部关键路径特征的调度方 法。

背景技术

近年来随着云计算技术的普及，当前云市场上出现了许多不同的云服务提供 商，如GoGrid,AmazonEC2和Rackspace。根据具体服务提供内容的差异，服 务类型可分为：基础设施即服务(InfrastructureasaService,IaaS)，软件 即服务(SoftwareasaService,SaaS)和平台即服务(PlatformasaService, PaaS)。终端用户通过与服务提供商之间订立的服务等级协议(ServiceLevel Agreements,SLAs)来保证自身应用的服务质量，并以按需付费的方式支付相应 的执行费用。云计算强大的并行计算能力，使许多科研工作者着手研究大规模科 学工作流在云计算环境中的优化调度问题，云平台中工作流调度效果的优劣直接 影响到整个系统的作业性能。任务调度本身就是一个NP完全问题，由于不同服 务提供商之间存在许多差异(如实例类型，要价机制，传输带宽等)，所以终端 用户需要一种良好的调度策略来保证其工作流约束前提下，尽可能降低用户代 价，这是一个带约束的单目标优化问题。虽然许多相关研究工作已在传统分布式 环境中展开，但涉及云环境的工作流调度研究工作却相对较少，特别是在IaaS 多云环境中处理带截止日期约束的复杂工作流调度问题。

工作流调度是一个传统的优化问题，它是在满足某些给定的约束前提下，将 工作流中的每个任务按序分配到对应资源中，从而获得最佳的预期结果。早期的 研究工作主要基于较为传统的多机处理时代，现有研究工作大多是针对共享社区 环境(如社区网格)的工作流调度问题而展开。无论是多机处理时代，还是社区 网格环境，涉及工作流的研究工作主要是考虑最小化工作流执行时间或满足用户 服务质量需求，并未涉及工作流执行代价的研究。

传统分布式环境的工作流调度科研成果为云环境下工作流研究提供一定的 借鉴作用。然而，它们并非完全适用于按区间要价并以利益为驱动的云计算环境。 现有云环境下的研究工作主要是基于代价优化目标而展开。然而许多研究工作仅 仅在多云环境下追求代价最优，而忽略其他约束条件，如截止日期；或者仅在单 云环境下考虑带约束条件的工作流代价优化调度，并未涉及不同带宽的多云环境 对工作流执行代价影响；或者忽略任务间的复杂依赖关系而仅考虑多云环境下批 任务调度问题；或者在追求工作流代价最优过程中，没有考虑云环境按需付费， 按区间要价的基本性质。因此，多云环境下，带截止日期约束的大规模工作流执 行代价的优化调度问题仍未得到妥善解决。

发明内容

本发明的目的是提供一种在多云环境下基于工作流自身结构和执行特性，以 及当前云资源环境等相关因素考虑的工作流调度方法，该方法基于局部关键路径 思想，压缩数据传输路径和任务间的数据传输时间，有效整合虚拟化资源，在满 足工作流截止日期约束的前提下，优化资源利用率，有效提高方法本身的执行效 率，并大幅度减少工作流在多云环境下的执行代价。

本发明采用以下技术方案实现：一种多云环境下带截止日期约束工作流的基 于代价驱动调度方法，其特征在于，包括以下步骤：步骤S1：输入工作流w， 用有向无环图G(Vertex,Edge)来表示工作流w，其中Vertex是一个含有n个任务 节点的有限点集{t₁,t₂,...,t_n}，而Edge则用来表示任务之间数据传输依赖关系的 有限边集{e₁₂,e₁₃,...,e_ij}，每条数据依赖边e_ij＝(t_i,t_j)代表任务t_i和任务t_j之间存 在数据传输依赖关系，其中任务t_i是任务t_j的直接父节点，而任务t_j则是任务t_i的直接子节点，e_ij的大小表示任务t_i到任务t_j的数据传输量；在工作流调度过 程中，一个任务必须在其所有父节点都已被执行完毕后，该任务才能开始执行， 没有父节点的任务称为入任务，没有子节点的任务称为出任务；步骤S2：执行 调度策略前预先分别加入一个零代价的伪入任务节点t_伪入任务和伪出任务节点t_伪出任务，将伪入任务与真实入任务通过零依赖边相连，将真实出任务与伪出任务通过 零依赖边相连；步骤S3：迭代合并其中存在有向割边相邻任务，所述有向割边 的为一条有向边，其出节点的出度为1，且其入节点的入度为1；步骤S4：确认 不同服务提供商P＝{p,q,...,r}所提供的有效计算服务类型S_p＝{s_p1,s_p2,...,s_pm}； 步骤S5：计算工作流w中所有任务的EFT(t_i)、EST(t_i)、LFT(t_i)及LST(t_i)；所述 EFT(t_i)表示在任务t_i未调度前的理想最早完成时间，其计算公式如下： 其中T_exe(t_i,s_pj)表示任务t_i在实例s_pj上的执行时间； Tboot(vm_pj)表示实例s_pj的初始化启动时间；EFT(t_j)表示EFT(t_j)表示在任务t_j未调 度前的理想最早完成时间；TE(e_ji,p)表示数据依赖边e_ji在云服务提供商preP_E(t_j) 和p之间的数据传输时间；preP_E(t_i)表示已计算EFT(t_i)的任务t_i对应的最早倾 向云，最早倾向云为在云服务提供商集合P中使任务t_i取得最小EFT(t_i)对应的 提供商；EST(t_i)表示未调度任务t_i的最早开始时间， EST(t_i)＝EFT(t_i)-MET(t_i,preP_E(t_i))；LFT(t_i)表示任务t_i最迟完成时间， LFT(t_i)＝LST(t_i)+MET(t_i,preP_L(t_i))，其中LST(t_i)表示任务t_i未被调度前的理想 最迟开始时间；preP_L(t_i)表示已计算LST(t_i)的任务t_i对应的最迟倾向云，最迟倾 向云为所有云服务提供商集合P中使任务t_i取得最大LST(t_i)对应的提供商；LST(t_i) 计算公式：TL(e_ij, p)表示数据依赖边e_ij在云服务提供商p和preP_L(t_j)之间的数据传输时间；D(w) 为整个工作流w能在其对应的截止日期；

步骤S6：标记t_伪入任务及t_伪出任务为已调度任务；步骤S7：若任务t_i不存在未调 度直接父任务直接输出调度方案，若存在未调度直接父任务执行步骤S8；步骤 S8：查找任务t_i的局部关键路径PCP(t_i)，整体调度PCP(t_i)到其对应的最佳 实施例s_p,j,k，标记PCP(t_i)上每个任务为t_j已调度；步骤S9：更新t_j所有未调 度父任务的LSTs及LFTs,更新t_i所有未调度子任务的LSTs及LFTs，返回步骤 S7。

在本发明一实施例中，所述步骤S3包括以下具体步骤：构造一个父亲儿子 图矩阵father-son[][]判定父节点是否仅有一个儿子节点，且该儿子节点入度为1， 并以该儿子节点为新的父节点迭代寻找新的有向割边；将寻找到的有向割边删 除，合并对应的两个任务，更新新任务的数据传输量和相应执行时间，重新扫描 全局，直到新生成的工作流中不存在有向割边。

在本发明一实施例中，所述步骤S5中当出现两个以上提供商使任务t_i取得 对应最早完成时间，则选取编号小的提供商作为任务t_i的最早倾向云。

在本发明一实施例中，所述步骤S8中整体调度PCP(t_i)到其对应的最佳实 施例s_p,j,k需要同时满足以下条件：条件1：s_p,j,k对应于局部关键路径PCP(t_i)的 执行代价增值Cgrow(s_p,j,k,PCP)最低，Cgrow(s_p,j,k,PCP)＝c_pj·(T₂-T₁)+Cdata，其 中T₁是实例s_p,j,k在执行PCP(t_i)之前，其已运行的窗口时间，T₂是在执行PCP(t_i) 之后实例s_p,j,k所运行的总窗口时间，Cdata为增值的数据传输代价；条件2：对 于某个局部关键路径PCP(t_i)，如果存在两个或两个以上实例满足条件1，则选择 产生Cdata最小的实例s_p,j,k作为最佳实际；条件3：对于某个局部关键路径 PCP(t_i)，如果存在两个或两个以上实例同时满足条件1和条件2，则选择剩余时 间最多，即当前窗口时间减去实际执行时间的差值最多的实例s_p,j,k作为最佳实 例。

在本发明一实施例中，算法的更新调度局部关键路径包括以下步骤：输入一 条带局部截止日期约束的局部关键路径PCP，更新当前多云环境中虚拟资源和所 有未调度子任务的状态，整体调度PCP到相应的最佳实例上，并在对应的局部 截止日期前执行完成PCP上的所有任务。

进一步的，整体调度PCP到相应的最佳实例上包括以下步骤：利用贪心选 择策略寻找执行PCP代价增值最低的运行中可用实例，若不存在代价增值最低 的运行中可用实例，则启动一个新的最便宜计算服务实例，该实例能够在满足该 PCP局部截止日期前提下执行完成其上的全部任务；所述可用实例满足：在路径 PCP被调度到该实例上执行时，路径PCP上的所有任务都可以在其相应的子截 止日期前完成；该实例的执行代价增值，包括实例执行代价和数据传输代价，必 须低于初始化一个同样计算服务实例来调度该路径PCP的执行代价。

本发明基于局部关键路径思想，从工作流自身结构特点和多云环境的全局角 度设计以代价驱动的调度方法。与现有技术相比，本发明具有以下优点：根据工 作流自身结构特点，迭代合并存在‘有向割边’的相邻子任务，减少算法执行时 间并初步降低数据传输成本；设计一种工作流局部关键路径查找策略，以保证满 足工作流截止日期约束和服务质量需求；基于局部关键路径查找并整体调度‘关 键’路径，进一步压缩数据传输时间和执行代价；根据多云环境特点，设计一种 ‘关键’路径到执行实例之间的映射方案，保证满足任务服务质量同时降低执行 代价。该调度方法能够在满足现有真实工作流截止日期约束前提下，有效提高方 法本身的执行效率，并大幅度减少工作流在多云环境下的执行代价。

附图说明

图1是多云环境下带截止日期约束工作流的基于代价驱动调度的流程图。

图2是本发明一实施例原工作流结构图。

图3是图2加入零代价依赖边的工作流结构图。

图4是压缩有向割边示意图。

图5是预处理前后的LIGO工作流结构图。

具体实施方式

下面结合附图和具体实施方式对本发明做进一步说明。

本发明考虑工作流自身结构特点和执行特性，通过迭代合并工作流中存在 ‘有向割边’相邻子任务的预处理操作，减少算法执行时间并初步降低数据传输 成本；根据当前云资源执行不同任务的情况以及工作流相应的截止日期要求，设 计一种工作流局部关键路径查找策略，以保证满足工作流截止日期约束和服务质 量需求；为提高虚拟资源的整体利用率，设计一种同时考虑数据传输代价和虚拟 机执行成本的最佳实例选择方案；考虑云环境按区间要价的特点，在实际调度阶 段设计一种带更新机制的关键路径到最佳执行实例之间的映射方案，保证满足任 务服务质量同时降低执行代价。

一种多云环境下带截止日期约束工作流的基于代价驱动调度方法，其特征在 于，一种多云环境下带截止日期约束工作流的基于代价驱动调度方法，其特征在 于，包括以下步骤：步骤S1：输入工作流w，用有向无环图G(Vertex,Edge)来表 示工作流w，其中Vertex是一个含有n个任务节点的有限点集{t₁,t₂,...,t_n}，而 Edge则用来表示任务之间数据传输依赖关系的有限边集{e₁₂,e₁₃,...,e_ij}，每条数 据依赖边e_ij＝(t_i,t_j)代表任务t_i和任务t_j之间存在数据传输依赖关系，其中任务t_i是任务t_j的直接父节点，而任务t_j则是任务t_i的直接子节点，e_ij的大小表示任 务t_i到任务t_j的数据传输量；在工作流调度过程中，一个任务必须在其所有父节 点都已被执行完毕后，该任务才能开始执行，没有父节点的任务称为入任务，没 有子节点的任务称为出任务；步骤S2：执行调度策略前预先分别加入一个零代 价的伪入任务节点t_伪入任务和伪出任务节点t_伪出任务，将伪入任务与真实入任务通过 零依赖边相连，将真实出任务与伪出任务通过零依赖边相连；步骤S3：迭代合 并其中存在有向割边相邻任务，所述有向割边的为一条有向边，其出节点的出度 为1，且其入节点的入度为1；步骤S4：确认不同服务提供商P＝{p,q,...,r}所 提供的有效计算服务类型S_p＝{s_p1,s_p2,...,s_pm}；步骤S5：计算工作流w中所有 任务的EFT(t_i)、EST(t_i)、LFT(t_i)及LST(t_i)；所述EFT(t_i)表示在任务t_i未调度前的 理想最早完成时间，其计算公式如下： 其中T_exe(t_i,s_pj)表示任务t_i在实例s_pj上的执行时间； Tboot(vm_pj)表示实例s_pj的初始化启动时间；EFT(t_j)表示EFT(t_j)表示在任务t_j未调 度前的理想最早完成时间；TE(e_ji,p)表示数据依赖边e_ji在云服务提供商preP_E(t_j) 和p之间的数据传输时间；preP_E(t_i)表示已计算EFT(t_i)的任务t_i对应的最早倾 向云，最早倾向云为在云服务提供商集合P中使任务t_i取得最小EFT(t_i)对应的 提供商；EST(t_i)表示未调度任务t_i的最早开始时间， EST(t_i)＝EFT(t_i)-MET(t_i,preP_E(t_i))；LFT(t_i)表示任务t_i最迟完成时间， LFT(t_i)＝LST(t_i)+MET(t_i,preP_L(t_i))，其中LST(t_i)表示任务t_i未被调度前的理想 最迟开始时间；preP_L(t_i)表示已计算LST(t_i)的任务t_i对应的最迟倾向云，最迟倾 向云为所有云服务提供商集合P中使任务t_i取得最大LST(t_i)对应的提供商；LST(t_i) 计算公式：TL(e_ij, p)表示数据依赖边e_ij在云服务提供商p和preP_L(t_j)之间的数据传输时间；D(w) 为整个工作流w能在其对应的截止日期；

步骤S6：标记t_伪入任务及t_伪出任务为已调度任务；步骤S7：若任务t_i不存在未调 度直接父任务直接输出调度方案，若存在未调度直接父任务执行步骤S8；步骤 S8：查找任务t_i的局部关键路径PCP(t_i)，整体调度PCP(t_i)到其对应的最佳 实施例s_p,j,k，标记PCP(t_i)上每个任务为t_j已调度；步骤S9：更新t_j所有未调 度父任务的LSTs及LFTs,更新t_i所有未调度子任务的LSTs及LFTs，返回步骤 S7。主要流程图参见图1。

在本发明一实施例中，所述步骤S3包括以下具体步骤：构造一个父亲儿子 图矩阵father-son[][]判定父节点是否仅有一个儿子节点，且该儿子节点入度为1， 并以该儿子节点为新的父节点迭代寻找新的有向割边；将寻找到的有向割边删 除，合并对应的两个任务，更新新任务的数据传输量和相应执行时间，重新扫描 全局，直到新生成的工作流中不存在有向割边。

在本发明一实施例中，所述步骤S5中当出现两个以上提供商使任务t_i取得 对应最早完成时间，则选取编号小的提供商作为任务t_i的最早倾向云。

在本发明一实施例中，所述步骤S8中整体调度PCP(t_i)到其对应的最佳实 施例s_p,j,k需要同时满足以下条件：条件1：s_p,j,k对应于局部关键路径PCP(t_i)的 执行代价增值Cgrow(s_p,j,k,PCP)最低，Cgrow(s_p,j,k,PCP)＝c_pj·(T₂-T₁)+Cdata，其 中T₁是实例s_p,j,k在执行PCP(t_i)之前，其已运行的窗口时间，T₂是在执行PCP(t_i) 之后实例s_p,j,k所运行的总窗口时间，Cdata为增值的数据传输代价；条件2：对 于某个局部关键路径PCP(t_i)，如果存在两个或两个以上实例满足条件1，则选择 产生Cdata最小的实例s_p,j,k作为最佳实际；条件3：对于某个局部关键路径 PCP(t_i)，如果存在两个或两个以上实例同时满足条件1和条件2，则选择剩余时 间最多，即当前窗口时间减去实际执行时间的差值最多的实例s_p,j,k作为最佳实 例。

在本发明一实施例中，算法的更新调度局部关键路径包括以下步骤：输入一 条带局部截止日期约束的局部关键路径PCP，更新当前多云环境中虚拟资源和所 有未调度子任务的状态，整体调度PCP到相应的最佳实例上，并在对应的局部 截止日期前执行完成PCP上的所有任务。

进一步的，整体调度PCP到相应的最佳实例上包括以下步骤：利用贪心选 择策略寻找执行PCP代价增值最低的运行中可用实例，若不存在代价增值最低 的运行中可用实例，则启动一个新的最便宜计算服务实例，该实例能够在满足该 PCP局部截止日期前提下执行完成其上的全部任务；所述可用实例满足：在路径 PCP被调度到该实例上执行时，路径PCP上的所有任务都可以在其相应的子截 止日期前完成；该实例的执行代价增值，包括实例执行代价和数据传输代价，必 须低于初始化一个同样计算服务实例来调度该路径PCP的执行代价。

在本发明一具体实施例中，本发明用有向无环图G(Vertex,Edge)来表示工作 流w，其中Vertex是一个含有n个任务节点的有限点集{t₁,t₂,...,t_n}，而Edge则 用来表示任务之间数据传输依赖关系的有限边集{e₁₂,e₁₃,...,e_ij}，如图2所示。 每条数据依赖边e_ij＝(t_i,t_j)代表任务t_i和任务t_j之间存在数据传输依赖关系，其中 任务t_i是任务t_j的直接先驱(父)节点，而任务t_j则是任务t_i的直接后继(子) 节点，另外，e_ij的大小表示任务t_i到任务t_j的数据传输量。在工作流调度过程中， 一个任务必须在其所有父节点都已被执行完毕后，该任务才能开始执行。在某个 给定的代表工作流的有向无环图中，把没有父节点的任务称为‘入任务’，同理， 把没有子节点的任务称为‘出任务’。本发明设计的工作流调度方法仅考虑唯一 一个‘入任务’和‘出任务’的工作流，所以在执行调度策略前预先分别加入一 个零代价的‘伪入任务’节点和‘伪出任务’节点，然后把‘伪入任务’与真实 ‘入任务’通过零依赖边相连，同样地，把真实‘出任务’与‘伪出任务’通过 零依赖边相连，该变化如图3所示，该处理不会对调度结果产生任何影响。

对有向割边定义：一条有向边，其出节点的出度为1，且其入节点的入度 为1，则称该有向边为‘有向割边’，其结构如图4所示。

在完成工作流初始零依赖边加入变化后，基于当前工作流自身结构特点，迭 代合并其中存在‘有向割边’相邻任务。本发明‘有向割边’的定义区别于传统 割边，压缩‘有向割边’可以有效降低数据传输量。首先，在输入工作流过程中 记录每个任务相应的出度和入度；然后，为了减少寻找‘有向割边’的时间复杂 度，本发明构造一个父亲儿子图矩阵father-son[][]来直接判定父节点是否仅有一 个儿子节点，且该儿子节点入度为1，并以该儿子节点为新的父节点迭代寻找新 的‘有向割边’；将寻找到的‘有向割边’删除，合并对应的两个任务，更新新 任务的数据传输量和相应执行时间，反复处理直到不存在‘有向割边’。试验表 明，经过预处理的工作流，可以大幅度减少任务数量，特别是存在大量‘有向割 边’的工作流，从而缩短算法执行时间，降低工作流执行代价。图5展示了LIGO 工作流在预处理前后的自身结构变化。

多云环境下包含多个不同的IaaS服务提供商P＝{p,q,...,r}，每个服务提供 商p向终端用户提供一组含有不同CPUs数量、内存容量的计算服务S_p＝{s_p1, s_p2,...,s_pm}，当前主要的商业云服务提供商，通常的要价区间是按1小时收费， 用户按1小时的区间按需付费。局部关键路径思想，它区别于以任务为基本单元 的传统调度方式，根据云环境按区间要价的特性，它是把同一关键路径上的局部 所有未调度任务当作一个基本单元而进行统一调度。试验表明，这样可以有效压 缩相互依赖任务之间的数据传输量，从而减少传输代价。对于某个任务t_i，它对 应的局部关键路径PCP(t_i)定义如下： 其中CP(t_i)表示 任务t_i的关键直接父任务，它是任务t_i的所有直接未调度父任务中，数据预估最 迟时刻传输到达任务t_i的对应父任务，具体定义如下所示：

其中EFT(t_j)表示在任务t_j未调度前，任务t_j的理想最早完成时间，其定义如下： 其中T_exe(t_i,s_pj)表示任务t_i在实例s_pj上的执行时间， Tboot(vm_pj)表示实例s_pj的初始化启动时间。本发明中，每个已计算EFT(t_i)的任 务t_i都有一个对应的最早倾向云preP_E(t_i)，它是在所有云服务提供商集合P中， 使任务t_i取得最小EFT(t_i)对应的提供商。如果出现两个以上提供商使任务t_i取得 对应最早完成时间，则选取编号小的提供商作为任务t_i的最早倾向云。TE(e_ji,p) 表示数据依赖边e_ji在云服务提供商preP_E(t_j)和p之间的数据传输时间。另外， 数据依赖边e_ij在服务提供商p和q之间的传输时间TT_inter(e_ij,s_pi,s_qj)表示如下: 其中Data(e_ij)表示依赖边e_ij的数据传输量， 即任务t_i在任务t_j执行前，传输到t_j的数据量。B_inter(s_pi,s_qj)表示服务提供商p的 计算服务s_pi到服务提供商q的计算服务s_qj的传输带宽速度。另外，未调度任务 t_i的最早开始时间EST(t_i)定义如下：EST(t_i)＝EFT(t_i)-MET(t_i,preP_E(t_i))。 path(way,t_i)表示一条局部关键路径，way是一条路径(可能仅含一个节点)。因 此，在局部关键路径PCP(t_i)上的任何一个任务，到达它的下一个后继任务的传 输时间都是最迟的。

算法的最佳实例选择：云服务提供商所提供的所有计算服务中的某个实例， 或者是已有任务在其上执行的，或者是刚刚启动的，如果能被选定为某个局部关 键路径对应的最佳实例，它能在该路径对应的局部截止日期前完成其上的所有任 务，即路径上的每个任务t_i必须在其对应的理想最迟完成时间LFT(t_i)前被执行完 成。最迟完成时间LFT(t_i)是任务未调度前被计算的，其定义如下： LFT(t_i)＝LST(t_i)+MET(t_i,preP_L(t_i))。其中LST(t_i)表示任务t_i未被调度前的理 想最迟开始时间。为确保整个工作流w能在其对应的截止日期D(w)前完成，任 务t_i必须在其最迟开始时间LST(t_i)前被分配并开始执行。未调度任务t_i的最迟开 始时间LST(t_i)定义如下：

其中每个已计算 LST(t_i)的任务t_i都有一个对应的最迟倾向云preP_L(t_i)，它是在所有云服务提供商 集合P中，使任务t_i取得最大LST(t_i)对应的提供商。TL(e_ij,p)表示数据依赖边e_ij在云服务提供商p和preP_L(t_j)之间的数据传输时间。另外，该最佳实例需要同 时满足以下三种条件的具体实例s_p,j,k：

条件1：该实例s_p,j,k对应于局部关键路径PCP(t_i)的执行代价增值Cgrow(s_p,j,k, PCP)最低，s_p,j,k的执行代价增值包括在该PCP(t_i)分配到s_p,j,k上时所带来新的实 例计算代价和数据传输代价。执行代价增值Cgrow(s_p,j,k,PCP)的定义如下： Cgrow(s_p,j,k,PCP)＝c_pj·(T₂-T₁)+Cdata，其中T₁是实例s_p,j,k在执行PCP(t_i)之前， 其已运行的窗口时间(即向上整合时间区间，如果已运行61分钟，则按2个小 时计算)。同理，T₂是在执行PCP(t_i)之后实例s_p,j,k所运行的总窗口时间。如果s_p,j,k是一个刚刚启动的实例，则T₁为0，而T₂则表示在执行PCP(t_i)之后实例s_p,j,k总 共运行的窗口时间，该时间包括启动实例所花销的时间。另外，增值的数据传输 代价Cdata，是该局部关键路径上刚被分配的子任务与已被分配的其他子任务之 间，由于分配在不同云服务提供商之间而产生的新数据传输代价。

条件2：对于某个局部关键路径PCP(t_i)，如果存在两个或两个以上实例满足 条件1，则选择产生数据传输代价最小的实例s_p,j,k作为最佳实际，试验表明条件 2的加入可以平均减少5％的执行代价；

条件3：对于某个局部关键路径PCP(t_i)，如果存在两个或两个以上实例同时 满足条件1和条件2，则选择剩余时间最多(即当前窗口时间减去实际执行时间 的差值)的实例s_p,j,k作为最佳实例。试验表明，具有同等计算能力的两个实例， 相对于剩余时间少得实例，剩余时间较多的实例更容易通过以上执行代价增值的 定义方式来调度相应的局部关键路径，从而提高虚拟资源的整体利用率。

以上选择条件均以代价驱动贪心策略为出发点，使选择的最佳实例在保证能 够完成相应任务前提下，降低执行代价。

算法的更新调度局部关键路径：输入一条带局部截止日期约束的局部关键路 径PCP，更新当前多云环境中虚拟资源和所有未调度子任务的状态，整体调度 PCP到相应的最佳实例上，并在对应的局部截止日期前执行完成PCP上的所有 任务。调度整条局部关键路径PCP到最佳实例中的过程以一条带局部截止日期 的路径作为其输入值。首先，利用贪心选择策略寻找执行PCP代价增值最低的 运行中‘可用’实例。一个运行中的实例如果是一条带局部截止日期路径PCP 的‘可用’实例，必须满足以下两个条件：

条件1：当路径PCP被调度到该实例上执行时，路径PCP上的所有任务都 可以在其相应的子截止日期前完成。

条件2：该实例的执行代价增值，包括实例执行代价和数据传输代价，必须 低于初始化一个同样计算服务实例来调度该路径PCP的执行代价。这意味着， 这个新的PCP调度必须占用已运行实例中一部分的剩余窗口时间。

在运行的实例中寻找‘可用’实例，必须注意以下3点：

注意1：由于路径PCP上的所有任务都被分配到同一个实例上执行，所以它 们之间的数据传输时间变为0，但它们与非该路径PCP上的任务之间的数据传输 时间依然存在。假设路径PCP上某个任务的直接父(子)任务已被分配到实例 s_p,j,k上执行，如果该路径在后续调度过程中也被分配到实例s_p,j,k上，则该任务与 其直接父(子)任务之间的数据传输时间为0。同样地，如果路径PCP上某个任 务与其直接父(子)任务被分配到同一个云服务提供商的不同实例上，则它们之 间的数据传输时间将变为TT_intra(e_ij,s_pi,s_pj)，其定义如下：

${\mathrm{TT}}_{intra}(e_{ij},s_{pi},s_{pj})=\frac{Data\left(e_{ij}\right)}{B_{\mathrm{int}ra}(s_{pi},s_{pj})},$

其中B_intra(s_pi,s_pj)表示服务提供商p的计算服务s_pi到计算服务s_pj的传输带宽。最 后，如果路径PCP上某个任务与其直接父(子)任务被分配到不同的云服务提 供商实例上，则它们之间的数据传输时间将变为TT_inter(e_ij,s_pi,s_qj)，且它们之间的 数据传输代价必须要考虑其中。

注意2：利用实例的剩余窗口时间执行整条路径PCP的代价增值为0。当存 在多个增长执行代价相等的实例，则利用上一小节中介绍的方法选择一个最佳运 行中实例。

注意3：本发明考虑运行中的实例上每个已调度相邻任务之间的空闲时间槽 (即后一个任务实际开始时间与前一个任务实际完成时间之间的差值)。当某个 时间槽满足路径PCP要求，则将整条PCP插入该槽中，否则将该PCP调度到该 实例上的第一个任务之前或最后一个任务之后执行。

如果不存在代价增值最低的运行中‘可用’实例，则启动一个新的最便宜计 算服务实例，该实例能够在满足该PCP局部截止日期前提下执行完成其上的全 部任务。在该PCP被调度到最佳实例上之后，需要更新一些与该PCP上所有任 务相关的参数，如选择的服务实例，被调度任务的实际开始时间和相应的调度状 态。

当PCP上的某个任务被调度完成，则该任务对应的实际开始时间和实际完 成时间将被确定，相应地，它将影响其所有未调度先驱任务的最迟完成时间 LFT(t_i)和最迟开始时间LST(t_i)，以及其所有未调度后继任务的最早开始时间 EST(t_i)和最早完成时间EFT(t_i)。因此，与该PCP上所有任务相关的这些参数， 在调度完成后要进行更新操作。

本领域技术人员可以在不违背本发明的原理和实质的前提下对本具体实施 例做出各种修改或补充或者采用类似的方式替代，但是这些改动均落入本发明的 保护范围。因此本发明技术范围不局限于上述实施例。