面向混合关键性系统与DRT模型的实时调度问题研究
发布时间：2023-06-27 23:01
现代实时嵌入式系统不断发展的一个重要趋势是在同一硬件平台中集成多种不同关键性级别的应用。与此同时,嵌入式系统硬件也在经历从单核平台向多核平台的变革之中,未来还将发展至众核平台。但是这种混合关键性系统的调度问题即便是对于单核平台也是极具挑战性的。目前,大多数复杂的嵌入式系统很难被传统基于周期的简单模型所精确描述。实时任务有向图(DRT)模型具备很强的描述能力,可以用于没有循环时间行为的复杂实时系统的建模。但是针对该模型的精确时间分析在时间复杂度上通常是不可接受的(指数级复杂度)。本文研究了基于混合关键性系统和DRT模型的实时调度算法的设计与分析等问题。在混合关键性系统研究方面,提出了一种高效的单核处理器运行时调度算法,和两种多核、多处理器划分调度算法。在DRT模型研究方面,提出了两种有效的近似响应时间分析方法,并通过计算加速比进行了量化评价,还提出了一种有效的有向图整形算法来提升系统的可调度性。本文的主要贡献点可以被总结如下:(1)提出了基于OCBP策略的固定作业优先级单处理器混合关键性实时调度算法LPA。与其它OCBP族的算法相比,LPA算法显著提升了系统的运行时时间效率(线性时间复杂...
【文章页数】：149 页
【学位级别】：博士
【文章目录】：
摘要
ABSTRACT
第1章 绪论
1.1 研究背景及意义
1.2 国内外研究现状
1.2.1 混合关键性系统
1.2.2 基于图的实时任务模型
1.3 本文研究内容与贡献
1.3.1 面向混合关键系统的研究
1.3.2 面向实时任务有向图模型的研究
1.4 本文组织结构
第2章 线性时间复杂度混合关键性调度算法
2.1 系统模型与定义
2.1.1 混合关键性偶发任务系统的运行时行为
2.1.2 混合关键性系统的可调度性
2.2 LPA算法
2.2.1 离线优先级分配算法
2.2.2 运行时调度算法
2.2.3 LPA算法实例
2.2.4 运行时时间复杂度
2.3 忙碌周期上界计算
2.4 LPA算法可调度性的证明
2.5 实验结果与分析
2.5.1 随机任务集合生成
2.5.2 时间开销
2.5.3 空间开销
2.5.4 可调度接受率
2.6 小结
第3章 基于虚拟截止期的划分调度算法
3.1 基本概念
3.1.1 混合关键性任务和混合关键性作业
3.1.2 需求上界函数DBF
3.1.3 EY-VD方法
3.2 MPVD划分调度算法
3.2.1 混合划分策略
3.2.2 MPVD划分调度算法
3.3 MPVD算法优化技术
3.3.1 重型低关键性任务敏感的划分策略
3.3.2 虚拟截止期调整优化算法
3.4 实验结果与分析
3.4.1 随机任务集合生成
3.4.2 实验结果分析
3.5 小结
第4章 多处理器混合关键性系统划分调度策略
4.1 基本概念
4.1.1 需求上界函数DBF
4.2 基于传统划分策略的混合关键性划分调度算法
4.2.1 多处理器划分调度的基本方法
4.2.2 MC-PEDF算法的描述
4.2.3 MC-PEDF算法的时间复杂性与正确性分析
4.3 针对混合关键性系统的多次划分实时调度策略
4.3.1 传统划分策略的局限性
4.3.2 混合关键性模型中的新型划分策略OCOP
4.3.3 MC-MP-EDF算法描述
4.3.4 算法正确性分析
4.3.5 算法复杂性分析
4.4 实验仿真与结果分析
4.4.1 随机任务集生成算法
4.4.2 实验结果分析
4.5 小结
第5章 实时任务有向图的近似响应时间分析
5.1 系统模型与定义
5.1.1 模型定义
5.1.2 模型语义
5.1.3 静态优先级调度和最差响应时间
5.2 近似响应时间分析
5.2.1 RBF:需求上界函数分析方法
5.2.2 IBF:干涉上界函数分析方法
5.2.3 一些性质
5.3 加速比分析
5.3.1 RBF方法的加速比
5.3.2 IBF方法的加速比
5.4 实验结果与分析
5.4.1 随机任务集合生成方法
5.4.2 实验结果分析
5.5 小结
第6章 基于DRT模型的优化可调度性算法
6.1 问题模型
6.2 任务有向图整形的基本思想
6.3 高效整形算法
6.3.1 算法概述
6.3.2 需求上界函数rbfT
6.3.3 SlfBound()过程
6.3.4 ItfBound()过程
6.3.5 整形算法的性质
6.4 实验评价
6.4.1 生成随机任务集合
6.4.2 实验结果分析
6.5 小结
第7章 结论
7.1 本文主要贡献与结论
7.1.1 面向混合关键系统的研究
7.1.2 面向实时任务有向图模型的研究
7.2 进一步的工作
7.2.1 基于混合关键系统
7.2.2 基于实时任务有向图模型
参考文献
致谢
攻博期间发表的论文
攻博期间参与的项目
作者简介
本文编号：3835504
【文章页数】：149 页
【学位级别】：博士
【文章目录】：
摘要
ABSTRACT
第1章 绪论
1.1 研究背景及意义
1.2 国内外研究现状
1.2.1 混合关键性系统
1.2.2 基于图的实时任务模型
1.3 本文研究内容与贡献
1.3.1 面向混合关键系统的研究
1.3.2 面向实时任务有向图模型的研究
1.4 本文组织结构
第2章 线性时间复杂度混合关键性调度算法
2.1 系统模型与定义
2.1.1 混合关键性偶发任务系统的运行时行为
2.1.2 混合关键性系统的可调度性
2.2 LPA算法
2.2.1 离线优先级分配算法
2.2.2 运行时调度算法
2.2.3 LPA算法实例
2.2.4 运行时时间复杂度
2.3 忙碌周期上界计算
2.4 LPA算法可调度性的证明
2.5 实验结果与分析
2.5.1 随机任务集合生成
2.5.2 时间开销
2.5.3 空间开销
2.5.4 可调度接受率
2.6 小结
第3章 基于虚拟截止期的划分调度算法
3.1 基本概念
3.1.1 混合关键性任务和混合关键性作业
3.1.2 需求上界函数DBF
3.1.3 EY-VD方法
3.2 MPVD划分调度算法
3.2.1 混合划分策略
3.2.2 MPVD划分调度算法
3.3 MPVD算法优化技术
3.3.1 重型低关键性任务敏感的划分策略
3.3.2 虚拟截止期调整优化算法
3.4 实验结果与分析
3.4.1 随机任务集合生成
3.4.2 实验结果分析
3.5 小结
第4章 多处理器混合关键性系统划分调度策略
4.1 基本概念
4.1.1 需求上界函数DBF
4.2 基于传统划分策略的混合关键性划分调度算法
4.2.1 多处理器划分调度的基本方法
4.2.2 MC-PEDF算法的描述
4.2.3 MC-PEDF算法的时间复杂性与正确性分析
4.3 针对混合关键性系统的多次划分实时调度策略
4.3.1 传统划分策略的局限性
4.3.2 混合关键性模型中的新型划分策略OCOP
4.3.3 MC-MP-EDF算法描述
4.3.4 算法正确性分析
4.3.5 算法复杂性分析
4.4 实验仿真与结果分析
4.4.1 随机任务集生成算法
4.4.2 实验结果分析
4.5 小结
第5章 实时任务有向图的近似响应时间分析
5.1 系统模型与定义
5.1.1 模型定义
5.1.2 模型语义
5.1.3 静态优先级调度和最差响应时间
5.2 近似响应时间分析
5.2.1 RBF:需求上界函数分析方法
5.2.2 IBF:干涉上界函数分析方法
5.2.3 一些性质
5.3 加速比分析
5.3.1 RBF方法的加速比
5.3.2 IBF方法的加速比
5.4 实验结果与分析
5.4.1 随机任务集合生成方法
5.4.2 实验结果分析
5.5 小结
第6章 基于DRT模型的优化可调度性算法
6.1 问题模型
6.2 任务有向图整形的基本思想
6.3 高效整形算法
6.3.1 算法概述
6.3.2 需求上界函数rbfT
6.3.3 SlfBound()过程
6.3.4 ItfBound()过程
6.3.5 整形算法的性质
6.4 实验评价
6.4.1 生成随机任务集合
6.4.2 实验结果分析
6.5 小结
第7章 结论
7.1 本文主要贡献与结论
7.1.1 面向混合关键系统的研究
7.1.2 面向实时任务有向图模型的研究
7.2 进一步的工作
7.2.1 基于混合关键系统
7.2.2 基于实时任务有向图模型
参考文献
致谢
攻博期间发表的论文
攻博期间参与的项目
作者简介
本文编号：3835504
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3835504.html
