CPU 调度算法是操作系统决定“下一个该让哪个进程/线程占用 CPU”的核心机制，目标是在吞吐量、响应时间、公平性、周转时间之间做权衡。下面按经典到现代、单核到多核的脉络系统梳理。

---

一、基础概念先对齐

• 抢占式 vs 非抢占式
  • 非抢占：进程主动放弃 CPU（阻塞、结束）才调度
  • 抢占：时间片用完或更高优先级到来，强行切走
• 核心评价指标
  • 周转时间（Turnaround）= 完成时间 − 到达时间
  • 带权周转时间 = 周转 / 实际运行时间
  • 响应时间（Response）= 首次获得 CPU 的时间 − 到达时间
  • 等待时间、吞吐量、CPU 利用率

---

二、经典单核调度算法

1. FCFS（First-Come, First-Served，先来先服务）

• 非抢占，按到达顺序排队列
• 优点：简单、公平（表面）
• 缺点：护航效应（一个长作业卡住后面所有短作业）
• 评价：平均等待时间随作业长度方差变大而恶化

2. SJF（Shortest Job First，短作业优先）

• 选“预计运行时间最短”的先跑
• 非抢占版叫 SJF，抢占版叫 SRTF（Shortest Remaining Time First）
• 优点：理论上平均等待时间最优（可证明）
• 缺点：
  • 需要预知运行时间（现实中用历史预测）
  • 长作业可能饥饿

3. 优先级调度（Priority Scheduling）

• 每个进程有优先级，选最高优先级
• 可抢占 / 可非抢占
• 问题：低优先级饥饿
• 解决：老化（Aging）——等待越久优先级动态提升

4. RR（Round Robin，时间片轮转）

• 抢占式，每个进程给固定时间片（如 10ms），用完排到队尾
• 优点：响应快，适合分时系统
• 缺点：时间片太小→上下文切换开销大；太大→退化为 FCFS
• 典型时间片：10~100ms

5. 多级队列（Multi-level Queue）

• 把进程按类型分多个队列（如交互型、批处理）
• 队列间可用固定优先级，队列内用 RR 或 FCFS
• 缺点：不够灵活

6. 多级反馈队列（MLFQ，Multi-level Feedback Queue）

• 现代分时系统基石思想（Linux 早期、BSD 都用过变体）
• 多个优先级队列，新进程进最高优先级队列
• 用完时间片没结束 → 降级；主动阻塞（IO 型）→ 升级或保级
• 自动区分：CPU 密集型（慢慢沉底）vs IO 密集型（保持高优）
• 配合 Aging 防饥饿

---

三、面向“现代系统”的演进

7. CFS（Completely Fair Scheduler，Linux 2.6.23+）

• 不是传统“队列+时间片”，而是红黑树 + 虚拟运行时间（vruntime）
• 谁 vruntime 最小谁跑，保证长期“公平分配 CPU 时间”
• 支持：
  • 优先级权重（nice 值）
  • 组调度（cgroup）
• 抢占点：当前进程 vruntime 领先太多就被切

8. 实时调度（RT）

• POSIX 标准两类
  • SCHED_FIFO：同优先级先到先跑，跑到阻塞/主动放弃
  • SCHED_RR：FIFO + 时间片
• 优先级高于普通进程，用于工业控制、音视频
• EDF（Earliest Deadline First）在实时理论里更优，但工程复杂度高

9. 多核 / NUMA 调度

现代不再是“选一个进程”，而是“选进程 + 选核”：

• 亲和性（Affinity）：尽量不让进程换核，保缓存热度
• 负载均衡：空闲核偷任务（work stealing）
• NUMA 感知：优先调度到就近内存节点的核
• Linux 的 CFS 之上还有 sched_domain 层级均衡

---

四、算法对比速查表

---

五、一个容易踩的坑：优先级反转

高优先级等中优先级占着的锁，中优先级被低优先级挡着——高优反而最晚跑。
解决：优先级继承（PI）、优先级天花板。