实时异构系统的集成动态调度模型与算法研究

论文摘要

实时异构系统已被广泛应用在航空航天、工业控制、电讯行业、图像处理以及Internet应用等诸多领域。在这些应用中，存在大量的硬、软实时任务共存的情况，对实时异构系统的集成动态调度模型与算法的研究具有重大理论和实际意义。本文对实时异构系统的集成动态调度问题进行了深入的研究，提出了一种实时异构系统的集成动态调度模型，基于这种模型，提出批优化的调度策略和批任务在处理器上运行的目标函数构造原则。在此基础上，提出了一种基于分批优化的实时异构系统的集成动态调度算法——GOIDSH算法。本文针对实时异构多任务调度的特点，采用集中式调度模型；提出软、硬实时任务形式化描述非精确计算的统一任务模型，清晰地描述实时任务的特点。系统任务描述简单，节省存储空间，为实现基于批优化的集成动态调度打下基础。论文提出了一种新的实时异构系统的集成动态调度算法——基于分批优化的集成动态调度算法(GOIDSH算法)。该算法以启发式搜索为基础，主要包括任务分批、构造目标函数和基于批优化的调度策略三大部分，采用统一形式完成了实时异构系统的集成动态调度。同时，在构造目标函数时，算法还引入软实时任务服务质量(Ouality of Service，Qos)降级策略来提高调度成功率。GOIDSH算法的核心思想是：在每次扩充当前局部调度时，首先按一定规则在待调度的任务集中选取一批任务组成任务子集，保证所选取的任务子集中某一任务对某个资源有访问需求时，子集中的其它任务不能对该资源有访问需求。然后，综合各种因素，对该批任务中的每项任务在每个处理器上的运行构造目标函数，将问题转化为非平衡指派问题，利用非平衡指派问题直接解法对任务进行优化分配，一次性为这些任务分配一个处理器或为每个处理器分配一项任务，使得这种分配具有最好的“合适性”，增大未被调度任务的被成功调度的可行性。论文通过仿真和模拟，从调度成功率、软实时任务的降级比率(DR)和被降级软实时任务的服务质量(QoS)三个方面，验证了GOIDSH算法的有效性及其调度性能。在仿真实验时，提出了一种按如下顺序设定的价值最高最优先的任务队列排序原则：①任务的截止期越近，其价值越高；②任务需要访问的资源越多，其价值越高；③任务要需访问的资源中，互斥方式的访问越多，其价值越高；④任务的空闲时间越短，其价值越高；⑤相同情形下，硬实时任务的价值高于软实时任务的价值。仿真实验结果表明，基于分批优化的实时异构系统集成动态调度算法(GOIDSH算法)不仅成功地解决了实时异构系统中硬、软实时任务的集成动态调度问题，而且还有效地提高了调度成功率，确保了软实时任务具有良好的服务质量，与其它相关算法，如传统的近视算法和节约算法相比较，具有明显优势。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 实时系统与实时调度基本概念
• 1.1.1 实时系统基本概念
• 1.1.2 实时调度基本概念
• 1.2 实时系统与实时调度研究进展
• 1.2.1 实时系统研究进展
• 1.2.2 实时调度研究进展
• 1.3 实时调度研究中存在的不足
• 1.4 研究目标和内容
• 1.5 论文的组织结构
• 第2章 实时异构系统的集成动态调度模型
• 2.1 实时异构系统的系统模型
• 2.2 调度器模型
• 2.3 实时异构系统的统一任务模型
• 2.3.1 非精确计算模型
• 2.3.2 统一任务模型的描述
• 2.4 本章小结
• 第3章 基于分批优化的实时异构系统的集成动态调度算法
• 3.1 相关定义
• 3.2 启发式搜索方法
• 3.3 任务分批规则
• 3.4 目标函数构造原则
• 3.6 基于批优化的任务调度策略
• 3.7 基于分批优化的实时异构系统的集成动态调度算法描述
• 3.8 对基于分批优化的实时异构系统集成动态调度算法的分析及讨论
• 3.9 非平衡指派问题直接解法
• 3.9.1 基本定理
• 3.9.2 直接解法
• 3.10 本章小结
• 第4章 仿真实验与分析
• 4.1 性能评估标准
• 4.2 仿真实验方法
• 4.2.1 仿真实验参数
• 4.2.2 仿真实验任务生成方法
• 4.3 仿真实验结果及其分析
• 4.3.1 处理器间的速度差异对调度成功率等的影响
• 4.3.2 软实时任务概率对调度成功率等的影响
• 4.3.3 最大回溯次数对调度成功率等的影响
• 4.3.4 分批窗口大小对调度成功率等的影响
• 4.3.5 任务的可延迟度对调度成功率等的影响
• 4.3.6 任务访问资源的概率的多少对调度成功率等的影响
• 4.3.7 任务对系统中资源数要求的多少对调度成功率等的影响
• 4.3.8 调度长度的大小对调度成功率等的影响
• 4.3.9 处理器数对调度成功率等的影响
• 4.4 算法的时间复杂度分析
• 4.5 仿真实验结论
• 4.6 本章小结
• 第5章 结束语和未来的工作展望
• 5.1 论文所做的主要工作和创新点
• 5.2 未来的工作展望
• 参考文献
• 致谢
• 攻读博士学位期间发表及录用的论文
• 攻读博士学位期间参加项目情况