学了进程状态以后，我们知道一个进程可能处于 R、S、D、T、Z 等不同状态。

其中，处于 R 状态的进程已经具备运行条件，可以被 CPU 调度执行。

但是新的问题也随之出现：

假设此时系统中同时存在大量处于可运行状态的进程：

进程 A：R
进程 B：R
进程 C：R
进程 D：R
...

CPU 应该先运行哪一个？

如果进程 A 比进程 B 更重要，操作系统又应该如何体现这种差异？

这就涉及 Linux 进程管理中的另外两个重要概念：

进程优先级与进程调度。

---

1. 为什么需要进程优先级

CPU 是一种有限资源。

尤其在单核 CPU 中，同一时刻只能真正执行一个进程的指令。

假设系统中同时存在三个可运行进程：

进程 A
进程 B
进程 C

它们都希望获得 CPU：

但 CPU 不可能同时满足所有进程。

因此操作系统需要根据一定的调度策略决定：

下一时刻应该让哪个进程运行。

而进程优先级，就是调度过程中需要考虑的重要因素之一。

---

2. 什么是进程优先级

进程优先级可以简单理解为：

当多个进程竞争 CPU 时，操作系统用于决定进程调度倾向的一种属性。

优先级较高的进程，通常会获得更加有利的调度机会。

不过这里需要注意：

优先级高并不意味着这个进程一定立即运行，也不意味着它一定获得固定比例的 CPU。

Linux 的调度还会受到调度策略、任务类型、运行时间等多种因素影响。

因此不能简单理解成：

优先级高 = 永远先运行

更加准确的理解是：

优先级
   ↓
影响调度器选择进程的方式

---

3. 查看进程优先级

可以使用：

ps -l

查看进程的详细信息。

可能得到类似：

F S UID   PID  PPID  C PRI NI ADDR SZ WCHAN TTY       TIME CMD
0 S 1000 4201  3157  0  80  0 -    600 -    pts/0 00:00:00 test

其中与优先级关系比较密切的两个字段是：

PRI
NI

分别表示：

PRI → Priority，优先级相关信息

NI  → Nice value，nice 值

---

4. Nice 值

Linux 给普通进程提供了一个用户可以调整的参数：

Nice 值。

通常情况下，Nice 值范围是：

-20 ~ 19

默认情况下：

NI = 0

可以简单理解为：

Nice 越小
   ↓
进程获得更有利调度待遇的倾向越高

Nice 越大
   ↓
进程越“谦让”

例如：

NI = -20

代表进程非常“不客气”。

而：

NI = 19

则代表：

大家先运行，我不是很着急。

这也是 nice 这个名字的由来。

因此：

-20              0                 19
 ↑                                  ↑
更加有利                       更加谦让

---

4.1 为什么 Nice 越大反而优先级越低

第一次看到这里可能觉得比较反直觉。

Nice 可以理解成：

这个进程愿意对其他进程“友好”到什么程度。

Nice 越大：

越友好
 ↓
越愿意让 CPU
 ↓
调度优先级倾向降低

Nice 越小：

越不友好
 ↓
越希望获得 CPU
 ↓
调度优先级倾向提高

所以：

Nice 数值和调度优先级倾向大体呈反向关系。

---

5. 修改进程 Nice 值

Linux 提供了：

nice

命令，可以使用指定的 Nice 值启动程序。

例如：

nice -n 10 ./test

表示以：

NI = 10

启动 test。

然后：

ps -l

就可以观察该进程的 Nice 值。

---

5.1 修改正在运行的进程

对于已经运行的进程，可以使用：

renice

例如：

renice -n 10 -p 4201

表示修改 PID 为：

4201

的进程 Nice 值。

普通用户通常可以把自己的进程调得更加“nice”，也就是降低调度待遇。

但是想把 Nice 值往更小的方向调整，从而提高调度待遇，通常需要相应权限。

这是因为如果普通用户可以随便：

我的程序 NI = -20
你的程序慢慢排队

一台多人服务器大概很快就会进化成人类社会的缩影。

---

6. PRI 与 NI 有什么区别

这是进程优先级中比较容易混淆的两个概念。

可以先简单理解：

NI
 ↓
用户可以调整的 Nice 值

PRI
 ↓
调度器所使用或展示的优先级相关信息

Nice 并不是简单等于 PRI。

更加合理的理解是：

Nice 会影响普通进程的调度优先级，但并不是 Linux 内核唯一考虑的因素。

因此不要简单写成：

PRI = NI

也不要理解为：

Nice 改 1
CPU 使用率就固定变化多少

Linux 调度没有这么机械。

---

7. Linux 内核中的优先级

在经典 Linux O(1) 调度器中，可以把调度优先级大致分成两部分：

