主副版本法是常见的容错方法,将每个任务的主版本和副版本分配到两个不同的处理机上执行,只要任务的主版本分配到一个处理机,则对应的副版本可以在另一个处理机上重叠执行。笔者研究了分布式控制系统中,基于主副版本容错算法的副版本可以在执行时间上重叠来调度分配独立的任务,该容错算法以副版本执行时间重叠部分的最小化为复制代价,通过仿真实验与集中式调度和分布式调度算法进行对比分析。
Primary-backup is a common approach used for fault-tolerance which in each task has a primary copy and a backup copy carried on two different processors.The corresponding backup copies can overlap on the other processor,as long as the primary copies are scheduled on the same processors.In this paper,we study the fault-tolerant scheduling of independent tasks using primary-backup approach with backup overlapping in distributed system.A fault-tolerant scheduling algorithm is developed,which minimizes replication costs for backup copy by taking into account backup overlapping in cost function.A centralized scheme and a distributed scheme are developed for the proposed algorithm and their performances are compared and analyzed through simulation experiments.
[1]周悦,刘春光,尹金玲,等.分布嵌入式实时系统容错调度算法[J].沈阳建筑大学学报(自然科学版),2008,24(1):153-156.
[2]Hwang S,Kesselman C.A flexible framework for fault tolerance in the Grid[J].Journal of Grid Computing,2003(1):251-272.
[3]Iamnitchi A,Foster I.A problem-specific fault-tolerance mechanism for asynchronous,distributed systems[C].The Proceedings of International Conference on Parallel Processing,Toronto,2000.
[4]Frey J,Tannenbaum T,Foster I,et al.Condor-G:a computation management agent for multi-institutional Grids[J].Cluster Computing,2002,5(3):1-14.
[5]Natrajan A,Humphrey M,Grimshaw A.Grids:harnessing geographically-separated resources in a multi-organisational context[C].The Proceedings of High Performance Computing Systems,Ontario Canada,2001.
[6]Lee B,Weissman J B.Dynamic replica management in the service Grid[C].The Proceedings of The IEEE Internation Symposium on High Performance Distributed Computing,Valencia,Spain,2001.
[7]Zhang X,Zagorodnov D,Hiltunen M,et al.Fault-tolerant grid services using primary-backup:feasibility and performance[J].CLUSTER,2004(4):105-114.
[8]Dogan A,Ozguner F.Optimal and suboptimal reliable scheduling of precedence-constrained tasks in heterogeneous distributed computing[C].Proceedings of the International Conference on Parallel Processing,Toronto,2000.
[9]He Y,Shao Z,Xiao B,et al.Reliability driven task scheduling for heterogeneous systems[C].Proceedings of the Lasted Internation Conference on Parallel and Distributed Computing and Systems,2003.
[10]Ghosh S,Melhem R,Mosse D.Fault-tolerance through scheduling of aperiodic tasks in hard real-time multiprocessor systems[J].IEEE Trans.on Parallel and Distributed Systems,1997,8(3):272-284.
[11]Manimaran G,Siva Ram Murthy C.A fault-tolerant dynamic scheduling algorithm for multiprocessor real-time systems and its analysis[J].IEEE Trans.on Parallel and Distributed Systems,1998,9 (11):1137-1152.
[12]Girault A,Lavarenne C,Sighireanu M,et al.Fault-tolerant static scheduling for real-time distributed embedded systems[C].In Proc.of the 21st International Conference on Distributed Computing Systems(ICDCS),Valencia,Spain,2001.
[13]Qin X,Jiang H,Swanson D.An efficient fault-tolerant scheduling algorithm for real-time tasks with precedence constraints in heterogeneous systems[C].In Proc.of the International Conference on Parallel Processing,Vancouver,B.C.,Canada,2002.
[14]周悦,刘春光.基于非精确计算模型的OSL算法[J].沈阳建筑大学学报(自然科学版),2009,25(1):179-183.
[15]Hong Y S,Goo H W.A fault-tolerant scheduling scheme for hybrid tasks in distributed real-time systems[J].In Proc.of the Third IEEE Workshop on Software Technologies for Future Embedded and Ubiquitous Systems,Waidhofen/YBBS,Austria,2005.
