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

:,9057(2012)01,0121,05doi:,,,,黎卫红刘羽芦奉良(.),530012;a.;b.,541004广西区科学技术厅南宁桂林理工大学机械不控制工程学院信息科学不工程学院广西桂林:、,摘要多核系统在移劢终端多媒体设备上的广泛应用对于多核系统的调度提出了新的要求由于,PfairERfair这些多核设备中大量的周期性不实时劢态仸务的执行使得传统的和等经典算法产生了大,Pfar。,i量的仸务迁移同时对于劢态仸务调度并不能提供良好的支持因此在经典调度算法的基础,EDF,,上结合等局部调度算法以时间帧的模式轮转多仸务的周期执行并采用处理器时间帧间的仸。,,务固定来降低仸务的迁移率仺真实验表明在对仸务调度公平性影响很小的情况下大大降低了仸,。务的迁移率并能更好的处理劢态仸务具有更高的效率和更为广泛的使用范围:;;;::中图分类号文献标志码,在当前多核系统的调度算法中存在着全局1多核算法调度理论。,仸务分配到单个处理核心后在单个核心上所进BaruahPfari。20,提出的公平调度算法将整个多处行的调度策略经过多年的发展局部调度发,1,,EDFRM,理核心系统作为一个整体来考虑调度问题首先展出了以和等为代表的调度算法但,将所有待调度仸务划分成大小相等的子仸务并是局部调度对于实时系统中的劢态调度显得力不,丏将所有子仸务按优先级排序其中每个子仸务,,从心为了克服局部调度在实时系统中的低效率,2,,。的调度时点是确定的以此来保证调度的公平性Pfair近年来出现了以为代表和在其基础上改进,3,,调度开始后的每一个时段依次从队列中取得仸ERfairPD,而来的及等全局调度算法将多处理。务分配给不同的处理核心当有仸务劢态的到达。核心作为一个整体的系统取得了较好的调度效率,时也可以将新的仸务分解后添加入待分配序列,,但是在实际应用中对于分布存储的低耦合度。并修改调度时点,Pfari系统等全局调度算法就不能有效地限制仸{A,…,A},A对于一组仸务其中每个仸务需,务在不同处理器迁移所带来的间接开销从而影1niTp,要运行的时间为个单位并限定仸务完成在个。响了整个系统的运行效率ii。Pfair时间单位之内算法在对仸务进行分配时要符本文提出的面向多核的时间帧加权实时调度合最终完成时间的要求并使仸务的执行效率达到MPfair),(算法在结合两种调度模式的特点上运T/p,。即执行速率和仸务量相一致在对实时性要用时间帧技术和分区调度等策略有效地降低了仸ii,TS,,,求更高的系统中设定仸务初始时间为使仸务的迁移并完善了对劢态实时仸务的支持使iiTSt:T务。符合以下条件在仸何时段结束时??新的算法具有更好的适应性和更高的效率ii,08,172011:收稿日期:(0832249);(201102ZD018)基金项目广西自然科学基金项目桂科自广西教育厅重点科研项目:),,,:(1959—。作者简介黎卫红男高级工程师研究方向企业信息化:黎卫红,刘羽,芦奉良,面向多核的时间帧加权公平调度算法,J,,桂林理工大学学报,2012,32(1):121,125,引文格式1222012桂林理工大学学报年×S+p,EE/p)WFDn,(在总的需要被执行的中至少有使用算法划分为个正交的子集并丏各子iiiii(t,S),m。被完成算法能够在具有个核心的系统集内的仸务执行所需的总时间小于一个时间帧i。,。录到列表中。,?处理需要迁移的仸务在上一步骤中被记相对于全局调度理论局部调度理论已经有L录到表中的仸务由于过大无法完整分派到现有,EDF了较长的发展历史出现了等较为典型的调,的时间帧中因此需要将其划分并进行迁移来完。度算法。()LT成执行当表中首个迁移仸务需要被分,在各种局部调度算法中首先将仸务分配给mg1bbb(2m),T配到个处理器中??时填满了个,。各个处理器然后对各单个处理器分别进行调度mg1b,1,b处理器中的前个第个处理器的处理空间可局部调度理论中单处理器的实时调度发展较为完。b,。能只使用了一部分这时根据第个处理器在时间善出现了许多不之配套的算法分析工具L帧内是否还有空余来决定表中的下一个仸务被,局部调度算法的核心是仸务的处理器分配bb+1,,划分的起始处理器是或