Re:Linux 系统篇（十六）：进程篇（五）：O (1) 调度算法深度解析 —— 优先级数组、位图优化与活跃 / 过期双队列

上一篇我们讲透了进程上下文切换的完整流程。切换谁、选哪个进程上 CPU，这件事由调度器决定。

早期 Linux 调度器很简单：所有就绪进程放一个链表，每次调度遍历整个链表找优先级最高的。进程少还好，进程多了，每次调度都要遍历一遍，复杂度 O (n)，调度越来越慢。

于是经典的O (1) 调度算法横空出世：无论系统里有多少个进程，选择下一个进程的时间永远是固定的，不随进程数增长而变慢。
本篇我们从 O (n) 的痛点讲起，一步步拆解位图优化、优先级数组、活跃 / 过期双队列设计，彻底搞懂 O (1) 的核心精髓。

一、进程调度的核心诉求与优先级数组

1.1 调度的核心工作

调度器的核心任务只有一个：

从就绪队列里，选出下一个应该上 CPU 运行的进程。

评判调度器好不好，两个关键指标：

1. 调度速度：选下一个进程要多久
2. 公平性：会不会有进程饿死，响应及不及时

1.2 为什么要有进程优先级？

进程不是人人平等的。
比如交互程序（点击鼠标、打字）需要快速响应，优先级要高；后台编译、下载可以慢一点，优先级低。
Linux 给每个进程分配了优先级，调度器优先选高优先级的进程。

1.2.1 区分：优先级与权限

很多人混淆优先级和权限：

• 优先级：调度层面的，决定进程能不能抢到 CPU 时间
• 权限：系统资源层面的，决定能不能访问文件、能不能执行特权操作

root 用户的进程权限高，但不代表优先级一定高；普通用户也可以把自己进程的优先级调高调低（在允许范围内）。

1.2.2 UID 与优先级无关

UID 是用户 ID，是权限标识，和调度优先级是两个维度。
root 可以调整进程优先级到更高范围，但不是 root 进程就一定优先级高。

1.3 进程优先级的正面作用

• 高优先级进程获得更多 CPU 时间，响应更快
• 重要任务优先执行，保证核心业务体验
• 低优先级后台任务闲时运行，充分利用 CPU

1.4 Linux 下查看进程优先级

1.4.1 使用 ps -l 命令查看

ps -l

输出里两个核心指标：

• PRI：进程最终优先级，数值越小优先级越高
• NI：Nice 值，用户可以调整的友好值，范围 - 20 到 19，越小优先级越高

1.4.2 核心指标：PRI 与 NI

最终优先级 = 基础优先级 + Nice 值偏移。
Nice 值是用户能控制的部分：

• Nice=-20：最高优先级加成
• Nice=0：默认
• Nice=19：最低优先级

1.5 进程优先级的计算公式

Linux 优先级是动态计算的，不是固定值。
调度器会根据进程的行为动态调整：

• 总是睡觉的 IO 密集型进程：自动提升优先级，因为它平时不占 CPU，响应要快
• 一直死循环的 CPU 密集型进程：自动降低优先级，因为它一直占 CPU

Nice 值是用户设定的基准偏移，在动态计算的基础上叠加。

1.6 Nice 值的取值范围与限制原因

Nice 值范围是-20 到 19，共 40 档。
为什么范围这么小？
因为优先级分档太多的话，调度复杂度上升，且差别太小没意义。40 档足够区分不同类型的进程了。

普通用户只能调大 Nice 值（降低优先级），不能调小（提升优先级），防止普通用户把自己进程调最高霸占 CPU。
root 用户可以调整全范围。

1.7 优先级修改方法

1.7.1 命令行工具

• nice：启动程序时指定 Nice 值

nice -n -5 ./myprocess # 启动时设置Nice为-5

• renice：修改已经运行的进程的 Nice 值

renice -10 -p 进程PID

1.7.2 系统调用

程序里可以用nice()系统调用修改自己的优先级。

1.7.3 通过 top 命令交互式修改

top 里按r，输入 PID，再输入 Nice 值，即可修改。

二、O (n) 调度的痛点：引出位图优化

2.1 传统的顺序遍历困境

最早的调度器：所有就绪进程串成一个链表。
每次调度：从头遍历整个链表，找出优先级最高的进程。

• 10 个进程：遍历 10 次，很快
• 1000 个进程：遍历 1000 次，调度变慢
• 10000 个进程：遍历 10000 次，调度开销大到不可接受

时间复杂度 O (n)，进程越多，调度越慢。服务器上几百上千进程很常见，这种调度器性能跟不上。

2.2 性能破局：引出位图技术

核心思路：按优先级分组排队。
优先级一共就几十档，我们给每个优先级单独建一个队列。同优先级的进程，放在同一个队列里。

然后用一个位图（bitmap）来标记：哪个优先级队列里有进程。

• 比如第 0 位是 1，代表优先级 0 的队列有进程
• 第 5 位是 0，代表优先级 5 的队列是空的

