容错优先级混合式分配搜索算法

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.