面向多核的时间帧加权公平调度算法.pdf.pdf

:1674-9057(2012)01—0121-05doi:.1674-,刘羽,芦奉良b(,南宁530012;&,广西桂林541004)摘要:多核系统在移动终端、多媒体设备上的广泛应用对于多核系统的调度提出了新的要求,由于这些多核设备中大量的周期性与实时动态任务的执行,使得传统的Pfair和ERfair等经典算法产生了大量的任务迁移,同时对于动态任务调度并不能提供良好的支持。因此,在Pfair经典调度算法的基础上,结合EDF等局部调度算法,以时间帧的模式轮转多任务的周期执行,并采用处理器时间帧间的任务固定来降低任务的迁移率。仿真实验表明,在对任务调度公平性影响很小的情况下,大大降低了任务的迁移率并能更好的处理动态任务,具有更高的效率和更为广泛的使用范围。关键词:多核系统;任务调度;公平调度;任务迁移中图分类号::A在当前多核系统的调度算法中,存在着全局性调度和局部调度两种模式。其中局部调度是在任务分配到单个处理核心后,在单个核心上所进行的调度策略。经过20多年的发展,局部调度发展出了以EDF和RM等为代表的调度算法?,但是局部调度对于实时系统中的动态调度显得力不从心,为了克服局部调度在实时系统中的低效率,近年来出现了以Pfair_2为代表和在其基础上改进而来的ERfair及PD等全局调度算法,将多处理核心作为一个整体的系统取得了较好的调度效率。但是,在实际应用中,对于分布存储的低耦合度系统,Pfair等全局调度算法就不能有效地限制任务在不同处理器迁移所带来的间接开销,从而影响了整个系统的运行效率。本文提出的面向多核的时间帧加权实时调度算法(MPfair)在结合两种调度模式的特点上,运用时间帧技术和分区调度等策略有效地降低了任务的迁移,并完善了对动态实时任务的支持,使新的算法具有更好的适应性和更高的效率。,首先将所有待调度任务划分成大小相等的子任务,并且将所有子任务按优先级排序,其中每个子任务的调度时点是确定的,以此来保证调度的公平性。调度开始后的每一个时段,依次从队列中取得任务分配给不同的处理核心。当有任务动态的到达时也可以将新的任务分解后添加入待分配序列,并修改调度时点。对于一组任务{A一,A},其中每个任务A需要运行的时间为个单位,并限定任务完成在P个时间单位之内。Pfair算法在对任务进行分配时要符合最终完成时间的要求并使任务的执行效率达到即执行速率和任务量相一致。在对实时性要求更高的系统中,设定任务初始时间为s,使任务符合以下条件:在任何时段结束时Js≤t≤收稿日期:2011—08—17基金项目:广西自然科学基金项目(桂科自0832249);广西教育厅重点科研项目(201102ZD018)作者简介:黎卫红(1959一),男,高级工程师,研究方向:企业信息化。引文格式:黎