Linux 进程优先级与 O(1) 调度算法解析
一、进程优先级的概念
CPU 资源有限，无法让运行队列中的进程同时执行。因此，操作系统需要决定谁先获得时间片，这个先后顺序就是进程优先级。
二、查看优先级信息
使用 ps -l 命令可以查看系统中更详细的进程信息：
其中与进程优先级相关的核心字段是 PRI 和 NI，它们也是存在于 task_struct 结构体中的两个整型成员变量。
- PRI：代表进程可被执行的优先级，数值越小越优先。
- NI：代表进程的 nice 值。
1. PRI 与 NI 的理解
PRI 直观反映程序被 CPU 执行的先后顺序。NI 则是进程优先级的修正数值。
两者的关系公式为：进程 PRI 值 = 80 + 进程 nice 值。 nice 值变小，PRI 随之变小，进程优先级变高；反之亦然。调整进程优先级，在 Linux 下本质上就是调整 nice 值。 nice 值的取值范围是 -20 到 19，共 40 个级别。对应的 PRI 取值范围则是 [60, 99]。
2. 修改 nice 值
我们可以跑一个循环程序进行演示，此时查看 PRI 和 NI 默认分别为 80 和 0。
一种修改方式是通过 top 命令动态调整已存在进程的 nice 值：输入 top 回车，再按 r 键，输入进程 PID，最后输入新的 nice 值。
这里我将 nice 值尝试修改为 20。退出 top 后再次查询：
可以看到 nice 值变成了 19，这是因为 20 超过了规定范围，最高只能修改到 19。此时 PRI 值也就变成了 19 + 80 = 99，符合预期。不过生产环境中，频繁调整 nice 值需谨慎。
三、进程调度切换
系统会给每个进程分配时间片，执行完毕后自动让出 CPU。CPU 寄存器由所有进程共享，每次保存一个进程的上下文数据。当轮转回来时，临时数据再转移回寄存器。这种机制被称为分时操作系统。
那么，系统是如何高效切换调度进程的呢？以 Linux 2.6 内核为例，其核心调度机制采用了 O(1) 算法。
1. list_head 与 prio_array 结构
在源码的 task_struct 定义中，有两个关键成员：
prio_array_t *array 指向当前进程所属的优先级数组指针，记录该进程是在活跃队列还是过期队列。
struct list_head 是一个双向链表结构，run_list 是 CPU 运行队列的核心。
分析 prio_array_t 结构：
根据优先级选择进程队列的过程，本质上是哈希映射。虽然 queue 中存放的是 list_head 类型节点，看似没有进程信息，但这里涉及一个关键概念：容器对象（container_of）。
假设有一个结构体变量 struct A obj，它内部包含成员 a。如果只知道 a 的地址，可以通过 &a - &((struct A*)0->a) 计算出 obj 的地址。原理是结构体成员的地址偏移量固定，通过成员地址减去偏移量即可反推结构体起始地址。
实际上，queue 中的每一个 list_head 就是一个进程的 task_struct 的成员变量 struct list_head run_list。利用上述方法，就能用 run_list 的地址算出 task_struct 的地址，进而获取进程的各种信息。这种将链表节点嵌入目标结构体内部的设计，被称为'侵入式链表'，无需额外内存开销且灵活复用。
选定进程的策略很简单：从下标 0 开始遍历 queue，找到第一个非空队列，依次调度其中的进程。由于 queue 大小固定为 140，这种算法的时间复杂度是 O(1)。为了进一步提升效率，prio_array 中还包含一个 bitmap 位图，用 140 个比特位表示 140 个进程队列是否为空，利用位运算大大提高查找非空队列的效率。
2. 活跃队列与过期队列
一个 CPU 拥有一个 runqueue 结构，即 CPU 的运行队列：
- active：活跃指针，指向的
prio_array_t称为活跃队列。 - expired：过期指针，指向的
prio_array_t称为过期队列。 - arrays：数组中存放着这两个队列。
活跃队列中存放时间片未结束的进程，变量 nr_active 记录运行状态进程数。过期队列中存放时间片耗尽的进程。当活跃队列上的进程执行完，就放入过期队列并重新计算时间片。
随着进程不断被执行，活跃队列进程减少，过期队列进程增多。当活跃队列清空，直接交换 active 与 expired 指针，刚才的过期队列变为新活跃队列，继续执行。
这套设计非常巧妙，处理特殊情况如下：
- 新进程：插入到过期队列，等下一轮再执行。
- 修改优先级：本轮位置不变，等到插入过期队列时再计算新优先级位置。这也是引入 nice 中间值的原因之一。
若只有一套队列，进程时间片用完或修改优先级时需在同一队列内重算和调整，会导致遍历开销变大，逻辑混乱。有了这样一套完整的调度逻辑，查找最合适调度进程的时间复杂度即为常数，不随进程增多而增加成本，这就是 O(1) 调度算法。
四、补充概念
- 竞争：系统进程众多而 CPU 资源较少，进程间存在竞争性。合理竞争就有了进程优先级。
- 独立：多进程运行需独享资源，互不干扰。父子进程之间也有独立性。
- 并行：多个进程在多个 CPU 下分别同时运行。
- 并发：多个进程在一个 CPU 下采用切换方式，在一段时间内让多个进程都得以推进。
