›› 2012, Vol. 42 ›› Issue (05): 1243-1250.

Previous Articles     Next Articles

Schedulability of rollback recovery fault-tolerant real-time system based on priority mixed strategy

LIU Xian1,2, GUO Rui-feng2, DING Wan-fu1,2   

  1. 1. Graduate University of Chinese Academy of Sciences, Beijing 100039, China;
    2. Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China
  • Received:2011-07-18 Online:2012-09-01 Published:2012-09-01

PDF (PC)

458

Abstract: A real-time system must guarantee the stringent requirements of real-time response and reliability. Taking account of the effects of errors, an investigation of the schedulability of fault-tolerant real-time systems was conducted based on the rollback recovery fault-tolerant model. A priority mixed strategy of fault-tolerance was proposed, and the computing formula of worst-case response time of a task under the new strategy is deduced. The new strategy allows the faulty task to execute at higher or lower priority levels. According to the schedulability analysis, an efficient priority assignment search algorithm (FTPCS_MS) was proposed. The algorithm reduces the search space of optimal fault-tolerant priority mixed assignment from O(nn) to O(n2). The simulation shows that the mixed strategy can improve system fault resilience efficiently.

Key words: computer systems organization, fault-tolerant real-time system, rollback recovery, schedulability analysis, worst-case response time, priority configuration

CLC Number: 

  • TP316
