ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (2): 354-361.doi: 10.7544/issn1000-1239.2016.20148380

• 系统结构 • 上一篇    下一篇

副版本优先级可提升的全局容错调度算法

彭浩,韩江洪,魏振春,卫星   

  1. (合肥工业大学计算机与信息学院 合肥 230009) (hanjh@hfut.edu.cn)
  • 出版日期: 2016-02-01
  • 基金资助: 
    国家自然科学基金项目(61370088);国家国际科技合作专项项目(2014DFB10060);国家科技支撑计划项目(2013BAH51F01,2013BAH51F02)

Fault Tolerant Global Scheduling with Backup Priority Promotion

Peng Hao, Han Jianghong, Wei Zhenchun, Wei Xing   

  1. (School of Computer and Information, Hefei University of Technology, Hefei 230009)
  • Online: 2016-02-01

摘要: 在主副版本机制的全局容错调度中,副版本运行窗口短,采用优先级继承策略的副版本响应时间长,容易错失截止期.针对副版本实时性差的问题,提出基于优先级提升策略的全局容错调度算法(fault tolerant global scheduling with backup priority promotion, FTGS-BPP),通过赋予副版本比主版本高的优先级,减少副版本在运行过程中受到的干扰,缩短了副版本的响应时间,改善了副版本的实时性,从而减少了实现容错所需的额外处理器资源.仿真结果表明,和采用优先级继承策略的全局容错调度算法相比,FTGS-BPP在调度相同的任务集时明显降低了处理器资源需求.

关键词: 多处理器, 容错调度, 全局调度, 硬实时系统, 优先级提升

Abstract: Fault tolerance is of great importance in hard real-time systems due to the impossibility of eliminating faults. In such a system the fault tolerant scheduling algorithm plays a critical role for achieving fault tolerance capability. In primary-backup scheme based fault tolerant global scheduling algorithms, the execution window of backup is relatively small. When priority inheritance strategy is adopted, the response time of the backup is likely too long to guarantee deadline requirement. For improving the real time property of the backup, we propose a fault tolerant global scheduling algorithm based on backup priority promotion strategy—FTGS-BPP. In FTGS-BPP, the backup has a higher priority than its corresponding primary so that during the execution the backup suffers less interference. Consequently the response time of the backup is reduced which means better real time performance. FTGS-BPP can achieve fault tolerance with less processors than the algorithms which follow priority inheritance strategy. A backup priority searching algorithm is also proposed. The simulation result shows that, compared with the fault tolerant global scheduling algorithm based on priority inheritance strategy, FTGS-BPP is able to reduce processor requirement significantly when scheduling the same task set.

Key words: multiprocessor, fault-tolerant scheduling, global scheduling, hard real-time systems, priority promotion

中图分类号: