吉林大学学报(工学版) ›› 2014, Vol. 44 ›› Issue (2): 433-439.doi: 10.13229/j.cnki.jdxbgxb201402025

• 论文 • 上一篇    下一篇

基于检查点间隔优化的容错实时系统可调度性

何忠政, 门朝光, 李香   

  1. 哈尔滨工程大学 计算机科学与技术学院, 哈尔滨 150001
  • 收稿日期:2012-11-01 出版日期:2014-02-01 发布日期:2014-02-01
  • 作者简介:何忠政（1986- ），男，博士研究生.研究方向：可信计算，移动计算.E-mail：hezhongzheng@hrbeu.edu.cn
  • 基金资助:

    国家自然科学基金项目（60873138，61100004）.

Schedulability of fault-tolerant real-time system based on checkpoint interval optimization

HE Zhong-zheng, MEN Chao-guang, LI Xiang   

  1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
  • Received:2012-11-01 Online:2014-02-01 Published:2014-02-01

RICH HTML

0   

PDF (PC)

388

摘要：

针对实时系统容错模型只能容忍任务执行时一次故障发生的缺陷，基于卷回恢复容错模型，提出了任务局部最优检查点间隔求解算法，使实时系统任务能够容忍任务执行过程中多次故障的发生；进而基于局部最优检查点间隔提出任务集检查点间隔全局优化（CIGO）策略。基于不同的检查点间隔优化机制，结合实时系统任务最坏响应时间的计算公式进行系统可调度性分析。仿真实验表明，与局部最优检查点间隔相比，基于全局优化检查点间隔的实时系统容错能力有显著提升。

关键词: 计算机系统结构, 实时系统, 检查点设置与卷回恢复, 可调度性分析, 检查点间隔优化

Abstract:

To overcome the defect of the real-time system fault-tolerant model that could only tolerate one fault occurred during the task execution process, a task Local Optimum Checkpoint Interval (LOCI) iterative algorithm was proposed. The algorithm is based on the checkpoint and rollback recovery fault tolerant model to make the task of the real-time system could tolerate multiple faults occurred during the task execution process. Then the Checkpoint Interval Global Optimization (CIGO) algorithm of the task set was proposed. The schedulability of the real-time system was analyzed based on the different checkpoint interval optimization mechanisms according to the calculation formula of the task worst case response time. The simulation results show that the strategy based on the GIGI can significantly improve the system fault resilience compared to that based on the LOCI.

Key words: computer system architecture, real-time system, checkpoint and rollback recovery, schedulability analysis, checkpoint interval optimization

中图分类号: 

  • 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] Shivakumar P, Kistler M, Keckler S W, et al. Modeling the effect of technology trends on the soft error rate of combinational logic[C]//Proc of the Int'1 Conference on Dependable Systems and Networks, 2002: 389-399.

[3] 傅忠传, 陈红松, 崔刚, 等.处理器容错技术研究与展望[J].计算机研究与发展, 2007, 44(1): 154-160. Fu Zhong-chuan, Chen Hong-song, Cui Gang, et al. Processor fault-tolerance technology research and prospect[J].Journal of Computer Research and development, 2007: 44(1): 154-160.

[4] Clark J A, Pradhan D K. Fault injection: a method for validating computer system dependability[J]. IEEE Computer, 1995, 28(6): 47-56.

[5] Ziegler J F. IBM experiments in soft fails in computer electronics(1978-1994)[J]. IBM Journal Research Development, 1996, 40(1): 3-18.

[6] Zhang F, Burns A. Schedulability analysis for real-time systems with EDF scheduling[J]. IEEE Transactions on Computers, 2009, 58(9): 1250-1258.

[7] Punnekkat S, Burns A, Davis R. Analysis of checkpointing for real-time systems[J]. Real-time Systems, 2001, 20(1): 83-102.

[8] Paul Pop, Viacheslav Izosimov, Petru Eles, et al. Design optimization of time-and cost-constrained fault-tolerant embedded systems with checkpointing and replication[J]. IEEE Trans on Very Large Scale Integration Systems, 2009, 17(3): 389-402.

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

[10] 刘娴, 郭锐锋, 丁万夫. 基于优先级混合策略的回卷恢复容错实时系统的可调度[J]. 吉林大学学报:工学版, 2012, 42(5): 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]. Journal of Jilin University(Engineering and Technology Edition), 2012, 42(5): 1243-1250
[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, 郭锐锋1. 制的容错节能调度算法[J]. 吉林大学学报(工学版), 2014, 44(4): 1112-1117.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发