基于EDF算法的嵌入式Linux实时调度策略

关斌斌，王勇

（南京邮电大学 南京 210003）

0 引言

目前市场上比较著名的嵌入式操作系统有Vxwork、pSOS、Windows CE和Neculeus，但这些专用操作系统都是商业化产品，其高昂的价格使许多低端产品的小公司望而却步，而且，源代码封装性也大大限制了开发者的积极性。嵌入式Linux以其免费、适应于多种CPU和多种硬件平台、性能稳定、裁剪性能好以及开放源代码、开发和使用都很容易等众多特性获得越来越多的关注。

标准Linux是一个多任务多用户的分时操作系统，尽管系统通过为实时任务赋予较高的优先级使得系统具有一定的实时性，但对于大多数时限要求较高的实时任务来说，标准Linux还远远达不到其对于时间约束的要求。常用的实时性改造方法是采用双内核方法[1]，这种方法的弊端在于实时任务的开发是直接面向提供精确实时服务的小实时核心的，而不是功能强大的常规Linux核心。基于此，目前修改核的方法吸引了更多研究和开发人员的注意力，这种方法是基于已有Linux系统对于软件开发的支持，进行源代码级修改而使Linux变成一个真正的实时操作系统。本文分析了基本Linux内核的实时任务调度策略，基于其对实时应用的技术障碍，提出了一种新颖的Linux内核实时任务调度策略，并提出了以最早期限优先动态调度算法代替原内核的FIFO调度算法，以增强Linux内核的调度性能。

1 Linux内核的调度策略

Linux作为一个通用操作系统，主要考虑的是调度的公平性和吞吐量等指标。然而，在实时方面它还不能很好地满足实时系统方面的需要，其本身仅仅提供了一些简单的实时处理的支持，这包括支持大部分POSIX（可移植操作系统接口）标准中的实时功能，如支持多任务、多队列，具有丰富的通信机制等；同时也提供了符合POSIX标准的调度策略，包括FIFO调度策略、时间片轮转调度策略和静态优先级抢占式调度策略。

为了同时支持实时和非实时两种进程，Linux的调度策略[2]简单讲就是优先级加上时间片。当系统中有实时进程到来时，系统赋予它最高的优先级。体现在实时性上，Linux采用了两种简单的调度策略，即先来先服务调度（SCHED-FIFO）和时间片轮转调度（SCHED-RR）。具体是将所有处于运行状态的任务挂接在一个run-queue 队列中，对不同的任务，在其任务控制块task_struct中用一个policy属性来确定其调度策略，并将此任务分成实时和非实时任务。对实时性要求较严的实时任务采用SCHED-FIFO调度，使之在一次调度后运行完毕。对普通非实时进程，Linux采用基于优先级的轮转策略。尽管Linux本身提供了一些支持实时性的机制，由于缺乏有效的实时任务调度策略和调度算法，实时性问题仍然是将Linux应用于实时应用中一大障碍。

2 EDF动态优先级调度算法

动态优先级可以防止优先级高的进程不停的执行，例如可以在每一个时钟中断时降低正在运行着的进程优先级。这样该进程必然在某个时刻优先级低于其他进程，从而被切换掉。系统还可以通过动态确定优先级，以使某些特定的进程得以优先执行。最著名的动态优先级调度算法就是最早期限优先调度算法EDF[3]，按照任务的最终响应期限来调度。哪个任务的期限最早，就是最紧急的任务，就会被赋予高优先级，得到优先调度。EDF是可抢占的调度算法，通常周期任务的最终期限是它下一个周期开始的时刻。Liu和Layland证明，如果存在某一种调度能够满足所有的时限要求，那么每一次总是执行当前具有最早时限的未完成任务就可以满足所有时限的要求，并证明了对于一个n个周期任务的任务集T= {t1，t2，……，tn}可以被EDF所调度，当且仅当： ≤1

EDF表示时限最早的任务优先调度，是调度理论中一个很重要的动态调度算法，对于同步周期任务组是佳调度算法。

在EDF算法中，任务调度优先级定义为：di(t)-t，di(t)是任务时限，t是当前时间，两者的差值就表示任务的紧迫程度。这种调度优先级定义方式，表明在每个时刻，都要计算下个时刻系统中哪个任务的时限最小，从而决定了系统在下个时刻应该调度哪个任务。系统下个时刻调度的任务的不确定性，使得系统的适应性比较好。

根据EDF算法，处理器将分配给当前距离绝对时限最近的任务。EDF算法是动态调度算法，任务的优先级不是固定的，而是根据各任务距离其绝对时限的接近程度决定。

