基于ECT的优先权约束的作业调度模型及算法研究与实现

论文摘要

随着科学技术的发展，Internet迅速蔓延到世界各地，成为人们沟通信息和协同工作的有效工具。其中，通过Internet连接的成千上万的计算资源、存贮资源、软件资源、信息资源等各种数字化设备共同构成了生产、传播和使用知识的重要载体。而网格作为一种新兴的计算基础设施，将这些物理上互连的众多资源汇聚起来，实现了资源共享、协同工作和联合计算的功能，并为广大用户提供了科学、工程、金融、军事等各种综合性服务。由于Internet所提供的计算资源在地理上分布广泛，隶属于不同社区，而且这些资源从硬件架构到软件部署都不尽相同，因此，在采用网格计算为广大用户解决各种领域（比如：高能物理生物信息学、化学分子模拟以及数值天气预报等）中的超大规模、超级复杂的问题时，需要合理地将这些具有超级计算能力的分布式异构资源，分配给具有不同应用需求的用户，使得用户的问题既能够及时得到处理，同时也要确保资源使用过程中，各类资源能够平衡使用。因此需要一种可靠、高效率的调度算法来解决资源共享中作业调度、资源分配的问题。而根据解决问题的目的不同，调度算法有着不同的目标函数：面向资源和面向应用。例如目前一些流行的、基于应用QoS的网格调度管理算法就是以面向用户为主要目的，在调度过程中考虑用户对作业管理、资源分配的影响。对用户来说，他最关心的莫过于自己作业的执行效率（make span）和使用资源的总耗费（cost）。具体体现：要求作业必须要在特定时间内完成，或者完成作业的总费用不能超过预算上限等。还有一些更复杂的、结合资源的别的约束条件，如：容错性能不可低于某一下限，资源安全性能要高等。目前，网格环境中资源共享时，用户提交的作业，大都要根据实际目标附加各式各样的需求约束。本文提出的基于ECT的优先权约束的作业调度模型和相关的调度算法，以网格中的异构资源为研究背景，采用随机Petri网（SPN）技术，借鉴现有的容错性网格作业调度模型，建模时，既考虑调度过程中用户优先权对作业调度、资源分配的影响，同时兼顾用户提出的期望完成时间（ECT）和作业实际完成时间二者的协调统一，既希望高优先权用户的作业得到高质量的服务（作业提早完成），又保证绝大多数作业都能在各自用户期望的完成时间内完成，从而协调不同用户之间无冲突共享资源的矛盾。本文以大规模科学与工程计算为背景，网格为基础环境，着力研究了网格过程中作业调度、资源分配、资源共享等相关问题，分别给出了满足实际需求的作业调度模型和相应的调度算法。前者诠释了调度过程中资源、用户以及作业之间的相互依赖关系和约束；后者则详细描述了调度过程中作业调度、资源分配的具体策略。最后给出与Min-min、Max-min、XSuffrage等多种经典调度算法的性能比较。结果表明，采用本文算法调度作业，可使得绝大部分用户所提交的作业都能在用户指定的期望完成时间内完成，尤其保证高优先权用户的作业远早于其期望完成时间完成，从而保障了高优先权用户的权益，也使用户总体上满意程度比较好，实现了多用户合理共享异构资源的目标。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景
• 1.2 研究目标
• 1.3 主要工作
• 1.4 论文的组织结构
• 第2章 相关基础知识
• 2.1 网格概述
• 2.2 网格调度概述
• 2.2.1 网格调度的含义
• 2.2.2 网格调度的特征
• 2.2.3 网格调度模型
• 2.2.4 调度功能组件
• 2.3 网格调度算法
• 2.3.1 网格调度算法的含义
• 2.3.2 网格调度算法的类别
• 2.3.3 目标函数
• 2.3.4 静态启发式调度算法
• 2.4 甘特图
• 2.4.1 甘特图含义
• 2.4.2 甘特图评价
• 2.5 本章小结
• 第3章 基于 ECT 的优先权约束的作业调度模型的设计
• 3.1 设计原则
• 3.2 设计目标
• 3.3 模型设计
• 3.3.1 设计前言
• 3.3.2 问题描述
• 3.3.3 假设与约定
• 3.3.4 模型描述
• 3.4 本章小结
• 第4章 基于 ECT 的优先权约束的作业调度算法
• 4.1 调度策略
• 4.2 算法描述
• 4.3 本章小结
• 第5章 基于 ECT 的优先权约束的作业调度算法的性能评估
• 5.1 算法评价与分析
• 5.2 评估结果
• 5.3 本章小结
• 第6章 结束语
• 6.1 结论
• 6.2 今后展望
• 参考文献
• 致谢
• 攻读学位期间发表的主要学术论文
• 攻读学位期间参加的项目
• 学位论文评阅及答辩情况表