0 ~ 99
实时进程优先级

100 ~ 139
普通进程优先级

其中普通进程的 Nice：

-20 ~ 19

可以映射到：

100 ~ 139

例如可以简单理解为：

NI = -20
   ↓
静态优先级约为 100

NI = 0
   ↓
静态优先级约为 120

NI = 19
   ↓
静态优先级约为 139

在这种内部优先级表示中：

数值越小，优先级越高。

需要注意，这里讨论的是经典 O(1) 调度器内部的优先级模型，不应简单把它和所有 ps、top 输出中的 PRI/PR 数值完全等同。

---

8. 什么是进程调度

理解了优先级以后，就可以正式认识：

Scheduler，进程调度器。

调度器的主要任务之一就是：

从当前可以运行的进程中，选择一个合适的进程交给 CPU 执行。

例如：

          可运行进程

进程 A
进程 B
进程 C
进程 D
   │
   ↓
┌──────────────┐
│   调度器      │
└──────┬───────┘
       │
       ↓
   选择进程 B
       │
       ↓
      CPU

因此：

进程状态
   ↓
哪些进程可以运行？

进程调度
   ↓
选择哪个进程运行？

这是两个不同但密切相关的问题。

---

9. 为什么要学习 O(1) 调度器

Linux 的调度算法并不是从始至终都保持不变。

经典 O(1) Scheduler 是 Linux 2.6 早期非常重要的一代调度器。

它后来被新的公平调度设计取代，因此：

现代 Linux 的普通进程调度已经不是这里介绍的经典 O(1) active/expired 调度模型。

但是 O(1) 调度器的数据结构非常经典，非常适合理解：

• 运行队列；
• 优先级队列；
• 时间片；
• 进程调度；
• 调度复杂度。

所以仍然非常值得学习。

---

10. O(1) 中的运行队列

CPU 想选择一个进程运行，首先就必须知道：

当前有哪些进程已经准备好运行？

因此调度器需要维护：

运行队列 Run Queue。

可以简单理解：

等待 CPU 的进程
      ↓
┌──────────────────┐
│     Run Queue    │
│                  │
│  process A       │
│  process B       │
│  process C       │
│  process D       │
└──────────────────┘
      ↓
   调度器选择
      ↓
      CPU

但是，如果所有进程只是简单放进一个队列：

A → B → C → D → E → F → ...

调度器寻找最高优先级进程时，可能需要遍历大量进程。

系统中的进程越多，查找成本就可能越高。

经典 O(1) 调度器采用了一套更加巧妙的数据结构。

---

11. O(1) 调度器的核心结构

经典 O(1) 调度器会根据优先级，将可运行任务组织到不同的优先级队列中。

可以简化理解成：

优先级
  0  → [进程] [进程]
  1  → [进程]
  2  → []
  3  → [进程] [进程]
 ...
139  → [进程]

也就是说：

不同优先级拥有对应的任务队列。

调度器不需要在所有进程中挨个寻找优先级最高的进程，而是找到：

最高优先级的非空队列

然后从其中选择任务运行。

---

12. prio_array

经典 O(1) 调度器中有一个非常重要的数据结构思想：

Priority Array，优先级数组。

可以把它简化成：

prio_array
│
├── bitmap
│
└── queue[140]
      │
      ├── queue[0]
      ├── queue[1]
      ├── queue[2]
      ├── ...
      └── queue[139]

其中：

queue[]

保存不同优先级上的可运行进程。

而：

bitmap

用于快速记录：

哪些优先级队列里面存在进程。

---

13. Bitmap 为什么重要

假设：

queue[100] 空
queue[101] 空
queue[102] 有进程
queue[103] 空
queue[104] 有进程

如果一个一个检查：

100
 ↓
101
 ↓
102

虽然也能找到，但设计上还可以更高效。

因此 O(1) 调度器使用 bitmap 标记队列是否为空。

可以简单理解：

优先级        是否存在进程

100             0
101             0
102             1
103             0
104             1

通过位图相关操作，内核可以非常快速地找到最高优先级的非空队列。

然后：

找到队列
   ↓
取出其中的进程
   ↓
交给 CPU

---

14. 为什么叫 O(1)

这也是这套调度器名字的来源。

算法复杂度中的：

O(1)

表示：

操作所需要的时间不会随着待调度进程数量的增长而线性增长。

例如：

系统中 10 个进程

系统中 1000 个进程

系统中 10000 个进程

经典 O(1) 调度器在选择下一个任务时，不需要遍历所有进程。

因此调度决策的关键查找过程可以保持近似常数时间复杂度：

O(1)

这就是：

O(1) Scheduler

名字的核心含义。

需要特别注意：

