Linux实时性能优化算法分析与研究

李 梅

（西安欧亚学院 陕西 西安 710065）

Linux是一源代码公开、功能强大、内核模块化，裁剪方便。Linux支持多种体系结构，适合在嵌入式领域应用。作为嵌入式产品的操作系统平台，实时性是一个很重要的目标。但随着Linux逐渐应用到嵌入式领域，其实时性不够强而一直受到批评。文中提出了一种提高Linux2.6实时性能的O(1)算法。

1 实时系统基本概念

实时操作系统（RealTime Operation System，RTOS）是指能够接受外部数据发生并以足够快的速度进行处理，其处理的结果又能在规定的时间之内来控制生产过程或对处理系统做出快速响应，并控制所有时间协调运行的操作系统[1]。在实时操作系统中，进程的执行结果的正确与否不仅与逻辑运算或数学计算结果的正确性相关，还与进程运行结束得出结果的时间有关，也就是说，如果一个进程的运算结果是正确的，但是由于它完成时间已经超出了系统给定的最后期限，在实时系统中，这个结果就是毫无意义的。所以RTOS的核心是必须在规定的时间内完成系统的指定操作，否则将引起系统性能急剧下降甚至系统崩溃[2]。实时操作系统有“软实时”和“硬实时”之分[3]。软实时需要系统尽可能快地完成操作，系统整体吞吐量达或者响应时间快，但特殊的任务在规定时间内不一定完成；硬实时则要求系统务必在规定时间内对时间进行处理。实时操作系统性能优劣可以从调度策略、内存管理、任务切换时间和中断禁止时间等多方面衡量[4-5]。

2 Linux用于实时性操作系统的缺点

1)Linux中有大量不可抢占的区域

在Linux2.6中,内核己经可以抢占,因而实时性得到了加强"但是内核中仍有大量的不可抢占区域,如由自旋锁(SPinlock)保护的临界区。

2)时钟粒度粗糙

Linux2.6内核虽然把时钟频率提高到1 000 赫兹，定时精度达到了1 ms，但远不能满足实时系统要求的微秒级定时精度，如数控系统要求50μs 的定时精度。

3)关闭中断

系统调用和中断服务程序中，为了保护临界区资源,Linux会长时间关闭中断"有些系统调用和中断服务程序的时间还很长,这样会加大中断延迟时间。

4)缺乏有效的实时任务调度机制和调度算法

Linux系统是按照分时系统的目标设计的,以达到系统较好的平均性能，强调平衡各进程之间的响应时间来保证公平的CPU时间占用。通常采用固定时间片的分时调度算法，内核不能抢占，而实时系统的行为更多的取决于复杂的不可预知的情况。这些原则不能满足实时系统短的响应时间和确定的执行行为的要求。

5)优先级反转的问题

当一个低优先级的进程占用了某种资源，导致同样需要这个资源的高级进程无法运行，并且此时有一个优先级在他们之间的就绪进程获得了CPU 的控制权，这样就使得高级别的任务需要等待比他优先级别低的任务，这种现象就叫做优先级反转。在Linux中，由于资源是不可抢占的，并且不支持优先级继承等策略，所以优先级反转现象可能会发生，这影响了系统的实时性能。

3 Linux 2.6O(1)调度算法的设计

在Linux2.6开始以后，其进程调度程序被重新改写，以适应嵌入式领域的发展。2.6版本的Linux内核使用了新的调度器算法，称为O(1)算法，它在高负载的情况下执行得相当出色，并且当有很多处理器时也可以很好地扩展。O(n)表示算法时间复杂度，括号里的数字代表最坏情况下算法效率的上限取决于算法涉及到的元素的个数，O(1)说明是一个常数，在这种情况下，每次调度的效率是一样的，与涉及的元素的多少没有关系，O(n)表示算法效率取决于算法涉及元素的个数。

3.1 Linux2.6 新的数据结构

Linux 2.4 内核中，就绪进程队列是一个全局的双向链表，整个队列由一个读／写自旋锁保护着，调度器对它的所有操作都会因全局自旋锁而导致系统各个处理机之间相互等待，使得就绪队列成为一个明显的瓶颈。而在Linux 2.6 中，就绪队列被定义为一个复杂得多的数据结构 runqueue，并且每个 CPU 都将维护一个自己的就绪队列，这将大大减小竞争。Linux2.6 的O(1)算法就是以这个数据结构为基础进行调度的[6-7]。

Linux2.6为每个CPU定义了一个runqueue.。下面给出runqueue中关键的部分

此结构中最关键的是active和expired指针变量。其中active指针指向时间片没用完、当前可被调度的就绪进程，即活跃进程的优先级数组，而expired指向时间片已用完的就绪进程，即过期进程的优先级数组。当一个进程时间片用完并且没有被立刻激活时，只需重新计算时间片，并且将它移入expired指向的优先级数组即可。在 active指向的数组为空时，只要将两个指针交换，由于expired指向的数组中的时间片都已计算好，只要放到active的位置立刻可以执行，此时的 active指向的数组则恰好充当新的expired数组。

active和expired两者结构相同，均是prio_array 类型，prio_array其定义如下：

typedef struct

{

int nr_active;

unsigned long bitmap[BITMAP_SIZE];

struct list_head queue[MAX_PRIOR];

}priorarray;

