基于优先级降低策略的回卷恢复容错实时调度算法研究

Research on Real-time Scheduling Algorithms for Rollback Recovery Fault-tolerance Based on Priority Decrease Strategy

实时系统中任务的超时完成将会导致灾难性后果,因此实时系统必须具备实时性和可靠性保障。为了提升系统的容错能力,该文基于回卷恢复容错模型,提出了容错优先级降低策略,并基于此策略对系统进行可调度性分析,推导出了任务最坏响应时间的计算公式。为了快速确定一组最优的容错优先级降低配置,该文提出了一种有效的搜索算法,该算法能够将容错优先级降低配置的搜索空间由O(n!)降低为O(n 2)。最后,仿真实验表明容错优先级降低策略可以显著提升系统的容错能力。

A real-time system is required to guarantee its stringent requirements in real-time response and reliability since any task＇s failure to response correctly within its deadline may result in a catastrophe.Based on the rollback recovery fault-tolerant model,a fault-tolerant priority decrease strategy is proposed,which allows the faulty task to execute at lower priority levels,to improve system fault resilience.Then,the schedulability analysis is presented based on the derivation of computing formula of task＇s worst-case response time under the new strategy.To find out an optimal fault-tolerant priority decrease assignment quickly,an efficient priority assignment search algorithm is proposed,which reduces the search space from to.Finally,the simulation shows that the new strategy can improve system fault resilience efficiently.