Linux 进程优先级与 O(1) 调度算法解析

在源码的 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 下采用切换方式，在一段时间内让多个进程都得以推进。