基于EDF的分布式控制系统容错调度算法
作者:

A Fault-Tolerant Scheduling Algorithm Based on EDF for Distributed Control Systems
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [20]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    现有的分布式实时系统的容错调度算法要求系统中所有任务的周期相同且等于其时限,而实际中任务的周期常常是互不相同的.根据控制系统中任务的特点,结合任务分配算法与处理器的调度算法,提出了基于基版本/副版本技术和EDF算法的容错调度算法.该算法不要求任务的周期都相同,并通过设置基版本/副版本任务时限控制它们的执行时间不重叠,给出了基版本/副版本任务时限的设置方法,并对任务集的可调度性进行了分析.当任务集可调度时,给出其最大利用率和最小处理器个数的约束条件.最后给出一个仿真实例,结果表明了算法的有效性.

    Abstract:

    In recent result, the fault-tolerant scheduling algorithm almost requires that all task's periods are the same and equal to their deadlines, but in fact the periods are not the same in many cases. According to the characteristics of distributed control systems and the technique of primary/backup copies, based on EDF algorithm the novel fault-tolerant scheduling algorithm is proposed in this paper. The algorithm can deal with the different periods of all tasks. By using setting their deadlines the problem that execution times of primary and backup copies are not overlap can be controlled. The method for setting deadlines of primary and backup copies is given and the schedulability of task set is analyzed. The maximal utilization of task set and the minimal number of processor are investigated. The result of simulation shows that the algorithm is effective.

    参考文献
    [1]Kieckhafer RM, Walter CJ, Finn AM, Thambidurai PM. The MAFT architecture for distributed fault tolerance. IEEE Transactions on Computers, 1988,37(4):398~405.
    [2]Factor M, Gelernter DH, Kolb CE, Miller PL, Sittig DF. Real-Time data fusion in the intensive care unit. IEEE Computer, 1991,24(11):45~54.
    [3]Xu LH, Bruck J. Deterministic voting in distributed systems using error-correcting codes. IEEE Transactions on Parallel and Distributed Systems, 1998,9(8):813~824.
    [4]Lin TH, Shin KG. Damage assessment for optimal rollback recovery. IEEE Transactions on Computers, 1998,47(5):603~613.
    [5]Davoli R, Giachini LA, Babagiu O, Amoroso A, Alvisi L. Parallel computing in networks of workstations with parallex. IEEE Transactions on Parallel and Distributed Systems, 1996,7(4):371~384.
    [6]Zhang YJ, Zhang Y, Peng YX, Chen FJ, A multiprocessor-based fault-tolerant real-time task scheduling algorithm. Journal of Computer Research and Development, 2000,37(4):425~429 (in Chinese with English abstract).
    [7]Qin X, Han ZF, Li SL, Pang LP. Efficient scheduling algorithm with fault-tolerance for real-time tasks in multi-processor systems. Journal Huazhong University of Science & Technology, 1999,27(7):14~16 (in Chinese with English abstract).
    [8]Han ZF, Qin X, Pang LP, Li SL. Design of fault-tolerant scheduling algorithm for real-time tasks in distributed systems. Journal of Huazhong University of Science & Technology, 1999,27(7):12~14 (in Chinese with English abstract).
    [9]Zhang KL, Qin X, Han ZF, Pang LP. Study of the model for fault-tolerant scheduling algorithm in heterogeneous distributed real-time systems. Journal of Huazhong University of Science & Technology, 2000,28(8):17~18 (in Chinese with English abstract).
    [10]Qin X, Han ZF, Pang LP. Real-Time scheduling with fault-tolerance in heterogeneous distributed systems. Chinese Journal of Computers, 2002,25(1):49~56 (in Chinese with English abstract).
    [11]Qin X, Han ZF, Pang LP, Li SL. Design and performance analysis of a hybrid real-time scheduling algorithm with fault-tolerance. Journal of Software, 2000,11(5):668~693 (in Chinese with English abstract).
    [12]Kieckhafer RM. Fault-Tolerant real-time task scheduling in the MAFT distributed system. In: Proceedings of the 22nd Annual Hawaii International Conference on System Sciences. IEEE CS Press, 1989,I:143~151.
    [13]Cervin A. Improved scheduling of control tasks. In: Proceedings of the 11th Euromicro Conference on Real-Time Systems. IEEE Computer Society Press, 1999. 4~10.
    [14]Tovar E, Vasques F. Non pre-emptive scheduling of messages on SMTV token-passing networks. In: Proceedings of the 12th Euromicro Conference on Real-Time Systems (RTS 2000). IEEE CS Press, 2000. 209~218.
    [6]张拥军,张怡,彭宇行,陈福接.一种基于多处理机的容错实时任务调度算法.计算机研究与发展,2000,37(4):425~429.
    [7]秦啸,韩宗芬,李胜利,庞丽萍.多处理机系统的高效实时容错调度算法.华中理工大学学报,1999,27(7):14~16.
    [8]韩宗芬,秦啸,庞丽萍,李胜利.分布式系统的实时容错任务调度算法设计.华中理工大学学报,1999,27(7):12~14.
    [9]张坤龙,秦啸,韩宗芬,庞丽萍.异构分布式实时系统中容错调度模型的研究.华中理工大学学报,2000,28(8):17~18.
    [10]秦啸,韩宗芬,庞丽萍.基于异构分布式系统的实时容错调度算法.计算机学报,2002,25(1):49~56.
    [11]秦啸,韩宗芬,庞丽萍,李胜利.混合型实时容错调度算法的设计和性能分析.软件学报,2000,11(5):668~693.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

刘怀,费树岷.基于EDF的分布式控制系统容错调度算法.软件学报,2003,14(8):1371-1378

复制
分享
文章指标
  • 点击次数:4679
  • 下载次数: 6041
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2002-12-14
  • 最后修改日期:2003-04-09
文章二维码
您是第19630632位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号