【Linux】进程调度

在操作系统中，一个进程被创建出来就是为了完成我们所需要完成的任务的，而这个任务无非就是两种，一种叫做计算密集型任务，比如我们平常打的游戏，其本质就是在进行各种运算，你当前的血量是多少，放了技能之后你所剩的蓝量是多少，都是 cpu 在进行各种运算，所以这类的任务竞争的就是 cpu 资源；另一种进程叫做 I/O 密集型任务，这种进程进行的主要是跟外设相关的任务，比如将字符串打印到屏幕上，将内容写进文件里，读取文件内容等，所以这类任务竞争的就是外设资源，一旦外设资源没有继续，那么进程就会进入阻塞队列进行等待。

但是不管是上面的哪种进程，本质上都是在竞争计算机资源。资源是有限的，但是我们可以创建的进程可以是 “无限” 的，所以进程多、资源少，就需要有一个概念来标识谁先获得资源，谁后获得资源，这个概念就是进程的优先级。就比如大学食堂的打饭窗口，打饭窗口就相当于计算机中的各种资源，大学生就相当于一个一个的进程。大学生很多，但是打饭窗口就那么几个，造就了进程多、资源少的局面，所以我们需要通过排队来确定优先级，优先级高的先获得资源。

2）查看系统进程的优先级

我们可以通过 ps 命令来查看系统的优先级

ps -al | head -1 && ps -al | grep [进程名字]

这里我们写了一个测试代码：

//test.c
#include <stdio.h>

int main()
{
    while (1) ;
    return 0;
}

然后我们使用 ps -al | head -1 && ps -al | grep test 来查看一下进程的优先级：

可以看到展示出了各种信息，各种信息的详细信息如下：

UID：执行的用户编号

PID：当前进程的标识符

PPID：父进程的进程标识符

PRI：就是当前进程的优先级 priority

NI：进程优先级的 nice 值

PID 和 PPID 我们在进程概念中早就讲过了，接下来我们来讲解一下 UID、PRI 以及 NI。

UID 是执行用户的用户编号，一般 root 用户为 0，普通用户为的 uid 大于 1000，我们可以通过 id 命令来查看用户的 uid

id [用户名]

我们用户识别 Linux 中的用户一般用的都是用户名，但是内核并不是通过用户名来识别，而是通过 uid 来识别的。所以 uid 是系统区别用户的键值。

PRI 是 priority 的简称，也就是优先级的意思。所以 PRI 就是进程的优先级字段，可以看到 test 进程的 PRI 是 80，所以进程的优先级本质上也就是一个数字。数字越小，其优先级越高，进程越早被执行。

NI 是 nice 的简称，nice 值是调整进程优先级的核心属性。在 Linux 中，一般不是通过调整 PRI 值来调整优先级，而是通过 nice 值来调整优先级的。nice 值一共有 40 个级别，值的范围是 [-20, 19]，调整了 nice 值之后，PRI(new) = nice + PRI(old)，其中 PRI(old) 固定为 80。所以 PRI 的范围也就是 [60, 99]。而 PRI 值越小，优先级越高，所以与之对应的就是 nice 值越小，优先级越高。在 Linux 中调整优先级本质上就是调整进程的 nice 值。

而这三个属性属于进程，所以这三个属性也会在进程描述属性的结构体 task_struct 中保存起来：

虽然 nice 值没有具体存储在 task_struct 中，但是却可以通过 static_prio 算出来。static_prio 称为静态优先级，static_prio = 120 + nice ==> nice = static_prio - 120，这样就可以算出 nice 值了。

但是需要注意的一点是这里的 PRI 只是 ps 工具显示的优先级，内核中真正的优先级是 PRI + 40，至于为什么是 PRI + 40，是跟具体的 Linux 调度算法有关，下面讲解调度算法就知道了。

还有需要强调的一点，就是不管在 ps 工具还是内核中，nice 值都是一样的，都是 [-20, 19]，一共 40 个级别，而且 nice 值并不是真正的进程优先级，但是确是调整进程优先级的核心字段。

为什么 nice 值会有范围呢？

对于这个问题跟操作系统是有关系的。现在的操作系统都是分时操作系统，也就是对于每个进程来说，操作系统调度的时候要做到尽可能的公平公正，每个进程调度的时间都尽量是相同的。所以如果 nice 值没有范围，那么优先级就无法做到可控。那么如果有一个进程的优先级很低，就会被操作系统忽略，进而没有办法得到调度，进程就会 "饿死"，出现进程饥饿问题。为了防止出现此问题，所以 nice 值才会有范围，进程的优先级也就有了范围。

3）调整进程优先级

我们可以通过 top 命令来修改进程的优先级。top 命令就类似于 Windows 操作系统中的任务管理器，执行命令之后就可以看到执行起来的进程：

