Linux 进程调度分析

Linux 进程调度分析

李方军 ^1,2 蒋波 ¹ 邓豫蜀 ¹

（ 1. 中国工程物理研究院工学院，四川 绵阳 621900 ；

2 . 西南交通大学 信息科学与技术学院，四川 成都 610031 ）

摘 要：进 程调度是多任务操作系统的核心。 Linux 中的每个进程用 task_struct 结构来描述，进程调度的依据是 task_struct 结构中的 policy 、 priority 、 counter 和 rt_priority 。 Linux 根据 policy 将进程划分为实时和普通两类，普通进程采用动态优先调度，实时进程采用基于优先级的 FIFO 调度和多级反馈轮转调度。函数 schedule( ) 是实现进程调度的函数，它通过调用函数 goodness( ) 来选择最值得运行的进程获得 CPU 。 2.6 内核的 O (1) 调度算法及其他快速响应策略更加适合实时环境。

关键词：Linux ；进程；调度；优先级； O (1) 调度算法

Research on the Linux Process Schedule

LI Fang-jun^1,2 JIANG Bo¹ DENG Yu-shu¹

(1. Institute of Technology, China Academy of Engineering Physics, Mianyang 621900;

2. School of Information Science & Technology, Southwest Jiaotong University, ChengDu 610031)

Abstract ： The process schedule is very important to the multi-task operating systems. The Linux scheduling policy is based on four fields, including policy, priority, counter and rt_priority, of a task_struct type structure, which plays the role of a single process descriptor. There are two kinds of processes determined by the field policy, the real-time processes, to which a First-In, First-Out or A Round Robin scheduling is applied, and the non real-time processes, to which a dynamic priority scheduling is applied. The schedule( ) function implements the scheduler by invoking the goodness( ) function to identify the best candidate among all processes in the runqueue list. The O(1) scheduling algorithm and the improvement on response time in the 2.6 kenel can be used in the real-time environment.

Key words ： Linux ； process ； schedule ； priority

0 引言

    Linux 是一个庞大、高效而复杂的操作系统，它的内核包括进程调度、内存管理、进程间通信、虚拟文件系统和网络接口五部分，其中进程调度是核心 ^[1] 。

    进程调度作为操作系统的核心，调度算法的优劣直接关系到系统的运行效率。一个好的调度算法应该考虑很多方面：公平、效率、响应时间、周转时间、吞吐量等 等，但是这些因素之间又是相互矛盾的，最终的取舍应根据系统需要达到的目标而定。 Linux 是一个多进程操作系统，它的进程调度很巧妙地把分配给进程的时间片和进程的优先级结合起来，直接用进程的时间片作为进程优先级的量度。

    近年来， Linux 系统在嵌入式领域得到了广泛的应用，为了满足嵌入式系统的实时性需求往往需要对内核进行改造，许多改造实例是从修改调度程序入手的 ^[2][3] 。因此，充分了解 Linux 进程调度的原理和策略，将有利于我们更加深入理解计算机操作系统中多进程调度的原理，为实时操作系统的开发，特别是嵌入式系统的开发提供理论指导。

