基于空间时间冗余的替代主版本冗余调度算法

An Alternate Primary Redundancy Scheduling Algorithm Based on Time and Space Redundancy

目的研究空间冗余与时间冗余各自的特点,提出一种将时间冗余与空间冗余方式的优点相结合的容错调度算法,提高调度算法的处理器利用率.方法将每个任务分为主版本、副版本和替代主版本.根据任务利用率将任务集分为高频任务集和低频任务集两类,分别采用空间冗余和时间冗余策略实现容错.采用EDF算法为任务分配动态优先级,且在主版本任务频繁发生错误的情况下激活替代主版本.结果所提算法将空间冗余与时间冗余相结合,满足任务的实时与容错需求,且避免系统因频繁执行一个易出错的主版本任务而造成资源的浪费.结论该算法降低了任务集对系统处理器数量的需求,提高了系统资源利用率.

In this paper, the characters of space redundancy and time redundancy are studied, and a scheduling algorithm is presented. Both of the two redundancy policies＇ advantages are integrated with this new algorithm, and as a result, the utilization of the scheduling algorithm was improved. Each task has three versions：Primary, Backup and Alternate Primary. The tasks set is divided into high frequency tasks set and low frequency tasks set, then space redundancy and time redundancy are adopted to schedule sub - tasks set respectively. The advantages of both space redundancy and time redundancy are combined. Each task gets its priority according to EDF. When Primary faults frequently, Alternate Primary will be activated and replace Primary to avoid waste of system resource. By this way, the tasks＇ requirement of real-time and fault-tolerance can be satisfied. The simulation shows APR-STR algorithm can reduce requirement of processor quantity for task set and improve utilization of system resources.