观众老爷们大家好 这里是邪修KING的独家频道本文属于系列Linux系统篇 ——操作指令一起学Linux的小伙伴可订阅专栏 Linux系统篇上一篇我们讲透了进程上下文切换的完整流程。切换谁、选哪个进程上 CPU这件事由调度器决定。早期 Linux 调度器很简单所有就绪进程放一个链表每次调度遍历整个链表找优先级最高的。进程少还好进程多了每次调度都要遍历一遍复杂度 O (n)调度越来越慢。于是经典的O (1) 调度算法横空出世无论系统里有多少个进程选择下一个进程的时间永远是固定的不随进程数增长而变慢。本篇我们从 O (n) 的痛点讲起一步步拆解位图优化、优先级数组、活跃 / 过期双队列设计彻底搞懂 O (1) 的核心精髓。一、进程调度的核心诉求与优先级数组1.1 调度的核心工作调度器的核心任务只有一个从就绪队列里选出下一个应该上 CPU 运行的进程。评判调度器好不好两个关键指标调度速度选下一个进程要多久公平性会不会有进程饿死响应及不及时1.2 为什么要有进程优先级进程不是人人平等的。比如交互程序点击鼠标、打字需要快速响应优先级要高后台编译、下载可以慢一点优先级低。Linux 给每个进程分配了优先级调度器优先选高优先级的进程。1.2.1 区分优先级与权限很多人混淆优先级和权限优先级调度层面的决定进程能不能抢到 CPU 时间权限系统资源层面的决定能不能访问文件、能不能执行特权操作root 用户的进程权限高但不代表优先级一定高普通用户也可以把自己进程的优先级调高调低在允许范围内。1.2.2 UID 与优先级无关UID 是用户 ID是权限标识和调度优先级是两个维度。root 可以调整进程优先级到更高范围但不是 root 进程就一定优先级高。1.3 进程优先级的正面作用高优先级进程获得更多 CPU 时间响应更快重要任务优先执行保证核心业务体验低优先级后台任务闲时运行充分利用 CPU1.4 Linux 下查看进程优先级1.4.1 使用 ps -l 命令查看ps -l输出里两个核心指标PRI进程最终优先级数值越小优先级越高NINice 值用户可以调整的友好值范围 - 20 到 19越小优先级越高1.4.2 核心指标PRI 与 NI最终优先级 基础优先级 Nice 值偏移。Nice 值是用户能控制的部分Nice-20最高优先级加成Nice0默认Nice19最低优先级1.5 进程优先级的计算公式Linux 优先级是动态计算的不是固定值。调度器会根据进程的行为动态调整总是睡觉的 IO 密集型进程自动提升优先级因为它平时不占 CPU响应要快一直死循环的 CPU 密集型进程自动降低优先级因为它一直占 CPUNice 值是用户设定的基准偏移在动态计算的基础上叠加。1.6 Nice 值的取值范围与限制原因Nice 值范围是-20 到 19共 40 档。为什么范围这么小因为优先级分档太多的话调度复杂度上升且差别太小没意义。40 档足够区分不同类型的进程了。普通用户只能调大 Nice 值降低优先级不能调小提升优先级防止普通用户把自己进程调最高霸占 CPU。root 用户可以调整全范围。1.7 优先级修改方法1.7.1 命令行工具nice启动程序时指定 Nice 值nice -n -5 ./myprocess # 启动时设置Nice为-5renice修改已经运行的进程的 Nice 值renice -10 -p 进程PID1.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 硬件有专门的指令bsfBit 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 变 BB 变 A开始下一轮。3.5 完整流转梳理初始所有进程分配好时间片全部放入活跃数组调度器从活跃数组选最高优先级进程运行进程时间片用完移出活跃数组加入过期数组活跃数组不为空回到步骤 2 继续活跃数组空了交换活跃和过期数组指针开始新一轮3.6 设计优势保证公平每一轮所有进程都跑完才开始下一轮不会有进程永远轮不到性能恒定所有操作都是 O (1)不随进程数增加变慢支持动态优先级每一轮重新计算时间片和优先级灵活调整四、周边问题4.1 新进程来了怎么办新创建的进程直接放到过期数组里等当前轮结束下一轮再参与调度。好处不打乱当前轮的秩序保证当前轮所有进程公平跑完新进程不会一进来就抢占避免调度抖动。4.2 调度队列其他元素每个 CPU 都有自己独立的调度队列runqueue。多核系统里每个 CPU 自己调度自己的队列不用全局抢锁减少竞争提升多核性能。每个 runqueue 里就是一个活跃优先级数组一个过期优先级数组对应的位图调度相关统计信息4.3 优先级与调度算法的关系优先级决定了进程在哪个优先级队列决定了被选中的先后调度算法O (1决定了怎么高效选出最高优先级的进程优先级是规则调度算法是高效执行规则的方法。五、O (1) 调度的核心设计总结表格设计点作用复杂度按优先级分队列同优先级排队优先级之间独立-位图 bitmap标记哪个优先级有进程bsf 指令快速找最高优先级O(1)活跃 过期双数组保证每轮公平防止饥饿O (1) 指针交换每个 CPU 独立 runqueue减少多核锁竞争提升并行性-O (1) 调度的精髓就是用空间换时间用分组、位图、双队列的设计把调度操作从 O (n) 降到 O (1)让 Linux 在大负载、多进程场景下调度性能依然稳定。补充O (1) 是 Linux 2.6 内核的经典调度器。后来的 CFS 完全公平调度是更现代的调度器但 O (1) 里的位图、双队列、每 CPU 队列等设计思想依然是调度算法的经典也是理解现代调度的基础。全文总结调度核心从就绪进程里选下一个上 CPU核心是速度和公平。优先级进程调度的权重Nice 值用户可调最终优先级动态计算。O (n) 痛点遍历链表选最高优先级进程越多越慢。位图优化按优先级分队列位图标记非空队列硬件 bsf 指令找最高优先级O (1) 选出。活跃 / 过期双队列每轮跑完交换指针保证公平防止饥饿交换 O (1)。每 CPU 队列多核独立调度减少锁竞争提升性能。