1 Linux 进程调度策略

  1.1 Linux 的进程模型

    Linux 中的每个进程由 task_struct 结构来描述。在 Linux 中任务和进程是相同的术语， task_struct 就是指 PCB （进程控制块）。 Linux 将进程状态分为五种： TASK_RUNNING 、 TASK_INTERRUPTIBLE 、 TASK_UNINTERRUPTIBLE 、 TASK_STOPPED 和 TASK_ZOMBILE 。进程的状态随着进程的调度发生改变（图 1 ） ^[4] 。

    TASK_RUNNING （运行）：无论进程是否正在占用 CPU ，只要具备运行条件，都处于该状态。 Linux 把处于该状态的所有 PCB 组织成一个可运行队列 run_queue ，调度程序从这个队列中选择进程运行。事实上， Linux 是将就绪态和运行态合并为了一种状态。

    TASK_INTERRUPTIBLE （可中断阻塞）： Linux 将阻塞态划分成 TASK_INTERRUPTIBLE 、 TASK_UNINTERRUPTIBLE 、 TASK_STOPPED 三种不同的状态。处于 TASK_INTERRUPTIBLE 状态的进程在资源有效时被唤醒，也可以通过信号或定时中断唤醒。

    TASK_UNINTERRUPTIBLE （不可中断阻塞）：另一种阻塞状态，处于该状态的进程只有当资源有效时被唤醒，不能通过信号或定时中断唤醒。

    TASK_STOPPED （暂停）：第三种阻塞状态，处于该状态的进程只能通过其他进程的信号才能唤醒。

    TASK_ZOMBILE （僵死）：进程已结束但尚未消亡，已经释放了大部分资源， PCB 仍未被释放。

  1.2 Linux 进程调度策略分析

    调度程序要在所有处于可运行状态的进程之中选择最值得运行的进程投入运行，选择进程的依据是进程的 task_struct 结构中的 policy 、 priority 、 counter 和 rt_priority 这四项。 policy 是进程的调度策略，用来区分实时进程和普通进程。 priority 是进程的优先级。 counter 是进程剩余的时间片，它的大小完全由 priority 决定。 rt_priority 是实时优先级，这是实时进程所特有的，用于实时进程间的选择。

    首先， Linux 根据 policy 从整体上区分实时进程和普通进程，实时进程和普通进程度调度是不同的，实时进程先于普通进程而运行。然后，对于同一类型的不同进程，采用不同的标准来选择进程。

  （ 1 ）普通进程的调度

    当 policy 的值为 SCHED_OTHER 时，是普通的用户进程，采用动态优先调度，选择进程的依据就是进程 counter 的大小。进程创建时，优先级 priority 被赋一个初值，一般为 0 ～ 70 之间的数字，这个数字同时也是计数器 counter 的初值，就是说进程创建时两者是相等的。字面上看， priority 是“优先级”、 counter 是“计数器”的意思，然而实际上，它们表达的是同一个意思，即进程的“时间片”。 priority 代表分配给该进程的时间片， counter 表示该进程剩余的时间片。在进程运行过程中， counter 不断减少，而 priority 保持不变，以便在 counter 变为 0 的时候（该进程用完了所分配的时间片）对 counter 重新赋值。当一个普通进程的时间片用完以后，并不马上用 priority 对 counter 进行赋值，只有所有处于可运行状态的普通进程的时间片都用完了以后，才用 priority 对 counter 重新赋值，这个普通进程才有了再次被调度的机会。这表明，普通进程在运行过程中， counter 的减小给了其它进程得以运行的机会，直至 counter 减为 0 时才完全放弃对 CPU 的使用，这就相当于优先级在动态变化，所以称之为动态优先级调度。时间片的概念和其他操作系统是一样的， Linux 的时间单位也是“时钟滴答”，只是不同操作系统对一个时钟滴答的定义不同而已， Linux 为 10ms 。进程的时间片就是指多少个时钟滴答，比如，若 priority 为 20 ，则分配给该进程的时间片就为 20 个时钟滴答，也就是 20 × 10ms=200ms 。 Linux 中某个进程的调度策略（ policy ）、优先级（ priority ）等可以作为参数由用户自己决定，具有相当的灵活性。内核创建新进程时分配给进程的时间片缺省为 210ms ，用户可以通过系统调用改变它。

  （ 2 ）实时进程的调度

    对于实时进程， Linux 采用了两种调度策略，即先来先服务调度（ First-In, First-Out ， FIFO ）和时间片轮转调度（ Round Robin ， RR ）。因为实时进程具有一定程度的紧迫性，所以衡量一个实时进程是否应该运行， Linux 采用了一个比较固定的标准。实时进程的 counter 只是用来表示该进程的剩余时间片，并不作为衡量它是否值得运行的标准，这和普通进程是有区别的。

    当 policy 的值为 SCHED_FIFO 时，遵守 POSIX1.b 标准的 FIFO 调度规则。它会一直运行，直到有一个进程因 I/O 阻塞，或者主动释放 CPU ，或者是 CPU 被另一个具有更高 rt_priority 的实时进程抢先。在 Linux 实现中， SCHED_FIFO 进程仍然拥有时间片，只有当时间片用完时它们才被迫释放 CPU 。因此，如同 POSIX1.b 一样，这样的进程就象没有时间片 ( 不是采用分时 ) 一样运行。 Linux 中进程仍然保持对其时间片的记录（不修改 counter ）主要是为了实现的方便，同时避免在调度代码的关键路径上出现条件判断语句

    if （ ! （ current->policy & SCHED_FIFO ）） { ... } ；

    这是一种优化措施，因为大量非 FIFO 进程都需要记录时间片，这种多余的检测只会浪费 CPU 资源。

    当 policy 的值为 SCHED_RR 时，遵守 POSIX1.b 标准的 RR 调度规则。除了时间片有些不同外，这种策略与 SCHED_FIFO 类似。当 SCHED_RR 进程的时间片用完后，就被放到 SCHED_FIFO 和 SCHED_RR 队列的末尾。

    只要系统中有一个实时进程在运行，则任何 SCHED_OTHER 进程都不能在任何 CPU 运行。每个实时进程有一个 rt_priority ，因此，可以按照 rt_priority 在所有 SCHED_RR 进程之间分配 CPU 。其作用与 SCHED_OTHER 进程的 priority 作用一样。只有 root 用户能够用系统调用 sched_setscheduler ，来改变当前进程的类型（ sys_nice ， sys_setpriority ）。

    此外，内核还定义了 SCHED_YIELD ，这并不是一种调度策略，而是截取调度策略的一个附加位。如同前面说明的一样，如果有其他进程需要 CPU ，它就提示调度程序释放 CPU 。特别要注意的就是这甚至会引起实时进程把 CPU 释放给非实时进程。

