云计算环境下科学工作流两阶段任务调度策略

0引言

科学工作流是指将一系列在科学研究中遇到的数据管理、计算、分析、展现等工作变成一个个独立的服务，再把这些服务通过数据链接组合在一起，满足研究人员科学实验和数据处理中的需要，从而实现相应的处理与科学计算。在该领域中的学科充分利用现代信息技术强大的数据、信息和知识处理能力，有力地促进了科学研究的发展[1]，科学工作流系统[2]也开始受到关注并被用来进行自动化科学任务的编排、执行、监控以及追踪[3]。但由于科学处理的复杂性，科学工作流也逐渐变成计算密集型和数据密集型[2]，因此，部署和执行科学工作流应用，不仅对资源要求高，而且要有海量存储空间，云计算[4]作为一种典型的分布式网格计算技术，能够提供给工作流一些不同于其他计算环境的特点，它提供共享基础架构的方法，通过虚拟技术将分布在不同地理位置的计算资源和存储资源模拟成一个资源池，用户需要使用时申请资源，使用完成后释放资源，从而能够以相对低廉的基础设施成本为科学工作流提供所需的计算和存储资源。如今，利用云环境去执行大规模的科学应用的需求也与日俱增[5-8]。

随着云计算技术的不断发展，它的灵活、弹性、可定制的特点为解决科学工作流运行过程中遇到的问题提供了新的想法。但在科学工作流调度过程中，现存的方法，在可用的资源上进行任务分配时会出现很多资源的空闲时间，这段时间资源不能得到有效利用，造成了资源和预算的浪费。

为解决上述问题，本文提出一种新的两阶段任务调度策略。在第一阶段，将工作流转换成有向无环图（Directed Acyclic Graph，DAG），采用一种新的方法对任务进行排序；第二阶段，对资源进行分析将任务分配到合适的资源上执行，并对资源空闲时间进行合理利用。实验表明，本文提出的策略不但减少了工作流任务执行的总时间；而且减少了资源的空闲时间，提高了资源利用率，节省了用户的云资源使用费用。

1相关工作

工作流调度算法目前已经有很多，它们分别从不同的角度考虑对流程应用进行调度，达到缩短流程运行时间、提高性能的目的。如遗传算法，实际是个动态规划算法，它是将问题的求解表示成染色体，从而构成一群染色体，将它们置于问题的环境中，根据适者生存的原则，从中选择出适应环境的染色体进行复制，通过交叉、变异产生出新一代更适应环境的染色体，这样一代一代不断进化，最后收敛到一个最适合环境的个体上，求得问题的最优解。在文献[9-11]中，作者分别基于遗传算法进行任务与资源的映射，并通过实验验证算法的有效性。其中：文献[9，11]的作者改进了算法，定义了三种收敛判据，并采用最优保存策略实现了跨代保留，避免了算法存在的过早收敛问题，提高了调度性能，缩短了工作流执行的时间；文献[10]的作者考虑了服务质量约束，在使用遗传算法进行调度的时候，是以任务之间的服务质量约束条件为依据来选择资源的。但遗传算法存在一个弊端是当求解到一定范围时往往会做大量无谓的冗余迭代，导致调度时间很长，调度性能不佳。

异态最早结束时间（Heterogeneous Earliest Finish Time， HEFT）算法[12]是一种列表调度算法，使用时首先为工作流图中的节点和边赋权值，然后按权值生成一个有序的任务列表，最后映射，为任务分配资源。文献[13-15]改进了HEFT算法。其中：文献[13]为该算法加入了回退（Backtracking）机制，可以更好地调度执行含有并行子任务的工作流应用；文献[14-15]以不同的方式使得HEFT算法支持预留资源，保证了某些实时性要求高的工作流的执行。

SHEFT算法[16]、HEFTSync和HEFTSyncBT算法[11]一样都是在HEFT算法的基础上对其进行改进。该算法能够动态地预分配和释放资源，从而提高工作流执行性能。