最早截止期优先调度算法的改进  

Improvement of earliest deadline first scheduling algorithm

作　　者：程禹[1] 赵宏伟[1] 龙曼丽[2] 李玉翠[1] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学公共外语教育学院,长春130012

出　　处：《吉林大学学报（工学版）》2013年第5期1338-1342,共5页Journal of Jilin University:Engineering and Technology Edition

基　　金：吉林省自然科学基金项目(20101504);吉林省教育厅科学基金项目(2009605)

摘　　要：在基于IEEE802.16d协议的服务流调度过程中,为了保证优先级较高的任务优先得到服务,并尽量将调度过程对系统资源的消耗控制在可承受的范围内,在分析已有的非抢占式及抢占式两种方案的最早截止期优先(EDF)算法优缺点的基础上,重点考虑时间特性、重要性特性、顺序参考三方面作为调节参数,同时兼顾传输距离,对已有的EDF算法进行改进。提出了基于重要性因素抢占的半抢占式EDF算法。通过仿真实验,把改进后的EDF算法应用到IEEE802.16d协议的实时轮询业务(RTPS)服务流调度中。结果表明,改进后的EDF算法较好地平衡了抢占及非抢占式EDF算法的优缺点,具备较前两者更小且更稳定的延时。In the process of service flow scheduling based on IEEE802. 16d agreement, a good scheduling algorithm should ensure that higher priority tasks get priority service; meanwhile, the occupation of system resources during the scheduling process should be minimized. The advantages and disadvantages of two kinds of existing Earliest Deadline First （EDF） algorithms, i.e. the non- preemptive EDF algorithm and preemptive EDF algorithm, are analyzed in depth. Then an improved semi-preemptive EDF algorithm based on the importance of factors is proposed. In this algorithm the time characteristics, the importance characteristics and the order of reference are taken as the adjustable parameters, and the transmission distance is also taken into account. By simulation, the improved EDF algorithm is applied to the Real-Time Polling Service （RTPS） service flow scheduling of IEEES02.16d agreement. The experimental results show that the improved EDF algorithm has a better balance between advantages and disadvantages than non-preemptive and preemptive EDF algorithms, with smaller and more stable delay.

关 键 词：计算机应用 最早截止期优先算法 平均延时 截止时间 时间特性 抢占 

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