高级检索

    主/副版本模型中预分配容错实时调度算法

    Fault-Tolerant Real-Time Scheduling Algorithm with Pre-Allocation in Primary/Alternate Model

    • 摘要: 实时系统中任务的超时完成可能导致灾难性后果,因此要求系统具备容错处理能力,以保证系统出错后的实时性及可靠性.主/副版本模型是提高实时系统容错能力的有效技术.传统的容错实时调度算法通过为副版本预留处理器时间来实现软件容错,为副版本预留的处理器时间在系统运行过程中需动态调整,增加了系统的容错调度开销.提出一种基于res-backwards-RM预分配子算法的容错实时调度算法BCE\+*,通过限制预分配过程中高优先级任务的抢占条件,在不影响系统可调度性的同时可以有效避免副版本预留时间的动态调整,降低系统的容错调度开销.仿真实验验证了BCE\+*算法的可行性及有效性,且在系统出错概率及主版本负载较低的环境下,BCE\+*算法对系统容错调度开销的优化效果更显著.

       

      Abstract: A real-time system is supposed to provide fault tolerance to keep the system meeting its stringent timeliness and reliability requirements in the presence of faults. The primary/alternate model is an effective method for enhancing the capability to tolerate faults. Most fault-tolerant real-time scheduling algorithms based on this model at present reserve time intervals for the alternates to provide software fault-tolerance. However, these reserved time intervals need to be modified when their corresponding primaries are successfully completed at run-time, thereby increasing the scheduling overhead. To address this problem, a new fault-tolerant real-time scheduling algorithm, termed as BCE\+*, is proposed in this paper. The major contribution of the algorithm is presenting a new pre-allocating scheme which imposes restrictions on the preemption of higher priority task while reserving time intervals for alternates. The theoretical performance analysis presented in the paper demonstrates that the proposed algorithm can avoid the modification of reserved time internals, and meanwhile keep the schedulability of the system. Finally, simulation experiments show that the proposed approach can effectively reduce the scheduling overhead of the system compared with the classic BCE algorithm, and the reduction is significant when both the processor utilization of the primaries and the software fault probability are low.

       

    /

    返回文章
    返回