实例密集型云工作流的改进调度算法

周瑶，盛国军，张益民，张泽瀚

（大连东软信息学院，大连116023）

0 引言

随着云计算和网络资源虚拟化技术的发展，越来越多的工作流任务在云环境中执行，并且其调度方法已成为云计算领域的热门主题[1]。文献[2]提出了一种截止期约束任务的算法以最小化运行成本，但该算法仅最小化了其中一个目标。文献[3]描述了云计算环境下任务调度中成本和截止期约束的重要性，并提出了相应的算法。但是，所提出的模型和算法仅针对类似的资源。文献[4]提出了BHEFT 算法，该算法充分考虑了用户对成本预算和截止期的要求。但是，当资源被分配时，全局资源搜索方法导致过多的时间成本。文献[5]考虑了云环境下工作流的安全需求，提出了基于安全性和成本预算的云工作流调度方法，以最小化完成时间。在文献[6]中，以风险概率和截止期因素为约束，提出了使云工作流的执行成本最小化的粒子群优化调度方法，但该方法主要针对单个工作流实例的执行优化，不适用于实例密集型工作流。Kianpisheh 等人[7]提出了一种调度算法，此算法在考虑用户定义的最新限制和预算的同时最大化工作流执行的可靠性。文献[8]提出了DeadlineMDP 算法，将流程任务分为简单任务和同步任务，分解用户指定的全局截止日期，然后根据不同的规则对工作流任务进行调度。Topcuoglu 等人[9]提出了HEFT 算法，使工作流的完成时间最小化，算法根据任务数量和传输数据的大小对工作流中的任务进行分级，优先分配优先级较高的任务，并选择当前具有最佳性能的空闲资源，以便能够尽快完成任务。Abrishami 等人[10]提出了一种基于部分关键路径的启发式方法，该方法以截止期为工作流完成时间，利用反向迭代为每个活动找到部分关键路径，在部分关键路径上为每个活动设置子截止期，并在子期限的约束下为每项活动选择最便宜的服务。

本文在上述工作的基础上，着重于减少整个执行时间和云工作流任务的总成本，并提出了一种称为ISACW（云工作流的改进调度）的算法，该算法使用基于DAG 的云工作流模型。该算法采用关键路径检索和深度优先搜索方法，根据DAG 模型考虑执行时间的复杂度，动态调整工作流任务的服务时间，降低云资源的使用成本。

1 ISACW算法

多云工作流引擎（CWE）通过邻居互连形成分布式工作流实例过程调度网络，并且每个CWE 具有称为过程请求调度器的组件以接收和调度用户工作流过程实例。CWE 从云服务注册中心获取该流程中每个工作流活动的候选服务列表。

云工作流调度架构如图1 所示。

图1 云工作流调度架构

在图2 中，V={v1,v2,...,vn}是DAG 图中所有顶点的集合，E={e1,e2,...,em}是一组DAG 图中的所有有向边的集合。每个边（vi→vj）表示工作流过程的任务之间的序数关系。没有父顶点的顶点称为初始任务顶点，用vst表示，在图2 中显示为v1，没有后续任务顶点的顶点称为结束任务定点，用ved表示，在图2 中显示为v8。

图2 云工作流程的DAG

从开始任务vst到结束任务ved的所有路径的时间约束等于整个工作流时间限制，这个原则可以确保每个任务的结束时间在指定的时间内，以便使整个工作流实例在指定时间完成。为每个任务分配的时间不能少于任务的最短时间，以保证在适当的时间限制内完成所有任务。预期的总结束时间按比例分配给每个任务。假设用户期望的结束时间tue 是整个工作流实例的最后结束时间，用户指定的总成本是Cu，可用服务资源的集合是CS={cs1,cs2,...,csn}，完成任务的时间是trd。

步骤1：输入一组工作流实例WFIS={wfi1,wfi2,...,wfin}和用户预期的结束时间tue。

步骤2：对输入实例的任务进行分类：

（1）将vi添加到DAG 并标记vst和ved；

（2）使用DFS 方法搜索从vst到ved的关键路径，并标记路径中的所有任务；

（3）标记任务vi的最新执行时间tsti和最早完成时间tedi；

步骤5：为每个就绪任务vi选择最佳可用服务资源。

步骤6：在就绪队列中执行任务，调整每个任务的最新结束时间，以确保它有更大的可能性来获得更低成本的服务资源。

2 讨论与结果

实验环境描述如下：Windows 8.1 操作系统，Eclipse 3.5，JDK 1.7 和CloudSim 3.0.3。

有5 种不同类型的服务资源，每种服务类型有4个服务节点；生成总共1,500 个工作流程实例作为CWE 的输入数据。每个工作流实例都遵循图3 中所示的模板来模拟实例密集型任务。

实验步骤描述如下：

步骤1：初始化CloudSim 库并在数据库中创建流程模板。

步骤2：创建数据中心作为云资源的提供者，实验需要至少一个数据中心来运行CloudSim 模拟。

步骤3：从数据库中选择DAG 作为模板。

步骤4：创建数据中心代理，创建虚拟机并将每个虚拟机添加到vmlist，然后将vmlist 提交给数据中心代理。

步骤5：创建1500 个工作流实例，每个实例对应一个用户ID，并将建立的任务添加到任务列表中。

步骤6：使用该算法执行每个实例任务，并标记一个任务的执行时间和成本。

步骤7：提交任务并结束模拟。

图3 实验中云工作流实例的模板

表1 任务计算量（MI）

表2 服务执行率和执行任务的成本

该实验将工作流实例的平均执行时间和平均执行成本作为评估标准。将所提出的ISACW 算法与常用的工作流调度算法Max-Min 和DeadlineMDP 调度算法进行比较。

从图4 可以看出，三种算法的平均执行成本随着用户预期结束时间的增加而减小，ISACW 算法成本低于其他两种算法，特别是当用户预期结束时间时差距明显逐渐增加。实验通过DAG 图调整时间和成本来确认ISACW 算法的有效性。

如图5 所示，三种算法的执行时间增加了上一个预期的结束时间，但ISACW 算法的增加幅度小于其他两种算法，ISACW 更有可能在用户特定的时间内以较小的成本完成所有任务。

图4 平均执行成本

图5 平均执行时间

3 结语

本文提出了一种名为ISACW 的云工作流调度算法。首先，分析了云工作流的执行过程，指出了限制云工作流执行性能的问题。该算法考虑了任务执行时间的复杂性，改进了任务执行时间和成本的计算方法。与MaxMin 算法和DeadlineMDP 算法相比，结果表明ISACW 算法在用户预期的最晚时间完成任务，同时降低任务的使用成本，有效提高云工作流执行的效率。