ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2015, Vol. 52 ›› Issue (5): 1177-1186.doi: 10.7544/issn1000-1239.2015.20140018

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

多处理器硬实时系统的抢占阈值调度研究

彭浩,韩江洪,陆阳,张建军   

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

Multiprocessor Hard Real-Time Systems Preemption Threshold Scheduling

Peng Hao, Han Jianghong, Lu Yang, Zhang Jianjun   

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

摘要: 在实时系统中,抢占在提高系统灵活性的同时带来额外的系统开销,特别在多处理器平台上抢占导致的作业迁移会造成相当大的性能下降,减少不必要的抢占是硬实时系统研究的重要方向.抢占阈值调度是处于抢占调度和不可抢占调度之间的一种混合调度方法,在保持调度能力的基础上限制抢占.基于截止期分析建立了多处理器硬实时系统抢占阈值调度的可调度性判定条件,针对抢占阈值调度提出一种改进的优先级分配算法OPA-MLL,并建立了抢占阈值分配(preemption threshold assignment, PTA)算法.仿真结果表明,采用OPA-MLL算法和PTA算法分别给任务集分配优先级和抢占阈值时,可调度任务集比率明显提高,同时能最大程度限制抢占次数.

关键词: 多处理器, 硬实时系统, 抢占阈值, 可调度判定, 优先级分配, 抢占阈值分配

Abstract: The preemption plays a critical role in hard real-time systems. Preemptions are able to increase the schedulability of system. However, in multiprocessor platform, the large amount of preemptions may cause significant run-time cost due to context switch, running scheduler, job migration, etc. Besides quite amount of these preemptions are unnecessary regarding to schedulability. Limited preemption scheduling is the hybrid method between preemptive and non-preemptive scheduling, which can reduce unnecessary preemptions. In this paper, we extend the preemption threshold scheduling (PTS), one of the major methods of limited preemption scheduling, to multiprocessor hard real-time systems, which is firstly proposed for uniprocessor. The main focus of this paper is reducing preemptions. Based on DA-LC test, we derive the schedulability test for PTS. An efficient priority assignment algorithm OPA-MLL is proposed which is optimized for PTS from the combination of OPA and DA-LC. We also establish the threshold assignment algorithm aiming at reducing preemptions. The simulation result shows the PTS can reduce preemptions significantly for multiple priority assignment algorithms. At the meantime OPA-MLL has the largest percentage of schedulable task sets and most potential for reducing preemptions.

Key words: multiprocessor, hard real-time systems, preemption threshold, schedulability test, priority assignment, preemption threshold assignment

中图分类号: