多核处理器限制性可抢占G-EDF调度策略研究  

Limited Preemption for G-EDF Scheduling on Multiprocessors

作　　者：韩美灵 邓庆绪 张天宇 冯智伟 林宇晗 HAN Mei-Ling;DENG Qing-Xu;ZHANG Tian-Yu;FENG Zhi-Wei;LIN Yu-Han(Department of Computer Science and Engineering,Northeastern University,Shenyang 110819)

机构地区：[1]东北大学计算机科学与工程学院

出　　处：《计算机学报》2019年第11期2355-2367,共13页Chinese Journal of Computers

基　　金：国家自然科学基金(61472072,61528202)资助

摘　　要：多核处理器全局最早截止期优先(Global Earliest Deadline First,G-EDF)调度策略允许任务的抢占和任务在处理器之间迁移,频繁的抢占和核间迁移会导致较高的处理器开销,造成系统资源的浪费.然而目前针对多核处理器的可调度性分析方法都基于这样的假设:任务抢占和系统间迁移的开销计入最差响应时间或者忽略不计.但是实际研究表明该部分的开销在系统资源总开销中占重要部分,因此不可简单的忽略不计.而不可抢占调度,会给高优先级任务代入太多的阻塞从而导致其不可被调度.针对这类问题,实时领域的研究者们提出了限制性可抢占调度策略,且在全局固定优先级方面取得了很多的研究成果,然而在G-EDF方面的研究工作相对较少.该文研究了限制性可抢占全局最早截止期优先(Limited Preemption Global EDF,G-LP-EDF)调度策略,该策略结合了完全可抢占和完全不可抢占的优点.G-LP-EDF调度策略把目前G-EDF最佳的分析方法和限制性可抢占调度策略相结合,目的是减少G-EDF的额外系统开销,避免系统资源的浪费,而不降低G-EDF的调度性.最后通过仿真实验,G-LP-EDF分析方法在平均抢占次数上比G-EDF至少可减少40%,而两个分析方法之间的可调性没有明显差距,大约为1%.效率上两个方法随着最差执行时间的取值增大而增多,这是两个方法的本质造成的.然而G-LP-EDF整体比G-EDF的平均处理时间要慢,但差距都不足1s.With the increasing trend towards using multi-core architecture for embedded systems,the study of multiprocessor scheduling becomes attractive and desirable in the literature.G-EDF(Global Earliest Deadline First)is one of the most popular scheduling policy which allows preemption and migration between processors.There are many techniques proposed to derive an upper bound of the worst case response time or schedulable tests based on the assumption that the overheads of preemption and migration is omitted or just used an over-estimated value which is included in the worst case execution time.But there are works have been done to show that the overheads of preemption and migration cannot omit or include in the worst case execution time which would waste lots resource.And non-preemption does not have this problem but it would involve more blocks to the tasks with higher priority and make them un-schedulable.To combine the advantages of preemption and non-preemption,researchers in real-time area proposed the concept called limited-preemption.There are a lot of work about G-FP(Global Fixed-Priority)limited preemption,and the schedulability analysis of this problem is easier than G-EDF limited preemption.The method in G-FP limited preemption is not only reducing the preemption caused by higher priority tasks also improved the schedulability due to the character of G-FP scheduling method.The limited preemption has been well studied in G-FP scheduling while less has been done in G-EDF.Because the priority of each job of each task may be different in G-EDF while the priority of each job of each task is the same in G-FP.The differences involves much hardness to handle the preemption among each job of each task,and it is hard to find an available schedulability test of limited preemption G-EDF scheduling policy.Now,the G-EDF scheduling policy has been well studied on the multiprocessors which allowed preemption.But there no such a work to combine the state-of-the-art G-EDF scheduling method with the limited preemption.In thi

关 键 词：多核处理器 实时嵌入式系统 限制性可抢占 最早截止期优先 偶发性任务集 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]