在FIFO调度算法中，进程一旦占用CPU则一直运行，直到有更高优先级任务到达或自己放弃，因此灵活性差。EDF调度算法最大的优点是：对于突发实时事件的实时处理能力强，系统调度灵活，同时CPU的利用率较高，可以达到100%的利用率。最大缺点在于系统的开销较大，在超载的情况下，系统不可能保证所有的任务都能够满足截止期。

3 基于EDF算法的实时任务调度策略

该调度策略吸取了EDF算法的优点，又保证了内核可以在任何时间被抢占，它主要取决于以下三个问题的解决，临界区的保护、优先级的确定、快速查找将调度实时进程，下面就这三个问题的解决方法进行说明。

3.1 临界区的保护

主要保护措施如下：

(1)在临界区上使用抢占锁。系统维护一个全局变量，使用临界区前设置该变量，使用完毕清除该变量。当该变量被设置时说明有进程使用临界区，不允许抢占。如果此时发生中断，在执行完中断处理程序后将恢复被中断的进程，不会进行调度。当获得抢占锁的进程使用完临界区释放锁，并检查是否有高优先级进程就绪，如果有则执行上下文切换。

(2)使用互斥锁保护执行时间较长的临界段。利用信号量，进程使用临界区前进行P操作,使用完毕进行V操作。

(3)中断处理过程的修改。在中断返回时进行抢占性判断。

下面详细说明每种保护措施的具体实现方法。

3.1.1 抢占锁实现方法

为了实现抢占锁[4],需要在Linux的进程结构taskstruct中增加一项抢占计数器atomic_preempt_count。当进程执行抢占锁时抢占计数器加1，当进程释放抢占锁时抢占计数器减1；如果进程的抢占计数器值为0，则该进程在内核态下执行时可以被抢占。抢占锁属于一种递归锁，对于己经拥有锁的进程可以再次获得抢占锁，也就是允许嵌套使用临界段。

为了在抢占式内核的实现中保持原来使用的自旋锁，在禁止抢占之后设置自旋锁。将原来对自旋锁的实现函数改名为pre_ spin_ lock()和pre_spin_unlock ()，用抢占锁的加锁和解锁代替原来的自旋锁实现函数spin_lock()和spin_unlock()。新的抢占锁加锁操作为:先禁止抢占，再执行pre_ sp in_lock()：解锁操作为：先执行pre_spin_unlock()，再解除抢占。这样就由抢占锁代替了自旋锁对临界区提供保护，同时也保持了原来定义的自旋锁，代码修改尽量少。

3.1.2 互斥锁的实现方法

为了减少由于抢占锁长时间锁定临界段而可能带来的延迟，使用互斥锁来保护执行时间较长的临界段。互斥锁的实现利用了Linux内核中的二元信号量。信号量[5]使用两个原子操作P操作和V操作，进入临界段之前执行P操作，离开临界段后执行V操作。P操作减少信号量，并当信号量的新值为0时被阻塞；V操作增加信号量，若信号量的新值小于等于0时，如果存在阻塞于该信号量的进程则将之唤醒。如果信号量的初值为1，也就是由信号量保护的资源数目为1，称之为二元信号量。内核必须保证对信号量的操作是原子的。Linux对信号量的数据结构的定义在include/rim-i386/semaphore.h中，在内核信号量的实现中，与P操作和V操作相对应的内核例程分别是downQ和upQ。可以直接利用Linux的信号量原语down()和up()来实现互斥锁，其定义添加在头文件nclude/rim-i386/semaphore.h中。

3.1.3 中断的处理方法

Linux中断处理的流程[6]是：中断产生源→中断向量表→中断入口程序→中断处理程序→中断返回。为了实现抢占式的Linux内核，必须对中断的处理过程进行修改。其要点是在中断返回进行抢占性判断时，如果进程在内核态下运行，还必须要判断是否可以对内核抢占，即判断进程抢占计数器的值是否为0。修改后的中断处理流程如图1所示。

图1 修改后的中断处理流程

3.2 优先级的确定

每次内核抢占时，从就绪进程中选出优先级最高的进程进行调度。考虑到EDF算法采用动态优先级，尽管CPU利用率高，但会增大系统开销，而且嵌入式系统资源又有限，因此这里以任务的截止期限作为任务调度的首选指标，当两个任务的截止期限在允许的范围内时，根据任务的静态优先级来决定要运行的任务，在一定程度上增强了算法的可控性，保证实时任务得到确定的响应时间。确定任务的静态优先级，主要依据以下参数。

1）任务紧迫程度：根据任务的紧急程度，人为安排任务的优先级。任务越紧急，静态优先级越高；

2）任务周期：任务周期越短，静态优先级越高；3）执行时间：执行时间越短 ，静态优先级越高。将以上三个参数的和作为静态优先级，如果任务的静态优先级相同则放在同一个就绪队列的队首，同一就绪队列中的任务被分时调度，这样可以保证在下次调度发生时被优先调度。