找最高优先级，就变成了：找位图里第一个 1 的位置。

2.3 位图是什么？

位图就是用整数的每一位来表示一个状态。
比如一个 32 位整数，可以表示 32 个优先级的空 / 非空状态。
Linux 有 140 个优先级，用两个 64 位整数就能全部表示。

2.4 为什么找第一个 1 是 O (1)？

CPU 硬件有专门的指令：bsf（Bit Scan Forward，位扫描向前）。
一条 CPU 指令，就能直接返回位图里第一个 1 的位置，不管位图多大，都是一条指令搞定，时间固定。

所以：

• 找最高优先级 = 一次 bsf 指令 → O (1)
• 找到对应优先级队列，取第一个进程 → O (1)

整个调度过程，无论多少进程，时间都是固定的，这就是 O (1) 名字的由来。

三、活跃队列与过期队列

3.1 为什么要两个队列？

只有一个优先级队列会有问题：
高优先级进程源源不断，低优先级进程永远轮不到，直接饿死。
比如一直有高优先级的 IO 进程醒来，CPU 永远被它们占着，低优先级的后台计算进程永远跑不到。

所以 O (1) 调度设计了两个数组：活跃数组（Active Array）和过期数组（Expired Array）。

3.2 活跃队列（Active Array）

当前这一轮，所有时间片没用完的进程，都在活跃数组里。
调度器每次都从活跃数组里选进程。
进程时间片用完了，就从活跃数组里拿出来，放到过期数组里。

3.3 过期队列（Expired Array）

已经用完时间片的进程，都放在过期数组，等待下一轮。
当活跃数组里所有进程都跑完了，空了，就把两个数组交换：

• 过期数组 变成 新的活跃数组
• 原来的活跃数组（空了）变成 新的过期数组

然后开始新一轮调度。

3.4 指针交换：O (1) 的互换

两个数组交换，不是把所有进程挪来挪去，那又变成 O (n) 了。
Linux 的做法很巧妙：交换指针。
两个数组各有一个指针指向自己，交换的时候，只交换两个指针的值，O (1) 操作，瞬间完成。

💡 类比理解：
两个篮子，A 篮装当前轮的乒乓球，B 篮装打完的。
A 篮空了，不用把球一个个从 B 搬到 A，直接把两个篮子的标签互换，A 变 B，B 变 A，开始下一轮。

3.5 完整流转梳理

1. 初始：所有进程分配好时间片，全部放入活跃数组
2. 调度器从活跃数组选最高优先级进程，运行
3. 进程时间片用完，移出活跃数组，加入过期数组
4. 活跃数组不为空，回到步骤 2 继续
5. 活跃数组空了，交换活跃和过期数组指针，开始新一轮

3.6 设计优势

• 保证公平：每一轮所有进程都跑完，才开始下一轮，不会有进程永远轮不到
• 性能恒定：所有操作都是 O (1)，不随进程数增加变慢
• 支持动态优先级：每一轮重新计算时间片和优先级，灵活调整

四、周边问题

4.1 新进程来了怎么办？

新创建的进程，直接放到过期数组里，等当前轮结束，下一轮再参与调度。
好处：不打乱当前轮的秩序，保证当前轮所有进程公平跑完；新进程不会一进来就抢占，避免调度抖动。

4.2 调度队列其他元素

每个 CPU 都有自己独立的调度队列（runqueue）。
多核系统里，每个 CPU 自己调度自己的队列，不用全局抢锁，减少竞争，提升多核性能。

每个 runqueue 里就是：

• 一个活跃优先级数组
• 一个过期优先级数组
• 对应的位图
• 调度相关统计信息

4.3 优先级与调度算法的关系

• 优先级决定了进程在哪个优先级队列，决定了被选中的先后
• 调度算法（O (1））决定了怎么高效选出最高优先级的进程

优先级是规则，调度算法是高效执行规则的方法。

五、O (1) 调度的核心设计总结

表格

O (1) 调度的精髓就是：用空间换时间，用分组、位图、双队列的设计，把调度操作从 O (n) 降到 O (1)，让 Linux 在大负载、多进程场景下，调度性能依然稳定。

补充：O (1) 是 Linux 2.6 内核的经典调度器。后来的 CFS 完全公平调度是更现代的调度器，但 O (1) 里的位图、双队列、每 CPU 队列等设计思想，依然是调度算法的经典，也是理解现代调度的基础。

全文总结

1. 调度核心：从就绪进程里选下一个上 CPU，核心是速度和公平。
2. 优先级：进程调度的权重，Nice 值用户可调，最终优先级动态计算。
3. O (n) 痛点：遍历链表选最高优先级，进程越多越慢。
4. 位图优化：按优先级分队列，位图标记非空队列，硬件 bsf 指令找最高优先级，O (1) 选出。
5. 活跃 / 过期双队列：每轮跑完交换指针，保证公平，防止饥饿，交换 O (1)。
6. 每 CPU 队列：多核独立调度，减少锁竞争，提升性能。