基于半划分调度的Linux 实时调度算法改进*

李 辉 刘志红

（1.中国电子科技集团公司第二十八研究所 南京 210007）（2.武汉达梦数据库股份有限公司 武汉 430073）

1 引言

实时系统在工业控制、航空航天、自动驾驶等众多领域扮演着重要角色。不同于一般的操作系统，实时系统的目标不是高的吞吐量，而是保证任务在特定时间内完成。在实时系统中，实时调度算法处于核心位置，实时调度算法为实时任务能在截止期限前完成提供保证。

传统的多处理器实时调度算法分为划分调度（Partitioned Scheduling）算法和全局调度（Global Scheduling）算法［1～2］。在全局调度中，所有实时任务都存储在一个按照优先级排序的队列中，全局调度程序从该队列中选择优先级最高的任务执行。在分区调度中，每个任务被分配给一个处理器，其中每个任务将在其上执行，并且处理器之间是独立调度的。全局调度能够带来较高的系统利用率，但是因为任务可能会频繁地在处理器间切换，所以会带来较高的系统开销；划分调度可以比较容易地应用已有的单处理机调度算法，但是系统利用率低［3］。Anderson 等首次提出了半划分调度（Semi-partitioned Scheduling）算法EDF-fm［4～5］，该算法中大部分任务采用划分调度的思想被划分到指定处理器上运行，而另一部分任务采取全局调度的思想，允许在多个处理器上迁移。这种方法可以提升系统可调度性并相比全局调度降低了上下文切换次数，降低了系统负载，相比纯粹的划分调度提升了处理器利用率。随后，文献［6］提出半划分调度算法EKG，不同于EDF-fm，EKG设定迁移任务在特定的时间段内执行，而固定任务则根据EDF 进行调度，实现了硬实时系统上的可调度性保障。Kato 和Yamasaki 在文献［7～11］中提出了EDDHP、EDDP、RMDP、DMPM 和EDF-WM 算法，这些算法旨在使用任务拆分的方法实现高可调度性和低抢占次数，其中EDDP 的最坏资源利用率界限为65%，基于固定优先级的RMDP 和DMPM 则达到了50%的最坏资源利用率界限，EDF-WM 由DMPM 方法扩展而来。文献［12］提出的SPA1 和SPA2 算法首次将单个处理器上的最坏资源利用率界限提高到了Liu&Layland 提出的使用率上限［13］。文献［14］提出了一种多处理器EDF调度的任务分割方案，不同于上述其他方案，该方案有着易于实施和低负载的特点。

Linux 于3.14 版本引入了基于GEDF 实现的deadline 调度器，该调度器能够保证实时任务在最坏截止期限前完成，但是多核全局调度会遇到Dhall效应［15］。针对该问题和上述半划分调度算法的研究，文章基于半划分调度对Linux 内核中实时调度算法做了改进；在EDF 算法的基础上，加入半划分调度的思想，在实时任务处理器利用率差别较大时也能成功调度，提高Linux 实时任务可调度性的同时降低了上下文切换频率，从而降低了上下文切换带来的系统开销。

2 任务模型

EDF算法基于这样一个周期任务模型：一个周期性任务（或简称任务）τi是一个三元组(Ci,Di,Pi)，其中各元素定义为

1）Ci：最坏情况执行时间（Worst Case Execution Time，简称WCET），即任务每次释放需要的最长执行时间。

2）Di：相对截止期。即τi每次释放后期望在Di时间内完成执行。

3）Pi：最短释放间隔（也称为周期）。τi的两次释放之间需要至少Pi时间间隔。

EDF 算法总是最先调度执行deadline 最早到来的那个任务。对于有M个处理器的系统，优先级最高的前M 个任务（即deadline 最早到来的前M 个任务）将被选择在对应M个处理器上运行。

下面按照Linux 中deadline 调度器的准入策略，对于运行在M 个处理器上的N 个周期性任务{τ1,τ2,…,τN}，给出该任务集的可调度性必要条件如定义1。

定义1：假设有N 个周期性任务τ1,τ2,…,τN运行在M 个处理器上，任务τi的最坏执行时间为Ci，相对截止器为Di，周期为Pi，1 ≤i≤N。若任务利用率总和不超过M，则任务集可调度，即：

Linux 中基于GEDF 算法实现的deadline 调度器并不严格遵守上文描述的EDF周期任务模型，调度基于如下三个参数来调度任务：

1）runtime：任务执行时间，通常设置为大于等于Ci的值。

2）deadline：相对截止期限，即Di。

3）period：任务周期，通常设置为小于等于Pi的值。

Linux 中提供了sched_setattr（）系统调用对这三个参数进行设置。

3 调度策略

Linux 中deadline 调度器的调度过程可以用例1来描述。