[1] Sha L, Abdelzaher T F, Arzén K E, et al. Real time scheduling theory: a historical perspective[J]. Real-Time Systems, 2004, 28(2-3):101-155.
[2] 徐跃,王太勇,赵艳菊,等. 基于ARM和DSP的可重构数控系统[J]. 吉林大学学报:工学版, 2008, 38(4): 848-851. Xu Yue, Wang Tai-yong, Zhao Yan-ju, et al. Re-configurable CNC system based on ARM and DSP[J]. Journal of Jilin University(Engineering and Technology Edition), 2008, 38(4): 848-851.
[3] 慈轶为, 张展, 左德承,等. 可扩展的多周期检查点设置[J]. 软件学报, 2010, 21(2): 218-230. Ci Yi-wei, Zhang Zhan, Zuo De-cheng, et al. Scalable time-based multi-cycle check pointing[J]. Journal of Software, 2010, 21(2): 218-230.
[4] 富弘毅, 丁滟, 宋伟,等. 一种基于扩展数据流分析的OpenMP程序应用级检查点机制[J]. 计算机学报, 2010, 33(10): 1809-1822. Fu Hong-yi, Ding Yan, Song Wei, et al. An application-level checkpointing based on extended data flow analysis for openMP programs[J]. Chinese Journal of Computers, 2010, 33(10): 1809-1822.
[5] 潘雪增, 姚鑫骅, 傅建中,等. 基于回卷恢复的数控系统实时容错调度策略[J]. 浙江大学学报:工学版, 2007, 41(12): 2011-2016. Pan Xue-zeng, Yao Xin-hua, Fu Jian-zhong, et al. Fault tolerant real-time scheduling strategy for NC system based on rollback recovery[J]. Journal of Zhejiang University(Engineering Science), 2007, 41(12): 2011-2016.
[6] 杨金民, 张大方. 基于分块消息日志的回卷恢复策略[J]. 电子学报, 2004, 32(5): 857-859. Yang Jin-min, Zhang Da-fang. A rollback recovery scheme based on partitioned message-logging [J].Chinese Journal of Electronics, 2004, 32(5): 857-859.
[7] 门朝光, 徐振朋, 李香. 移动计算系统检查点迁移策略的性能评价[J]. 哈尔滨工业大学学报, 2010, 42(5): 806-810. Men Chao-guang, Xu Zhen-peng, Li Xiang. The performance evaluation of checkpoint handoff scheme for the mobile computing system[J]. Journal of Harbin Institute of Technology, 2010, 42(5): 806-810.
[8] 王健, 孙建伶, 王新宇,等. 容错多处理机中一种高效的实时调度算法[J]. 软件学报, 2009, 20(10): 2628-2636. Wang Jian, Sun Jian-ling, Wang Xin-yu, et al. Efficient scheduling algorithm for hard real-time tasks in primary-backup based multiprocessor systems[J]. Journal of Software, 2009, 20(10): 2628-2636.
[9] 梁毅, 王磊, 樊建平,等. 基于共享内存的机群服务检查点机制研究[J]. 计算机研究与发展, 2010, 47(4): 571-580. Liang Yi, Wang Lei, Fan Jian-ping, et al. Research on the shared memory-based checkpointing for cluster services[J]. Journal of Computer Research and Development, 2010, 47(4): 571-580.
[10] Zhang F, Burns A. Schedulability analysis for real-time systems with EDF scheduling[J]. IEEE Transactions on Computers, 2009, 58(9): 1250-1258.
[11] 万加富,李迪,叶峰,等. 提高混合实时任务确定性的两级调度算法[J]. 吉林大学学报:工学版, 2009, 39(3): 753-758. Wan Jia-fu, Li Di, Ye Feng, et al. Two-level hierarchical scheduling algorithm to improve certainty of hybrid real-time tasks[J]. Journal of Jilin University(Engineering and Technology Edition), 2009, 39(3): 753-758.
[12] Punnekkat S, Burns A, Davis R. Analysis of checkpointing for real-time systems[J]. Real-Time Systems, 2001, 20(1):83-102.
[13] Liu L C, Layland J W. Scheduling algorithms for multiprogramming in a hard real-time environment[J]. Journal of the ACM, 1973, 20(1): 46-61.
[14] Audsley N C, Burns A, Wellings A J. Deadline monotonic scheduling theory and application[J]. Control Engineering Practice, 1993, 1(1): 71-78.
[1] DONG Jian-feng, ZHANG Yu-feng, DAI Zhi-qiang. Improved recommendation algorithm based on DPM model [J]. 吉林大学学报(工学版), 2018, 48(2): 596-604.
[2] LIU Lei, LIU Li-juan, WU Xin-wei, ZHANG Peng. Compiler testing method based on ECP metamorphic relation [J]. 吉林大学学报(工学版), 2017, 47(4): 1262-1267.
[3] DONG Li-yan, WANG Yue-qun, HE Jia-nan, SUN Ming-hui, LI Yong-li. Collaborative filtering recommendation algorithm based on time decay [J]. 吉林大学学报(工学版), 2017, 47(4): 1268-1272.
[4] DENG Chang-yi, GUO Rui-feng, ZHANG Yi-wen, WANG Hong-liang. Lower power dynamic scheduling algorithm for sporadic tasks based on balance factor [J]. 吉林大学学报(工学版), 2017, 47(2): 591-600.
[5] HE Zhong-zheng, MEN Chao-guang, LI Xiang. Schedulability of fault-tolerant real-time system based on checkpoint interval optimization [J]. 吉林大学学报(工学版), 2014, 44(2): 433-439.
[6] ZHANG Hua, PENG Lai-hu, HU Xu-dong, WANG Xian-mei. Model of enterprise cloud manufacture applying to textile machining industry [J]. 吉林大学学报(工学版), 2012, 42(增刊1): 337-340.
[7] WANG Xin-ying, LIU Gang, GU Fang-ming, XIAO Wei. Heterogeneous feature fusion method based on semantic and shape for 3D model retrieval [J]. 吉林大学学报(工学版), 2012, 42(增刊1): 359-363.
[8] WU Xiao-xuan, NI Zhi-wei, NI Li-ping. Clustering ensembles algorithm based on fractal dimension [J]. 吉林大学学报(工学版), 2012, 42(增刊1): 364-367.
[9] LIU Zhuang, FANG Zhi-yi, ZHANG Chun-fei, CHEN Lin, ZHAO Yang. Energy-efficient amendatory algorithm based on energy-consumption transference and data gravitation in wireless sensor networks [J]. , 2012, 42(05): 1237-1242.
[10] CHAI Zheng-yi, WU Hui-xin, WU-Yong. Optimization algorithm for immune real-value detector generation [J]. , 2012, 42(05): 1251-1256.
[11] LI Min, JIA Chun-fu, LI Jing-wei, LIU Zhe-li, DONG Zong-qing. Format-preserving encryption for variable-length encoding character data [J]. , 2012, 42(05): 1257-1261.
[12] LIU Yan-heng, FU Feng, ZHU Jian-qi, SUN Xin. DoS detection model base on alive entropy [J]. 吉林大学学报(工学版), 2011, 41(4): 1059-1064.
[13] LI Rui-Xue, FANG Zhi-Yi, YI Ting-Ting. Improved DVHop localization algorithm based on regularly moving anchor(RMAN) and received signal strength indicator(RSSI) and its performance analysis [J]. 吉林大学学报(工学版), 2011, 41(02): 435-0441.
[14] QU Liang-Dong, LIU Yan-Hang, WEI Da. System of vertical handoff for heterogeneous wireless network based on VPN on invehicle gateway [J]. 吉林大学学报(工学版), 2010, 40(05): 1292-1297.
[15] SUN Zhi-Xin, ZHANG Yu-Feng. P2P network traffic identification model based on MSVM [J]. 吉林大学学报(工学版), 2010, 40(05): 1298-1302.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd