异构分布式混合关键级系统调度优化研究

摘要

现代汽车电子系统是基于异构分布式集成架构的混合关键级系统。它同时融合了实时系统、混合关键级系统和异构分布式系统的相关特征，但在体系结构、软件系统和功能安全需求上又有自己的特定要求，特别是在性能与时间的约束方面需要仔细权衡。若从系统的角度来看，降低整个系统的调度长度，提高系统性能是其主要目标。若从功能的角度来看，满足其时间约束，确保实时性是其主要需求。然而，对于资源受限的大规模异构分布式混合关键级系统，很难满足所有分布式功能的时间约束。如何提高系统的整体性能，并确保高关键级功能的实时性是异构分布式混合关键级系统的任务调度需要优化的主要目标。为此，本文通过提出精确反映汽车电子系统中分布式功能的混合关键级系统模型，从“功能级”及“并行与分布式计算”的角度，提出优化的调度算法，最小化系统性能与功能时限之间的冲突，并在性能、实时性、成本和资源开销等方面取得合理的权衡。
　　本文的主要工作如下:
　　(1)静态多关键级系统的调度优化。多个不同安全关键级别的分布式功能集中到同一异构分布式混合关键级系统之中，良好的静态多关键级调度优化能够有效的指导现代汽车电子系统在分布式处理方面的设计。针对上述需求，本文基于网关互联的总线体系结构和汽车安全完整性等级中的伤害严重性级别，从“功能级”以及“并行与分布式计算”的角度，提出了一系列面向不同目标的静态调度算法。包括以提高系统性能为目标的公平策略算法F MHEFT，以满足更多高关键级功能实时性的整体优先策略算法WP_MHEFT和以优化性能与实时性为目标的部分优先策略算法PP_MHEFT，使得在系统整体性能和高关键级功能实时性之间取得良好的平衡。最后，通过实验对本文提出的3种算法进行了详细评估，实验结果验证了本文所提出的PP_MHEFT算法在满足更多高关键级功能实时性的条件下，能够有效的提高系统整体性能。
　　(2)动态双关键级系统的调度优化。混合关键级汽车电子系统是典型的信息物理融合系统，系统中的高安全关键级功能大都与物理世界进行动态交互。以线控刹车为代表的一类安全关键功能，不仅需动态实时触发，而且具有较高的时间关键级认证级别。动态与并发是汽车信息物理融合系统的固有属性。针对上述需求，以动态双关键级模型为基础，提出了面向不同目标的调度算法。包括以提高系统性能为目标的公平策略算法F DDHEFT，以满足更多高关键级功能实时性的关键级策略算法C DDHEFT，和在满足更多高关键级功能实时性的基础上，提高系统性能的时限时距策略算法D_DDHEFT。D_DDHEFT在不提高算法时间复杂度的情况下，使得在系统整体性能和高关键级功能的实时性之间能够达到一种合理的权衡。最后利用仿真实验对提出的算法进行比较，验证了提出的优化算法的有效性。
　　(3)通信竞争的动态双关键级系统的调度优化。高端的混合关键级汽车电子系统是基于异构分布式的集成体系结构，是计算与网络均异构且深度融合的嵌入式系统。在该系统中，计算与网络具有同等重要的地位，需对相关计算进行精确化，并使用合理的任务与消息同步分配的调度算法。本文基于双关键模型，研究通信竞争的动态环境下的调度优化。通过建立通信竞争的异构计算模型和异构网络模型，在通信竞争环境下，实现了向上排序值和最早完成时间的精确化，以适应系统中计算与网络均异构且任务与消息同步的特征。更进一步，分别提出公平策略、关键级策略和时限时距策略的调度算法。最后利用仿真实验对提出的算法进行评估，验证了提出的优化算法的有效性。
　　(4)多核混合关键级系统中关键级感知的调度优化。多个关键级功能在同一硬件平台上的集成将促使多核等高性能嵌入式计算平台在汽车电子等混合关键级关键系统中得到广泛应用。但是多核调度优化首先需解决任务到处理核的分配问题。混合关键级系统中的高关键级功能可通过关键级分解来降低开发和认证成本，但是同时它将在处理器、带宽资源方面带来一定开销。因此，多核混合关键级系统中的任务分配需在成本和系统资源利用率之间取得平衡。提出基于模拟退火算法的启发式任务分配算法CTM，在保证满足系统可调度的前提下实现成本和资源开销的联合优化。最后通过在真实汽车电子功能集和仿真功能集上开展的多个对比实验证明了CTM算法在实现成本和资源权衡优化方而的有效性。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景及意义

1．2 体系结构

1．3 软件系统

1．4 功能安全

1．5 本文主要工作

1．6 本文组织结构

第2章 相关研究

2．1 概述

2．2 单处理器混合关键级调度相关研究

2．2．1 固定优先级调度算法

2．2．2 动态优先级调度算法

2．3 多处理器混合关键级调度相关研究

2．4 分布式系统混合关键级调度相关研究

2．5 国内的相关研究

2．6 本章小结

第3章 静态多关键级系统的调度优化

3．1 系统模型

3．1．1 分布式功能抽象

3．1．2 混合关键级系统抽象

3．1．3 静态多关键级模型

3．2 公平策略与整体优先策略的调度

3．2．1 认证分析

3．2．2 公平策略的高性能调度

3．2．3 整体优先策略的实时调度

3．3 部分优先策略的优化调度

3．3．1 PP_MHEFT算法

3．3．2 PP_MHEFT实例

3．4 实验

3．4．1 评价指标

3．4．2 实验分析

3．5 本章小结

第4章 动态双关键级系统的调度优化

4．1 系统模型

4．2 公平策略与关键级策略的调度

4．2．1 认证分析

4．2．2 公平策略的高性能调度

4．2．3 关键级的实时策略

4．3 时限时距策略的优化调度

4．3．1 D_DDHEFT算法

4．3．2 D_DDHEFT实例

4．4 实验

4．4．1 评价指标

4．4．2 实验分析

4．5 本章小结

第5章 通信竞争的动态双关键级系统的调度优化

5．1 系统模型

5．1．1 通信竞争

5．1．2 任务与消息的同步

5．1．3 通信竞争的功能模型

5．1．4 异构网络模型

5．2 通信竞争下的计算精确化

5．2．1 向上排序值的精确化

5．2．2 最早完成时间的精确化

5．3 考虑通信竞争的优化调度

5．3．1 公平策略的高性能调度

5．3．2 关键级策略的实时调度

5．3．3 时限时距策略的优化调度

5．4 实验

5．4．1 评价指标

5．4．2 实验分析

5．5 本章小结

第6章 多核混合关键级系统中关键级感知的调度优化

6．1 系统模型

6．1．1 系统结构

6．1．2 任务和消息模型

6．1．3 成本模型

6．2 关键级感知的任务分配算法

6．3 实验

6．4 本章小结

结论

参考文献

攻读博士学位期间所发表的学术论文

攻读博士学位期间所参加的科研项目

致谢