基于被动副版本优先级提高策略的分布式实时容错调度

Real-Time Fault-Tolerant Scheduling for Distributed Systems Based on Improving Priority of Passive Backup

FTRMFF(fault-tolerant rate-monotonic first-fit)分布式容错算法具有实现简单、调度开销小的优点,但是副版本的优先级继承策略不利于处理器空闲资源的充分利用.针对这个问题并结合各类型任务的最坏响应时间的分析,提出IPPBS(improving priority for passive backup based scheduling)算法.IPPBS算法能在不破坏处理机上已分配任务的可调度性的前提下,适当提高待分配的被动副版本的优先级来缩短响应时间,增加其在现有处理机上的可调度性,从而提高处理器的利用率.在此基础上,给出了具体的优先级提高因子搜索算法.仿真实验验证了IPPBS算法的可行性和有效性,较FTRMFF算法可节约的处理器个数百分比最高可达13%.

Fault-tolerant rate-monotonic first fit（FTRMFF） algorithm is a hard-real-time scheduling broadly used in distributed systems.This scheduling algorithm has the advantages of easy operation and low cost.However,the strategy of priority inheritance on the backup copy probably makes it hard to make full use of the slack located in the existing processors.To solve the problem and on the basis of analyzing the worst case response time of all types of task copies,the ＂improving priority for passive backup based scheduling（IPPBS）＂ algorithm is then proposed.When a passive backup copy could not be assigned to the existing processors and needs a new processor,IPPBS algorithm will improve its priority to a reasonable level to shorten the response time.Because its worst case response time becomes shorter,the passive backup copy is likely to be scheduled to the existing processor without breaking the scheduablity feasibility of other tasks with higher priority in the same processor.Moreover,the priority improving of factor searching algorithm is presented in detail.Finally,the adequate simulation experiments show that the IPPBS algorithm is feasible and effective.Compared with the classic FTRMFF algorithm,it can save the processors up to 13%.