Research on Real-time Scheduling Algorithms for Rollback Recovery Fault-tolerance Based on Priority Decrease Strategy
Guo Rui-feng② Liu Xian①② Ding Wan-fu①②
①(Graduate University of Chinese Academy of Sciences, Beijing 100039, China) ②(Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China)
Abstract：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 O(n!) to O(n2). Finally, the simulation shows that the new strategy can improve system fault resilience efficiently.
2012, Vol. 34 
