论文部分内容阅读
近年来随着网格、云计算工作流等异构分布式计算技术的发展,关于多DAG(有向无环图)共享异构分布式资源的调度问题逐渐成为备受关注的研究热点。目前,尽管有关多DAG共享异构分布式资源调度的研究取得了一定进展,但仍有很多问题亟待进一步研究和解决。本文围绕多DAG共享异构分布式资源调度的若干问题展开了研究,这些问题包括:具有多优先级的多DAG调度和具有期限约束的多DAG调度吞吐量最大化、费用优化以及费用优化的公平性等。对这些问题的解决将有利于提高网格、云计算工作流等异构分布式计算系统的资源利用率、合理处理多个DAG应用之间的调度关系和有效降低用户DAG应用的费用,因此有着重要的理论意义和应用价值。本文的主要研究工作和创新点如下:(1)针对在不同时间提交的具有多优先级的多DAG的调度问题,提出了适用于处理具有多优先级的多DAG混合调度的调度系统模型、一种改进的公平调度算法和一种回填算法Backfill,并在此基础上提出了具有多优先级的多DAG混合调度策略MMHS,既解决了不同时间提交的多个DAG中优先级相同DAG之间的调度公平性问题,也能够使得高优先级DAG的调度执行避免受到低优先级DAG的影响。实验表明,MMHS策略能够较好地处理具有多优先级的多DAG之间的调度关系,同时也能提高资源的利用效率。另外,通过实验还发现了关于两个DAG调度所特有的“拖尾”现象,具有进一步研究和应用的价值。(2)针对具有期限约束的多DAG共享资源调度的DAG吞吐量最大化问题,首先提出了在调度中由于每个DAG期限过于严格可能会产生“过饱和”情况的概念,并给出了“相对严格程度”和“宽松度”两种衡量DAG期限约束紧急程度的方法。然后分别提出了基于相对严格程度的调度算法MDRS和基于宽松度优先LLF方法与MDRS算法相结合的LLF-Sim-MDRS调度算法。这两种算法分别依据不同的期限紧急程度衡量方法,对具有期限约束的多个DAG进行调度,并能够对可能的“过饱和”情况进行探测。一旦探测到“过饱和”情况,则利用“堆栈”和“调度回溯”相结合的机制尽可能少地丢弃DAG,最终达到期限内完成DAG数量最大化的调度目标。实验表明,MDRS和LLF-Sim-MDRS两种算法都能够有效改善相关的调度性能,其中MDRS算法的性能最佳。(3)针对DAG吞吐量最大化基础上的多DAG总费用优化问题,提出了一种基于MDRS算法和总费用降低量探测的算法PDTC。当MDRS算法调度多个DAG后,如果仍有DAG存在冗余时间,则PDTC算法将在保证每个DAG满足期限约束条件下,对多个DAG的总费用进行优化。实验表明,与MDRS算法相比,PDTC算法能改善多个DAG调度的总费用性能指标。(4)针对DAG吞吐量最大化基础上的多DAG调度费用优化的公平性问题,讨论和分析了费用优化中出现较大不公平性的“马太效应”的可能性,并提出了衡量费用优化公平性的有关方法和基于单位相对严格程度变化量的费用降低率最大化的费用优化算法CDVRS。实验表明,与MDRS和PDTC算法相比,CDVRS算法不仅能有效降低多DAG的总费用,也能够改善多个DAG费用优化的公平性。