王亚军 中国人民武装警察部队学院

Linux内核优先级倒转分析

王亚军 中国人民武装警察部队学院

Linux对于访问同一内核临界区的多个进程进行同步的有效手段是内核信号量机制。解决Linux内核信号量操作中存在的优先级倒转问题，是将Linux运用于实时系统的重要手段。文中在分析Linux内核信号量操作源代码的基础上，结合嵌入式应用深入分析其中存在的优先级倒转问题。

信号量 优先级倒转 嵌入式系统 等待队列 实时性

1 引言

Linux内核允许多个进程并发执行，从而极大限度地利用了CPU资源。但是为了避免多个进程同时进入临界区，Linux内核采取了严格的同步机制，信号量就是其中之一。如果一个进程试图获得一个已经被占用的信号量，该进程就会被推进一个等待队列进入“睡眠”状态，从而释放处理器，使处理器可以执行其它进程的代码。当持有信号量的进程释放信号量以后，在等待队列中睡眠的进程将被唤醒，并再次试图获得该信号量以进入临界区。

2 Linux内核优先级倒转分析

在Linux-2.6.10内核中，当有多个进程等待进入一个临界区时，当前进程略有优势，然后就是“先来先进”，即先链入等待队列的进程先进入临界区，而进程的优先级并没有起作用。也就是说，在这个等待队列中，如果优先级较低的进程排在前面，而优先级较高的进程排在后面，那么优先级较高的进程就只能等待。Linux内核实现了POSIX.4关于“实时进程”调度的要求，支持执行SCHED_FIFO、SCHED_RR和SCHED_OTHER三种不同的调度政策。适用于前两种政策的进程称为实时进程，而适用于SCHED_OTHER的则为面向分时应用的普通进程。由于实时进程有较高的实时性要求，所以要将Linux内核用于实时要求较高的嵌入式应用，就应该对等待进入临界区的进程链表进行优化，减少实时进程的等待时间。

从Linux-2.6.10内核代码中还可以看出，如果一个优先级很低的进程A已经进入某个临界区，那么当另一个优先级很高的进程B也要进入该临界区时，由于互斥信号量机制的阻拦而只能睡眠等待。由于互斥信号量所保护的临界区内允许进程调度，已经进入某个临界区的那个优先级很低的进程A一旦受阻进入睡眠，再被唤醒时就很难得到机会运行，因为系统中所有优先级比A高但比B低的进程都有可能挤在A的前面得到运行。而进程B尽管优先级很高，却反而只能等待这些进程都交出运行权，然后才能让正在占用临界区的进程A完成其操作而退出临界区。为了将Linux内核用于实时要求较高的嵌入式应用，也需要通过修改进程优先级的方法来解决优先级倒转问题。

3 Linux内核优先级倒转解决方法

Linux-2.6.10内核调度进程的主要依据是进程的优先级，但又不是单纯地按优先级调度。普通进程拥有一个初始的优先级，即静态优先级，它从一开始由用户指定后，就不能改变。而调度程序要用到的动态优先级是通过一个关于静态优先级和进程交互性的函数关系计算而来的。而对于实时进程，它们所采用的是实时优先级，内核不为它们计算动态优先级，这能保证给定优先级别的实时进程总能抢占优先级比它低的进程。SCHED_FIFO实现了一种简单的、先入先出的调度算法，它不使用时间片。SCHED_FIFO级的进程会比任何SCHED_OTHER级的进程都先得到调度。一旦一个SCHED_FIFO级的进程处于可执行状态，就会一直运行，直到它自己受阻或显式释放处理器为止。SCHED_RR则是带有时间片SCHED_FIFO，当SCHED_RR级的进程耗尽事先分配给它的时间片以后就不能继续运行了，这是一种实时轮流调度算法。

为了对等待进入临界区的进程链表进行改进，减少实时进程的等待时间，需要修改内核中与此相关的源代码，在将需要等待进入临界区的进程链入到相应的等待链表时，按照进程的优先级将其插入到链表中的适当位置。由于内核中需要在临界区内进行的操作一般都是很短促的，而普通进程又没有较高的实时要求，所以这种改进只对实时进程来进行。当一个普通进程等待进入临界区时，只是按照内核中原来的安排，将其简单地链入等待队列的尾部。而对于实时进程，则与进程调度的思想相一致，按照实时优先级从高到低的顺序，将其插入到等待进入临界区的进程链表之中。对于优先级相同的实时进程，仍然按照内核中原来的安排，即先链入等待队列的实时进程先进入临界区。为此，需要对内核中的相关源代码进行修改，将等待队列分成两个小的等待队列。

4 结语

综上所述，在Linux内核中，信号量及其操作是内核对访问共享资源的多个进程进行同步的关键，对系统的性能具有重要影响。当把linux内核应用于嵌入式系统时，由于嵌入式系统通常具有实时性要求，应该对信号量操作中存在的优先级倒转情况进行改进，以提高内核的实时性，这对于将Linux内核应用于具有实时性要求的嵌入式系统时是有意义的。

[1]毛德操,胡希明.Linux内核源代码情景分析[M].杭州:浙江大学出版社，2002.

[2]毛德操,胡希明.嵌入式系统[M].杭州:浙江大学出版社，2003.[3]彭晓明、王强编著，《Lniux核心源代码分析》,北京,人民邮电出版社，2002

河北省科研基金项目支持(HBSZKT-2014143)。

王亚军，1978年生，男，汉族，籍贯：黑龙江绥化市，单位：中国人民武装警察部队学院，副教授，硕士，研究方向：Linux操作系统。