O(1) 并不是说“进程一定一瞬间运行完”。

也不是：

“O(1) 调度器永远比任何其他调度器快。”

它描述的是特定调度操作的算法时间复杂度。

---

15. Active 与 Expired

经典 O(1) 调度器还有一个非常漂亮的设计：

Active
Expired

两组优先级数组。

可以简单理解为：

              Run Queue

      ┌─────────────────┐
      │     Active      │
      │ 当前可以参与调度 │
      └────────┬────────┘
               │
               ↓
             CPU

      ┌─────────────────┐
      │     Expired     │
      │ 时间片耗尽的任务 │
      └─────────────────┘

---

15.1 Active

Active 保存：

当前拥有时间片，可以参与本轮调度的进程。

调度器不断从 Active 中选择进程运行。

例如：

Active

P1
P2
P3
P4

P1 被选中运行。

时间片使用完成以后，需要重新安排后续运行机会。

在简化模型中，可以理解为任务会进入：

Expired

---

15.2 Expired

Expired 可以理解为：

已经完成当前一轮时间片，需要等待下一轮调度的任务集合。

例如：

Active

P2
P3
P4

Expired

P1

继续调度以后：

Active

P3
P4

Expired

P1
P2

直到：

Active
空

此时神奇的地方来了。

---

16. Active 与 Expired 交换

当 Active 中已经没有任务时，并不需要：

把 Expired 中所有进程一个个复制回 Active

只需要交换两个数组的引用或指针。

可以理解为：

原来：

Active  → A数组
Expired → B数组

交换以后：

Active  → B数组
Expired → A数组

于是原来的 Expired：

瞬间变成新的 Active

整个过程不需要遍历并搬运所有进程。

这也是 O(1) 调度器设计中非常经典的一点。

---

17. O(1) 调度整体过程

把前面的知识串起来，可以得到一个简化模型：

这张图描述的是为了学习 O(1) 调度思想而进行的简化模型。

真实 Linux 2.6 早期 O(1) 调度器还会考虑：

• 实时任务；
• 动态优先级；
• 交互性；
• 睡眠时间；
• 时间片计算；
• SMP 多 CPU；
• 负载均衡；

等更加复杂的问题。

---

18. O(1) 调度器为什么后来被替换

O(1) 调度器虽然拥有非常优秀的常数级调度性能，但是随着 Linux 使用场景不断发展，也暴露出一些问题。

特别是在：

• 交互任务公平性；
• 调度参数；
• 任务行为判断；
• 不同负载场景的一致性；

方面越来越复杂。

Linux 后来引入了新的公平调度思想。

从 Linux 2.6.23 开始，经典 O(1) 普通任务调度器被 CFS（Completely Fair Scheduler，完全公平调度器）取代。

所以需要明确：

学习 O(1) 调度器，是为了理解 Linux 调度器发展历史以及运行队列、优先级数组、时间片等经典调度思想，而不是认为现代 Linux 仍然完整使用这套调度模型。

---

19. 进程状态、优先级与调度的关系

现在我们终于可以把前面几篇文章串起来。

假设系统中存在：

进程 A：R
进程 B：R
进程 C：S

其中：

A 和 B

都处于可运行状态。

而：

C

正在睡眠等待事件，因此暂时不参与普通 CPU 竞争。

调度器会从能够运行的任务中选择下一项任务：

所以可以简单总结：

进程状态
   ↓
决定当前是否具备运行条件

进程优先级
   ↓
影响任务获得 CPU 的调度待遇

调度器
   ↓
从可运行任务中选择下一个进程

CPU
   ↓
执行该进程

这样，进程状态、进程优先级和进程调度三个概念就真正联系起来了。

---

20. 小结

这一篇主要学习了 Linux 中的进程优先级和经典 O(1) 调度器。

首先，Linux 中多个进程会竞争有限的 CPU 资源，因此需要进程调度。

对于普通进程，我们可以通过 Nice 值影响调度待遇：

Nice 范围：

-20 ~ 19

数值越小
   ↓
通常调度待遇越有利

可以使用：

nice

和：

renice

调整 Nice 值。

在 Linux 2.6 早期经典 O(1) 调度器中，调度器通过：

优先级队列
+
Bitmap
+
Active
+
Expired

高效管理大量可运行任务。

其中最核心的思想可以概括成：

不同优先级
     ↓
进入不同队列
     ↓
Bitmap快速寻找最高优先级非空队列
     ↓
选择任务运行
     ↓
时间片完成
     ↓
重新安排任务
     ↓
Active耗尽后与Expired交换

而所谓：

O(1)

指的是核心调度选择操作不会因为系统中进程数量增加而需要遍历所有进程，其时间复杂度可以保持常数级。