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

Optimization of EDF scheduling algorithm based on bucket sort

作　　者：于国龙[1] 张明富[1] 

机构地区：[1]毕节学院数学与计算机科学学院,贵州毕节551700

出　　处：《兰州理工大学学报》2013年第4期110-113,共4页Journal of Lanzhou University of Technology

摘　　要：EDF调度算法在系统过载的情况下,就不能有效地实时调度系统中的所有任务,使任务的截止期错失率非常高.利用桶排序算法,将实时系统中任务按不同优先级等级分组排序,使得高优先级等级任务组中的任务优先被调度执行;对于其他低优先级等级任务组中的任务,根据资源利用率动态调整它们的优先级等级,从而降低实时系统的任务截止期错失率.仿真实验表明,优化后的EDF调度算法的截止期错失率,明显比优化前低,说明基于桶排序的EDF调度算法的实时任务截止期错失率比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 optimiza- tion, illustrating that the real-time task deadline miss ratio of EDF scheduling with bucket sort was lower than EDF scheduling.

关 键 词：嵌入式系统 桶排序 调度算法 优先级 错失率 

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