3.3 快速查找将调度实时进程的方法

在抢占式内核中，调度发生前，如何快速找到优先级最高的就绪实时任务是内核所要解决的一个首要问题。目前发布的Linux内核都是把实时进程看作活动进程，放在就绪队列中,按先进先出策略进行调度。这种方法没有考虑实时进程的紧迫性,很有可能延误实时进程,从而使嵌入式系统出现严重故障。本文在查表法及文献[7]的基础上，给出了快速查找将调度实时进程的方法。

在本调度策略中优先级由3.2部分介绍的方法确定，一个优先级对应着一个任务队列，不同的任务可以具有相同的优先级，但必需具有唯一的任务ID号。应用查表法首先要解决的问题是建立查找表，考虑到目前发布的Linux内核中实时优先权的范围是从1到99及内核实时功能扩充的需要，查找表可以看作一个预先设计好的常量数组ST[]，数组有65536个元素,从ST[0]到ST[65535]，本策略使用前8192个元素，各个元素的值通过计算得到。这样每次可对一个13位数进行查表，确定最高优先级任务所在位置。ST[]表的设计方法为首先把数组下标用16位二进制数来表示(最低位为第0位,最高位为第15位)，再看为1的最低位在第几位，然后把该值填入到数组下标所指定的元素中。例如ST[80]，其下标为80，转换成二进制为01010000，为1的最低位在第1位，所以ST[80]=4。系统最多可支持128个优先级，把这128个优先级分为16组，每组8个，通过两次查表即可获得当前表中的最高优先级的任务。用RRG中的位来指示任务的优先级组，RRG的定义为 INT16U RRG(INT16U为无符号的16位整数)。数组RRPT[]用来指示优先级，RRPT[]的定义为INT8U RRPT[8] (INT8U为无符号的8位整数)。RRPT[]里的元素只要不为0则RRG对应位置1。

调度任务时，先依据RRG的值与ST[]表中的下标对应，该值记为k，ST[k]即是找到最高任务优先级所在的组，假设查到的值为i，再用RRPT[i]值查表找到任务所在组里的位置，假设查到的值为j，即可得到最高优先级为i×16+j，该优先级对应的就绪队列中的第一任务就是将被调度的任务。

4 实时性能测试

常用的嵌入式实时操作系统性能测试方法包括：Rhealstone方法、进程分配延迟时间（PDLT）法和三维表示法[8]，本文使用PDLT法测试改进内核的性能。进程分派延迟时间定义为从中断的产生到由中断激活的实时任务开始执行之间的时间间隔，这段间隔由几部分时间组成，如图2所示。这里的进程分配延迟时间可以理解为任务响应时间。

图2 进程分配时间延迟

4.1 测试环境

硬件平台CPU为3G，内存为512MB，软件环境为redhat9.0，采用裁减的Linux2.6内核以及基于裁减的Linux2.6进行本文所述调度策略修改后的内核，测试方法为PDLT方法，测试工具为Linux Trace ToolKit。

4.2 测试结果

通过LTT对裁减的Linux（嵌入式Linux）和基于裁减Linux按本文所述策略修改后的内核进行跟踪测试，对比它们的任务响应时间，前者为32ms，后者为407μs。测试结果表明，修改后的内核在任务响应方面有所改进，较好的解决了嵌入式Linux在实时方面的不足。

5 结论

本文介绍了基本Linux内核的调度策略，针对其缺乏有效的实时任务调度机制和调度算法而导致实时性效差的问题，提出了一种增加Linux内核调度性能的调度算法和调度策略，经测试，修改后的内核在实时调度方面有所提高。

[1] 王长安.一种嵌入式Linux实时实现[J].科学技术与工程，2007(15):3940-3942.

[2] 姚君兰.增强Linux内核实时任务调度性能的研究[J].微计算机信息， 2006(5):42-44.

[3] 洪艳伟,赖娟,杨斌.其于EDF算法的可行性判定及实现[J].计算机技术与发展，2006(11):257-261.

[4] 王海珍,廉佐政.一种实时的嵌入式Linux调度策略[J].科学技术与工程，2009(14):4197-4201.

[5] 徐宗元.操作系统[M]. 北京：高等教育出版社,2005.

[6] 杨黎,杨琳芳.嵌入式Linux的实时性分析与研究[J].仪表技术，2009(7):58-61.

[7] 王新政,程小辉.实时操作系统任务调度策略策略的研究与设计[J].微计算机信息，2007(23):57-58.

[8] 李庆诚,顾健.嵌入式实时操作系统性能测试方法研究[J].单片机与嵌入式系统应用，2005(8):19-21.