摘要： 最早截止期优先(EDF)调度算法在系统过载的情况下会产生“多米诺效应”,导致无法满足多数任务的实时性要求。针对该问题,提出一种基于贪心策略的最优调度集选择方法。通过引入一个表示任务价值的因子与任务的截止时间共同决定任务的优先级,当系统过载时,在 EDF算法的可调度范围内选取重要任务作为优先调度对象。理论性能分析和实验结果表明,该算法不仅能在过载时降低实时系统的任务截止期错失率,而且能保证关键任务的优先调度。

关键词: 实时操作系统, 调度算法, 最早截止期优先调度, 贪心策略, 优先级, 截止期错失率

Abstract: The Earliest Deadline First(EDF) scheduling algorithm has “Domino effect” when the system overloads causing most tasks’ real time requirement can not be satisfied.Aiming at this problem,this paper proposes an algorithm of optimal scheduling set selecting based on greedy policy.Using a factor which reflects the value of task and deadline to decide the priority of task,it selects important task to schedule when system overloads.Theoretical performance analysis and experimental result show that the proposed algorithm can reduce Deadline Missing Ratio(DMR) and guarantee the key tasks to be scheduled firstly.

Key words: real-time operating system, scheduling algorithm, Earliest Deadline First(EDF) scheduling, greedy policy, priority, Deadline Missing Ratio(DMR)

中图分类号: 

• TP316.2