951 lines
14 KiB
Markdown
951 lines
14 KiB
Markdown
好，这个问题你其实已经踩在“操作系统最核心的一条主线”上了——**线程调度本质就是：CPU 时间如何被分配**。我从你之前问的“线程 / 进程 / 虚拟内存 / 内核”这些点串起来，从底层一步一步讲清楚。
|
||
|
||
---
|
||
|
||
# 一、从最底层出发：CPU 到底在干嘛？
|
||
|
||
CPU 在任意时刻只做一件事：
|
||
|
||
> 执行某个线程的指令流（instruction stream）
|
||
|
||
注意几个关键点：
|
||
|
||
* CPU 不关心“进程”
|
||
* CPU 不关心“程序”
|
||
* CPU 只认：
|
||
|
||
* **寄存器状态（context）**
|
||
* **下一条指令地址（PC / RIP）**
|
||
|
||
所以：
|
||
|
||
> **线程 = 可被调度执行的最小单位**
|
||
|
||
---
|
||
|
||
# 二、线程调度的本质
|
||
|
||
线程调度可以用一句话总结：
|
||
|
||
> **操作系统决定：下一刻 CPU 跑哪个线程**
|
||
|
||
这就引出三个核心问题：
|
||
|
||
1. 有哪些线程可以运行？
|
||
2. 选哪个？
|
||
3. 怎么切过去？
|
||
|
||
---
|
||
|
||
# 三、线程的生命周期（调度的基础）
|
||
|
||
线程在操作系统中通常有几种状态：
|
||
|
||
```
|
||
┌────────────┐
|
||
│ 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：读磁盘
|
||
```
|
||
|
||
过程：
|
||
|
||
1. A 运行
|
||
2. 时间片结束 → A → Ready
|
||
3. B 被调度
|
||
4. B 发起 IO → Blocked
|
||
5. 调度器选 A
|
||
6. 磁盘完成 → 中断 → B → Ready
|
||
7. 下一轮调度 → B 运行
|
||
|
||
👉 核心：
|
||
|
||
> 调度器一直在“Ready队列”里选
|
||
|
||
---
|
||
|
||
# 十一、你需要真正掌握的“本质总结”
|
||
|
||
我给你压缩成三句话：
|
||
|
||
---
|
||
|
||
### 1️⃣ 线程调度 = CPU 分配问题
|
||
|
||
---
|
||
|
||
### 2️⃣ 操作系统通过：
|
||
|
||
* Ready 队列
|
||
* 调度算法
|
||
* 上下文切换
|
||
|
||
来控制执行顺序
|
||
|
||
---
|
||
|
||
### 3️⃣ 同步原语（mutex / semaphore）
|
||
|
||
本质就是：
|
||
|
||
> **控制线程进入 Ready 还是 Blocked**
|
||
|
||
---
|
||
|
||
# 如果你想继续深入（建议下一步）
|
||
|
||
你现在这个水平，可以往这三个方向继续挖：
|
||
|
||
1. **Linux CFS 源码（vruntime 细节）**
|
||
2. **调度 + 虚拟内存（TLB / cache 影响）**
|
||
3. **用户线程 vs 内核线程调度模型（1:1 / M:N）**
|
||
|
||
---
|
||
|
||
如果你愿意，我可以下一步给你画一个：
|
||
|
||
> **“Linux 线程从创建 → 调度 → 阻塞 → 唤醒”的完整内核级流程图**
|
||
|
||
那个会直接把你带到“可以看内核源码”的水平。
|
||
|
||
---
|
||
|
||
很好，这一块已经进入“操作系统调度的核心实现层”了。我分三部分讲：
|
||
|
||
1. **MLFQ（多级反馈队列）——经典策略模型**
|
||
2. **CFS（Linux 完全公平调度）——工程实现**
|
||
3. **上下文切换（Context Switch）——底层机制**
|
||
|
||
尽量做到：不仅知道“是什么”，还知道“为什么这么设计”。
|
||
|
||
---
|
||
|
||
# 一、MLFQ（Multi-Level Feedback Queue）
|
||
|
||
## 1. 设计目标（先抓本质）
|
||
|
||
MLFQ 要解决的是：
|
||
|
||
> **既要高吞吐（CPU利用率高），又要高响应（交互快）**
|
||
|
||
核心矛盾：
|
||
|
||
* CPU 密集型任务：一直占 CPU
|
||
* IO 密集型任务：频繁等待，但需要快速响应
|
||
|
||
---
|
||
|
||
## 2. 基本结构
|
||
|
||
MLFQ = 多个优先级队列：
|
||
|
||
```text
|
||
Q0（最高优先级，时间片最短）
|
||
Q1
|
||
Q2
|
||
...
|
||
Qn（最低优先级，时间片最长）
|
||
```
|
||
|
||
特点：
|
||
|
||
* 越高优先级 → 时间片越短
|
||
* 越低优先级 → 时间片越长
|
||
|
||
---
|
||
|
||
## 3. 五条经典规则（必须掌握）
|
||
|
||
这是 MLFQ 的“算法本体”。
|
||
|
||
---
|
||
|
||
### 规则 1：高优先级优先运行
|
||
|
||
```text
|
||
如果 Q0 有任务 → 一定先运行 Q0
|
||
```
|
||
|
||
---
|
||
|
||
### 规则 2：同级别轮转（RR）
|
||
|
||
```text
|
||
同一队列内部 → Round Robin
|
||
```
|
||
|
||
---
|
||
|
||
### 规则 3：新任务进入最高优先级
|
||
|
||
```text
|
||
新线程 → Q0
|
||
```
|
||
|
||
👉 目的：快速响应
|
||
|
||
---
|
||
|
||
### 规则 4：用完时间片 → 降级
|
||
|
||
```text
|
||
如果线程用完整个时间片 → 降到下一层
|
||
```
|
||
|
||
👉 推断：
|
||
|
||
> “你是 CPU 密集型任务”
|
||
|
||
---
|
||
|
||
### 规则 5：周期性提升（避免饿死）
|
||
|
||
```text
|
||
每隔一段时间 → 所有任务提升到最高优先级
|
||
```
|
||
|
||
👉 解决 starvation
|
||
|
||
---
|
||
|
||
## 4. 为什么这样设计（关键理解）
|
||
|
||
MLFQ 本质在做一件事：
|
||
|
||
> **用“行为”动态推测线程类型**
|
||
|
||
| 行为 | 推测 |
|
||
| -------- | ------ |
|
||
| 很快放弃 CPU | IO 密集 |
|
||
| 一直用满时间片 | CPU 密集 |
|
||
|
||
---
|
||
|
||
## 5. 一个典型过程（你要能脑补）
|
||
|
||
### 情况：
|
||
|
||
* 线程 A（计算密集）
|
||
* 线程 B（频繁 IO）
|
||
|
||
---
|
||
|
||
### 执行过程：
|
||
|
||
1. A、B 都在 Q0
|
||
2. A 用满时间片 → 降到 Q1
|
||
3. B 很快 IO → 留在 Q0
|
||
4. B 每次都优先执行
|
||
|
||
👉 结果：
|
||
|
||
* B 响应快（交互流畅）
|
||
* A 慢慢跑（后台任务）
|
||
|
||
---
|
||
|
||
## 6. MLFQ 的问题
|
||
|
||
MLFQ 很聪明，但也有问题：
|
||
|
||
---
|
||
|
||
### ❌ 可被“欺骗”
|
||
|
||
线程可以：
|
||
|
||
```c
|
||
每次时间片快结束时主动让出 CPU
|
||
```
|
||
|
||
👉 永远停在高优先级
|
||
|
||
---
|
||
|
||
### ❌ 参数难调
|
||
|
||
* 队列数
|
||
* 时间片长度
|
||
* 提升周期
|
||
|
||
---
|
||
|
||
### ❌ 不够“精确公平”
|
||
|
||
只是启发式
|
||
|
||
---
|
||
|
||
# 二、CFS（Completely Fair Scheduler）
|
||
|
||
MLFQ 是“经验派”，CFS 是“数学派”。
|
||
|
||
---
|
||
|
||
## 1. 核心思想
|
||
|
||
> **每个线程都应该获得“公平的 CPU 时间”**
|
||
|
||
但现实问题：
|
||
|
||
* 线程数量不同
|
||
* 优先级不同
|
||
|
||
---
|
||
|
||
## 2. 核心概念：vruntime
|
||
|
||
每个线程维护一个值：
|
||
|
||
```text
|
||
vruntime = 虚拟运行时间
|
||
```
|
||
|
||
理解：
|
||
|
||
> “你已经跑了多少 CPU 时间（加权）”
|
||
|
||
---
|
||
|
||
## 3. 调度规则（极其重要）
|
||
|
||
```text
|
||
总是选择 vruntime 最小的线程运行
|
||
```
|
||
|
||
👉 直觉：
|
||
|
||
* 谁“欠 CPU”最多 → 谁先跑
|
||
|
||
---
|
||
|
||
## 4. vruntime 怎么增长？
|
||
|
||
不是简单的时间，而是：
|
||
|
||
```text
|
||
vruntime += 实际运行时间 × 权重
|
||
```
|
||
|
||
权重由 nice 值决定：
|
||
|
||
| nice | 权重 | 效果 |
|
||
| ------ | -- | ------------------ |
|
||
| 低（-20） | 大 | 跑得慢（不容易涨 vruntime） |
|
||
| 高（+19） | 小 | 跑得快（vruntime 快涨） |
|
||
|
||
👉 结果：
|
||
|
||
* 高优先级线程 → 更常被调度
|
||
|
||
---
|
||
|
||
## 5. 数据结构：红黑树（关键）
|
||
|
||
CFS 用：
|
||
|
||
```text
|
||
红黑树（按 vruntime 排序）
|
||
```
|
||
|
||
结构：
|
||
|
||
```text
|
||
(最小 vruntime)
|
||
↑
|
||
root
|
||
/ \
|
||
... ...
|
||
```
|
||
|
||
👉 调度就是：
|
||
|
||
```text
|
||
取最左节点（最小 vruntime）
|
||
```
|
||
|
||
复杂度：
|
||
|
||
```text
|
||
O(log n)
|
||
```
|
||
|
||
---
|
||
|
||
## 6. 时间片在 CFS 里怎么体现？
|
||
|
||
CFS 没有“固定时间片”，而是：
|
||
|
||
```text
|
||
调度周期（sched_period）
|
||
```
|
||
|
||
每个线程分到：
|
||
|
||
```text
|
||
时间 = 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：进入内核态
|
||
|
||
```text
|
||
用户态 → 内核态
|
||
```
|
||
|
||
发生：
|
||
|
||
* 保存用户寄存器到内核栈
|
||
|
||
---
|
||
|
||
### Step 3：保存当前线程上下文
|
||
|
||
本质代码类似：
|
||
|
||
```c
|
||
current->thread.sp = rsp;
|
||
current->thread.ip = rip;
|
||
保存所有寄存器
|
||
```
|
||
|
||
---
|
||
|
||
### Step 4：调用调度器
|
||
|
||
```c
|
||
schedule()
|
||
```
|
||
|
||
选出 next
|
||
|
||
---
|
||
|
||
### Step 5：切换地址空间（关键）
|
||
|
||
如果是不同进程：
|
||
|
||
```text
|
||
切换 CR3（页表基址）
|
||
```
|
||
|
||
影响：
|
||
|
||
* TLB 失效（可能 flush）
|
||
|
||
---
|
||
|
||
### Step 6：恢复新线程上下文
|
||
|
||
```c
|
||
rsp = next->thread.sp;
|
||
rip = next->thread.ip;
|
||
恢复寄存器
|
||
```
|
||
|
||
---
|
||
|
||
### Step 7：返回用户态
|
||
|
||
```text
|
||
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）
|
||
|
||
决定：
|
||
|
||
```text
|
||
选谁运行
|
||
```
|
||
|
||
---
|
||
|
||
## 上下文切换
|
||
|
||
负责：
|
||
|
||
```text
|
||
怎么切过去
|
||
```
|
||
|
||
---
|
||
|
||
## 同步原语（mutex / semaphore）
|
||
|
||
控制：
|
||
|
||
```text
|
||
谁能进入 Ready
|
||
```
|
||
|
||
---
|
||
|
||
# 五、最后给你一个“工程级理解”
|
||
|
||
你现在可以用一句话总结整个调度系统：
|
||
|
||
> 操作系统维护一个“可运行线程集合”，用调度算法（CFS）选出“最该运行的线程”，再通过上下文切换把 CPU 从当前线程切到目标线程。
|
||
|
||
---
|
||
|
||
# 如果你想继续深入（建议）
|
||
|
||
下一步你可以挑战这些：
|
||
|
||
1. **Linux CFS 源码（sched_fair.c）逐行解析**
|
||
2. **TLB shootdown 是怎么实现的（多核）**
|
||
3. **NUMA 对调度的影响**
|
||
4. **用户级线程（Go / 协程）如何绕开内核调度**
|
||
|
||
---
|
||
|
||
如果你想，我可以下一步带你：
|
||
|
||
> **“从 Linux 内核源码角度，完整走一遍 schedule()”**
|
||
|
||
这个会直接把你带到“能读内核”的水平。
|
||
|
||
---
|
||
|