摘要
针对截止期最早优先(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.
出处
《华中科技大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2009年第10期1-4,共4页
Journal of Huazhong University of Science and Technology(Natural Science Edition)
基金
国家自然科学基金资助项目(60603032)
关键词
实时调度算法
截止期最早优先
偶发任务
容错
挪用时间
real-time scheduling algorithm
earliest deadline first
aporadic task
fault-tolerance
stealing time
