混合关键级调度的若干关键问题研究

摘要

以航空、汽车领域为代表的现代嵌入式实时系统，高安全标准的软件功能与其它非安全关键的软件功能共享一个嵌入式平台，以解决软件功能多样化、复杂化的需求与硬件平台受限SWaP（size weight and price）需求的冲突。此类系统的实时调度需同时满足两个目标:一是在相对保守的时间属性设定下，满足认证标准对涉及安全关键功能的验证要求;同时在较乐观的时间属性设定下，满足高效利用计算资源的设计要求。这类混合关键级系统的调度问题，无法使用传统的实时调度算法解决。混合关键级调度问题已成为嵌入式领域极富挑战的课题之一。
　　本文基于混合关键级调度对安全关键与非安全关键任务的不同调度需求，以及高效利用资源的目标，分别研究了针对高、低关键级任务的不同调度策略。主要研究工作与成果如下:
　　(1)基于事件触发系统关键级提升的实际情况，分析了高关键级任务的可调度性，得到了关键级提升期，高关键级任务可调度的充分条件。指出系统关键级提升的触发源于系统外部事件，基于响应时间分析技术，研究了关键级提升时刻对满足高关键级任务截止时限的影响;并据此，在关键级提升期，提出了一个有条件的优先级交换算法，可确保更多高关键级任务得到正确调度。仿真实验显示了可调度条件以及优先级交换算法的有效性。
　　(2)提出了一种适合以截止时限为关键参数的混合关键级任务调度算法。定义了截止时限依赖于关键级的混合关键级任务模型，分析了关键级提升期低关键级任务对高关键级任务调度可能产生的干扰，以预先提升关键级的方式，牺牲有限的低关键任务，可始终满足高关键级任务随系统关键级动态变化的截止时限。仿真实验验证了预关键级提升算法适合以截止时限为关键参数的任务调度，且不受高关键级任务比率和截止时限变化程度的影响。
　　(3)提出了一种适合同构多处理器平台上调度混合关键级任务的半局部调度算法。兼顾高关键任务利用率和低关键级任务可调度性，将全部高关键级任务和大部分低关键级任务固定在既定处理器上执行，仅有数量不超过处理器数目的低关键级任务成为迁移任务，能且仅能在相邻的两个处理器上发生迁移，并同步执行。以有限的迁移换取对处理器资源的高效利用，并总能满足高关键级任务的截止时限。仿真实验结果表明该半局部调度算法，相较于局部调度混合关键级任务的方法，将可调度任务比率提升了近10％。
　　(4)提出了一种积极处理低关键任务的策略。对于符合标准认证的混合关键级系统，在关键级提升之后，回收多处理平台上执行中的空闲时段，以全局分配的方式匹配到被抛弃的低关键级任务，既不干扰局部调度的高关键级任务，又能让尽可能多的任务获得正确调度，以提升资源利用率。仿真实验与既有的TA、CD、CD-A算法比较，积极处理低关键级任务策略在系统可接受任务数目和抛弃任务比率上，均有明显优势。
　　(5)提出了一种自适应回落系统关键级的闭环机制。基于实时任务在不同执行模式下实际执行时间的分布特性，监测高关键级任务的实际执行时间，预测高关键级任务利用率变化趋势与执行模式，可及时恢复调度此前关键级提升时被抛弃的低关键任务，且不影响高关键级任务的正确执行，实现安全降低系统关键级。仿真实验结果显示了自适应关键级回落算法优于至今被认为最优的BP方法。

目录

声明

摘要

插图索引

插表索引

第1章 绪论

1．1 安全关键分级的实时系统

1．2 混合关键级系统概述

1．2．1 混合关键级的提出

1．2．2 混合关键级系统模型

1．2．3 混合关键级系统研究现状

1．3 研究内容

1．4 本文研究成果

1．5 论文的组织

第2章 相关研究

2．1 关键级与优先级对任务调度的不同影响

2．2 单处理器平台混合关键级任务调度

2．2．1 混合关键级调度研究目标

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

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

2．2．4 关键参数是周期的混合关键级调度

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

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

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

2．4 低关键级任务处理

2．4．1 处理关键级提升后的低关键级任务

2．4．2 回落系统关键级

2．5 其它相关研究

2．6 本章小结

第3章 事件触发关键级提升时的可调度性分析

3．1 混合关键级系统的关键级提升诱因

3．2 以执行时间为关键参数的混合关键级任务模型

3．3 关键级提升时刻对系统的影响

3．4 关键级提升期的响应时间分析

3．4．1 响应时间分析

3．4．2 混合关键级的响应时间分析

3．4．3 高关键级任务的可调度性判定

3．4．4 扩展至多关键级

3．5 优先级可交换的判定

3．5．1 动机示例

3．5．2 交换优先级的条件

3．6 实验与结果分析

3．6．1 测试任务集的生成

3．6．2 可调度性测试

3．6．3 优先交换算法的有效性测试

3．7 本章小结

第4章 截止时限为关键参数的混合关键级调度

4．1 截止时限

4．2 截止时限与关键级

4．2．1 截止时限为关键级的系统模型

4．3 受限截止时限高关键级任务的可调度性

4．3．1 低关键级任务的干扰

4．3．2 预先提升关键级

4．3．3 扩展至多关键级

4．4 实验与结果分析

4．4．1 生成测试任务集

4．4．2 结果分析

4．5 任意截止时限高关键级任务的可调度性

4．6 受影响的低关键级任务

4．7 本章小结

第5章 半局部调度混合关键级任务

5．1 半局部调度

5．1．1 典型半局部调度固定优先级任务SPA

5．1．2 典型半局部调度动态优先级EKG

5．2 半局部调度混合关键级任务

5．2．1 任务到处理器的分配

5．2．2 各处理器上任务的调度执行

5．3 实验与结果分析

5．3．1 测试任务集参数设定

5．3．2 实验结果分析

5．4 本章小结

第6章 积极调度低关键级任务

6．1 低关键级任务

6．2 空闲时段

6．3 低关键任务对空闲时段的再分配

6．3．1 模型与动机示例

6．3．2 积极调度低关键级任务算法描述

6．3．3 MC-DQ算法的再讨论

6．4 实验与结果分析

6．5 本章小结

第7章 安全降低系统关键级

7．1 嵌入式系统的自适应闭环特性

7．2 基于反馈的实时调度

7．3 系统关键级的安全降低

7．3．1 关键级模式

7．3．2 性能评估标准

7．4 单处理器平台上的自适应关键级回落

7．4．1 系统模型

7．4．2 关键级回落机制

7．4．3 混合关键级任务实际执行时间分布

7．4．4 取消仅有双关键级的限制

7．4．5 实验与结果分析

7．5 本章小结

结论

参考文献

致谢

附录A 攻读学位期间完成的论文

附录B 攻读学位期间参与的项目