2 与进程调度相关的函数

  2.1 schedule( ) 函数

    schedule( ) 是 Linux 系统实现进程调度的函数，因此也被称为调度器。它按照不同的调度策略对实时进程和非实时进程进行不同的调度处理。

  schedule( ) 函数的简单流程可以描述如下。

  （ 1 ）检查是否是中断服务程序调用了 schedule( ) （这是不允许的）。若是，则退出 schedule( ) 。

  （ 2 ）若有 half bottom 服务请求，则处理 half bottom 。

  （ 3 ）保存当前 CPU 调度进程的数据区，对运行队列加锁。

  （ 4 ）如果采用轮转法进行调度，则要重新检查一下当前进程的 counter 是否为零。若是则重新分配时间片 (counter) ，并将其挂到队列尾部。

  （ 5 ）检测进程状态，对 need_resched 重新置 0 。

  （ 6 ）搜索运行队列，计算出每一个进程的 goodness 并与当前的 goodness 相比较， goodness 值最高的进程将获取 CPU 。

  （ 7 ）若整个运动队列中的进程的时间片耗尽，重新分配时间片。

    对于非实时进程，运行队列中的进程由于时间片已耗尽，重新赋值后 p->counter=p->priority=20 ；不在运行队列的进程通过 p->counter>>1 将原有时间片减半再加 p->priority ，以此来提高其优先级，使之能够在转入就绪态时有较高的竞争力。但这种竞争力的提高不是无限制的，通过 p->counter>>1 使 p->counter 永远不会超过两倍 p->priority 的值，这样就避免了由于 p->counter 无限增长导致其优先级高于实时进程的情况。

    对于实时进程，由于实时进程不采用 counter 值作为优先级，所有对实时进程的 counter 的赋值操作无关紧要。

