基于分层调度的实时系统容错技术研究

摘要

近年来，实时系统被广泛地应用到安全关键的汽车电子领域。除保证实时应用输出结果的逻辑正确性外，还必须具有严格的时间确定性和高度的可靠性，否则会导致严重后果。然而随着应用需求的扩展，当前实时系统应用软件朝着大规模、高复杂度的方向发展，其安全性与可靠性问题变得日益突出。如何利用容错技术，使实时系统在出错后行为可控是十分必要的。
　　 本文对分层实时调度框架进行了研究，详细分析实时系统中广泛采用的基于任务复制的容错算法，归纳出其中存在的问题:1）已有系统可靠性模型假设系统某一时刻只有一个故障，且在下个故障来时上个故障已解决，假设较为理想导致实用性不强;2）盲目地使每个任务拥有ε+1个副版容忍可能的ε个故障，虽然提高可靠性但易造成系统冗余度过高，可能引发任务因竞争计算资源而错过截止期。
　　 针对上述问题，本文将借助分层调度框架提供的基于组件的设计和分析方法以及主动任务复制容错技术，以满足系统可靠性目标和最小化冗余资源为目的，在多处理器平台上展开实时系统容错理论和算法研究。
　　 首先，提出了一种同构系统周期任务复制容错算法。在建模阶段，以一个超周期作为量化标准，从总体上通过使用概率统计的方法分析系统可靠性，实现了对基于周期任务集的系统可靠性模型建模。在精确量化分析阶段，依据系统可靠性目标和对系统可靠性模型的分析，给出了任务复制次数边界值的计算方法，在一定程度上避免对任务的盲目复制。接着，根据任务对系统可靠性贡献和占用系统计算资源情况的差异，提出了一种经济的任务复制策略，从而在尽量减少因任务复制而增加计算资源消耗的条件下，达到动态确立各个任务的复制个数。
　　 其次，提出了一种异构系统DAG任务复制容错算法。针对建模阶段，通过对DAG图中任务依赖关系分析，建立了单DAG的可靠性模型，并在其基础上，实现了对多DAG系统的可靠性建模。在量化分析阶段，借助已建立的可靠性模型和每次选择可靠性代价最小处理机的思想，提出了一种任务复制次数下限值算法。然后采用上述经济的任务复制策略，在系统可靠性目标的驱使下动态地量化各个任务需要冗余复制次数，并在多处理机平台上为任务分配处理器调度。
　　 仿真实验结果表明，与以往盲目的任务复制容错方法相比，以上算法能够从整体上达到系统的可靠性目标并最小化占用的冗余计算资源。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 选题背景及意义

1．2 实时系统的容错问题

1．3 本文主要工作

1．4 论文组织结构

1．5 小结

第2章 相关研究

2．1 容错研究基础

2．1．1 容错相关概念

2．1．2 传统容错技术

2．2 实时系统的分层调度

2．2．1 分层调度框架

2．2．2 基于分层调度框架的相关研究

2．3 实时系统的容错算法

2．3．1 基于主动复制的容错算法

2．3．2 基于被动复制的容错算法

2．3．3 基于混合复制的容错算法

2．3．4 几种任务复制容错算法的比较

2．4 实时系统容错解决方案

2．5 小结

第3章 同构系统周期任务复制容错算法

3．1 同构系统模型与假设

3．1．1 同构系统架构

3．1．2 周期任务模型

3．1．3 周期任务可靠性模型

3．2 问题描述

3．3 同构系统可靠性分析

3．4 容错算法设计

3．4．1 系统可靠性约束与可靠性代价

3．4．2 周期任务复制次数边界值分析

3．4．3 周期性任务动态复制容错算法

3．5 仿真实验

3．5．1 实验平台及参数设置

3．5．2 实验结果及分析

3．6 小结

第4章 异构系统DAG任务复制容错算法

4．1 异构系统模型与假设

4．1．1 异构系统架构

4．1．2 DAG任务模型

4．1．3 DAG任务可靠性模型

4．2 异构系统可靠性分析

4．2．1 单DAG系统可靠性分析

4．2．2 多DAG系统可靠性模型

4．3 容错算法设计

4．3．1 系统可靠性约束与可靠性代价

4．3．2 DAG任务复制次数下限值算法

4．3．3 DAG任务动态复制容错算法

4．4 仿真实验

4．4．1 实验平台及实验样本

4．4．2 实验结果及分析

4．5 小结

结论

参考文献

附录A (攻读硕士学位期间所发表的学术论文)

附录B (攻读硕士学位期间所参与科研项目)

致谢