导　　师： 齐德昱

授予学位： 博士

作　　者： ;

机构地区： 华南理工大学

摘　　要： 随着网格和云计算等异构分布式计算技术的不断深入发展,异构分布式计算系统受到了广泛的关注。在异构分布式计算环境中,如何为用户合理分配资源是一个重要的研究内容。目前,尽管有关异构分布式计算环境下任务调度的研究取得了一定进展,但仍存在许多问题亟待进一步研究和解决。本文针对异分布式计算环境下多处理机的任务调度的若干问题进行了研究,具体工作主要从最小化跨度和保证服务质量(Qos)两个方面开展。前者跨度指的是从第一个任务开始执行到最后一个任务执行完成所经历的时间,即调度长度。它是任务调度中一个最主要、最常见的目标。通常跨度越短说明调度策略越好。后者服务质量是近些年“面向服务”的计算模式发展后,任务调度中必须要考虑的一个重要因素。本文的主要研究工作和创新点总结如下:(1)针对分布式计算环境中异构多处理机的相关任务调度的最小化跨度问题,本文提出了一种表调度算法IPEFT(Improvement Predict Earliest Finish Time)。IPEFT的基本思想是运用悲观代价表计算任务优先级和关键节点代价表进行特征预测为任务选择处理机。IPEFT算法从两个方面减少调度长度。一方面基于悲观代价表计算任务优先级使得最耗时路径上的任务被优先调度,从而有效地缩短了调度长度。另一方面基于关键节点代价表为任务选择处理机,所选择的处理机对于当前任务来说可能完成时间不一定是最早的,但能使得下一个阶段的关键任务的完成时间更短,达到减少调度长度的目的。为验证该调度方法的有效性,分别从随机生成图和现实世界应用图两个方面进行实验,并验证了该方法在调度长度比率、鲁棒性及最好结果频率等方面的效果。实验结果表明,相对于PEFT(Predict Earliest Finish Time)和HEFT(Heterogeneous Earliest Finish Time)调度方法,IPEFT在

关 键 词： 任务调度 相关任务 并发工作流 多目标

领　　域： []