一种改进的进程调度算法在机顶盒上的设计与实现

王铭伟, 吕华

（重庆邮电大学 通信与信息系统学院 重庆 400065）

0 引言

目前，大多机顶盒系统使用的Linux2.6内核中采用的是0（1）调度算法，此算法相对于Linux2.4核心的0（n）算法有了很大的改进。但由于在2.6内核中，仍然使用源自2.4核心的SCHED_FIFO（先入先出）和SCHED_RR（时间片轮转）作为对实时线程的调用的主要策略，对实时进程的调用效率上没有大的提升。在0（1）调度算法中，由于任务的优先级及抢占阈值都采用的是固定的整数[3]，并且等待任务的空闲时间遵循严格递减的规律[4]，造成了在任务执行过程中无法动态地分配CPU资源导致的实时性能降低。基于以上原因许多嵌入式系统中的Linux都引入了最小裕度算法，以期能达到动态分配优先级进而优化Linux2.6核心的实时调度性能的目的。不过，最小裕度算法也存在问题，若有两个优先级相近的进程同时运行，会出现两个线程间的频繁切换现象[5]。针对这一最小裕度算法的缺点，本文通过对其增加二级优先级进行了改进，使之能在一定程度下减小频繁切换造成的系统资源浪费[6]，并通过将之运用到机顶盒产品中，证明了该算法对于增强机顶盒系统实时性能方面的有效性。

1 最小裕度算法的改进与分析

1.1 最小裕度算法的改进

作为实时系统中较为常用的动态优先级调度算法，最小裕度优先(Least Slack First)调度算法是对最早截止期优先EDF算法的改进，根据任务所剩余的裕度（即剩余时间）的多少来分配优先级。裕度越少，任务就越紧急，就为之分配更高的优先级，以此保证紧急任务能够得到优先执行。但是由于等待任务的裕度是严格随时间递减的，在系统执行过程中，等待执行的任务可能会由于紧急程度的提高而又抢占当前执行的任务，从而造成两个任务之间的频繁切换（又称为颠簸），使系统性能下降。通过引入抢占阈值的调度策略，控制不必要的任务抢占，可降低由于任务抢占引起的系统开销和过多的上下文切换。需要注意的是过于复杂的调度算法也会消耗太多的系统资源，反而会降低系统的调度性能。在调度算法的开销与系统的调度性能之间需要找到一个平衡点，为了找到这个平衡点，需要找到最合适的优先级和抢占阈值。

设T时刻，X为任务剩余部分的执行时间，截止期限(绝对)为G，则该任务的空闲时间(裕度)S定义如下：

在裕度相同时，G（截止期限）靠前的任务的优先级高；当S≥0时任务才会被调度，否则进入下一个周期。这种算法存在一个问题：当系统中有1个以上(假设有3个，分别为T1、T2、T3)最小裕度相近或相等的任务，且系统中没有比这3个任务裕度更小的任务了。由于正在执行的任务裕度不变(假设为T1)，这时在等待队列上等待的任务(T2、T3)的裕度随着时间的推移而减小，从而使它们的优先级动态地发生变化。随着调度的执行，T2（或T3）就会因裕度变得足够小而抢占CPU。经过任务切换后，同样的道理，在T2（T3）执行一段时间后，T3（或T2）也会抢占CPU，然后T1因裕度减小也会加入抢占的队伍中，如此反复进行。这种频繁的任务切换即称为颠簸现象。如图1就是3个任务下的颠簸现象。可见其中在完成这3个任务中，总共进行了多达10次切换。

图1 LSF算法的颠簸现象

为了减少颠簸现象造成的系统资源浪费，本文对LSF算法进行了如下改进：每个任务除了按裕度分配优先级外，还有一个抢占阈值，从而构成一个双优先级系统。一旦任务得到CPU，其优先级就提升到其抢占阈值的水平，直到它的执行结束或被其他任务抢占后再回复到其原先的优先级。设定任务的优先级值越大，其优先级越高，任务的抢占阈值大于其优先级值。改进后的schedule（）函数的流程图如图2所示。