运行起来之后我们可以按 q 退出。

我们可以按照以下步骤来修改进程的优先级（注意，修改进程优先级需要是 root 用户）：

（1）在 top 命令中按下 r，之后输入 pid

（2）再输入要调整的 nice 值，进程的优先级就被修改了

此时可以看到进程的优先级被修改为 60 了。那么我们如果将进程的 nice 值再修改为 10，进程的优先级是否会变成 70 呢？

可以看到进程的优先级变为了 90，而不是 70，所以进程优先级的修改并不会基于上次的结果修改，而是覆盖式的修改，PRI(new) 就是固定的为 PRI(old) + nice。

2 进程切换

Linux 操作系统是一个分时操作系统，也就是要公平公正的调度每一个进程，那么如何做到公平公正的调度每一个进程呢？其实就调度运行每个进程的时间是一样的，所以每个进程都会有其合适的时间片（就是一个计数器 count），一旦时间片达到（count 减到了0），进程就会被操作系统从 CPU 上剥离下来。

进程运行的时候会产生很多临时数据，而这些临时数据是存储在 CPU 的寄存器里面的，比如下面这段代码：

//Add.c
#include <stdio.h>

int main()
{    
    int a = 1, b = 2;
    int c = a + b;
    printf("a + b = %d\n", c);    

    return 0;
}

该程序的汇编代码

其中的 eax、esp 就是 CPU 中的寄存器之一。

所以通过上述汇编代码我们可以看到，即使是一个简单的加法，也需要将数据放到寄存器中，所以寄存器中会保存程序运行过程中的各种临时数据。上面我们又说，一旦进程的时间片到了，进程就会被操作系统从 CPU 中剥离下来，此时寄存器中必然保存着程序运行的临时数据，如果不将这些寄存器中的临时数据进行保存，那么程序就白白花了这么长时间去运行。就比如上面的Add.c 程序，在运行完 int c = a + b 这段代码之后， a + b 的结果存储在 eax 寄存器中，此时程序的时间片正好到了，程序被从 CPU 上剥离下来，但是如果寄存器 eax 计算的结果没有保存，那么下次再调度到 Add.c 这个程序时，程序又需要从头开始计算，这样就得不偿失了。所以在切换进程时必须要保存 CPU 寄存器中的各种临时数据。像这样的，保存在寄存中的各种临时数据，就叫做进程的上下文数据。

所以进程切换，本质上就是进程上下文数据切换，也就是 CPU 寄存器切换。进程在切换之前，必须先将进程的上下文数据存储起来，也就是保存 CPU 寄存器中的临时数据。等到下次调度到该进程时，再将进程的上下文数据恢复到寄存器中，这样程序就可以从上次被调度的位置继续运行，不用重新运行了，这一过程就称为 context switch。

在很早版本的内核中，进程的上下文数据会存储在进程的 task_struct 中。比如 Linux 0.11 版本的内核，就有一个 struct tss_struct tss 字段来保存进程的上下文数据：

可以看到 struct tss_struct 结构体中就是各种寄存器的名称，包括 eax、esp 等。所以进程是会将进程的上下文数据保存起来的。

3 Linux O(1) 进程调度算法

Linux 的进程调度算法主要是通过一个运行队列 runqueue 实现的，一个 CPU 拥有一个 runqueue 队列，接下来我们就来讲解一下这个 runqueue。

1） runqueue 的结构

在 2.6.18 版本的 Linux 内核源代码中我们可以看到这么一句话

所以就说明每一个 CPU 会有一个 runqueue 运行队列用来进行进程的调度。

在 Linux 内核源代码中，runqueue 的结构体名称为 struct rq，具体结构如下：

其中 struct prio_array *active, *expired, arrays[2] 是实现 Linux 进程调度算法的核心字段。接下来我们来看一下 struct prio_array 的结构：

MAX_PRIO 的定义：

DECLARE_BITMAP 的定义：

所以 DECLARE_BITMAP(bitmap, MAX_PRIO+1) 其实就是 unsigned long bitmap[3]（注意在 Linux 中，unsigned long 是 8 个字节，也就是 64 位）。

通过以上定义，所以 runqueue 的结构就如下图所示：

第一眼看上去是这样的，但是那 3 个核心成员的结构真是这样的吗？

2） Linux 调度算法

Linux 的进程调度算法主要是由 struct prio_array* active, *expired, arrays[2] 实现的。arrays 为 struct prio_array 的数组，在 struct prio_array 中实现进程调度的核心结构为 queue[140]，所以这两个数组又称为队列。

其中 active 是活动的意思，expired 为过期的意思。其实 active 指向了 arrays[2] 中的一个元素，expired 指向了 arrays[2] 中的另一个元素，比如 active = &arrays[0], expired = &arrays[1]。所以，runqueue 的真实结构是这样的：

