Appearance
进程调度：算法与评价指标
一句话总览：调度器（scheduler）决定「CPU 下一个给谁用、用多久」。面试考点集中在三块：评价指标的定义与手工计算、各算法的推演（平均周转/等待时间）、以及「为什么通用 OS 最终落在多级反馈队列 / CFS」。
一、为什么需要调度
- CPU 是独占且稀缺的资源，同一时刻一个核只能跑一个线程。
- 程序分为 CPU 密集型（长时间计算）与 IO 密集型（频繁等待 IO）；若无调度，一个死循环即可独占 CPU，其余进程全部饿死。
- 调度要同时满足互相冲突的目标：公平、响应快（交互式）、吞吐高（批处理）、实时性（不超截止期）。冲突的存在正是算法多样性的根源。
按层次划分调度：
| 层次 | 别称 | 作用 | 发生频率 |
|---|---|---|---|
| 高级调度 | 作业调度 | 从外存后备队列选作业调入内存 | 低 |
| 中级调度 | 内存调度 | 挂起 / 激活进程，配合换页 | 中 |
| 低级调度 | 进程调度 | 从就绪队列选进程占用 CPU | 高（最核心） |
二、调度时机与进程切换
调度发生的时机（低级调度）：
- 进程主动放弃 CPU：运行结束（终止）、请求 IO / 等待资源（阻塞）、主动 yield。
- 进程被动失去 CPU：时间片耗尽、更高优先级进程就绪、被更高优先级中断抢占。
据此分两类：
- 非抢占式（non-preemptive）：只在前一进程主动让出时才切换。实现简单、开销小，但一个长作业会拖垮响应。
- 抢占式（preemptive）：可由时钟中断等强制剥夺。响应好，是现代通用 OS 的主流，代价是切换开销与同步复杂度。
进程切换的时机点：只有在内核态才可以切换；且不能任意时刻切换——处于内核临界区（持自旋锁）、中断处理上半部时通常不可抢占，否则会破坏内核数据结构。
Q1. 进程切换具体做了什么？开销来自哪里？
答案
切换 = 保存旧进程的上下文 + 恢复新进程的上下文：
- 保存/恢复寄存器组（PC、SP、通用寄存器、PSW）到/从 PCB；
- 切换栈（用户栈 / 内核栈）与地址空间：换页表（
CR3），若启用 PCID/ASID 可避免全量 TLB 失效，否则 TLB 被刷新； - 刷新 CPU 缓存带来 cache / TLB 冷启动，这部分隐式开销往往比显式寄存器保存大得多。
因此线程切换（同进程，仅换寄存器+栈，共享地址空间）远便宜于进程切换（还要换页表、刷 TLB）。量化大约：进程切换数微秒，线程切换不足一微秒，协程切换百纳秒级。
三、评价指标
设进程 i 的到达时刻为 A_i、服务（运行）时间为 S_i、完成时刻为 C_i。
| 指标 | 定义 | 说明 |
|---|---|---|
| CPU 利用率 | 忙碌时间 / 总时间 | 越高越好 |
| 吞吐量 | 单位时间完成的进程数 | 批处理关注 |
| 周转时间 | C_i − A_i | 从提交到完成的总耗时 |
| 带权周转时间 | (C_i − A_i) / S_i | 越大说明等得越久 |
| 等待时间 | 周转时间 − 服务时间 | 在就绪队列里干等的时间 |
| 响应时间 | 首次获得 CPU 时刻 − A_i | 交互式关注 |
易错点：等待时间不包含 IO 阻塞和运行时间，只算就绪队列中的排队；周转时间则包含一切。做题时先画甘特图，再逐个填 C_i。
四、经典调度算法
下面统一用一组例子推演：P1、P2、P3 都在 0 时刻到达，服务时间分别为 24, 3, 3。
Q2. FCFS（先来先服务）？
答案
按到达顺序排队，非抢占。
甘特图：P1[0,24] → P2[24,27] → P3[27,30]
| 进程 | 完成 | 周转 | 等待 |
|---|---|---|---|
| P1 | 24 | 24 | 0 |
| P2 | 27 | 27 | 24 |
| P3 | 30 | 30 | 27 |
平均周转 = 27，平均等待 = 17。结论：实现最简单，但对短作业极不友好（护航效应，convoy effect）——一个长作业堵住后面所有短作业。
Q3. SJF / SPF（短作业优先）？
答案
每次选服务时间最短的就绪进程。非抢占版称 SJF/SPF（可抢占版见 SRTN）。
甘特图：P2[0,3] → P3[3,6] → P1[6,30]
| 进程 | 完成 | 周转 | 等待 |
|---|---|---|---|
| P2 | 3 | 3 | 0 |
| P3 | 6 | 6 | 3 |
| P1 | 30 | 30 | 6 |
平均周转 = 13，平均等待 = 3。结论：在非抢占且所有作业同时到达时，SJF 的平均等待时间理论最短（可证明：交换任意相邻逆序对不增等待）。缺陷：需要预知运行时间（现实中只能靠历史估计），且长作业可能饿死。
Q4. SRTN（最短剩余时间优先）？
答案
SJF 的抢占版本：新进程到达时，若其服务时间小于当前进程的剩余时间，则抢占。
例：P1 0 到服务 8；P2 1 到服务 4。t=1 时 P1 剩 7，P2 只需 4 → 抢占 P2，P2 于 t=5 完成，再回来跑 P1 剩余 7 → t=12 完成。相比非抢占，响应更好，但抢占开销与实现复杂度上升，同样会饿死长作业。
Q5. RR（时间片轮转）？
答案
就绪队列按 FCFS，每个进程最多跑一个时间片 q，用完放回队尾。抢占式。
以上例、q=4 推演：P1[0,4] → P2[4,7] → P3[7,10] → P1[10,30]（P2、P3 各 3 就够，P1 还需 20 继续跑）。
| 进程 | 完成 | 周转 | 等待 |
|---|---|---|---|
| P1 | 30 | 30 | 6 |
| P2 | 7 | 7 | 4 |
| P3 | 10 | 10 | 7 |
平均周转 ≈ 15.7，平均等待 ≈ 5.7。时间片权衡：
q过大 → 退化成 FCFS，响应变差；q过小 → 切换开销占比高，吞吐下降；- 经验值：
q略大于一次典型交互/上下文切换成本的量级，通常为 10~100 ms，且应使多数进程在一个时间片内完成。
Q6. 优先级调度与「饿死 / 老化」？
答案
给每个进程一个优先级，每次选最高优先级（可分抢占/非抢占）。问题：低优先级进程可能永远得不到 CPU（饥饿 / 饿死）。
对策 老化（aging）：等待越久优先级越高，最终必然被调度到。另一个技巧是优先级反转问题——用优先级继承 / 优先级天花板缓解（如 Mars Pathfinder 事件）。
Q7. HRRN（高响应比优先）？
答案
响应比 R = (等待时间 + 服务时间) / 服务时间 = 1 + 等待时间/服务时间，每次选 R 最大者，非抢占。
它折中了 FCFS（R 随等待增长）与 SJF（短作业 R 天生大）：既照顾短作业，又让等待久的作业随等待时间上升而被选中，缓解饿死。缺点是需要计算响应比，且仍需预知服务时间。
Q8. 多级队列（Multilevel Queue）？
答案
把就绪队列静态划分为多个队列（如系统进程、交互进程、批处理），队列间有固定优先级或按比例分配时间；队内可用 RR 或 FCFS。
局限：进程固定在某个队列，不能动态迁移，灵活性差 → 演进为多级反馈队列。
Q9. 多级反馈队列 MLFQ——为什么它兼顾响应与吞吐？ ⭐
答案
MLFQ 用多级优先级队列 + 动态调整优先级来近似 SJF，无需预知运行时间。经典规则：
- 优先级高的队列先运行（不能跨级抢占低优当前运行者则用规则 4 处理）。
- 同一队列内部按 RR 轮转。
- 新进程进入最高优先级（假设是短作业 / 交互式）。
- 进程用完了整个时间片仍未阻塞（说明是 CPU 密集型）→ 降一级；若在时间片内主动让出（IO 等待）→ 留在原级。
- 经过一个周期
S，把所有进程提升回最高优先级（防止饿死 + 适应行为变化）。 - （工程优化）改用配额记账防止进程通过「每片快用完时故意让出 IO」来骗优先级。
为何兼顾：短作业 / 交互进程在高层用很小的片即完成，响应快；长作业逐步下沉到低层、用越来越大的时间片，调度切换少、吞吐高。这正是「学习式 SJF」——用运行行为反推作业长短。
Q10. Linux CFS（完全公平调度）？
答案
CFS 摒弃固定时间片，追求公平：引入虚拟运行时间 vruntime，每个进程按权重分摊 CPU。
text
vruntime += 实际运行时间 * (NICE_0_LOAD / weight)- 红黑树按
vruntime排序，每次取最左（最小vruntime）者运行，保证「谁欠得多谁先跑」。 - 权重来自
nice值（每级差约 1.25 倍），nice越低权重越大、vruntime增长越慢、分到的 CPU 越多。 - 目标调度延迟
sched_latency（默认约 6ms）在所有可运行进程间按权重分配时间片，并有min_granularity下限防止片太小。 - 新进程 / 唤醒进程的
vruntime会被设到min_vruntime附近并做上下限约束，防止它长期霸占或长期饥饿。
更新：新内核（6.6+）用 EEVDF 取代纯 CFS，思想仍是按权重公平 + 虚拟时间，但改良了延迟敏感任务的唤醒抢占。
五、实时调度
实时任务分硬实时（必须满足截止期，如飞控）与软实时（尽量满足，如音视频）。
Q11. RM 与 EDF？
答案
设周期任务 i 的执行时间 C_i、周期/截止期 D_i = P_i。
- RM（Rate Monotonic，速率单调）：静态优先级，周期越短优先级越高。对固定优先级是最优的。可调度充分条件：
Σ(C_i / P_i) ≤ n·(2^(1/n) − 1)（n→∞时收敛到约 0.693）；不满足时不一定不可调度，需精确分析。 - EDF（Earliest Deadline First，最早截止优先）：动态优先级，每次选截止期最近者。对动态优先级是最优的，可调度充要条件：
Σ(C_i / P_i) ≤ 1（利用率不超 100%）。
对比：RM 实现简单、稳定、易分析，利用率上限偏低；EDF 利用率可达 100%，但实现复杂、且过载时（利用率突然超 1）表现会雪崩式退化。
六、多处理器调度简介
- 负载均衡：周期性把任务从忙核迁移到闲核——推迁移（push migration，内核主动搬）与拉迁移（pull migration，空闲核来抢任务）。
- 处理器亲和性（affinity）：尽量让任务固定在同一个核上跑，保住其 cache / TLB 命中（软亲和）；硬亲和可通过
sched_setaffinity绑定。 - NUMA 架构：跨节点访问内存更慢，调度需尽量「就近」，避免跨节点迁移带来的远端内存延迟。
- 工作窃取（work stealing）：每核维护自己的就绪队列，空闲核从别人的队尾偷任务——减少锁竞争、天然负载均衡，见 C++ 线程池 / TBB / Go runtime。
- 组调度 / 并行度控制：如
cgroupCPU 配额、gang scheduling，保证相关线程同时上核。
七、高频 Q&A
Q12. SJF 的「平均等待时间最短」成立条件？
答案
仅在 非抢占 + 所有作业同时到达 时严格成立。若作业陆续到达，最短平均等待由 SRTN（抢占式） 达成（如 §Q4：P1 会被 P2 抢占）。
Q13. 为什么时间片不能太小也不能太大？
答案
太小 → 上下文切换的固定开销（保存寄存器、换栈、cache 冷启动）占比过高，有效吞吐下降；太大 → 退化为 FCFS，交互响应变差。理想 q 使上下文切换开销占总时间一小部分（经验上 < 1%），并让多数进程在一个片内完成。
Q14. 抢占式调度会带来什么麻烦？
答案
需保证被抢占点的内核数据结构一致：因此在持有自旋锁的临界区、中断上下文不可抢占。多核下还要处理优先级反转、锁竞争、缓存一致性等问题。