EDF实时调度算法中的关键问题求解  

Solving a key problem of EDF scheduling algorithm

作　　者：张杰[1] 阳富民[1] 卢炎生[1] 涂刚[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《华中科技大学学报（自然科学版）》2009年第10期1-4,共4页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60603032)

摘　　要：针对截止期最早优先(EDF)调度算法存在的问题,通过分析和证明EDF调度算法中最大可挪用时间的性质,结合EDF的最优调度过程,提出一种可延迟时间逼近(DTA)算法,以快速准确地计算EDF算法调度周期任务的最大可挪用时间,并且证明了该算法的时间复杂度只和周期任务数、处理器的占用率之和有关.仿真实验验证了DTA算法的时间性能.At present,the calculating the max stealing time of the EDF（earliest deadline first） algorithm scheduling periodic tasks is limited to whole hyper period,and the time complexity is pseudo-polynomial time.The properties of the maximum stealing time with the EDF scheduling algorithm is analyzed and proved.Combined with the optimal scheduling process,the delay time approximation（DTA）algorithm is proposed,which can calculate the maximum stealing time quickly and accurately.It is proved that the time complexity of DTA algorithm is only relative to the number of periodic tasks and the total utilization of the processor. The time performance of DTA algorithm is verified through the simulation results.

关 键 词：实时调度算法 截止期最早优先 偶发任务 容错 挪用时间 

分 类 号：TP311.2[自动化与计算机技术—计算机软件与理论]