基于独立任务的分布式容错调度算法

《基于独立任务的分布式容错调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第30卷第3期2013年6月沈阳航空航天大学学报JournalofShenyangAerospaceUniversityV01．30No．3Jun．2013文章编号：2095—1248(2013)03一0044—05基于独立任务的分布式容错调度算法李伟英(辽宁省公安边防总队司令部，沈阳110034)摘要：主副版本法是常见的容错方法，将每个任务的主版本和副版本分配到两个不同的处理机上执行，只要任务的主版本分配到一个处理机，则对应的副版本可以在另一个处理机上重叠执行。笔者研究了分布式控制系统中，基于主副版本容错算法的副版本可以在执行时间上重叠来调度分配独立的任务，该容错算法以副版本执行时间重叠部分

2、的最小化为复制代价，通过仿真实验与集中式调度和分布式调度算法进行对比分析。关键词：容错算法；分布式；主副版本中图分类号：弼38．8文献标志码：Adoi：10．3969／j．issn．2095—1248．2013．03．010Fault-toleranceschedulingalgorithmofindependenttasksindistributedcontrolsystemsLIWei·ying(LiaoningProvincialPublicSecurityFrontierCorpsCommand，Shenyang110034)Abstract：Primary—backupisacomm

3、onapproachusedforfault—tolerancewhichineachtaskhasaprimarycopyandabackupcopycarriedontwodifferentprocessors．Thecorrespondingbackupcopiescanoverlapontheotherprocessor，aslongastheprimarycopiesarescheduledonthesanleprocessors．Inthispaper，westIldythefault—tolerantschedulingofindependenttasksusingprimary

4、—backupapproachwithbackupoverlap—pingindistributedsystem．Afault—tolerantschedulingalgorithmisdeveloped，whichminimizesreplicationcostsforbackupcopybytakingintoaccountbackupoverlappingincostfunction．Acentralizedschemeandadistributedschemearedevelopedfortheproposedalgorithmandtheirperformancesarecompar

5、edandana-lyzedthroughsimulationexperiments．Keywords：fault—tolerancealgorithm；distribution；primary／backupcopy随着各种应用复杂性的提高，分布式实时系统开始越来越广泛地应用于各种领域，如工业控制系统、武器防御控制系统、飞行控制系统、电站控制系统及实时多媒体系统等。但是随着分布式系统中节点数目的增加，系统出现故障的可能性增大。在实时系统中，每个任务都有严格的时间约束(截止期)，如果控制器故障使某些任务不能在其截止期前完成，就可能造成很大的损失。为了避免控制器出现故障而造成严重后果，需要在分布式

6、实时系统中提供一定的容错能力，且保证任务仍可以满足其截止期，以提高整个系统的可靠性‘1—2。。实时容错调度算法是在分布式系统容错调度算法的基础上，通过软件解决分布式实时系统容错问题，其优点是不需要额外的硬件开销来保证系统可靠性。A．Iamnitchi等∞o把容错方法分为两类：(1)将容错机制嵌入到中间设备软件中，与文献[4—5]方法相似；(2)把容错机制嵌入算法内，文献[2，6，7]为第一种类方法。A．Iamnitchi等旧1提出了一个基于空间算法的故障恢复机制，收稿日期：2013—03—17基金项目：国家自然科学基金项目(项目编号：60434030；61070024)作者简介：李伟英(196

7、7一)，男，辽宁沈阳人，工程师，主要研究方向：控制系统和网络安全技术，E·mail：1742781769@qq．corn。第3期李伟英：基于独立任务的分布式容错调度算法45A．Dogan等‘8。91拓展了该算法，使其应用和系统中的故障率减到最小。主副版本法也叫被动复制策略，是一种用于容错的常用方法。此方法是将一个任务的主版本和多个副版本被调度执行，且副版本只有在主版本没通过测试时才被执行¨o-11