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

Preemption Threshold Scheduling Algorithm with Higher Fault-Tolerant Priority

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

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

出　　处：《软件学报》2011年第12期2894-2904,共11页Journal of Software

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

摘　　要：基于软件容错模型,提出了允许容错优先级提升的抢占阈值容错调度算法(extended fault-tolerantfixed-priority with preemption threshold,简称FT-FPPT*).该算法能够在抢占式容错调度算法(fault-tolerantfixed-priority preemptive,简称FT-FPP)和抢占阈值容错调度算法(fault-tolerant fixed-priority with preemptionthreshold,简称FT-FPPT)无法提高系统容错能力的情况下,进一步提高系统的容错能力.为了获得系统中任务优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,提出了一种最优的优先级配置搜索算法(priorityassignment search algorithm,简称PASA).经过深入分析和实验证明,与FT-FPPT算法相比,FT-FPPT*算法能够有效地提高硬实时系统的容错能力.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.

关 键 词：实时系统 容错调度 抢占阈值调度 可调度性分析 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]