例1：对于在具有M 个CPU 的系统上的M+1个任务的集合{τ1,τ2,…,τM+1} ，我们考虑这样一种情况：其中第一个任务τ1=(P,P,P)的WCET、相对截止期和周期都等于P，剩下的M 个任务τi=(e,P-1,P-1) 具有任意小的最坏情况执行时间（这里用“e”表示）和比第一个任务小的周期。因此，如果所有任务在同一时间t 激活，全局EDF 将首先调度这M 个任务（因为它们的绝对期限为t+P-1，小于τ1的绝对期限t+P）。因此，τ1只能在时间t+e安排执行，并将在其绝对截止日期之后的t+e+P时刻完成。任务集的总利用率为

对于较小的e 值，这个值可能变得非常接近1，看起来在M（M＞1）个处理器上这个任务集肯定可以很好地调度，但是事实上τ1只能在其他M个任务运行完毕之后才开始执行，因此τ1的deadline 不能得到满足，这就是Dhall 效应，Dhall 效应调度如图1所示。

图1 Dhall效应

图1 说明了在任务集中任务的处理器利用率相差较大的时候，即使任务集的利用率并不高，deadline调度器有时并不能保证每一个实时任务都可调度。

为了解决上述问题，文章提出新的调度策略如下：对于有N 个任务的队列，将N 个任务按照利用率进行排序，每次找出利用率最大的任务τtop从队列中取出，尝试将其分配给第m=1 个处理器，采用单处理器EDF可调度条件进行判断，如果可调度就完成分配，否则将其重新放到队尾，如此循环N 次完成第m=1个处理器的任务分配，然后对于其他任务继续按照全局EDF 在剩下的其他CPU 上进行调度。具体算法如算法1所示。

算法1 基于半划分调度改进的调度算法

input：the task set Γ={τ1,τ2,…,τn}

output：0 if Γ is schedulable and-1 if not

1）sort Γ according to the utilization rate from largest to smallest

2）for i=1，2，……n do

3）take out the first task from Γ asτ

4）utili0 ←0

5）for task in CPU0.tasks do

6） utili0+=task.runtime/task.period

7）end

8）utili0+=τ.runtime/τ。period

9）if utili0 ＜=1

10） assignτto CPU0（partitioned EDF）

11）else

12） putτat the end of Γ

13）end

14）assign tasks in Γ to the other CPUs（global EDF）

对算法一继续用例1 中的情况进行分析：任务集{τ1,τ2,…,τM+1} 运行在M 个处理器上，其中第一个任务τ1=(P,P,P)的WCET、相对截止期和周期都等于P，剩下的M 个任务τi=(e,P-1,P-1) 具有任意小的最坏情况执行时间（这里用“e”表示）和比第一个任务小的周期。根据我们的算法τ1会被分配到CPU0 上，此时CPU0 的利用率达到1，所以其他任务无法再分配给CPU0，{τ2,…,τM+1} 将被分配到剩下的M-1 个CPU 上根据GEDF 策略进行调度。此时的调度顺序如图2所示。

图2 改进后的调度顺序

可以看到在文章提出的算法中，所有任务的截止期限都被满足了，处理器利用率最高的τ1独占一个CPU，其他M 个任务在M-1 个CPU 上继续按照全局调度的策略进行调度。

4 实验结果与分析

首先使用实时多处理器体系结构的调度模拟器SimSo 进行仿真，对于例1 所述情况使用GEDF进行调度时，绘制甘特图，如图3所示。其中任务1的WCET、相对截止期、周期均为10ms，其他任务WCET=1ms，相对截止期、周期均为10ms。可以发现在第一个周期，任务1 只能在任务3 完成后开始执行，在执行9ms 后被任务5 抢占，并且在后续每一个周期都会被提前抢占，任务不能保证完成。使用基于半划分调度改进过的算法进行调度时，绘制甘特图，如图4 所示，任务一独占CPU2，其他任务在另外三个CPU 上按照GEDF 算法进行调度，所有任务都能在截止期限前保证完成。

图3 GEDF调度结果

图4 改进后的调度结果

然后在具有四个核心的Loongson-3A R4 处理器上进行测试，Linux 内核版本为Linux 4.19.0-12-loongson-3 mips64。使用随机的runtime、period和deadline创建总利用率固定的任务集分别使用Linux 中的deadline 调度器和文章改进的EDF调度器进行调度，绘制出任务集调度成功率与任务集总利用率关系的图像，如图5所示。

图5 不同利用率的任务集调度成功率

在任务集总利用率较低时，deadline 调度器与基于半划分调度改进的调度都能满足所有任务的截止期限，但当任务集总利用率接近甚至超过处理器总数时，基于半划分调度改进的调度对任务集的可调度性明显优于deadline调度器。

由于部分任务被固定到一单独处理器上运行，改进后的调度算法能明显降低上下文切换次数，如图6所示。

图6 不同利用率的任务集上下文切换次数

5 结语

实时任务的调度算法在许多重要系统中发挥着关键作用，Linux 操作系统也一直在实时性上做出各种尝试，现有的Linux 实时调度算法是基于全局EDF 调度实现的，在多核处理器上容易出现Dhall 效应，本文针对此问题提出了一种基于半划分调度改进的调度算法，避免了全局EDF调度带来的Dhall效应，同时提高了调度器的可调度性，降低了上下文切换次数和系统开销。