基于桶排序的EDF调度算法优化

摘要

EDF scheduling algorithm can not schedule all the tasks effectively in real-time system is when the system is overloaded,so that the task deadline miss ratio is very high.Utilizing bucket sort algorithm to sort the tasks in real-time system according to their different priority level,the high priority level task group will be scheduled and executed.And the priority level of other low priority level task group will be adjusted dynamically according to the resource utilization.By using such method,the task deadline miss ratio of real-time systems can be reduced.Simulation experiments showed that the deadline miss ratio of the optimized EDF scheduling algorithm was significantly lower than that of algorithm before optimization,illustrating that the real-time task deadline miss ratio of EDF scheduling with bucket sort was lower than EDF scheduling.%EDF调度算法在系统过载的情况下,就不能有效地实时调度系统中的所有任务,使任务的截止期错失率非常高.利用桶排序算法,将实时系统中任务按不同优先级等级分组排序,使得高优先级等级任务组中的任务优先被调度执行;对于其他低优先级等级任务组中的任务,根据资源利用率动态调整它们的优先级等级,从而降低实时系统的任务截止期错失率.仿真实验表明,优化后的EDF调度算法的截止期错失率,明显比优化前低,说明基于桶排序的EDF调度算法的实时任务截止期错失率比EDF调度算法低.