A Fault-Tolerant Priority Configuration Mixed Search Algorithm

Hard real-time systems are those that specified in terms of strong timing constraints. 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 such as transient faults. In these systems, it is essential that the exploitation of time redundancy for correctness should not jeopardize the timeliness attribute. Hence scheduling aspects of fault tolerant hard real-time systems become all the more important. In this paper, a fault-tolerant priority-configuration-mixed search algorithm is proposed, that can be used, together with the schedulability analysis, to effectively increase the fault resilience of the fault-tolerant hard real-time systems. Schedulability analysis takes into account the fact that the recoveries of tasks are allowed to execute at some appropriate priority levels, either higher priority levels or lower priority levels. The performance of this mixed search algorithm is compared with that of other fault-tolerant priority configuration search algorithms by simulation. The results show that the average obtained increment on fault resilience when using the proposed algorithm is over 20%, which is higher than that of the three traditional algorithms.