基于回卷恢复的容错硬实时系统可调度性分析

Schedulability analysis for fault-tolerant hard real-time systems based on rollback recovery

在硬实时系统中,由于任务超时完成将会导致灾难性后果,因此硬实时系统必须具有实时性和可靠性保障。为了提高硬实时系统的容错能力,基于回卷恢复模型提出了允许容错优先级提升的分配策略。为了获得系统中容错优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,提出了一种最优的容错优先级配置搜索算法(fault-tolerant priority configuration search algorithm,FTPCSA)。该算法能够将搜索空间由O(n!)减少到O(n2)。最后给出了该算法的最优性证明。经过深入分析和实验证明,允许容错优先级提升的分配策略能够在容错优先级继承策略的基础上,进一步提高系统的容错能力。

Hard real-time systems are subject to stringent reliability and timing constraints owing to the fact that any failure to produce correct outputs in a timely manner may result in a disaster.Based on the rollback recovery model,a new fault-tolerant priority assignment policy,which allows a faulty task to be carried out at higher priority levels,is proposed in order to improve system fault resilience.Furthermore,an optimal fault-tolerant priority configuration search algorithm（FTPCSA）,which uses some properties of the schedulability analysis,is presented.It is shown that the method used to find out an appropriate fault-tolerant configuration reduces the search space from O（n!） to O（n2）.At last,the FTPCSA is proved to be optimal.Simulation experiment shows that this assignment policy can be used to effectively enhance the fault-tolerant capability when traditional fault-tolerant priority assignment policy may no longer be appropriate.