基于虚拟截止期的混合关键任务调度研究

摘要

随着信息技术的飞速发展，嵌入式系统的使用越来越广泛，硬件系统的集成功能也日益复杂。由于受到系统成本、体积、能耗、利用率等方面的约束，在嵌入式系统中采用一个共享的处理器平台来处理不同关键性功能的应用，成为新的发展方向。此类系统也称为混合关键性系统，混合关键性概念的产生，为嵌入式系统的设计提供了新的发展空间。其中，混合关键性调度算法设计以及调度的正确性分析成为了学术界研究的热点。混合关键性实时调度需同时满足两个目标:即在悲观的时间属性下，要满足高关键性功能的验证要求;同时在不那么悲观的时间属性下，满足高效利用系统资源的设计要求。
　　本研究首先对现有混合关键性任务调度算法进行了详细分析，最早虚拟截止期混合关键性任务调度算法具有较好的调度性能，成为了一个主流调度算法，算法在不同模式下为高关键任务设置两个不同的截止期，提高了低关键任务的可调度数。虽然在单处理器混合关键调度中此算法是最优算法，但它是基于模式转换时所有高关键任务同时转换到高关键模式的假设，实际应用中这种现象出现的概率很小。本文在满足高关键任务调度的情况下，以提高低关键任务和系统资源利用率为目标，在混合关键性最早虚拟截止期算法的基础上，提出了一种改进的虚拟截止期调度算法。算法引入高关键任务超出低关键模式下最坏执行时间的概率和系统失败率的阈值到任务模型中，然后基于任务分簇算法为超出低关键模式下的高关键任务提供额外资源。由于只有部分高关键任务同时进入高关键模式，则在高关键模式下部分低关键任务仍可调度，无需完全抛弃。仿真结果也表明，在保证任务调度性能的前提下，所提出的改进算法可调度任务数多于经典最早虚拟截止期算法。

目录

摘要

1．1 研究背景及意义

1．2 研究现状

1．3 本文研究工作

1．4 本文结构安排

2 混合关键系统调度相关知识

2．1 实时系统的基本概念

2．1．1 实时系统

2．1．2 实时调度

2．1．3 实时任务分类

2．2 传统实时调度算法

2．2．1 静态调度算法

2．2．2 动态调度算法

2．2．3 混合调度算法

2．3 混合关键系统的概念

2．4 混合关键系统研究内容

2．5 混合关键性调度模型

2．5．1 任务模型与定义

2．5．2 系统处理器利用率

2．6 可调度性分析

2．6．1 可调度性判定方法

2．6．2 调度性能评价

2．7 本章小结

3 混合关键性任务调度算法

3．1 单处理器混合关键性任务调度

3．1．1 基于固定优先级的混合关键任务调度

3．1．2 基于动态优先级的混合关键任务调度

3．2 多处理器平台混合关键任务调度

3．2．1 多处理器混合关键调度分类

3．2．2 局部混合关键任务调度

3．2．3 全局混合关键任务调度

3．3 低关键级任务的处理

3．4 其他相关的研究

3．5 本章小结

4 改进的最早虚拟截止期算法

4．1 改进算法设计

4．1．1 基于概率的调度模型

4．1．2 实例分析

4．1．3 任务分簇

4．2 算法过程

4．2．1 算法预处理

4．2．2 算法调度

4．3 算法应用实例

4．4 本章小结

5．1 仿真设置

5．2 仿真结果分析

5．2．1 不同参数下PEDF-VD性能分析

5．2．2 EDF-VD与PEDF-VD算法比较

5．3 本章小结

6．1 工作总结

6．2 全文展望

参考文献

攻读硕士期间取得的研究成果

致谢

声明