任务调度过程中就绪队列的优化研究  

Ready Queue Optimization Research in Task Scheduling

作　　者：陈英革[1] 王小英[1] 赵海[2] 尹震宇[2] 

机构地区：[1]常熟理工学院计算机系,江苏常熟215500 [2]东北大学信箱信息科学与工程学院,辽宁沈阳110004

出　　处：《系统仿真学报》2006年第4期877-882,885,共7页Journal of System Simulation

基　　金：国家自然科学基金(60203011);江苏省教育厅自然科学基金项目(05KJD520005)

摘　　要：绝大多数嵌入式实时系统仅配置了必不可少的资源,任务间抢占行为导致的额外开销严重影响着系统的性能。通过分析周期性任务的调度过程,得出在确保任务不错过截止期条件下,各个任务在就绪队列中可等待的最长期限计算公式,并根据公式推导出任务满足截止期的最后抢占时刻等属性,从而定量地刻画了周期性任务抢占行为发生的必要条件,提出了一套对周期性任务的就绪队列进行微调度的抢占模型,通过改变抢占关系来减少抢占次数、优化实时系统性能。本文最后通过实验验证了该微调度的抢占模型不仅有效地减少抢占次数,同时对于静态优先级调度策略如RM,能有效地提高处理器的可调度利用率。Most of embedded real-time systems only equip limited necessary resources so the extra overheads of preemptions among tasks debase the performance of systems significantly. Through scheduling process analysis of periodic task, the waiting limit formula of each task in ready queue was obtained while guarantees its deadline. In addition, some properties, such as final preempting time was deduced and the necessary condition of periodic tasks preempting behavior was described quantitatively. Based on them, a micro scheduling preemption model for periodic tasks in ready queue was put forward, which decreased the number of preemptions and optimized system performance through changing the preempting sequences. The simulation results of the case study show that the model can not only decrease the number of preemptions effectively but also improve the processor utilization for static priority scheduling algorithm such as rate monotonic scheduling.

关 键 词：任务调度 RM调度算法 EDF调度算法 微调度模型 实时系统 

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