【作者】 李俊；

【导师】 卢炎生； 阳富民；

【作者基本信息】 华中科技大学 ， 计算机软件与理论， 2007， 博士

【摘要】 硬实时系统的一个关键因素在于时间上系统必须具有可预测性,系统必须确保每个实时任务在限定的时间内完成。而正确的可调度性分析是建立可预测的硬实时系统的重要手段之一。与无容错需求的实时系统相比,容错硬实时系统具有及时响应、高可靠性、效率高和容错能力强等特征,容错实时系统的特点为可调度性分析的研究提出了新的要求,这样就需要对原有的硬实时系统的可调度性分析进行容错方面的扩充,以进一步提高其在容错硬实时系统中的实际应用水平,使其能更好地同时满足硬实时和容错的需求。针对现有基于截止期限小于周期的容错硬实时任务模型的两种容错优先级分配策略——容错优先级继承策略和允许容错优先级提高策略在提高容错实时系统的容错能力存在的缺陷,通过对截止期限小于周期的容错硬实时任务进行基于最坏响应时间的可调度性分析,提出了一种允许容错优先级降低的分配策略,以便挪用高优先级任务的空闲时间来处理低优先级任务的容错,从而保证出错的任务满足截止期限的要求;并且根据这种分配策略的性质,设计了改进的容错优先级分配搜索算法IFPCS(Improved Fault-Tolerant Priority Configuration Search Algorithm)。经过研究分析和实验验证,在继承和提高两种容错优先级分配策略无法提高系统的容错能力的情况下,合理地降低任务的容错优先级,能够有效地提高容错实时系统的容错能力。虽然容错优先级提高分配策略和容错优先级降低分配策略在一定程度上能解决在容错优先级继承分配策略下任务不可调度的问题,但是这两种分配策略都只是单一地提高或降低容错优先级。基于这一原因,进一步分析了这三种容错优先级分配策略在提高系统容错能力的不足,提出了一种容错优先级混合分配策略,既允许容错优先级提高又允许容错优先级降低,并基于任务最坏响应时间分析,设计了在这种容错优先级混合分配策略下的容错优先级混合式分配搜索算法FPCMS(Fault-Tolerant Priority Configuration Mixed Search Algorithm)。实验结果验证了在提高系统容错能力方面,容错优先级混合分配策略均优于上述三种分配策略。为了使容错硬实时任务模型更具典型性,所进行的可调度性分析结果能够适用于各种容错实时系统,特别是实时通信系统和分布式系统中,解除了以往容错硬实时任务的可调度性分析中对任务截止期限不能大于对应周期的限制。当截止期限任意值时,任务在完成第一次激活之前,可能会被第二次激活。这就意味着任务的第二次激活不仅仅会被高优先级任务抢占,而且也会被第一次激活打断执行。因此,通过分析任务的一系列激活的响应时间来分析这种任务模型在容错优先级继承策略和容错优先级提高策略下的任务可调度性。经研究分析和实例验证,采取容错优先级提高策略,能够有效地提高任务的可调度性。最后根据容错优先级提高策略,设计了基于截止期限任意值的容错硬实时任务模型的容错优先级分配搜索算法。现有的静态优先级调度算法都假定系统优先级个数无限多,而实际上底层系统支持的优先级个数是有限的。通过对优先级有限时的容错硬实时任务进行可调度性分析,提出了一种合适的解决方案来提高任务的可调度能力。这个方法主要的思想是允许任务的替代任务在更高的系统优先级上来恢复故障,这样能更好地挪用高系统优先级上的空闲时间。为了比较在不同容错优先级分配策略下优先级有限时容错硬实时任务的可调度性,引入了“相对可调度饱和度”的概念来作为评价所讨论的优先级有限时容错硬实时任务可调度性的指标。经过研究分析和实验验证,与容错优先级继承策略相比,允许容错优先级合理地提高,能够有效地提高系统的可调度能力。为了满足高可靠性实时系统的应用需求,对RTLinux实时操作系统进行了容错实时性改造。首先,采取了基于主/副版本技术的容错模型,对实时线程控制块进行了重新定义;其次,根据先前提出的基于最坏相应时间的容错任务可调度性分析实现了基于FPCMS算法的容错实时任务分析器;最后,给出了容错实时任务的设计框架。更多还原

【Abstract】 Hard real-time systems are those that specified in terms of strong timing constraints. And, predictability and fault tolerant are major 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 orthogonal 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 for 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 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 of fault occurrences.Considering the fault-tolerant hard real-time task sets with the case that the task’s 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 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 approaches cannot do it. The proposed 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 analysis. 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 set 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 fault-tolerant priority configuration search algorithms by simulation. The results show that the effectiveness of this proposed algorithm is better than that of other algorithms.Due to the restriction that the traditional schedulability analysis for fault-tolerant real-time systems only considered that the deadline of each task must be no larger than its period, we extended the computation model that the deadlines of all tasks are allowed to be arbitrary large. Then, a new priority assignment algorithm, which can be used, together with the presented schedulability analysis, to improve system fault resilience as possible as it can. The proposed schedulability analysis takes into account the fact that the deadlines are allowed to be larger than the period. The proposed priority assignment algorithm, which uses some properties of the analysis, is very efficient. The result from the proposed analysis is particularly useful for real-time communication or distributed real-time systems where end-to-end latencies can be quite high compared to the process periods.Considering fixed priority scheduling of fault-tolerant hard real-time tasks in which the priority level of the system is insufficient. In this case, more than one task must be grouped into a same priority. We extends necessary and sufficient conditions for the purposed of limited priority levels on fault-tolerant hard real-time systems which takes into account the effect of temporary faults. The major contribution of our approach is to consider the recovery of tasks running with higher system priorities for the case of limited priority levels. This characteristic is very useful since the available slack time of higher system priority tasks can be make use of for recovering the faulty tasks of lower system priorities. Due to its flexibility and simplicity, the proposed approach provides an effective schedulability analysis, where the schedulability utilization of the system can be improved.Due to the fact that the fault-tolerance is not taken into consider in the scheduling mechanism of the RTLinux, we introduces the improvement of the fault-tolerant capability of the RTLinux. Firstly, the fault model based on the Primary/Backup technique is realized into the hard real-time thread structure. Secondly, the fault-tolerant priority configuration mixed search algorithm FPCMS is, together with the schedulablitiy analysis of the fault-tolerant real-time systems, realized in the scheduling algorithm of RTLinux. At last, this paper gives the design architecture of the fault-tolerant real-time tasks.更多还原