开放式实时系统任务调度的研究

论文摘要

随着计算机硬件技术的巨大进步,独立开发与发布的硬实时、软实时与非实时应用程序一起运行于快速、通用目的的工作站与个人计算机系统的情况成为了可能,并且这些应用程序可以动态地进入或退出系统,这种系统就是“开放式实时系统”,它是目前研究最热的实时计算领域之一。实时系统的关键技术之一是实时调度。传统的实时调度理论与方法虽然已经相当成熟,但它们用于传统实时系统,专门针对某一特定类型的实时应用。如何调度开放式实时系统中的任务是一个新的挑战性问题。二维优先级实时调度机制不仅划分任务优先级,还划分调度策略优先级。首先设置各种调度策略的优先级,如:将EDF（Earliest Deadline First）策略优先级设为最高,其次是RM（Rate-Monotonic）,再其次是软实时调度策略SD（Share-Driven）,优先级最低的是用于调度非实时任务的策略。然后划分各调度策略内部任务的优先级。二维优先级调度机制中任务的执行顺序由任务的调度策略优先级与任务的优先级共同决定。这种算法不仅解决了传统优先级调度方法中调度策略依赖于调度机制的问题,还克服了以往开放式实时调度架构不适合并行分布式实时应用的缺点,适用于具有特权等级的场合。但是,二维优先级实时调度机制中,高优先级调度策略的实时任务可能会让较低优先级策略的任务长时间得不到CPU（Central Processing Unit）而处于死等状态,并且不适合公平性的场合。基于常量利用率服务器的混合调度架构为每个实时调度策略分配一个常量利用率服务器,在底层,一个全局的EDF调度器负责调度和维护顶层各服务器。这种调度架构不仅解决了以往方案中存在的问题,而且弥补了二维优先级调度机制的不足,适用于公平性场合。通过引入空闲带宽回收及任务溢出控制机制对常量利用率服务器进行改进,其性能可以得到进一步提升。常量利用率服务器的大小是固定的,而开放式系统的负载是动态变化的,因此,常量利用率服务器大小的设置会影响系统性能,若其大小大于任务实际需求,会浪费多余CPU资源;若小于实际需求,会将一些本可接受的任务拒之门外。可变利用率服务器的大小能根据系统负载的变化而变化,且其维护算法优于常量利用率服务器。实验结果表明,基于可变利用率服务器的二级层次调度架构的性能更优,更适合开放式实时系统任务调度。随着应用规模的扩大,若干相互独立开发与发布的实时应用程序与非实时应用程序一起协同运行于一个分布式系统的需要在不断增长。这类分布式开放实时系统对任务调度提出了新的要求。基于处理节点归类分配（CPNA, Classified-Processing Node Allocation）算法与启发式和FCF（First Committed First）调度算法结合的实时调度架构比较适合同构系统,且有较好的性能,但当处理节点太少或节点归类不多时,调度机制与调度策略分离程度不高,开放程度受限,其优势不能发挥出来。基于最大需求优先与最空闲适应分配算法及可变利用率服务器算法的实时调度架构克服了以往方案的缺点,适合多种任务模型,支持调度机制与策略相分离,适合复杂的并行分布式应用程序,适合异构的物理环境,另外,最大需要优先与最空闲适应分配算法能较好地保持系统的负载平衡。这种调度架构开放程度高、性能也较好,是一种理想的分布式开放实时调度方案。在理论研究的基础上,实现了一个基于Linux的分布式开放实时系统的原型。测试表明,该系统具有很好的实时性能,调度延迟与周期抖动一般在25μs以内。该系统在实时控制、数控系统、制造业等领域具有很好的应用前景。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 实时系统发展现状
• 1.3 实时调度算法
• 1.4 研究内容和主要贡献
• 1.5 论文组织结构
• 2 二维优先级实时调度
• 2.1 相关研究
• 2.2 传统优先级实时调度
• 2.3 二维优先级实时调度
• 2.4 任务模型及可调度性分析
• 2.5 调度实例
• 2.6 性能分析
• 2.7 小结
• 3 基于常量利用率服务器的混合调度架构
• 3.1 常量利用率服务器
• 3.2 调度架构
• 3.3 任务模型及可调度性分析
• 3.4 性能测试与分析
• 3.5 方案改进
• 3.6 小结
• 4 基于可变利用率服务器的二级层次调度架构
• 4.1 服务器调度技术概述
• 4.2 可变利用率服务器（VUS）算法
• 4.3 基于VUS 二级层次调度架构
• 4.4 任务模型及可调度性分析
• 4.5 性能分析
• 4.6 小结
• 5 分布式开放实时系统任务调度
• 5.1 系统结构
• 5.2 基于处理节点归类分配的实时调度
• 5.3 基于最大需求优先与最空闲适应分配的实时调度
• 5.4 小结
• 6 基于Linux 的分布式开放实时系统实现
• 6.1 概述
• 6.2 系统功能
• 6.3 时钟同步
• 6.4 任务调度
• 6.5 实时性能测试与分析
• 6.6 小结
• 7 总结
• 致谢
• 参考文献
• 附录1 攻读博士学位期间发表的学术论文
• 附录2 攻读博士学位期间参加的主要科研项目