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

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

作　　者：丁万夫[1,2] 郭锐锋[2] 赵进[3] 刘娴[1,2] 李杰[1,2] 

机构地区：[1]中国科学院研究生院,北京100049 [2]中国科学院沈阳计算技术研究所,辽宁沈阳110171 [3]沈阳机床(集团)有限责任公司,辽宁沈阳110142

出　　处：《系统工程与电子技术》2011年第7期1673-1679,共7页Systems Engineering and Electronics

基　　金：国家科技重大专项(2011ZX04016-071)资助课题

摘　　要：在硬实时系统中,由于任务超时完成将会导致灾难性后果,因此硬实时系统必须具有实时性和可靠性保障。为了提高硬实时系统的容错能力,基于回卷恢复模型提出了允许容错优先级提升的分配策略。为了获得系统中容错优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,提出了一种最优的容错优先级配置搜索算法(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.

关 键 词：回卷恢复 硬实时系统 可调度性分析 检查点 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]