实时系统任务调度若干关键技术的研究

论文摘要

随着实时系统在各领域的广泛应用，任务调度技术在实时系统中扮演的角色越来越关键。针对实时系统多任务、多处理器和具有复杂优先约束等特点，论文在传统任务调度理论的基础上，重点研究了当代任务调度技术的新理论和新方法，特别是对不同环境和条件下的任务系统可调度性分析方法和调度算法进行了深入研究。 本文研究工作主要集中在以下几个方面： 针对速率单调分析技术在系统设计建模阶段缺乏对任务间优先约束关系及多处理器环境的考虑，提出基于可抢占时间Petri网的任务建模与检测方法。通过状态空间枚举和暂停变迁的概念，对具有优先约束的任务集在多处理器环境下进行建模与检测，并用仿真实例说明该方法在多处理器可抢占条件下，能够快速量化分析具有复杂属性的实时任务集合。 针对周期任务的可调度性判定问题，提出基于累积时间需求的任务可调度性分析方法和一种改进的抢占阈值任务响应时间分析方法。在对任务繁忙区的分析中，加入对任务释放抖动所需的额外响应时间的计算，提高了周期任务可调度性测试的精确性，解决了周期任务缺少通用可调度性分析方法的问题。 针对优先级驱动的任务调度过程中可能出现的非受控优先级逆转问题，提出一种基于抢占阈值理论的新型防范方法。在抢占阈值下重新定义了优先级逆转问题以及优先级继承协议和优先级限顶协议，通过加入有效优先级等概念，有效减少了任务抢占，避免发生优先级逆转现象。 针对任务具有优先约束的情况，研究了与或优先约束任务的调度算法。基于非精确模型强制任务概念，提出一种改进的顶点删除算法，解决了此类任务调度完成时间最小化问题。同时还提出一种与或优先任务最早开始时间算法，解决了时间跨度最小化问题。 针对实时系统多任务、多处理器特点，对多处理器环境下基于划分策略的任务分配算法可调度条件进行了分析，从任务分配调度算法所需处理器数量和任务集总利用率的角度比较多种任务分配算法的性能，并对算法利用率界限进行了分析。最后给出不同特征任务集选择不同分配算法的指导性原则。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景、目的与意义
• 1.1.1 实时系统应用背景
• 1.1.2 研究目的与意义
• 1.2 实时系统概述
• 1.2.1 实时系统体系结构
• 1.2.2 实时系统特征
• 1.2.3 实时系统分类
• 1.2.4 实时任务分类
• 1.3 实时任务调度技术现状
• 1.3.1 经典调度理论
• 1.3.2 实时任务调度理论
• 1.3.3 国内外发展与研究现状
• 1.4 论文主要研究内容
• 1.4.1 研究内容
• 1.4.2 研究内容相关性
• 1.5 论文组织结构
• 第2章 基于抢占时间PETRI网的实时系统建模
• 2.1 实时系统参考模型
• 2.1.1 模型总览
• 2.1.2 周期任务模型
• 2.2 可抢占的时间PETRI网模型
• 2.2.1 形式化定义
• 2.2.2 行为语义
• 2.3 状态空间分析
• 2.3.1 状态类的语义可达性
• 2.3.2 可达性分析
• 2.4 任务集建模和检验
• 2.4.1 独立任务建模与比较
• 2.4.2 多处理器优先约束任务建模与检验
• 2.4.3 复杂性分析
• 2.5 本章小结
• 第3章 周期任务可调度性分析方法
• 3.1 背景和问题描述
• 3.1.1 背景
• 3.1.2 问题提出及贡献
• 3.2 基于时间需求的任务可调度性分析
• 3.2.1 时间需求分析
• 3.2.2 任务可调度性测试方法
• 3.2.3 性能仿真
• 3.3 改进的基于抢占阈值的任务可调度性分析
• 3.3.1 抢占阈值调度假设与过程
• 3.3.2 任务集可调度性、属性分配和定量评估
• 3.3.3 抢占阈值调度的可调度性分析
• 3.3.4 性能比较
• 3.4 本章小结
• 第4章 不受控的任务优先级逆转防范方法
• 4.1 问题描述
• 4.1.1 一般优先级逆转
• 4.1.2 非受控的优先级逆转
• 4.2 传统解决方案
• 4.2.1 禁用所有硬件中断
• 4.2.2 基本优先级继承协议
• 4.2.3 基本优先级限顶协议
• 4.3 基于抢占阈值模型的方案
• 4.3.1 抢占阈值模型
• 4.3.2 抢占阈值模型下的优先级逆转
• 4.3.3 性能仿真
• 4.4 本章小结
• 第5章 与或优先约束任务调度算法
• 5.1 问题描述与相关工作
• 5.2 非精确计算技术
• 5.3 与/或网模型描述
• 5.4 与或优先调度的可行性
• 5.5 与/或优先约束任务启发式调度算法
• 5.5.1 问题的复杂性
• 5.5.2 跳跃系统最小完成时间算法
• 5.6 最早开始调度算法
• 5.6.1 ES算法调度可行性及问题描述
• 5.6.2 严格正处理时间下的ES算法
• 5.6.3 算法示例与分析
• 5.7 本章小结
• 第6章 多处理器任务分配算法选择原则的分析
• 6.1 调度策略
• 6.2 多处理器任务调度模型
• 6.3 装箱问题的启发式算法
• 6.4 划分策略下的RM调度方法
• 6.4.1 多处理器RM可调度性判定条件
• 6.4.2 基于划分方案的启发式RM任务分配算法
• 6.4.3 多处理器分配算法利用率界分析
• 6.5 性能仿真
• 6.5.1 处理器集和任务集描述
• 6.5.2 性能指标
• 6.5.3 实验结果及分析
• 6.6 本章小结
• 结论
• 参考文献
• 攻读博士学位期间发表的论文和取得的科研成果
• 致谢