截止日期约束的云中资源调度成本优化算法

摘要：随着越来越多的工作流应用程序部署在云端，如何在满足工作流截止期限约束的前提下优化资源调度成本成为一个热门研究领域。本文提出了一种截止日期约束的成本优化（CODC） 算法。首先，合并工作流任务以减少不同实例之间的数据传输开销。其次，关注父任务和子任务对当前任务优先级的影响，并考虑任务的子截止日期未被满足的情况，以选择最早完成任务执行的实例。最后，在5 种工作流上与现有算法进行对比。与3 种对照算法相比，CODC 算法具有更低的工作流执行成本。

关键词：云计算；资源调度；截止日期约束；任务实例映射；成本优化

中图分类号：TP311 文献标志码：A

云计算（Cloud Computing） 是将物理设备抽象为虚拟资源，以互联网为媒介向用户提供的一种新型分布式计算模式[1]。受益于服务器不断提升的处理能力以及高速网络的低延迟，用户能够随时随地通过服务接口动态地获得可扩展的便捷资源，并根据实际使用量进行付费，而不需要大量的前期投资。成本优化是云资源调度的重要考虑因素之一，它试图在满足服务质量（Quality of Service， QoS） 的同时获得最小的调度成本，然而任务之间的依赖约束使得可调度条件变得更加复杂[2]，QoS 的要求也间接地提高了在任务响应时间和执行成本之间寻找平衡的难度。因此，设计一种有效的资源调度方法来均衡任务执行的时间和成本变得日益重要。

针对此问题，Chen 等[3] 提出了一种实时任务调度算法，旨在减少工作流响应时间、降低执行成本并提高服务实例的资源利用率。该算法基于任务的最早开始时间为任务分配调度优先级，并根据任务的最晚完成时间将任务分配到合适的租赁实例上。Toussi 等[4] 提出了一种分而治之的调度算法，将工作流分为多个子工作流，针对每个子工作流的关键路径上的任务选择满足截止日期和最低执行成本的服务资源，并将关键路径上的任务从工作流中删除。王旖旎[5] 提出了一种主动响应式工作流调度算法，在新工作流到达时将当前所有工作流的就绪任务进行混合调度以满足期限约束，并优先选择具有最小调度成本的计算资源。Ahmad 等[6] 提出了一种截止日期感知的启发式算法，通过工作流最短执行时间确定其截止日期，并实时监控资源池动态，为工作流任务分配执行成本最低的虚拟实例。张艮山等[7] 提出了一种期限预算双重约束的工作流调度算法，根据工作流结构特征对其进行分层处理，将任务划分为若干个互不关联的任务包，以提高调度过程中的并行程度。

尽管上述方法考虑了工作流任务之间的数据依赖关系，但未进行任务合并以降低数据传输成本，并忽略了父任务对于当前任务优先级的影响。此外，它们很少关注任务子截止日期未被满足的情况。为了克服上述方法的不足，本文提出了一种截止日期约束的成本优化（CODC） 算法，包括4 个调度阶段：任务合并、任务优先级分配、任务子截止日期分配和租赁实例选择。CODC 算法的主要优势如下：

（1）明确云工作流任务合并条件，将满足条件的任务进行合并，以减少不同实例之间的数据传输开销；

（2）关注父任务以及子任务对于当前任务优先级的影响，给出优化任务优先级分配过程；

（3）设计每个任务的子截止日期，将工作流中的任务分离，以便在子截止日期的约束下分别调度任务，并选择最早完成当前任务执行的实例。