• Article
  • | |
  • Metrics
  • |
  • Reference [20]
  • |
  • Related [20]
  • |
  • Cited by [3]
  • | |
  • Comments
    Abstract:

    Heterogeneous distributed real-time simulation system is a special kind of real-time system. This paper solves its fault-tolerant problem based on the CSP (checkpoint-based spare processor) model, which is an improvement of the traditional SP (spare processor) model with checkpoint mechanism. Firstly, two propositions are put forward based on the characters of simulation system. Secondly, the Worst Case Response Time of the simulation tasks are analyzed based on Markov chains and the schedulability analysis rules for simulation task are presented. In the end of the paper, a fault-tolerant scheduling algorithm CSP-RTFT is proposed and simulated. The results show that the algorithm can achieve better stability, higher task accept ratio than SP-RTFT which is based on SP model, whereas the resource utilization ratio is lower than those based on PB model.

    Reference
    [1]Huang KD,et al.System Simulation Technology.Changsha:Publishing House of National University of Defense Technology,1998.307-326 (in Chinese).
    [2]Brutzman D,Zyda M,Pullen JM,Morse KL.Extensible modeling and simulation framework (XMSF):Challenges for Web-based modeling and simulation.Proc.of the Technical Challenges Workshop,Strategic Opportunities Symp.Monterey,2002.http://www.MovesInstitute.org/xmsf
    [3]Ekl(o)f M,Moradi F,Ayani R.A framework for fault-tolerance in HLA-based distributed simulations.In:Kuhl ME,Steiger NM,Armstrong FB,Joines JA,eds.Proc.of the 2005 Winter Simulation Conf.Orlando:IEEE Press,2005.1182-1189.
    [4]Damani OP,Garg VK.Fault-Tolerant distributed simulation.In:Alberta B,ed.Proc.of the 12th Workshop on Parallel and Distributed Simulation.Washington:IEEE Press,1998.38-45.
    [5]M(o)ller B,Karlsson M,L(o)fstrand B.Developing fault tolerant federations using HLA evolved.In:Proc.of the 2005 Spring Simulation Interoperability Workshop.San Diego,2005.http://www.sisostds.org/siw/05spring/readlist.htm
    [6]Xu ZW,Feng BM,Li W.Grid Computing Technology.Beijing:Publishing House of Electrnics Industry,2004.1-19 (in Chinese).
    [7]Han CC,Shin KG,Wu J.A fault-tolerant scheduling algorithm for real-time periodic tasks with possible software faults.IEEE Trans.on Computers,2003,52(3):362-372.
    [8]Manimaran G,Murthy CSR.A fault-tolerant dynamic scheduling algorithm for multiprocessor real-time systems and its analysis.IEEE Trans.on Parallel and Distributed Systems,1998,9(11):1137-1152.
    [9]Ghosh S,Melhem R,Mossé D.Fault-Tolerance through scheduling of aperiodic tasks in hard real-time multiprocessor systems.IEEE Trans.on Parallel and Distributed Systems,1997,8(3):272-284.
    [10]Ripoll I,Crespo A,García-Fornes A.An optimal algorithm for scheduling soft aperiodic tasks in dynamic-priority preemptive systems.IEEE Trans.on Software Engineering,1996,23(6):388-400.
    [11]Kartik S,Murthy SR.Task allocation algorithms for maximizing reliability of distributed computing systems.IEEE Trans.on Computer,1997,46(6):719-724.
    [12]Qin X,Jiang H,Swanson DR.An efficient fault-tolerant scheduling algorithm for real-time tasks with precedence constraints in heterogeneous systems.In:Proc.of the 31st Int'l Conf.on Parallel Processing (ICPP 2002).2002.360-368.http://www.cs.nmt.edu/~xqin/pubs/icpp02.pdf
    [13]Vaidya NH.A case for two-level recovery schemes.IEEE Trans.on Computer,1998,47(6):656-666.
    [14]Dinatele M,et al.Dynamic end-to-end guarantees in distributed real-time systems.In:Proc.of the Real-Time Systems Symp.1994.67-73.http://citeseer.ist.psu.edu/cache/papers/cs/529/http:zSzzSzretis.sssup.itzSzpaperszSzrtss1994.pdf/ dinatale94dynamic.pdf
    [15]Lauzac S,Melhem R,Mossé D.Adding fault-tolerance to P-fair real-time scheduling.In:Proc.of the Workshop on Embedded Fault-Tolerant Systems.Boston:IEEE Press,1998.34-37.
    [16]Liu YS,Zhang CF,Zhang T,Zha YB,Huang KD.The analysis of best checkpoint interval of distributed simulation system using Markov chains.Journal of National University of Defense Technology,2005,27(5):73-78 (in Chinese with English abstract).
    [17]Chandy M,Lamport L.Distributed snapshots:Determining global states of distributed systems.ACM Trans.on Computing Systems,1985,3(1):63-75.
    [18]Punnckkat S.Schedulability analysis for fault tolerant teal-time systems[Ph.D.Thesis].York:University of York,1997. [1]黄柯棣,等.系统仿真技术.长沙:国防科学技术大学出版社,1998.307-326.
    [6]徐志伟,冯百明,李伟.网格计算技术.北京:电子工业出版社,2004.1-19.
    [16]刘云生,张传富,张童,查亚兵,黄柯棣.基于Markov链的分布式仿真系统最佳检查点间隔研究.国防科技大学学报,2005,27(5):73-78.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

刘云生,张童,张传富,查亚兵.异构分布式实时仿真系统的容错调度算法.软件学报,2006,17(10):2040-2047

Copy
Share
Article Metrics
  • Abstract:4530
  • PDF: 5986
  • HTML: 0
  • Cited by: 0
History
  • Received:May 07,2005
  • Revised:December 31,2005
You are the first2038809Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063