比如说，在教学“以此函数的图像和性质”时，教师要做好启发的准备，要让学生去走进实际知识中。教师可以为学生准备这样的一个题目，x=（n-1）y-2n是x关于y的一次函数，你可以添加一个适当的条件求出它的解析式吗？在提问后，教师可以先告诉学生，这个答案是不限制一个的，你们可以尝试多求出几个答案。学生在分析这道题中，其思维可以得到有效的释放，由于答案不限制一项，就算是某些学生算的比较快，其他学生也都能投入到计算中。同时随着学生们纷纷说出自己的答案，课堂的导向也从教师转变为学生，学生主体性得到有效的展现，不仅活跃了课堂的氛围，学生的思维也得到了有效的发散。

其中，nr_active表示当前中active中的进程数量；queue是一个list_head类型的数组；数组的每个元素都指向具有某一类优先级的进程。因为在每个进程控制块中，都有一个run_list属性，它是list_head类型数组，queue中的元素与具有某一类优先级的进程，以及具有同一类优先级的进程，都是通过run_list属性链接起来的，比如说：queue[138]表示优先级为139的哪一类进程，这类进程通过各自进程控制中的runl_ist属性链接在一起。当某个进程进入任务队列时，通过一个名为list_add_tail的函数，将此进程挂到queue[R]所指向的队列中。当要得到某个具体进程的进程控制块时，先是通过queue[R]找到具有这类优先级的进程链表，然后得到某个具体进程的run_list属性，再由函数list_entry通过run_list返回整个进程控制块的结构。Bitmap是位图数组，该数组中的每个元素都表示优先级在某一范围内的进程。如：bitmap[0]对应的是优先级范围为0～31的那些进程，bitmap[1]对应的是优先级范围在32～63的那些进程，以此类推。正是因为在位图数组与就绪任务队列建立了一种映射关系，才使得Linux在高负载情况下，其进程调度的效率也是非常高的。

3.2 Linux2.6 O(1)调度程序的构成

整个调度程序的实现由两部分组成：将进程加入到就绪队列和检索优先级最高的进程。

1)将进程加入到就绪队列

①用enqueue_task（）将新进程加入到queue[n]所指向的链表中，其中n表示某类优先级。

②调用函数 _set_bit计算出该进程的优先级值，并将该进程优先级值与该进程所对应的bitmap中的值相加。

2)检索优先级最高的进程

①获取当前处理器运行的任务队列

rq=this_rq();

array=rq-＞active;

②调用函数sched_find_first_bit()对任务队列中的进程进行检索。并返回具有最高优先级的那个进程在renqueue中的位置。idx = sched_find_first_bit(array-＞bitmap);

sched_find_first_bit()函数定义如下：

static inline int sched_find_first_bit(const unsigned long *arr)

{

if(unlikely(array[0]))

return _ffs(array[0]);

if(unlikely(array[1]))

return _ffs(array[1]+32);

if(unlikely(arr[2]))

return _ffs(array[2]+64);

if(unlikely(array[3]))

return _ffs(array[3]+96);

return _ffs(array[4]+128);

}

其中参数array为位图数组，array[0]表示优先级为0～31的那类进程。函数_ffs()作用是根据数组array中各元素值找出优先级最高的进程。

③调用函数list_entry得到最高优先级进程的进程控制块。

queue = array-＞queue + idx;

next = list_entry(queue-＞next, task_t, run_list);

④将此进程的next交给处理器执行

4 结束语

在 2.4 版的内核里，查找优先级最高的就绪进程的过程是在调度器 schedule() 中进行的，每一次调度都要进行一次，这种查找过程与当前就绪进程的个数相关，因此，查找所耗费的时间是 O(n) 级的，可见调度动作的执行时间和当前系统负载相关，这与嵌入式系统实时性的要求相违背。

为了加速搜索就绪进程链表中优先级最高的进程，2.6 版本用一个位图数组来对应每一个优先级链表，如果该优先级链表非空，则对应位为 1，否则为 0。而且还构造了sched_find_first_bit() 函数来执行这一搜索操作，快速定位第一个非空的就绪进程链表。将检索优先级最高的进程过程分解为n步，每一步所耗费的时间都是 O(1) 量级的。

最高优先级检索算法是整个Linux2.6进程调度算法的重要组成部分，它的时间复杂度为O（1），这为整个Linux2.6进程调度算法的时间复杂度为O(1)做出了很大贡献，从而提高了Linux2.6作为内核的嵌入式操作系统的实时响应能力。

[1] 龙飞.嵌入式Linux系统内核实时性研究[D].沈阳:沈阳工业大学,2012.

[2] Williams C.Linux Scheduler Lateney[C]//RedHatIne,March 2002.

[3] 代玲莉.Linux内核分析与实例应用[M].北京:国防工业出版社,2002.

[4] 毛佳.实时系统调度算法的优化设计[J].计算机工程与应用，2003,39(15):112-115.MAO Jia.Optimization design of real-time scheduling algorithm[J].Computer Engineering and Applications,2003,39(15):112-115.

[5] 刘磊,Linux内核进程调度算法的分析、研究与改进[D].黑龙江:黑龙江大学,2011.

[6] 张永选，姚远耀.Linux2.6内核O(1)调度算法剖析[J].韶关学院学报:自然科学版,2009,30(6):5-9.ZHANG Yong-xuan,YAO Yuan-yao.Linux2.6 The kernel O(1)scheduling algorithm[J].Journal of Shaoguan University:Natural Science,2009,30(6):5-9.

[7] 张同光.Linux2.6内核分析-对进程调度机制的分析[J].长春工业大学学报:自然科学版,2006,27(4):333-337.ZHANH Tong-guang.Linux2.6 Kernel analysis- Analysis of the process of scheduling mechanism[J].Journal of Changchun University of Technology:Natural Science,2006,27(4):333-337.