高级检索

    基于延迟主动副版本的分布式实时容错调度算法

    A Real-Time Fault-Tolerant Scheduling Algorithm for Distributed Systems Based on Deferred Active Backup-Copy

    • 摘要: 主/副版本备份技术是分布式系统常用的实时容错调度方法,然而传统的主动方式副版本即使在无处理机故障时也需要在备份处理机上完全运行,增加了处理机消耗.提出一种基于固定优先级调度算法的延迟主动副版本(deferred active backup-copy)备份技术,该技术通过尽量向后调度主动方式的副版本,并在主版本成功执行时终止副版本的执行来减少备份的冗余度.在此基础上,提出一种基于该技术的以最小化处理机数目为优化目标的启发式任务分配算法——基于延迟主动副版本的最佳适应算法DABCBF (deferred active backup-copy based best-fit algorithm). DABCBF在保证系统的实时性和容错能力的前提条件下,通过尽量减少主版本的最坏响应时间来最大程度地减少冗余,以节省处理机.最后通过仿真实验,证明了算法的可行性和有效性.

       

      Abstract: The primary/backup copy scheme plays a vital role in the context of real-time fault-tolerant scheduling based on distributed systems. However, traditional active backup copies are required to be completely executed on the backup processors even in fault-free scenario, thereby increasing unnecessary redundancies. In this paper, a novel deferred active backup-copy technique is proposed which is integrated with the fixed-priority scheduling algorithm to exploit redundancies of active backup copies. The proposed technique exploits the processor redundancies through scheduling active backup copies as late as possible and terminating the execution of backup copies when corresponding primary copies are successfully completed. Moreover, based on the aforementioned technique, a “best-fit” heuristic algorithm is designed with the aim of achieving minimal number of processors. Therefore, compared with similar algorithms, this algorithm can further reduce processors needed while guaranteeing real-time and fault-tolerant properties of distributed systems. Finally, simulation experiments are carried out to prove the feasibility and effectiveness of the algorithm.

       

    /

    返回文章
    返回