Schedulability Analysis For The Fault-Tolerant Hard Real-Time Systems

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.