多处理机实时任务动态调度算法研究

摘要

现今，实时嵌入式系统在许多领域都得到了广泛应用，包括但不限于，通信系统、消费电子、车辆电子、医疗图像和航天航空等等。显而易见，这些领域最为关键的核心问题在于任务的调度，亦即计算资源的管理，因此实时调度一直是人们研究的重点。随着信息科学和电子技术的高速发展，面向应用的嵌入式专用多处理机系统正越来越普及，人们拥有了质量和数量都远超从前的计算资源。然而，传统的单处理机实时任务调度已开始逐渐不能适应当前多处理机强劲的发展趋势。所以，大力研究多处理机的调度技术以便更加高效地利用计算资源在理论上和实际上都具有重要意义。
　　 本文的研究目的在于，根据各种实时应用的复杂性和多样性建立更加通用的多处理机实时任务模型并且提供一种新的调度算法，通过批处理和并行的方式尽量提高实时任务的调度成功率。本文的主要工作体现在如下几个方面。
　　 (1)研究实时系统的主要特点，给出调度算法常见的分类以及相关的性能度量和最优准则。
　　 (2)全面总结近半个世纪以来单处理机实时任务调度的研究。文章渐进地分析了常用的任务模型，并详细讨论四种经典的调度算法，指出各自的适用范围、优缺点以及计算复杂度。多处理机的实时任务调度问题哪怕是使用简化的任务模型在绝大部分情况下都是NP完全的。本文从静态调度和动态调度两个方面仔细研究多处理机实时任务的多种调度策略。
　　 (3)既然不存在最优的动态调度算法来为多处理机安排事先并不知晓相关参数的实时任务，本文提出一种时间复杂度是线性的新型多处理机实时任务启发式调度算法，它能利用任务的并行性为动态的实时系统提供较优的解。
　　 (4)开发用于仿真和实验的软件框架，它能够产生大量存在可行调度的任务集合。使用大量的任务集合测试多种多处理机实时任务调度算法的性能，分析数种主要参数对调度成功率的影响。实验表明新的调度算法具有更高的调度成功率。

目录

声明

摘要

第1章 绪论

1．1 研究背景与意义

1．2 研究现状

1．3 基本术语

1．3．1 实时调度

1．4 本文的研究工作与组织结构

第2章 实时调度研究

2．1 引言

2．2 经典调度模型

2．3 性能度量和最优准则

2．4 调度问题的计算复杂度

2．5 实时调度算法的分类

2．5．1 静态调度算法

2．5．2 动态调度算法

2．5．3 时钟驱动调度算法

2．5．4 轮转调度算法

2．5．5 优先级驱动调度算法

2．6 本章小结

第3章 单处理机实时调度研究

3．1 引言

3．2 一个简单的例子

3．3 经典参考模型

3．3．1 使用优先级调度

3．3．2 分析方法

3．3．3 速率单调算法和时限单调算法

3．3．4 最早时限优先算法和最小空闲时间优先算法

3．4 补充说明

3．5 本章小结

第4章 多处理机实时调度研究

4．1 引言

4．2 多处理机调度分类

4．3 多处理机静态调度

4．3．1 非抢占情形

4．3．2 可抢占情形

4．4 多处理机动态调度

4．5 本章小结

第5章 并行分批多处理机实时动态调度算法

5．1 引言

5．2 系统模型与资源约束

5．3 批处理窗口中作业的分配

5．4 调度算法

5．5 仿真和实验

5．5．1 评价指标

5．5．2 仿真环境

5．5．3 实验方法

5．5．4 结果对比和分析

5．6 本章小结

第6章 总结与展望

6．1 工作总结

6．2 未来展望

参考文献

致谢

在读期间发表的学术论文与取得的其他研究成果