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

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

作　　者：丁万夫[1,2] 郭锐锋[2] 刘娴[1,2] 秦承刚[1,2] 郭凤钊[1,2] 

机构地区：[1]中国科学院研究生院,北京100039 [2]中国科学院沈阳计算技术研究所,沈阳110168

出　　处：《系统仿真学报》2012年第2期318-323,共6页Journal of System Simulation

基　　金：国家科技重大专项(2009ZX04009-022)

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

关 键 词：硬实时系统 容错调度 抢占阈值 算法仿真 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]