副版本不可抢占的全局容错调度算法  

Fault Tolerant Global Scheduling with Non-Preemptive Backups

作　　者：彭浩[1] 陆阳[1] 孙峰[1] 韩江洪[1] PENG Hao LU Yang SUN Feng HAN Jiang-Hong(School of Computer and Information, Hefei University of Technology, Hefei 230009, Chin)

机构地区：[1]合肥工业大学计算机与信息学院,安徽合肥230009

出　　处：《软件学报》2016年第12期3158-3171,共14页Journal of Software

基　　金：国家自然科学基金(61370088);国家国际科技合作专项(2014DFB10060)~~

摘　　要：容错是硬实时系统的关键能力,容错调度算法可以在有错误发生的情况下满足任务的实时性需求.在主副版本机制的容错调度算法中,主版本出错后留给副版本运行的时间窗口小,副版本容易错失截止期.针对副版本需要快速响应的问题,提出副版本不可抢占的全局容错调度算法FTGS-NPB(fault-tolerant global scheduling with non-preemptive backups),赋予副版本全局最高优先级,使副版本在主版本出错后可以立刻获得处理器资源,并且在运行过程中不会被其他任务抢占.这样,副版本可以在最短时间内响应.分别基于截止期分析和响应时间分析建立了FTGS-NPB的可调度性测试,并分析了两种可调度性测试分别适用于不同的优先级分配算法.仿真实验结果表明,FTGS-NPB可以有效地减少实现容错的代价.Fault tolerance is a critical capability of hard real-time systems. Even with faults, fault tolerant scheduling algorithms are able to guarantee the real time property of tasks. In primary-backup based fault tolerant scheduling algorithms, only a small time window is left for the backup when the primary faults occur, therefore the backup will likely miss its deadline. This paper proposes a fault tolerant global scheduling with non-preemptive backups（FTGS-NPB）. By assigning the highest priority to all backups, the backup can attain processor immediately in case of primary faults, and keep executing until finishing its job. In this way the backup can achieve the shortest response time. The schedulability tests are set up based on deadline analysis and response time analysis. The compatibility of priority assignment algorithms and schedulability tests is discussed. The simulation results show that FTGS-NPB can reduce the amount of additional processors for achieving fault tolerant capability.

关 键 词：多处理器 硬实时系统 主副版本 容错调度 全局调度 

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