《容错硬实时系统的可调度性分析》由会员分享，可在线阅读，更多相关《容错硬实时系统的可调度性分析（120页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学 博士学位论文 容错硬实时系统的可调度性分析 姓名：李俊 申请学位级别：博士 专业：计算机软件与理论 指导教师：卢炎生;阳富民 20070604 I 华华 中中 科科 技技 大大 学学 博博 士士 学学 位位 论论 文文 摘摘 要要 硬实时系统的一个关键因素在于时间上系统必须具有可预测性，系统必须确保 每个实时任务在限定的时间内完成。而正确的可调度性分析是建立可预测的硬实时 系统的重要手段之一。与无容错需求的实时系统相比，容错硬实时系统具有及时响 应、高可靠性、效率高和容错能力强等特征，容错实时系统的特点为可调度性分析 的研究提出了新的要求，这样就需要对原有的硬实时系统的可调度性分
2、析进行容错 方面的扩充，以进一步提高其在容错硬实时系统中的实际应用水平，使其能更好地 同时满足硬实时和容错的需求。 针对现有基于截止期限小于周期的容错硬实时任务模型的两种容错优先级分配 策略容错优先级继承策略和允许容错优先级提高策略在提高容错实时系统的容 错能力存在的缺陷，通过对截止期限小于周期的容错硬实时任务进行基于最坏响应 时间的可调度性分析，提出了一种允许容错优先级降低的分配策略，以便挪用高优 先级任务的空闲时间来处理低优先级任务的容错，从而保证出错的任务满足截止期 限的要求；并且根据这种分配策略的性质，设计了改进的容错优先级分配搜索算法 IFPCS（Improved Fault-Tol
3、erant Priority Configuration Search Algorithm）。经过研究 分析和实验验证，在继承和提高两种容错优先级分配策略无法提高系统的容错能力 的情况下，合理地降低任务的容错优先级，能够有效地提高容错实时系统的容错能 力。 虽然容错优先级提高分配策略和容错优先级降低分配策略在一定程度上能解决 在容错优先级继承分配策略下任务不可调度的问题，但是这两种分配策略都只是单 一地提高或降低容错优先级。基于这一原因，进一步分析了这三种容错优先级分配 策略在提高系统容错能力的不足，提出了一种容错优先级混合分配策略，既允许容 错优先级提高又允许容错优先级降低，并基于任务最坏响
4、应时间分析，设计了在这 种容错优先级混合分配策略下的容错优先级混合式分配搜索算法 FPCMS II 华华 中中 科科 技技 大大 学学 博博 士士 学学 位位 论论 文文 （Fault-Tolerant Priority Configuration Mixed Search Algorithm）。实验结果验证了在 提高系统容错能力方面，容错优先级混合分配策略均优于上述三种分配策略。 为了使容错硬实时任务模型更具典型性，所进行的可调度性分析结果能够适用 于各种容错实时系统，特别是实时通信系统和分布式系统中，解除了以往容错硬实 时任务的可调度性分析中对任务截止期限不能大于对应周期的限制。当截止期限
5、任 意值时，任务在完成第一次激活之前，可能会被第二次激活。这就意味着任务的第 二次激活不仅仅会被高优先级任务抢占，而且也会被第一次激活打断执行。因此， 通过分析任务的一系列激活的响应时间来分析这种任务模型在容错优先级继承策略 和容错优先级提高策略下的任务可调度性。经研究分析和实例验证，采取容错优先 级提高策略，能够有效地提高任务的可调度性。最后根据容错优先级提高策略，设 计了基于截止期限任意值的容错硬实时任务模型的容错优先级分配搜索算法。 现有的静态优先级调度算法都假定系统优先级个数无限多，而实际上底层系统 支持的优先级个数是有限的。通过对优先级有限时的容错硬实时任务进行可调度性 分析，提出了
6、一种合适的解决方案来提高任务的可调度能力。这个方法主要的思想是 允许任务的替代任务在更高的系统优先级上来恢复故障，这样能更好地挪用高系统优 先级上的空闲时间。为了比较在不同容错优先级分配策略下优先级有限时容错硬实时 任务的可调度性，引入了“相对可调度饱和度”的概念来作为评价所讨论的优先级有限 时容错硬实时任务可调度性的指标。经过研究分析和实验验证，与容错优先级继承策 略相比，允许容错优先级合理地提高，能够有效地提高系统的可调度能力。 为了满足高可靠性实时系统的应用需求，对 RTLinux 实时操作系统进行了容错 实时性改造。首先，采取了基于主/副版本技术的容错模型，对实时线程控制块进行了 重新
7、定义；其次，根据先前提出的基于最坏相应时间的容错任务可调度性分析实现了 基于 FPCMS 算法的容错实时任务分析器；最后，给出了容错实时任务的设计框架。 关键词：硬实时，容错，可调度性分析，最坏响应时间，容错优先级，系统容错能力 III 华华 中中 科科 技技 大大 学学 博博 士士 学学 位位 论论 文文 Abstract Hard real-time systems are those that specified in terms of strong timing constraints. And, predictability and fault tolerant are major
8、requirements for complex hard real-time systems, which are either safety or mission critical. Traditionally fault tolerant techniques were employed to tackle the problem of ensuring correctness in the value domain only. We stress that the fault tolerance requirements and timing constraints are not o
9、rthogonal issues as they appear to be, and hence any viable approach must be an integrated one. Fault tolerance in a real-time system implies that the system is able to deliver correct results in a timely manner even in the presence of faults. Techniques employing time redundancy are commonly used f
10、or tolerating a wide class of faults sucn as transient faults. In these systems, it is essential that the exploitation of time redundancy for correctness does not jeopardize the timeliness attribute. Hence scheduling aspects of fault tolerant hard real-time systems become all the more important. The
11、 research work described in this thesis, focuses on the schedulability analyisis of fault tolerant task sets. These schedulability analyses are based on the assignment approach of fault-tolerant priorities, and are formulated under various assumptions regarding the computation models and frequency o
12、f fault occurrences. Considering the fault-tolerant hard real-time task sets with the case that the tasks deadline must be no more than its period. Due to the shortcoming of the two traditional fault-tolerant priority assignment policies for the system fault resilience, including the fault-tolerant
13、priority inheritance approach and the fault-tolerant priority improvement approach, a new fault-tolerant priority assignment algorithm was proposed. This algorithm can be used, together with the presented schedulability analysis, to effectively improve system fault resilience when the two former app
14、roaches cannot do it. The proposed IV 华华 中中 科科 技技 大大 学学 博博 士士 学学 位位 论论 文文 schedulability analysis takes into account the fact the recoveries of tasks may be executed at lower priority levels. And, an improved fault-tolerant priority configuration search algorithm is also presented for the proposed a
15、nalysis. Moreover, the effectiveness of the proposed approach is evaluated by simulation. It is worth noting that the three fault-tolerant priority assignment approaches as referred above allow the fault-tolerant priorities only monotonously improving or descreasing, which possibly makes the task se
16、t unschedulable. A fault-tolerant priority configuration mixed search algorithm based on schedulability analysis for fault-tolerant hard real-time system has been proposed. This algorithm can be used to effectively improve fault resilience since the recoveries of tasks are allowed to execute at either higher priority levels or lower priority levels. We compare the performance of this mixed search algorithm with that of other faul
