基于优先级混合策略的回卷恢复容错实时系统的可调度性

摘要/Abstract

摘要： 实时系统具有严格的实时性及高度的可靠性要求。考虑到系统可能出错的情况,对回卷恢复容错模型下实时系统的可调度性进行了研究,提出了容错优先级混合策略,并推导出该策略下任务最坏响应时间的计算公式。结合系统的可调度性分析,提出了混合策略的优先级配置搜索算法(FTPCS_MS算法),该算法将最优容错优先级混合配置的搜索空间由O(nⁿ)降低为O(n²)。仿真实验表明,容错优先级混合策略能够在继承策略的基础上进一步提升系统的容错能力。

关键词: 计算机系统结构, 容错实时系统, 回卷恢复, 可调度性分析, 最坏响应时间, 优先级配置

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(n²). 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

中图分类号:

TP316

刘娴, 郭锐锋, 丁万夫. 基于优先级混合策略的回卷恢复容错实时系统的可调度性[J]. , 2012, 42(05): 1243-1250.

LIU Xian, GUO Rui-feng, DING Wan-fu. Schedulability of rollback recovery fault-tolerant real-time system based on priority mixed strategy[J]. , 2012, 42(05): 1243-1250.

参考文献

[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.

相关文章 15

[1]	余宜诚, 胡亮, 迟令, 初剑峰. 一种改进的适用于多服务器架构的匿名认证协议[J]. 吉林大学学报(工学版), 2018, 48(5): 1586-1592.
[2]	董坚峰, 张玉峰, 戴志强. 改进的基于狄利克雷混合模型的推荐算法[J]. 吉林大学学报(工学版), 2018, 48(2): 596-604.
[3]	赵博, 秦贵和, 赵永哲, 杨文迪. 基于半陷门单向函数的公钥密码[J]. 吉林大学学报(工学版), 2018, 48(1): 259-267.
[4]	刘磊, 刘利娟, 吴新维, 张鹏. 基于ECPMR的编译器测试方法[J]. 吉林大学学报(工学版), 2017, 47(4): 1262-1267.
[5]	董立岩, 王越群, 贺嘉楠, 孙铭会, 李永丽. 基于时间衰减的协同过滤推荐算法[J]. 吉林大学学报(工学版), 2017, 47(4): 1268-1272.
[6]	于斌斌, 武欣雨, 初剑峰, 胡亮. 基于群密钥协商的无线传感器网络签名协议[J]. 吉林大学学报(工学版), 2017, 47(3): 924-929.
[7]	邓昌义, 郭锐锋, 张忆文, 王鸿亮. 基于平衡因子的动态偶发任务低功耗调度算法[J]. 吉林大学学报(工学版), 2017, 47(2): 591-600.
[8]	魏晓辉, 刘智亮, 庄园, 李洪亮, 李翔. 支持大规模流数据在线处理的自适应检查点机制[J]. 吉林大学学报(工学版), 2017, 47(1): 199-207.
[9]	郝娉婷, 胡亮, 姜婧妍, 车喜龙. 基于多管理节点的乐观锁协议[J]. 吉林大学学报(工学版), 2017, 47(1): 227-234.
[10]	魏晓辉, 李翔, 李洪亮, 李聪, 庄园, 于洪梅. 支持大规模流数据处理的弹性在线MapReduce模型及拓扑协议[J]. 吉林大学学报(工学版), 2016, 46(4): 1222-1231.
[11]	车翔玖, 梁森. 一种基于大顶堆的SPIHT改进算法[J]. 吉林大学学报(工学版), 2016, 46(3): 865-869.
[12]	董悦丽, 郭权, 孙斌, 康玲. 药物分子对接动态任务迁移优化[J]. 吉林大学学报(工学版), 2015, 45(4): 1253-1259.
[13]	匡哲君，师唯佳，胡亮. 基于无线传感器网络的角色成员关系剩余能量新算法[J]. 吉林大学学报(工学版), 2015, 45(2): 600-605.
[14]	张忆文，郭锐锋. 实时系统混合任务低功耗调度算法[J]. 吉林大学学报(工学版), 2015, 45(1): 261-266.
[15]	张忆文^{1, 2}, 郭锐锋¹. 制的容错节能调度算法[J]. 吉林大学学报(工学版), 2014, 44(4): 1112-1117.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed