开放式混合实时系统中的调度方法研究

论文摘要

实时系统主要面向现实世界中与时间因素相关的应用需求，在工业控制、航空航天和军事设备等众多领域里有着广泛的应用。它所关注的不仅是计算结果在逻辑上的正确性，而且还有输出结果时间上的及时性。随着实时系统应用的不断深入发展，多类型的硬实时、软实时与非实时任务共存于同一系统中的情况越来越普遍，致使其复杂性不断提高。开放式混合实时系统即是针对这种实际情况被提出的。 本文在对开放式混合实时系统的调度问题进行了深入分析的基础上，对调度问题进行了系统的研究，提出了一种新的集成调度框架——RPDS（Rigorously Proportional Dispatching Server）。针对广泛存在的不确定实时环境，提出了一种反馈控制实时调度算法NF-QoS（Normalized Fair QoS）。结合具体的操作系统平台（MiniCore）讨论了集成上述两种调度算法的设计与实现方案，构建了一个原型操作系统RT-MiniCore。 在混合实时系统中，调度器必须既保证所有硬实时任务严格按照其时间约束在截止期内完成，又要尽可能提高软实时任务和非实时任务的服务质量。RPDS算法就是为解决这个问题而提出的，并以此为基础构建了一种层次式调度框架。该算法将不同类型实时任务分开，由不同调度器调度，由RPDS统一派发时间片。在保证硬实时任务不受其他类型任务影响的基础上，RPDS将处理器时间流分成连续的小段，并在每一小段中强制为非硬实时任务分配一个时间片，使软实时任务的截止期错失率达到了最小化。对于在系统中同时运行的各类应用程序，可单独进行开发和验证，并可以选择不同的局部调度器。 任务间的QoS公平性是多QoS级别的可调节动态实时调度系统中的一个重要问题。本文引入了标准化QoS公平的概念，在公平性中加入了任务的重要性因素，并构造了具有PID反馈控制环节的实时调度算法NF-QoS，以达到系统的标准化QoS公平。利用NF-QoS对系统截止期错失率进行实时采样，定期反馈给PID控制器，根据PID控制器计算的结果对各任务QoS级别进行动态调整，以保证各任务公平地得到处理器资源。 调度方法要在实际中得到应用，需要与具体的操作系统相结合。本文介绍了一种我们提出的基于服务体／执行流模型（Servant／Exe-Flow Model，SEF）的

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 选题背景与研究意义
• 1.1.1 实时系统
• 1.1.1.1 实时系统的产生、发展与定义
• 1.1.1.2 实时系统的特点
• 1.1.2 实时调度
• 1.1.3 开放式混合实时系统
• 1.1.4 反馈控制实时调度
• 1.2 本论文的工作
• 1.2.1 研究目标
• 1.2.2 主要研究工作
• 1.3 论文的组织结构
• 第2章 实时调度与实时操作系统
• 2.1 实时调度基本理论
• 2.1.1 基本概念和相关术语
• 2.1.2 实时调度方法的分类
• 2.1.3 实时调度基本策略
• 2.2 开放式混合实时系统调度及其研究现状
• 2.2.1 开放式混合实时系统调度问题
• 2.2.2 研究现状
• 2.3 反馈控制实时调度研究
• 2.3.1 反馈控制实时调度
• 2.3.2 研究现状
• 2.4 实时操作系统
• 2.4.1 对实时内核的要求
• 2.4.2 实时操作系统的分类和体系结构
• 2.4.2.1 小型快速私有内核
• 2.4.2.2 商业操作系统的实时扩展
• 2.4.2.3 基于部件的内核
• 2.4.2.4 基于QoS的内核
• 2.4.2.5 研究性质内核
• 2.5 小结
• 第3章 开放式混合实时系统调度研究
• 3.1 引言
• 3.2 开放式混合实时系统任务模型
• 3.3 严格按比例派发服务器（RPDS）
• 3.3.1 基本概念
• 3.3.2 基于RPDS的调度框架
• 3.4 RPDS算法描述
• 3.4.1 强制派发轮回FDR的长度
• Non-H'>3.4.2 非硬实时任务处理器时间预算Budget_Non-H
• 3.4.3 RPDS算法详述
• 3.4.4 示例
• 3.5 RPDS的理论分析
• 3.6 仿真实验及结果分析
• 3.6.1 仿真实验方案
• 3.6.2 实验结果比较与分析
• 3.7 小结
• 第4章 QoS公平的动态实时系统调度研究
• 4.1 引言
• 4.2 任务模型
• 4.3 一种QoS公平的反馈控制实时调度算法NF-QoS
• 4.3.1 标准化QoS公平
• 4.3.2 NF-QoS调度框架
• 4.3.3 控制规则
• 4.3.3.1 PID控制器
• 4.3.3.2 QoS调节器
• 4.3.3.3 接收控制器
• 4.3.4 稳定性分析
• 4.4 仿真实验及结果分析
• 4.5 小结
• 第5章 基于SEF模型的实时操作系统设计与实现
• 5.1 SEF（服务体/执行流）模型介绍
• 5.1.1 执行流
• 5.1.2 服务体
• 5.1.3 服务体的地址空间
• 5.1.3.1 服务体的地址空间结构
• 5.1.3.2 服务体空间的构成
• 5.1.4 服务体间通信机制
• 5.1.4.1 端口、对象和小端口
• 5.1.4.2 端口变换
• 5.1.4.3 消息
• 5.1.4.4 消息传递
• 5.1.5 系统并发及调度模型
• 5.2 SEF模型对实时调度的支持
• 5.2.1 服务体间同步消息传递与传统同步通信方式的比较
• 5.2.2 优先级反转问题
• 5.2.3 调度策略的动态加载
• 5.3 实时操作系统RT-MiniCore的设计
• 5.3.1 RT-MiniCore的整体架构
• 5.3.1.1 RT-MiniCore的架构层次
• 5.3.1.2 几个重要服务体的功能
• 5.3.1.3 调度服务体与其它服务体的交互
• 5.3.2 RT-MiniCore设计实现中的关键技术
• 5.3.2.1 中断处理机制
• 5.3.2.2 定时机制
• 5.3.2.3 抢占式并发
• 5.3.2.4 同步机制
• 5.3.2.5 通信机制
• 5.3.2.6 内存管理对实时性的支持
• 5.3.3 调度服务体的设计
• 5.3.3.1 总体调度方案
• 5.3.3.2 优先级的构成
• 5.3.3.3 核心数据结构
• 5.3.3.4 重要接口及内部函数
• 5.4 小结
• 第6章 RT-MiniCore的性能评测
• 6.1 实验环境
• 6.2 测试方法
• 6.3 混合实时调度实验
• 6.3.1 实验方案
• 6.3.1.1 方案设计
• 6.3.1.2 软实时任务参数设置及程序
• 6.3.1.3 硬实时任务参数设置及程序
• 6.3.2 实验组合1:轻度负载
• 6.3.3 实验组合2:中度负载
• 6.3.4 实验组合3:重度负载
• 6.3.5 实验分析
• 6.4 调度开销实验
• 6.4.1 实验方案
• 6.4.2 实验结果分析
• 6.5 小结
• 第7章 总结
• 7.1 本文工作的总结
• 7.2 本文的主要贡献
• 7.3 进一步工作的展望
• 参考文献
• 攻读学位期间撰写的学术论文