其中 active 称为活动队列，expired 称为过期队列。接下来我们就来讲解一下这两个队列。

（1） active 活动队列与 expired 过期队列

活动队列与过期队列结构相同，这里我们仅讲解活动队列。

活动队列中共有三个字段，分别是：

nr_active：共有多少个运行状态的进程

bitmap：位图结构，代表 queue[140] 中哪个下标的队列里面有进程

queue[140]：表示进程调度队列

active 活动队列的结构如图所示：

其中 bitmap 称之为位图，表示 queue 数组的情况。bitmap 的位置表示 queue 数组的下标，而内容表示该下标元素中是否还有等待调度的 task_struct。比如第 0 位如果为 1，就代表 queue[0] 中还有等待调度的 task_struct；第 80 位为1，就代表 queue[80] 中还有等待调度的 task_struct。虽然 unsigned long bitmap[3] 会有 192 位，但是由于 queue 只有 140 个元素，所以只会用到前 140 位。

queue[140] 是 struct list_head 类型

虽然这里 queue[i] 是 struct list_head 类型，但是 task_struct 中会含有struct list_head 对象。所以 queue 并不是直接将 task_struct 链接起来，而是将每个 task_struct 中的 list_head 对象链接起来，但是其实就是链接了每个 task_struct。为了方便表述，这里我们就认为 queue[i] 是直接将 task_struct 链接起来的。所以 queue 中的每个元素都会链接许多 task_struct，这样每个 queue[i] 就变成了一个 task_struct 队列。

（2） Linux 如何完成进程调度

Linux 调度过程：

a. 首先，系统会先通过 active 指针，找到 arrays[2] 中的活动队列，然后再通过 bitmap 位图，在 queue 数组从 0 下标开始到 139 号下标找到第一个非空的 queue[i]（其实就是一个 task_struct 队列），之后根据这个队列从头到尾的选择进程

b. 然后，每一个进程是有时间片的。当前进程的时间片结束之后，进程会在 CPU 上被剥离下来，然后该进程会从活动队列中的 queue[i] 再链入到过期队列中的 queue[i]（链入 queue 的下标要相同），再将过期队列中的 bitmap 相应位置置1，并且活动队列的 nr_active--，过期队列的 nr_active++。

c. 当前 queue[i] 队列的所有进程调度完成之后，再从当前位置开始继续向后扫描，再找到一个非空队列，按照上述步骤开始调度。

d. 当活动队列中的所有进程调度完成之后，也就是 active->nr_active == 0；此时只需要交换 active 与 expired 指针的内容，也就是 swap(&active, &expired)，此时活动队列就会变为过期队列，过期队列就会变为活动队列。再按照上述步骤调度即可。

上述调度过程的时间复杂度为 O(1)，所以我们称作 Linux O(1) 进程调度算法。在上述调度过程中，我们可以发现其实在活动队列 queue 下标越小的 queue[i] 队列的 task_struct 越早会被调度，所以优先级其实就是 queue 数组中的下标，task_struct 位于 queue 数组中的小标越小，代表进程的优先级越高。同一优先级的进程采用的调度原则为 FIFO（first in first out）原则。

但是之前 PRI 的优先级只有 [60, 99]，也就是 40 个啊，怎么这里有 140 个优先级啊？其实 queue 中的 [0, 99] 下标，也就是 [0, 99]，共 100 个优先级叫做实时优先级，主要用于工业场景实现实时优先级进程，这里我们不关心。所以我们真正使用的优先级其实是 [100, 139]，共 40 个级别，所以 ps 工具展示出的优先级 PRI 其实是真正的优先级减去 40 得到的。而通过调整 nice 值调整进程的优先级其实是通过将目标进程的 task_struct 链入不同的 queue[i] 队列实现的。比如将 nice 值调整为 -20，其实就是将 queue 120 下标队列中的目标进程链入 100 下标队列实现改变进程优先级的。

4 总结

我们可以通过 ps -al 工具查看进程的优先级 PRI，PRI 固定位 80。可以通过调整 nice 值来调整进程的优先级，而且是覆盖式的修改。nice 值共 40 个级别：[-20, 19]，代表了 PRI 就是 40 个级别：[60, 99]。但是真正的优先级位 PRI + 40。Linux 进程调度只要是通过 struct rq，也就是 runqueue 结构体中的 struct prio_array* active, *expired, arrays[2] 实现的。 active 与 expired 分别称为活动队列与过期队列。在 struct prio_array 中共有三个成员，nr_active、queue[140] 以及 bitmap。进程的优先级其实就是 task_struct 在 queue 数组中的下标。调度过程中， active 中的 nr_active--，expired 中的 nr_active++。一旦 active 中的 nr_active 减到了 0，那么就会 swap(&active, &expired)，此时就完成了活动队列与过期队列的交换，进程就可以继续调度了。