基于Linux 2.6进程调度系统的实时性研究

岳笑含, 刘艳秋

(沈阳工业大学,辽宁沈阳110023)

由于Linux是开源的操作系统,它拥有众多的开发和维护者,并且将其运用在各种不同的领域里,发挥了极好的作用.并且Linux的速度或效率都表现得非常好,只是在一些情况下,这样的速度还不能满足某些需求.有时需要的是在特定的容差范围内确定性地满足调度期限的能力.故此,本文将从Linux 2.6调度器的实时性分析入手,针对EDF实时调度算法进行讨论,并对内核进行相应的改进,以便更加适合实时进程(任务)的执行.

1 Linux 2.6进程调度系统的实时性分析

Linux 2.6加入了内核抢占并实现了调度算法时间复杂度为O(1),Linux 2.6的实时性得到了加强,对于O(1)调度算法和内核抢占,有很多资料对其进行了详细的阐述[1],本节只介绍Linux 2.6优先级的计算和Linux 2.6的实时调度策略.

1.1 进程的优先级计算

由于Linux 2.6调度器调度进程是依据优先级的大小(prio值),所以优先级的计算是人们所关心的,进程优先级的计算分为普通进程优先级的计算和实时进程优先级的计算.

1.1.1 非实时进程优先级的计算

非实时优先级的计算,一般通过2个函数来实现:effective_prio()和recalc_task_prio()[2],首先介绍recalc_task_prio()函数.

recalc_task_prio()函数的调用时机一般是当执行schedule()或active_task()系统调用,并且主要用于schedule()系统调用时,用于计算非实时进程的优先级.它首先通过计算并对当前进程(主要是对交互式进程)的平均睡眠时间做相应的调整;然后调用effective_prio()函数.

effective_prio()函数并不是只被 recalc_ task_prio()所调用,它还主要被调用在scheduler_tick()时钟中断程序、sched_fork()、wake_ up_new_task()等函数里.它用于计算进程的动态优先级(prio),同时也包括实时进程的动态优先级.对于非实时进程的计算它是通过该进程的平均睡眠时间(sleep_avg)和静态优先级(static_ prio等同于nice)2个因素来确定的,在i386结构体系中,其计算公式如下:(其中sleep_avg值类型为Jiffies)

prio=max(100,min((p-＞static_prio-(sleep_avg/10+5)),139))

其中(sleep_avg/10-5)计算出来的值作为对该进程的奖励/惩罚值,范围在(-5,+5)之间,那么就可以看出,当一个进程睡眠时间比较长的话,它就会得到+5的奖励,如果没有睡眠的话,那么它将得到-5的惩罚.

1.1.2 实时进程优先级的计算

实时进程优先级的计算,是通过effective_ prio()函数,但与实时进程的平均睡眠时间以及静态优先级无关,与计算有关的是rt_priority变量.这个变量通过sys_sched_setparam()来设置和改变,并且该值不会动态地修改,即内核不为实时进程计算动态优先级,那么就使得实时进程的调度单纯依赖于一个固定的值.其优先级的计算公式如下:

prio=MAX_RT_PRIO-1-p-＞rt_priority其中,MAX_RT_PRIO=100.

由此可见,rt_priority值越大,实时进程的优先级越高,该值的取值范围是0～99.

对于实时进程,固定的优先级表示了该进程的关键程度,越关键的实时进程,它对系统的贡献作用也越大,但是仅仅考虑任务的关键性对于实时进程是不够的,实时进程的最大特点就是具有截止期的特征.

1.2 Linux 2.6的实时调度策略

Linux 2.6的调度策略比较简单,分为4种: NORMAL、BA TCH、FIFO和RR.本节只讨论FIFO和RR两种实时调度策略,这两种调度策略为软实时调度策略[3].

1.2.1 FIFO调度策略

FIFO是先进先出的一种调度算法.它实现了一种简单的、先入先出的调度算法,它不使用时间片.FIFO级的进程会比任何NORMAL级的进程都先得到调度,一旦一个FIFO级进程处于可执行状态,就会一直执行,直道它自己受阻塞或显式地释放处理器为止;它不基于时间片,可以一直执行下去.只有较高优先级的FIFO或RR级进程才能抢占FIFO进程,而NORMAL级进程将不会被调用.

1.2.2 RR调度策略

RR调度策略,与FIFO大体相同,只是RR级的进程在耗尽事先分配给它的时间片后就不能再接着执行了,即RR是带有时间片的FIFO,这是一种实时的轮回调度算法.当RR级进程耗完自己的时间片后,将其插入到同等优先级进程队列的末尾,并与同等优先级进程一起轮流调度,时间片只用来重新调度同一优先级的进程.

对于实时进程优先级的计算方法,体现的是“静态优先级”,即将任务的关键性作为衡量实时进程优先级标准的唯一途径.这对于实时调度策略是比较简单和片面的,容易导致具有同样关键性进程的截止期不被满足或系统资源得不到充分利用而夭折.针对这些缺点,下面将引入EDF调度算法对Linux 2.6内核进行有针对性的改进和实施.

2 EDF调度策略在Linux 2.6上的改进

EDF调度算法,是最著名的基于截止期优先的实时调度算法,它按照任务的相对截止期进行由小到大的排序[4].

2.1 EDF调度策略在Linux 2.6上的实现方案

2.1.1 基于EDF的改进原理

