学了进程状态以后我们知道一个进程可能处于R、S、D、T、Z等不同状态。其中处于R状态的进程已经具备运行条件可以被 CPU 调度执行。但是新的问题也随之出现假设此时系统中同时存在大量处于可运行状态的进程进程 AR 进程 BR 进程 CR 进程 DR ...CPU 应该先运行哪一个如果进程 A 比进程 B 更重要操作系统又应该如何体现这种差异这就涉及 Linux 进程管理中的另外两个重要概念进程优先级与进程调度。1. 为什么需要进程优先级CPU 是一种有限资源。尤其在单核 CPU 中同一时刻只能真正执行一个进程的指令。假设系统中同时存在三个可运行进程进程 A 进程 B 进程 C它们都希望获得 CPU进程 A进程 B进程 CCPU但 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 valuenice 值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-n10./test表示以NI 10启动test。然后ps-l就可以观察该进程的 Nice 值。5.1 修改正在运行的进程对于已经运行的进程可以使用renice例如renice-n10-p4201表示修改 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通过位图相关操作内核可以非常快速地找到最高优先级的非空队列。然后找到队列 ↓ 取出其中的进程 ↓ 交给 CPU14. 为什么叫 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 ActiveActive保存当前拥有时间片可以参与本轮调度的进程。调度器不断从 Active 中选择进程运行。例如Active P1 P2 P3 P4P1 被选中运行。时间片使用完成以后需要重新安排后续运行机会。在简化模型中可以理解为任务会进入Expired15.2 ExpiredExpired 可以理解为已经完成当前一轮时间片需要等待下一轮调度的任务集合。例如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) 调度整体过程把前面的知识串起来可以得到一个简化模型否是可运行进程根据优先级进入 Active 对应队列Bitmap 找到最高优先级非空队列选择一个进程CPU 执行本轮时间片结束重新安排并进入相应队列Active 是否为空继续从 Active 调度交换 Active 与 Expired这张图描述的是为了学习 O(1) 调度思想而进行的简化模型。真实 Linux 2.6 早期 O(1) 调度器还会考虑实时任务动态优先级交互性睡眠时间时间片计算SMP 多 CPU负载均衡等更加复杂的问题。18. O(1) 调度器为什么后来被替换O(1) 调度器虽然拥有非常优秀的常数级调度性能但是随着 Linux 使用场景不断发展也暴露出一些问题。特别是在交互任务公平性调度参数任务行为判断不同负载场景的一致性方面越来越复杂。Linux 后来引入了新的公平调度思想。从 Linux 2.6.23 开始经典 O(1) 普通任务调度器被 CFSCompletely Fair Scheduler完全公平调度器取代。所以需要明确学习 O(1) 调度器是为了理解 Linux 调度器发展历史以及运行队列、优先级数组、时间片等经典调度思想而不是认为现代 Linux 仍然完整使用这套调度模型。19. 进程状态、优先级与调度的关系现在我们终于可以把前面几篇文章串起来。假设系统中存在进程 AR 进程 BR 进程 CS其中A 和 B都处于可运行状态。而C正在睡眠等待事件因此暂时不参与普通 CPU 竞争。调度器会从能够运行的任务中选择下一项任务等待事件进程 AR进程 BR进程 CS运行队列调度器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)指的是核心调度选择操作不会因为系统中进程数量增加而需要遍历所有进程其时间复杂度可以保持常数级。 【Linux】进程优先级
学了进程状态以后我们知道一个进程可能处于R、S、D、T、Z等不同状态。其中处于R状态的进程已经具备运行条件可以被 CPU 调度执行。但是新的问题也随之出现假设此时系统中同时存在大量处于可运行状态的进程进程 AR 进程 BR 进程 CR 进程 DR ...CPU 应该先运行哪一个如果进程 A 比进程 B 更重要操作系统又应该如何体现这种差异这就涉及 Linux 进程管理中的另外两个重要概念进程优先级与进程调度。1. 为什么需要进程优先级CPU 是一种有限资源。尤其在单核 CPU 中同一时刻只能真正执行一个进程的指令。假设系统中同时存在三个可运行进程进程 A 进程 B 进程 C它们都希望获得 CPU进程 A进程 B进程 CCPU但 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 valuenice 值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-n10./test表示以NI 10启动test。然后ps-l就可以观察该进程的 Nice 值。5.1 修改正在运行的进程对于已经运行的进程可以使用renice例如renice-n10-p4201表示修改 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通过位图相关操作内核可以非常快速地找到最高优先级的非空队列。然后找到队列 ↓ 取出其中的进程 ↓ 交给 CPU14. 为什么叫 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 ActiveActive保存当前拥有时间片可以参与本轮调度的进程。调度器不断从 Active 中选择进程运行。例如Active P1 P2 P3 P4P1 被选中运行。时间片使用完成以后需要重新安排后续运行机会。在简化模型中可以理解为任务会进入Expired15.2 ExpiredExpired 可以理解为已经完成当前一轮时间片需要等待下一轮调度的任务集合。例如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) 调度整体过程把前面的知识串起来可以得到一个简化模型否是可运行进程根据优先级进入 Active 对应队列Bitmap 找到最高优先级非空队列选择一个进程CPU 执行本轮时间片结束重新安排并进入相应队列Active 是否为空继续从 Active 调度交换 Active 与 Expired这张图描述的是为了学习 O(1) 调度思想而进行的简化模型。真实 Linux 2.6 早期 O(1) 调度器还会考虑实时任务动态优先级交互性睡眠时间时间片计算SMP 多 CPU负载均衡等更加复杂的问题。18. O(1) 调度器为什么后来被替换O(1) 调度器虽然拥有非常优秀的常数级调度性能但是随着 Linux 使用场景不断发展也暴露出一些问题。特别是在交互任务公平性调度参数任务行为判断不同负载场景的一致性方面越来越复杂。Linux 后来引入了新的公平调度思想。从 Linux 2.6.23 开始经典 O(1) 普通任务调度器被 CFSCompletely Fair Scheduler完全公平调度器取代。所以需要明确学习 O(1) 调度器是为了理解 Linux 调度器发展历史以及运行队列、优先级数组、时间片等经典调度思想而不是认为现代 Linux 仍然完整使用这套调度模型。19. 进程状态、优先级与调度的关系现在我们终于可以把前面几篇文章串起来。假设系统中存在进程 AR 进程 BR 进程 CS其中A 和 B都处于可运行状态。而C正在睡眠等待事件因此暂时不参与普通 CPU 竞争。调度器会从能够运行的任务中选择下一项任务等待事件进程 AR进程 BR进程 CS运行队列调度器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)指的是核心调度选择操作不会因为系统中进程数量增加而需要遍历所有进程其时间复杂度可以保持常数级。