14 KiB
好，这个问题你其实已经踩在“操作系统最核心的一条主线”上了——线程调度本质就是：CPU 时间如何被分配。我从你之前问的“线程 / 进程 / 虚拟内存 / 内核”这些点串起来，从底层一步一步讲清楚。
一、从最底层出发：CPU 到底在干嘛？
CPU 在任意时刻只做一件事：
执行某个线程的指令流（instruction stream）
注意几个关键点：
-
CPU 不关心“进程”
-
CPU 不关心“程序”
-
CPU 只认：
- 寄存器状态（context）
- 下一条指令地址（PC / RIP）
所以：
线程 = 可被调度执行的最小单位
二、线程调度的本质
线程调度可以用一句话总结：
操作系统决定：下一刻 CPU 跑哪个线程
这就引出三个核心问题：
- 有哪些线程可以运行？
- 选哪个？
- 怎么切过去？
三、线程的生命周期（调度的基础）
线程在操作系统中通常有几种状态：
┌────────────┐
│ Running │
└─────┬──────┘
│
时间片用完 / 被抢占
↓
┌────────────┐
│ Ready │ ←─────┐
└─────┬──────┘ │
│ │
被调度 │
↓ │
┌────────────┐ │
│ Running │ │
└────────────┘ │
│
┌────────────┐ │
│ Blocked │ ──────┘
└────────────┘
↑
IO / 锁 / 信号量
三个核心状态
- Running：正在 CPU 上执行
- Ready：可以运行，但没轮到 CPU
- Blocked：等资源（IO / 锁 / 信号量）
四、调度发生的时机（非常关键）
调度不是随便发生的，只会在这些点触发：
1. 主动让出 CPU
sleep()wait()- 等锁（mutex）
- 等信号量
👉 进入 Blocked
2. 被动抢占（重点）
- 时间片用完（timer interrupt）
- 更高优先级线程出现
👉 这是“操作系统控制力”的核心
3. 中断/系统调用返回
比如：
- IO 完成
- page fault 处理完
五、调度器内部在干嘛？
调度器核心就是一个函数：
schedule()
它做三件事：
1. 保存当前线程上下文
包括：
- 寄存器（RIP, RSP, 通用寄存器）
- 栈
- CPU 状态
👉 保存到：
task_struct（Linux）
2. 选择下一个线程
从 就绪队列（ready queue） 里选一个
3. 恢复新线程上下文
- 加载寄存器
- 切换栈
- 跳转执行
六、调度算法（怎么选线程）
这是策略层。
1. 先来先服务（FCFS）
简单但有问题：
- 长任务霸占 CPU
- 响应差
2. 时间片轮转（Round Robin）
你最应该掌握的：
- 每个线程分一个时间片（比如 10ms）
- 用完就换
优点：
- 公平
- 简单
问题：
- 上下文切换开销
3. 优先级调度
每个线程有 priority：
- 高优先级先执行
问题：
👉 优先级反转（你后面会遇到）
低优先级线程持锁 → 高优先级线程被阻塞
4. 多级反馈队列（MLFQ）
现代 OS 核心算法之一：
特点：
- 多个队列（不同优先级）
- 新任务优先级高
- CPU 密集型任务会被降级
- IO 密集型任务保持高优先级
👉 目标：
让“交互程序更快响应”
5. Linux 的调度（CFS）
Linux 用的是：
CFS（Completely Fair Scheduler）
核心思想：
每个线程“应该得到公平的 CPU 时间”
实现方式：
-
用红黑树维护
-
每个线程有：
vruntime（虚拟运行时间） -
谁 vruntime 最小 → 选谁
七、上下文切换（Context Switch）
这是性能关键点。
一次切换包括：
保存：
- 寄存器
- 栈指针
- 程序计数器
恢复：
- 新线程所有状态
额外开销：
- TLB flush（可能）
- cache miss
👉 所以：
线程不是越多越好
八、线程 vs 进程调度（你之前问过的点）
相同点：
- 都可以被调度
- 都有 task_struct
不同点：
| 项目 | 线程 | 进程 |
|---|---|---|
| 地址空间 | 共享 | 独立 |
| 切换开销 | 小 | 大 |
| 调度单位 | ✔ | ✔ |
👉 Linux：
调度单位其实统一是 task（轻量级进程）
九、结合你之前的问题：锁 / 信号量 / 管程
调度和同步是强耦合的。
1. mutex（互斥量）
- 拿不到锁 → 线程进入 Blocked
- 调度器切走
2. semaphore（信号量）
- P 操作失败 → Blocked
- V 操作 → 唤醒线程 → 进入 Ready
3. 管程（monitor）
你之前问的那个关键点：
“是不是为了不可中断操作块？”
更准确说：
管程 = 把共享数据 + 操作 + 同步机制打包
它通过：
- 自动加锁
- 条件变量
👉 本质还是：
控制线程什么时候进入 Ready / Blocked
十、一个完整运行例子（你应该重点理解）
假设：
线程 A：计算
线程 B：读磁盘
过程：
- A 运行
- 时间片结束 → A → Ready
- B 被调度
- B 发起 IO → Blocked
- 调度器选 A
- 磁盘完成 → 中断 → B → Ready
- 下一轮调度 → B 运行
👉 核心：
调度器一直在“Ready队列”里选
十一、你需要真正掌握的“本质总结”
我给你压缩成三句话：
1️⃣ 线程调度 = CPU 分配问题
2️⃣ 操作系统通过：
- Ready 队列
- 调度算法
- 上下文切换
来控制执行顺序
3️⃣ 同步原语（mutex / semaphore）
本质就是：
控制线程进入 Ready 还是 Blocked
如果你想继续深入（建议下一步）
你现在这个水平，可以往这三个方向继续挖：
- Linux CFS 源码（vruntime 细节）
- 调度 + 虚拟内存（TLB / cache 影响）
- 用户线程 vs 内核线程调度模型（1:1 / M:N）
如果你愿意，我可以下一步给你画一个：
“Linux 线程从创建 → 调度 → 阻塞 → 唤醒”的完整内核级流程图
那个会直接把你带到“可以看内核源码”的水平。
很好，这一块已经进入“操作系统调度的核心实现层”了。我分三部分讲：
- MLFQ（多级反馈队列）——经典策略模型
- CFS（Linux 完全公平调度）——工程实现
- 上下文切换（Context Switch）——底层机制
尽量做到：不仅知道“是什么”，还知道“为什么这么设计”。
一、MLFQ（Multi-Level Feedback Queue）
1. 设计目标（先抓本质）
MLFQ 要解决的是：
既要高吞吐（CPU利用率高），又要高响应（交互快）
核心矛盾：
- CPU 密集型任务：一直占 CPU
- IO 密集型任务：频繁等待，但需要快速响应
2. 基本结构
MLFQ = 多个优先级队列：
Q0（最高优先级，时间片最短）
Q1
Q2
...
Qn（最低优先级，时间片最长）
特点：
- 越高优先级 → 时间片越短
- 越低优先级 → 时间片越长
3. 五条经典规则（必须掌握）
这是 MLFQ 的“算法本体”。
规则 1：高优先级优先运行
如果 Q0 有任务 → 一定先运行 Q0
规则 2：同级别轮转（RR）
同一队列内部 → Round Robin
规则 3：新任务进入最高优先级
新线程 → Q0
👉 目的：快速响应
规则 4：用完时间片 → 降级
如果线程用完整个时间片 → 降到下一层
👉 推断：
“你是 CPU 密集型任务”
规则 5：周期性提升（避免饿死）
每隔一段时间 → 所有任务提升到最高优先级
👉 解决 starvation
4. 为什么这样设计（关键理解）
MLFQ 本质在做一件事：
用“行为”动态推测线程类型
| 行为 | 推测 |
|---|---|
| 很快放弃 CPU | IO 密集 |
| 一直用满时间片 | CPU 密集 |
5. 一个典型过程（你要能脑补）
情况：
- 线程 A（计算密集）
- 线程 B（频繁 IO）
执行过程：
- A、B 都在 Q0
- A 用满时间片 → 降到 Q1
- B 很快 IO → 留在 Q0
- B 每次都优先执行
👉 结果：
- B 响应快（交互流畅）
- A 慢慢跑（后台任务）
6. MLFQ 的问题
MLFQ 很聪明，但也有问题：
❌ 可被“欺骗”
线程可以：
每次时间片快结束时主动让出 CPU
👉 永远停在高优先级
❌ 参数难调
- 队列数
- 时间片长度
- 提升周期
❌ 不够“精确公平”
只是启发式
二、CFS（Completely Fair Scheduler）
MLFQ 是“经验派”，CFS 是“数学派”。
1. 核心思想
每个线程都应该获得“公平的 CPU 时间”
但现实问题：
- 线程数量不同
- 优先级不同
2. 核心概念：vruntime
每个线程维护一个值：
vruntime = 虚拟运行时间
理解：
“你已经跑了多少 CPU 时间（加权）”
3. 调度规则（极其重要）
总是选择 vruntime 最小的线程运行
👉 直觉：
- 谁“欠 CPU”最多 → 谁先跑
4. vruntime 怎么增长？
不是简单的时间，而是：
vruntime += 实际运行时间 × 权重
权重由 nice 值决定：
| nice | 权重 | 效果 |
|---|---|---|
| 低（-20） | 大 | 跑得慢（不容易涨 vruntime） |
| 高（+19） | 小 | 跑得快（vruntime 快涨） |
👉 结果：
- 高优先级线程 → 更常被调度
5. 数据结构：红黑树（关键）
CFS 用：
红黑树（按 vruntime 排序）
结构：
(最小 vruntime)
↑
root
/ \
... ...
👉 调度就是：
取最左节点（最小 vruntime）
复杂度：
O(log n)
6. 时间片在 CFS 里怎么体现？
CFS 没有“固定时间片”，而是：
调度周期（sched_period）
每个线程分到：
时间 = sched_period / 线程数
👉 线程越多 → 每个时间越短
7. CFS vs MLFQ 本质区别
| 维度 | MLFQ | CFS |
|---|---|---|
| 思想 | 启发式 | 数学公平 |
| 数据结构 | 多队列 | 红黑树 |
| 决策依据 | 行为 | vruntime |
| 可预测性 | 低 | 高 |
| 工程使用 | 教学为主 | Linux 实际使用 |
8. 一个直觉总结
MLFQ：
“我猜你是什么类型任务”
CFS：
“我不猜，我只算你跑了多少”
三、上下文切换（Context Switch）
这是最底层、最硬核的一块。
1. 什么是上下文？
线程的“全部运行状态”：
CPU 上下文
- 通用寄存器（RAX, RBX...）
- 程序计数器（RIP）
- 栈指针（RSP）
- 标志寄存器（EFLAGS）
内存相关
- 页表（CR3）
- 虚拟地址空间
内核数据
- task_struct
- 调度信息
2. 上下文切换发生的完整过程
我给你一个“真实接近内核”的流程：
Step 1：触发调度
来源：
- 时钟中断（最常见）
- 系统调用
- 阻塞操作
Step 2：进入内核态
用户态 → 内核态
发生：
- 保存用户寄存器到内核栈
Step 3：保存当前线程上下文
本质代码类似：
current->thread.sp = rsp;
current->thread.ip = rip;
保存所有寄存器
Step 4：调用调度器
schedule()
选出 next
Step 5：切换地址空间（关键）
如果是不同进程：
切换 CR3（页表基址）
影响：
- TLB 失效（可能 flush）
Step 6：恢复新线程上下文
rsp = next->thread.sp;
rip = next->thread.ip;
恢复寄存器
Step 7：返回用户态
iret / sysret
3. 线程切换 vs 进程切换
线程切换（同进程）
不需要：
- 切换页表
- TLB flush
👉 很快
进程切换
需要：
- 切换 CR3
- 刷新 TLB（或部分失效）
👉 很慢
4. 性能开销在哪里？
主要三块：
1️⃣ 寄存器保存/恢复（小）
几十个寄存器
2️⃣ Cache 失效（大）
新线程：
- L1/L2 cache 不命中
- 指令 cache 失效
3️⃣ TLB 失效（很大）
地址转换缓存失效
👉 结论：
真正慢的不是“切换”，而是“切换后的冷启动”
5. 一个关键理解（很多人忽略）
上下文切换不是“免费暂停”：
它破坏了 CPU 的局部性（locality）
这直接导致：
- cache miss
- pipeline stall
四、把三者串起来（你必须形成这个模型）
调度（MLFQ / CFS）
决定：
选谁运行
上下文切换
负责：
怎么切过去
同步原语（mutex / semaphore）
控制：
谁能进入 Ready
五、最后给你一个“工程级理解”
你现在可以用一句话总结整个调度系统：
操作系统维护一个“可运行线程集合”，用调度算法（CFS）选出“最该运行的线程”，再通过上下文切换把 CPU 从当前线程切到目标线程。
如果你想继续深入（建议）
下一步你可以挑战这些：
- Linux CFS 源码（sched_fair.c）逐行解析
- TLB shootdown 是怎么实现的（多核）
- NUMA 对调度的影响
- 用户级线程（Go / 协程）如何绕开内核调度
如果你想，我可以下一步带你：
“从 Linux 内核源码角度，完整走一遍 schedule()”
这个会直接把你带到“能读内核”的水平。