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

韩美灵; 邓庆绪; 张天宇; 冯智伟; 林宇晗

doi:10.11897/SP.J.1016.2019.02355

TP399; 多核处理器全局最早截止期优先(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 this paper, we study the problem of limited-preemption scheduling of sporadic task systems which are running on multiprocessor platforms under G-EDF scheduling policy. The purpose of this paper is combine the state-of-the-art scheduling analysis method on multiprocessors under G-EDF with limited preemption. To avoid involving too much complexity, we just consider the total non-preemption interval among the scheduling of tasks for each task. To reduce the overheads induced by preemption and inter-processor migration under G-EDF scheduling, this proposed G-EDF limited preemption policy is denoted by G-LP-EDF, which avoids unnecessary preemption among tasks without losing the system schedulability but reducing the run-time cost. G-LP-EDF considers the scheduling of tasks and makes sure it cannot reduce the schedulability of tasks through combining the state-of-the-art scheduling method of G-EDF with limited preemption scheduling. In the end, we conduct sufficient experiments to show the precise and efficiency of this G-LP-EDF compared with the state-of-the-art method through simulation experiments. The performance of our proposed approach reduced tasks preemption at least 40% on average compared to the state-of-the-art method, and the schedulability difference between G-LP-EDF and the state-of-the-art method is the same. In efficiency, G-LP-EDF is slower than the state-of-the-art method and at most slower 20ms which is not even 1s.

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

View Online

Abstract

Details

Metrics