基于软件容错的抢占阈值调度算法设计与仿真

为了提高硬实时系统的容错能力,同时减少任务间的抢占次数,基于软件容错模型提出了抢占阈值容错调度算法(FT-FPPT).为了获得系统中任务抢占阈值分配的最佳策略,基于任务最坏响应时间的可调度性分析,提出了一种最优的抢占阈值配置搜索算法(PTCSA).PTCSA算法能够将搜索空间由O(n!)减少到O(n 2),其中n为任务的个数.最后给出了该算法的最优性证明.仿真实验表明,抢占阈值容错调度算法能够在抢占式容错调度算法的基础上,进一步提高系统的容错能力。

Design and Simulation of Preemption Threshold Scheduling Algorithm with Software Fault-Tolerance

Based on software fault-tolerant model,a new scheduling algorithm called fault-tolerant fixed-priority with preemption threshold(FT-FPPT) was proposed in order to improve system fault resilience and reduce the preemptions.Furthermore,an optimal preemption threshold configuration search algorithm(PTCSA),which uses some properties of the schedulability analysis,was proposed.It is shown that the method used to find out an appropriate preemption threshold configuration reduces the search space from to,where is the number of tasks.At length,it is proved that PTCSA is optimal.Simulation experiment shows that FT-FPPT can be used to effectively enhance the fault-tolerant capability when traditional fixed-priority preemptive fault-tolerant scheduling algorithm may no longer be appropriate.