论文部分内容阅读
现代汽车电子系统是计算与网络都异构且深度融合的分布式嵌入式系统。系统的异构性、网络化和复杂化使得其调度问题相比通用异构分布式系统和传统嵌入式系统存在差异且更加复杂。现代汽车电子系统还是以安全关键为特征的,包含时间与性能关键、时间混合关键级及可靠性混合关键级的异构网络化嵌入式系统。为此,本文从汽车功能安全的角度出发,以确保车辆安全运行和车内外人身安全为主要目标,提出高性能、强实时和高可靠的若干调度理论与方法。异构网络化汽车电子系统的多种功能应用中,任务间的优先级约束日益复杂,AUTOSAR规范也指出需从功能级的角度对计算系统和网络系统进行集成设计。本文将汽车电子系统中的多个功能应用抽象成多个有向无环图DAG。在系统异构性、混合关键级和可靠性目标的驱动下,围绕性能、实时和可靠三个方面开展面向汽车的异构网络化嵌入式系统的多DAG调度研究。主要工作和创新点如下。(1)提出异构驱动的高性能多DAG静态调度的若干理论与方法。1)针对异构计算环境下的单DAG任务调度中,向上排序值使用平均计算开销的问题,定义异构优先级排序值HPRV作为任务优先级排序标准,实现计算开销的精确化。针对基于最小最早完成时间EFT的处理器分配方法仅考虑“向下看”的问题,从“向下看”和“向上看”的角度,定义异构最小选择值HSV作为处理器分配标准,提出高性能的单DAG任务调度算法HSV,以适应系统的计算异构性。2)针对融合异构网络环境的单DAG任务与消息调度中,向上排序值同样使用平均通信开销的问题,将通信开销定位到具体的处理器,实现通信开销的精确化。针对计算任务与通信消息独立调度的问题,提出高性能的单DAG任务与消息同步调度算法HSV_CC,以适应计算与网络都异构且深度融合的汽车电子系统。3)针对异构计算环境下的多DAG静态任务调度易出现局部单调和较高不公平性的问题,分别提出基于HPRV公平策略的多DAG静态任务调度算法F_MDSTS和多DAG静态任务与消息调度算法F_MDSTMS,最终实现高性能及公平的任务与消息同步调度。实验结果表明,提出的算法能够满足时间与性能关键的异构网络化汽车电子系统静态调度的高性能与公平性需求。(2)提出混合关键级驱动的强实时多DAG动态调度的若干理论与方法。1)针对异构计算环境下的多DAG动态任务调度存在因处理器忙碌而造成阻塞的问题,提出基于HPRV公平策略的多DAG动态任务调度算法F_MDDTS。在新DAG到达时,可以取消已分配处理器但未开始调度的任务,实现高性能的动态任务调度。提出基于关键级策略的多DAG动态任务调度算法C_MDDTS,确保高关键级应用的实时性。融合F_MDDTS和C_MDDTS,提出混合关键级策略的多DAG动态任务调度算法MC_MDDTS,既确保高关键级的实时性,又使得低关键级应用得到积极的处理。2)针对汽车电子系统中通信开销日益增长的问题,基于最小通信开销权值COW,以最小化通信开销为目标,提出公平策略的多DAG动态任务与消息调度算法F_MDDTMS。分别提出关键级策略的多DAG动态任务与消息调度算法C_MDDTMS和混合关键级策略的多DAG动态任务与消息调度算法MC_MDDTMS,在性能和实时性上取得合理的平衡。实验结果表明,提出的算法能够满足时间混合关键级的异构网络化汽车电子系统动态调度的强实时和高性能需求。(3)提出可靠性目标驱动的高可靠多DAG容错调度的若干理论与方法。1)通过分析异构计算环境下DAG任务的优先级约束,确定任务的可靠性模型,建立DAG计算可靠性模型。现有任务复制的容错方法要么DAG中的每个任务仅有一个副版本来容忍一个错误,要么盲目地使每个任务拥有ε个副本来容忍可能发生的ε个故障。针对上述问题,依次提出满足DAG计算可靠性目标的任务复制下限值算法、贪婪的和经济的任务复制策略算法,精确量化每个任务需要复制的次数。2)通过考虑任务与消息的同步特征,在任务复制策略的基础上,分别确定链路可靠性、通信路径可靠性和消息主版本集,最终建立消息可靠性模型和DAG通信可靠性模型。针对目前汽车电子系统中通信可靠性与容错方法采用固定个数的消息或链路复制的问题,依次提出满足通信可靠性目标的消息复制下限值算法、贪婪的和经济的消息复制算法,精确量化各消息需要复制的次数。3)基于DAG计算可靠性模型和任务复制容错算法,提出可选策略的多DAG处理器分配算法OSMDPA,实现任务与处理器的高效分配。基于DAG通信可靠性和消息复制容错算法,提出可选策略的多DAG通信路径分配算法OSMDRA,实现消息与通信路径的高效分配。基于OSMDPA和OSMDRA算法,提出可选策略的多DAG容错调度算法OSMDFTS,实现异构网络化汽车电子系统的高可靠容错。实验结果表明,提出的算法能够满足可靠性混合关键级的异构网络化汽车电子系统容错调度的高可靠和高性能需求。