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

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

作　　者：檀明[1,2] 魏臻[2] 韩江洪[2] 

机构地区：[1]合肥学院网络与智能信息处理重点实验室,合肥230601 [2]合肥工业大学计算机与信息学院,合肥230009

出　　处：《计算机应用研究》2012年第2期722-724,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(60873003;60873195);安徽省教育厅自然科学一般项目(KJ2011B139)

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

关 键 词：实时系统 时延抖动 非抢占式EDF算法 周期性任务 相对截止期 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]