容错优先级可提升的抢占阈值容错调度算法

摘要

Based on the worst-case response time (WCRT) schedulability analysis for hard real-time systems, a new scheduling algorithm called extended fault-tolerant fixed-priority with preemption threshold (FT-FPPT*) is proposed in the software fault-tolerant model. This algorithm can be used, together with the schedulability analysis, to effectively enhance the fault-tolerant capability when the traditional fault-tolerant fixed-priority preemptive (FT-FPP) scheduling and fault-tolerant fixed-priority scheduling with preemption threshold (FT-FPPT) are no longer appropriate. At length, an optimal priority assignment search algorithm (PASA) is presented. PASA is optimal in the sense that the fault resilience of task sets is maximized for the proposed analysis. The effectiveness of the proposed approach is also evaluated by simulation.%基于软件容错模型,提出了允许容错优先级提升的抢占阈值容错调度算法(extended fault-tolerant fixed-priority with preemption threshold,简称FT-FPPT*).该算法能够在抢占式容错调度算法(fault-tolerant fixed-priority preemptive,简称FT-FPP)和抢占阈值容错调度算法(fault-tolerant fixed-priority with preemption threshold,简称FT-FPPT)无法提高系统容错能力的情况下,进一步提高系统的容错能力.为了获得系统中任务优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,提出了一种最优的优先级配置搜索算法(priority assignment search algorithm,简称PASA).经过深入分析和实验证明,与FT-FPPT算法相比,FT-FPPT*算法能够有效地提高硬实时系统的容错能力.