论文部分内容阅读
随着网格和云计算等异构分布式计算技术的不断深入发展,异构分布式计算系统受到了广泛的关注。在异构分布式计算环境中,如何为用户合理分配资源是一个重要的研究内容。目前,尽管有关异构分布式计算环境下任务调度的研究取得了一定进展,但仍存在许多问题亟待进一步研究和解决。本文针对异分布式计算环境下多处理机的任务调度的若干问题进行了研究,具体工作主要从最小化跨度和保证服务质量(Qos)两个方面开展。前者跨度指的是从第一个任务开始执行到最后一个任务执行完成所经历的时间,即调度长度。它是任务调度中一个最主要、最常见的目标。通常跨度越短说明调度策略越好。后者服务质量是近些年“面向服务”的计算模式发展后,任务调度中必须要考虑的一个重要因素。本文的主要研究工作和创新点总结如下:(1)针对分布式计算环境中异构多处理机的相关任务调度的最小化跨度问题,本文提出了一种表调度算法IPEFT(Improvement Predict Earliest Finish Time)。IPEFT的基本思想是运用悲观代价表计算任务优先级和关键节点代价表进行特征预测为任务选择处理机。IPEFT算法从两个方面减少调度长度。一方面基于悲观代价表计算任务优先级使得最耗时路径上的任务被优先调度,从而有效地缩短了调度长度。另一方面基于关键节点代价表为任务选择处理机,所选择的处理机对于当前任务来说可能完成时间不一定是最早的,但能使得下一个阶段的关键任务的完成时间更短,达到减少调度长度的目的。为验证该调度方法的有效性,分别从随机生成图和现实世界应用图两个方面进行实验,并验证了该方法在调度长度比率、鲁棒性及最好结果频率等方面的效果。实验结果表明,相对于PEFT(Predict Earliest Finish Time)和HEFT(Heterogeneous Earliest Finish Time)调度方法,IPEFT在与PEFT和HEFT具有相同的时间复杂度的条件下,调度长度比率、鲁棒性及最好结果频率都优于这两个方法。(2)针对分布式计算环境中异构多处理机的相关任务调度的最小化跨度问题,本文还提出了一种综合启发式调度算法,任务合并和最早时间预测算法MTPEFT(Merge Tasks and Predict Earliest Finish Time)。MTPEET首先采用归并策略,减少任务之间依赖等待时间,同时兼顾任务之间的并行性。然后,为每一个任务分配优先级,最后为任务选择处理机。在处理机选择时,同时考虑了关键任务的父任务所选择的处理机对关键任务的影响和非关键任务所选择的处理机对其子任务的影响。MTPEFT在不增加算法的时间复杂度的前提下,有效地减少了调度长度。本文从随机生成图和现实世界应用图两个方面分别验证了调度方法的效果,实验结果证明,相对于已有的调度方法,本文的调度方法在调度长度比率、鲁棒性及最好结果频率等方面都有很好的表现,尤其是随着CCR的增大,MTPEET的优势得到更好的体现。(3)针对具有预算和期限约束的相关任务调度问题,本文提出了一个基于预算和期限约束的调度算法BDCWS(Budget-Deadline Constrained Workflow Scheduling)。BDCWS首先考虑非一致模型特点,兼顾时间和费用,引入新策略为任务分配优先级,以达到同时减少时间和费用的目的。其次提出任务可用预算TAB(Task Available Budget)控制处理机的选择范围。最后,依据乐观备用预算值,为当前任务提供不同的处理机选择策略,以达到更好地平衡时间和费用的目的。仿真实验数据表明,与现有算法相比,本文算法在成功率方面拥有更好的效果,尤其在预算紧张的情况下。(4)针对具有预算和期限约束的动态并发多DAG调度问题,提出了多工作流异构预算和期限约束的调度算法MW-HBDCS(Multi-Workflow Heterogeneous Budget-Deadline Constrained Scheduling algorithm)。MW-HBDCS兼顾时间和费用给出了工作流和工作组统一权重因子,为任务分配优先级。该策略不仅节省了任务选择阶段的计算时间,而且能有效提升并发工作流调度成功率。在处理机选择时利用当前任务乐观可用预算控制处理机选择范围,同时兼顾任务的子期限和子预算提出双因子,并根据双因子值为当前任务选择处理机,从而达到提高调度成功率的目的。从分析和实验结果可知,提出的MWHBDCS相比MW-DBS、修改版的Min-Min和Max-Min算法在调度成功率方面取得更好的性能。另外,为了保证多工作流中任务的安全,提出了一种基于参数化分解树的控制流二次平展混淆的改进方法。该方法首先根据设定的深度、广度及粒度的上界构建参数化分解树,然后用一个while-switch循环选择结构统筹整棵树,并对树中满足一定条件的节点进行二次平展。实验结果表明,与基于参数化分解树的控制流平展混淆方法相比,该方法减少了执行开销和解决深层不作为问题;与传统的控制流平展混淆方法相比,增加了反编译及逆向工程的难度。