通过引入抢占阈值，可以有效地减少颠簸现象的发生。现在还是假设有3个任务，分别为T1、T2、T3，它们的最小裕度相近或相等。T1的裕度(优先级值)和抢占阈值分别为S1、P1，T2的裕度和抢占阈值S2、P2，T3的裕度和抢占阈值S3、P3。T1开始执行，T2、T3则等待。随着时间的推移，S2、S3不断增大，S1保持不变。当S2（或S3）>S1时，并不进行抢占，而是让T1继续运行。直到S2（或S3）>P1时，T2（或T3）才可以抢占T1。于是，在前述3个任务的情况下，改进后的调度算法就减少了颠簸现象。3个任务下的模拟情况如图3所示。可以清晰地看到，3个任务完成总共跳转两次，用时也大大减少。

图2 改进后的schedule流程图

图3 LSF改进算法

1.2 抢占阈值的确定

这种改进的LSF算法的关键在于抢占阈值的确定,它直接影响到任务截止期的错失率,也影响到任务切换的频率,还影响到CPU的有效利用率。根据前面关于优先值越大,任务的优先级就越高的假设,任务的抢占阈值需要大于或等于（h≥p）相应的优先级。如果 h≥≥pmax,则调度策略变为非抢占模型,因此在新LSF算法中,抢占阈值的取值范围为 p≤≤h≤≤pmax；在任务空闲时间不为0时,排除完全抢占和非抢占模式,则抢占阈值的取值范围为p＜h＜pmax。由于任务的优先级p是随其空闲时间变化而变化的,因此,任务的抢占阈值不能事先确定(或者无条件预知),需要随着任务优先级值的变化而变化,因此,现有的关于抢占阈值的取值方法在这里都是不可行的。我们这里需要根据抢占阈值的取值范围以及优先级值确定阈值的计算公式,本文采用以下方法确定抢占阈值。

当pmax=0时, h = c e i l ( ⋅ p ) ,其中比例系数0＜ ＜1为给定常数,函数ceil( x)表示取大于x的最小的整数.

此种方法较简单，且能达到总体性能优化的目的，避免了过于复杂的阈值计算。在确保改进可操作性与提高系统效能的角度来说是非常有利的。

2 改进后的最小裕度算法在机顶盒中的实现

根据上面的设计，本文对Linux 2.6算法在原来算法的基础之上改进，在下面两个函数中进行了修改。

首先，在schduler_tick函数中，需要更新当前线程的剩余执行时间，而后更新实时线程的裕度值与实时线程优先权范围的部分，遍历完成后需加回裕度值。具体代码如下：

以上是在schduler_tick()函数中加入更新实时进程的裕度值与最低限度值，另外还有一些进程状态信息，例如，裕度值、时间片、是否可以抢占等等，在更新这些状态后，将检测是否允许抢占，然后发生抢占，并检测当前进程的时间片是否就位，并且确定截止点是否就位，如上述内容到了，就剔除现进程，接着运行一个进程。这些交由schedule函数判断执行。

3 验证与负面影响分析

3.1 调试环境

本方案的主要调试、开发等功能均是在宿主机上完成的（Linux环境PC或安装了虚拟机的Windows PC）。开发和编译时使用宿主机上的编译工具来生成目标板（机顶盒实验板）上的上运行的二进制代码，然后通过打包，并将打好的升级包通过网线传输至目标板中烧包。在烧包成功后重启即可对改进的系统进行验证。验证中，通过对串口的打印信息进行监控和调试，也可通过串口通信程序输入一些命令以测试我们的调度改进。调试环境如图4所示。

图4 调试环境

3.2 验证结果及分析

