非抢占式EDF算法下周期性任务的最小相对截止期计算*

现有的求解周期性任务最小相对截止期的方法均假定任务集是采取抢占式EDF调度算法,并不适用于当任务为基于非抢占式EDF调度算法的场合,如实时通信领域。在分析了非抢占式EDF调度算法的可调度性判定条件基础上,提出了基于非抢占式EDF调度算法下周期性任务最小相对截止期的计算算法。算法通过逐渐增加任务的相对截止期直到使任务集变为可调度的方式,实现某个任务相对截止期的最小化。仿真实验表明该算法具有较好的计算复杂度。

Minimum relative deadline calculation for periodic real-time tasks scheduled by non-preemptive EDF algorithm

Current deadline minimization methods that compute the shortest deadline of a periodic task are limited because they are all based on preemptive EDF algorithm which is not easily to implement in the application areas such as real-time communications.This paper analyzed the feasibility condition for periodic real-time tasks scheduled by non-preemptive EDF algorithm.In addition,by incrementing the deadline of a task step by step until the task set become feasible under non-preemptive EDF,it proposed an algorithm for calculating the minimum non-preemptive EDF-feasible deadline of real-time messages.And simulation results show that the algorithm can operate effectively.