基于期限约束与关键路径的云工作流调度

刘雨潇, , ,

(湖北文理学院 数学与计算机科学学院,湖北 襄阳 441053)

0 概述

云计算可以融合大规模计算能力应用于实际问题求解,如工业、医疗、商业和科学计算等领域。就调度而言,以上领域的应用通常涉及复杂且多阶段的操作处理过程,即工作流模式[1]。云计算正是通过其弹性的资源提供模式及即付即用的资源支付方式,使得各领域下的工作流任务可以高效完成,类似Globus Galaxies平台[2]的云工作流应用正使得云计算环境成为构建科学工作流调度与分析的主流方法。

将工作流调度至可用资源,同时满足任务依赖关系及用户定义的相关服务质量(Quality of Service,QoS)约束即为工作流调度问题,通常为NP-完全问题。云资源上的工作流调度包括2个阶段:资源提供与任务调度[3]。资源提供阶段旨在决定任务所需资源的类型和数量,并预留至工作流执行。工作流任务调度阶段旨在决定任务最优执行序列和满足用户与工作流约束的任务部署[4]。目前的研究工作多集中于第二阶段,即对于预定义的资源池(通常为同质资源),以最小化工作流执行时间为目标,未考虑资源使用代价。

本文提出一种基于期限约束与关键路径的云工作流调度算法,用于动态云资源提供环境中的调度优化。作为一种线性启发式调度方法,该算法包括2个阶段:任务优先级确定和任务分配。第1个阶段为各个工作流任务分配升秩/降秩值,并基于秩值和对任务进行调度排序;第2个阶段则寻找最优执行资源。……