在完成了代码的整改后，分别对原版的最小裕度2.6.16内核与改进了最小裕度优先级算法的内核进行了测试。测试中通过模拟两个实时线程进入竞态，并通过在schedule（）中添加调用打印函数，确定调用中的切换时间，线程运行时间等重要信息。具体实验中使用了两种线程，一种的CPU资源消耗较少，在原版的最小裕度内核中只通过单优先级判断容易造成线程间切换；另一种线程的CPU资源消耗较多，在原版的最小裕度内核中会出现多次切换的情况。通过两种类型线程的不同组合，可以模拟出3种情况。

(1) 两个或多个需要CPU资源较少的线程发生竞态的情况。

(2) 两个需要CPU资源较多的线程发生竞态的情况。

(3) 一个需要CPU资源较多的与一个需要CPU资源较少的线程发生竟态的情况。

经过3次实验后得到了如表1所示的数据。

表1 实验数据

通过对上面数据的分析，可以得出如下结果：

(1) 在两个或多个需要CPU资源较少的线程发生竞态的情况下，系统在完成两个占用CPU资源并不多的两个线程间仍然出现了一次线程的切换，在总的时间上相对于只作出了一次切换的改进后系统处于劣势，较改进后的系统，在总时间上多了近10%。

(2) 两个需要CPU资源较多的线程发生竞态的情况下，由于采取两重有限级判断的策略，改进后的系统中切换次数较未改进之前有了较大的减少，在运行的总时间上站有很大的优势，较改进前的系统，在总时间上提高了近10%的效率。

(3) 一个需要CPU资源较多的与一个需要CPU资源较少的线程发生竟态的情况下，由于此情况下在所占资源较少的线程实行中只作出了一次多余的切换，在整个运行过程中，一次切换所占的时间比例很小，所以改进后的核心在此与原系统没有太大出入。

通过以上的实验，得到以下结论。通过在线程调度优先级的计算中引入最小裕度算法，动态地获得线程的优先级，使得Linux 2.6的实时性得到了一定的提高，特别是在线程所需CPU资源较多和多线程的情况下对系统的提升较大，在这两种情况下，平均能得到10%左右的性能提升。

3.3 改进的负面影响

在使用了动态的优先级计算后，每次时钟中断都必须对实时任务的裕度值进行计算，而每次计算都必须遍历整个实时任务链表。这在应用中必然加重对系统的负担，但是由于机顶盒系统的实时线程并发量并不大，实时任务链表相对较小，此弊端并不会对系统造成较大的影响。相对于改进后对系统的提升来说，是可以接受的。

[1] Liu C L，Lay,J W.Scheduling algorithms for multiprograrrmaing in a hard real-time environment[J]. The Association for Computing Machinery，1973，20(1)：46-61.

[2] Hildebrandt J，Golatowski F，Timmermann D. Scheduling Coprocessor for Enhanced Least-Laxity-First Scheduling in Hard Real-Time Systems // Proc.of the llth Euromicro Conf.011. Real-Time Systems[M].Los Alamitos：IEEE Computer Society Press，2002：208-215.

[3] Jackson LE, Rouskas GN. Deterministic preemptive scheduling of real-time tasks[J]. Computer, 2002,35(1):72-79.

[4] Terrasa A，Garcia-Fomes A，Botti VJ.Flexible Real—Time Linux：A FIexible Hard Real-Time Environment[J].Real-Time Systems，2004，22(2)：151-173.

[5] 金宏，王强，王宏安，等.基于动态抢占阈值的实时调度[J].计算机研究与发展，2004(3)：393-398.

[6] 许占文，李歆. Linux2. 6 内核的实时调度的研究与改进[J] . 沈阳工业大学学报,2006 (8) :4382441.

[7] 关斌斌，王勇 基于EDF算法的嵌入式Linux实时调度策略[J]. 电子测量，2010（3）：27-31.

[8] 王刚，余兆Linux 2.6内核进程调度分析[J].计算机应用与软件，2007，24(9)：162-164.