EDF算法是截止时间驱动调度算法,是一种动态的调度算法.EDF指在调度时,进程的优先级根据进程的截止时间动态分配.截止时间越短,优先级越高,EDF调度算法是在进程执行期间,根据它的启动时间改变优先级;并以最后期限的顺序指定优先级.优先级最高的进程是距离最后期限最近的进程,优先级最低的进程是距离最后期限最远的进程.并且,EDF调度算法已被证明是动态最优调度,而且是充要条件,处理器的利用率最大可达 100%.将 EDF引入到Linux调度器中,可以采取如下策略:

①进程的优先级越大,越先得到调度;

②如果优先级相同,那么进程相对截止期越小越先得到调度;

可见,相对截止期在具有同等优先级的进程队列里得到了表现,根据以上原则,可以得到运行队列,如图1所示.

图1 基于EDF的实时进程调度Fig.1 Real-time process schedule based on EDF

2.1.2 基于EDF的算法步骤

具体的算法步骤如下:

(1)确定实时进程所在优先级队列,并按相对截止期的大小在同一优先级队列里进行由小到大的排序;

(2)如果有中断产生,都要重新计算各个队列的相对截止期,并查看是否有实时进程错失截止期,并将错失截止期的进程夭折;

(3)对新到达的任务将其送入到相应的优先级任务队列中,并按相对截止期大小入队;

(4)如果当前没有任务占用CPU,则从等待任务队列中选择优先级等级最高、截止期最早的任务调度执行,如上一节,即是该优先级队列的队首任务;

(5)如果当前有任务 Ti在执行并假设其实时优先等级为rpi,那么:

①如果有更高优先级的任务 Tj存在,即rpj＞rpi,则 Tj抢占 Ti;

②如果没有更高优先等级的任务,但有相同优先等级且相对截止期更小的任务存在,即rpj=rpi,且 dj＜di,则 Tj抢占 Ti;

③如果没有前两种情况发生时,Ti继续执行.

(6)转到步骤2,循环反复直到实验结束.

2.2 Linux 2.6实时调度策略的改进

由于篇幅所限,这一节只给出主要数据结构以及函数的改进.并且值得说明的是,在修改中,增加了EDF调度算法,即:

#define SCHED_EDF 4

2.2.1 数据结构的修改

调度策略由于采用EDF的调度原理,所以必须增加几个由CDF实时进程相关信息组成的队列,以便于优先级的计算.修改在task_struct中,如下:

unsigned long deadline; /＊任务的截止期限 ＊/

unsigned long relate_dl;/＊任务的相对截止期,用截止期减当前时间.＊/

当一个实时进程被创建时,把该进程的相关信息保存在此数据结构中;当该进程结束时,就从该链表中删除.

2.2.2 相关函数的修改

主要修改两个调度函数:scheduler_tick()和enqueue_rt_task().

scheduler_tick()的修改,增加了对实时进程的相对截止期进行更新以及过截止期进程的夭折:

enqueue_rt_task()是添加的一个函数,与enqueue_task()类似,不过在这里的入队方式是按截止期大小排列的.

static void enqueue_rt_task(struct task_

综上所述,首先提出了 EDF在Linux 2.6中的改进原理,并提出了相应的算法步骤,最后落实到了内核代码的修改上面,那么接下来进行试验分析.

3 试验分析

试验分析比较的是各个调度算法平均执行性能.这一指标根据的是截止期满足率,如果系统能够保证实时进程的运行在其截止期内完成,则称该进程在此运行时的截止期限得到满足;试验让几个实时进程有周期地多次运行,并根据每次运行得到的满足次数以及运行次数加以比较,即截止期满足率[5](用百分比表示),以此来对不同实时调度策略的性能加以区分.

试验环境:操作系统 FC6;内核 2.6.20; CPU为Pentium Ⅳ/3.0 GHz,内存512 MB.

测试工具:systemtap0.96.

FIFO、RR和EDF调度策略的比较:

根据试验程序,生成3个实时任务 T1、T2、T3(如表1所示),这里,截止期只对EDF算法有效,对FIFO和RR不起作用.

表1 任务集Table 1 The task sets

3个任务分别运行在FIFO、RR、EDF调度策略下,运行结果如图2所示.

图2 测试结果Fig.2 The experimental results

通过试验表明,基于EDF调度算法的进程调度系统具有较好的实时任务处理能力,能够基本保证任务的截止期错失率.

4 结 语

剖析了Linux 2.6进程优先级的计算,并分析了Linux 2.6实时调度策略在实时性以及实时进程处理上所存在的不足.基于以上两点,引入了基于进程截止期的EDF算法,并进行了详细的说明,更进一步地在Linux 2.6.20内核里进行了相应的修改和完善,最终根据试验结果,证明了该调度策略具备更强的关键性实时进程的调度能力,从而提高了Linux硬实时性以及处理关键性进程的能力.

[1] 栾建海,李众立,黄晓芳.Linux2.6内核分析[J].兵工自动化,2005,24(2):89-90,92.

[2] Rodriguez Claudia Salzberg, Fischer Gordon, Smolski Steven.The Linux Kernel Primer:A Topdown Approach for X86and PowerPC Architectures[M].北京:机械工业出版社,2006:78-79.

[3] Bovet Daniel P,Cesati Marco.Understanding the Linux Kernel[M].陈莉君,等译.北京:中国电力出版社,2007:258-289.

[4] Buttazzo G C.Rate Monotonic vs.EDF:Judgment day[J].J ournal of Real-Time Systems,2005,29 (1):5-26.

[5] Stankovic J A,Spuri M,Ramanritham K,et al. Deadline Scheduling for Real-time Systems:EDF and Related Algorithms[M].Boston:Kluwer Academic Publisher,1991:144-147.