时间片分配完成后转向（ 5 ）。

  （ 8 ）切换至新的进程。

    2.2 goodness( ) 函数

    Linux 用函数 goodness( ) 来衡量一个处于可运行状态的进程值得运行的程度。该函数给每个处于可运行状态的进程赋予一个权值（ weight ），调度程序以这个权值作为选择进程的唯一依据。

    goodness( ) 函数计算一个处于可运行状态的进程值得运行的程度。一个任务的 goodness 是以下因素的函数：正在运行的任务、想要运行的任务、当前的 CPU 。 goodness 返回下面两类值中的一个： 1000 以下或者 1000 以上。 1000 或者 1000 以上的值只能赋给“实时”进程，从 0 到 999 的值只能赋给普通进程。实际上，在单处理器（ UP ）情况下，普通进程的 goodness 值只使用这个范围底部的一部分，从 0 到 41 。在 SMP 情况下， SMP 模式会优先照顾等待同一个处理器的进程。不过，不管是 UP 还是 SMP ，实时进程的 goodness 值的范围是从 1001 到 1099 。

    goodness( ) 函数其实是不会返回 -1000 的，也不会返回其他负值。由于 idle 进程的 counter 值为负，所以如果使用 idle 进程作为参数调用 goodness ，就会返回负值，但这是不会发生的。

    goodness( ) 是个简单的函数，但是它是 linux 调度程序不可缺少的部分。运行队列中的每个进程每次执行 schedule 时都要调度它，因此它的执行速度必须很快。

3 内核进程调度机制

    与 2.4 内核相比， 2.6 内核的进程调度有了很大改进，调度算法时间复杂度为 O (1) ，支持抢占式调度，增强了多处理器环境下的支持。 O (1) 调度算法是指调度开销与系统当前负载大小无关。

    每个处理器的就绪队列都有两个优先级数组， active 指针指向的数组包含了有剩余时间片的任务队列， expired 指针指向的数组包含所有已用完时间片的任务队列。当一个进程的时间片耗完，系统会重新计算其时间片，并插入到 expired 队列，当 active 队列中所有进程耗完时间片，只需交换指向 active 和 expired 队列的指针即可，时间片轮转既简单又高效。

    优先级数组是 prio_array 类型的结构体，在 kernel/sched.c 中定义：

struct prio_array{

…

unsigned int nr_active; /* 相应 runqueue 中的进程数 */

unsigned long bitmap[BITMAP_SIZE]; /* 索引位图 */

struct list_head queue[MAX_PRIO]; /* 每个优先级的进程队列， MAX_PRIO 是系统允许的最大优先级数，默认值为 140 ，数值越小优先级越高 */

}

    bitmap[BITMAP_SIZE] 是 queue[MAX__PRIO] 的索引位图， BITMAP_SIZE 默认值为 5 ， bitmap 的每一位都与 queue[i] 相对应。首先，调用函数 sched_find_first_bit() 找到位图中第一个置位的位，该位正好对应于就绪队列中最高有限级进程链表，然后，调度器选择该链表中的第一个进程运行（图 2 ）。函数 sched_find_first_bit() 与就绪队列中的进程数无关，是实现 O (1) 调度算法的关键点之一。

4 结束语

    Linux 巧妙地将多种调度策略融合在一起，这些策略包括基于优先级的轮转法调度、基于优先级的 FIFO 调度和多级反馈轮转调度，调度程序实现代码简单明了，效率高。

    深入研究分析 Linux 进程调度，除了可以更加深入理解操作系统相关原理外，还可以根据具体的应用对调度程序进行改造，如增加实时性以适应嵌入式应用需求，还可以根据应用环境不同对调度程序进行改进，实现公平分享调度策略 ^[5] 。

参考文献：

[1] 陈莉君 .Linux 操作系统内核分析 [M]. 北京：人民邮电出版社 ,2000-01

[2] 屈浩然 , 李凤华 , 谷建华 . 一种嵌入式实时 Linux 系统设计与实现 [J]. 计算机工程与应用 ,2004, （ 2 ）： 119-159

[3] 赵明富 .Linux 嵌入式系统的实时性分析 [J]. 计算机工程 ,2003,29 （ 18 ）： 89-91

[4] 李善平 , 刘文峰，李程远等 .Linux 内核 2.4 版源代码分析大全 [M]. 北京：机械工业出版社 ,2002-01

[5] 李善平 , 陈文智 . 边干边学 -Linux 内核指导 [M]. 杭州：浙江大学出版社 ,2002-01