1. 调度的层次
高级调度（作业调度）：从后备队列选作业调入内存
↓
中级调度（交换调度）：内存紧张时换出/换入进程
↓
低级调度（CPU 调度）：从就绪队列选进程分配 CPU ← 本课重点
1.1 调度时机
- 进程终止
- 进程阻塞（等待 I/O）
- I/O 中断完成
- 时间片用完（抢占式）
- 新进程进入就绪队列（抢占式）
2. 调度算法
2.1 FCFS（先来先服务）
进程 到达时间 执行时间
P1 0 8
P2 1 4
P3 2 9
甘特图： P1(0-8) → P2(8-12) → P3(12-21)
周转时间：P1=8, P2=11, P3=19 平均=12.67
等待时间：P1=0, P2=7, P3=10 平均=5.67
护航效应（Convoy）：长进程阻塞短进程
2.2 SJF（最短作业优先）
非抢占式：选择执行时间最短的进程。
抢占式版本：SRTF（最短剩余时间优先），新到达的更短进程可抢占。
非抢占 SJF：
P1(0,8), P2(1,4), P3(2,9), P4(3,5)
T=0: 只有 P1，执行 P1 → 但 SJF 等待所有到达？
实际：T=0 执行 P1，T=1 P2 到达但 P1 已在执行（非抢占）
抢占 SRTF：
T=0: P1 执行
T=1: P2 到达（剩余 4 < P1 剩余 7），P2 抢占
T=3: P4 到达（剩余 5 < P2 剩余 2），不抢占
T=5: P2 完成，就绪队列 P1(剩余 7), P3(9), P4(5)
选 P4（最短剩余）
平均等待时间 SRTF < SJF < FCFS
2.3 时间片轮转（RR）
时间片 q = 4：
P1(8), P2(4), P3(9)
0-4: P1(剩余4)
4-8: P2(完成)
8-12: P3(剩余5)
12-16: P1(完成)
16-20: P3(剩余1)
20-21: P3(完成)
turnaround: P1=16, P2=7, P3=19 avg=14
时间片选择：
- q 太大 → 退化为 FCFS
- q 太小 → 上下文切换开销大（通常 q = 10-100ms）
2.4 优先级调度
静态优先级：创建时确定，不变
动态优先级：根据运行时间、等待时间等调整
问题：低优先级进程饥饿
解决：老化（Aging），等待时间增加则提升优先级
2.5 多级反馈队列（MLFQ）
队列优先级：Q0 > Q1 > Q2 > ... > Qn
Q0: 时间片 8ms, RR
Q1: 时间片 16ms, RR
Q2: 时间片 32ms, RR
Q3: FCFS
规则：
1. 新进程进入 Q0
2. 用完时间片降级到下一队列
3. 主动让出 CPU（I/O 完成）回到当前队列
4. 优先级高的队列空，才调度低优先级队列
优点：I/O 密集型小任务响应快，CPU 密集型大任务在背后运行
3. Linux CFS（完全公平调度器）
3.1 核心思想
CFS 不使用优先级队列，而是使用红黑树管理所有可运行任务，目标是让每个进程获得公平的 CPU 时间份额。
3.2 虚拟时间（vruntime）
vruntime = 实际运行时间 × 1024 / 进程权重
权重由 nice 值决定（nice -20 ~ 19）：
nice 越小，权重越大，vruntime 增长越慢 → 更容易被调度
权重表（近似 1.25 倍递增）：
nice 0 → 1024
nice 1 → 820
nice -1 → 1277
...
3.3 CFS 调度过程
1. 选择 vruntime 最小的进程运行
2. 运行一段时间后更新 vruntime
3. 如果新进程 vruntime 更小，发生抢占
4. 使用红黑树 O(log n) 查找最小 vruntime
// CFS 核心数据结构（简化）
struct sched_entity {
struct load_weight load; // 权重
struct rb_node run_node; // 红黑树节点
u64 vruntime; // 虚拟运行时间
u64 exec_start; // 本次执行开始时间
// ...
};
struct cfs_rq {
struct rb_root tasks_timeline; // vruntime 红黑树
struct sched_entity *curr; // 当前运行实体
// ...
};
3.4 CFS 时间片计算
targeted_latency = 20ms（可配置，sysctl kernel.sched_latency_ns）
min_granularity = 4ms（最小时间片）
时间片 = targeted_latency / 可运行进程数
如果进程太多导致时间片 < min_granularity：
时间片 = min_granularity
调度周期 = min_granularity × 进程数
4. 多核调度
4.1 亲和性（Affinity）
# 查看进程运行的 CPU
ps -eo pid,comm,psr | grep myapp
# 设置 CPU 亲和性（绑定到 CPU 0 和 1）
taskset -pc 0,1 [pid]
# 代码设置
#include <sched.h>
cpu_set_t cpuset;
CPU_ZERO(&cpuset);
CPU_SET(0, &cpuset);
sched_setaffinity(0, sizeof(cpuset), &cpuset);
4.2 负载均衡
逻辑 CPU 状态：
- CFS 运行队列：每个 CPU 一个
- 任务迁移：从负载重的 CPU 迁移到负载轻的 CPU
负载 = runnable_weight / capacity
触发时机：
- 周期性负载均衡（tick 检查）
- 进程唤醒时（选择最空闲 CPU）
- 创建新进程时
4.3 调度域（Scheduling Domain）
按硬件层级组织调度域：
SMT（超线程）→ MC（多核）→ NUMA 节点 → 系统
每个域内做负载均衡，从低到高逐级检查
5. 调度参数调优
# 查看调度策略
chrt -p [pid] # 实时进程
nice -n 10 cmd # 以 nice 10 运行
renice -n -5 -p [pid] # 调整已运行进程优先级
# CFS 参数
sysctl kernel.sched_latency_ns # 目标延迟（默认 20ms）
sysctl kernel.sched_min_granularity_ns # 最小时间片（默认 4ms）
sysctl kernel.sched_wakeup_granularity_ns # 唤醒抢占粒度
# 实时调度
chrt -f 99 ./realtime_app # FIFO，优先级 99（最高）
chrt -r 50 ./app # RR，优先级 50
| 调度类 | 说明 | 适用场景 |
|---|---|---|
| DL（Deadline） | 最早截止时间优先 | 实时音视频处理 |
| RT（Real-time） | FIFO / RR | 硬实时任务 |
| CFS | 完全公平调度 | 普通用户进程 |
| IDLE | 最低优先级 | 仅在 CPU 空闲时运行 |
参考文章
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。