进程调度原理
进程调度是操作系统的核心功能之一，决定了系统的响应性和公平性。
调度的本质
为什么需要调度
CPU 资源稀缺：
- 进程数量远大于 CPU 核心数
- 需要多个进程"同时"运行（时分复用）
- 调度器决定哪个进程获得 CPU
调度目标：
- 吞吐量：单位时间完成的任务数
- 响应时间：从请求到响应的时间
- 公平性：所有进程获得合理的 CPU 时间
- 优先级：重要任务优先执行
调度时机
非抢占式调度（早期系统）：
- 进程主动放弃 CPU（阻塞或结束）
- 简单但响应慢
- 一个进程可能长期占用 CPU
抢占式调度（现代系统）：
- 时间片用完强制切换
- 高优先级进程抢占低优先级
- 提高响应性和公平性
触发调度的事件：
- 时钟中断（时间片到期）
- 进程阻塞（I/O、睡眠）
- 进程创建或退出
- 优先级变化
- 系统调用返回
经典调度算法
FIFO（先来先服务）
原理：
- 按到达顺序排队
- 最简单的调度算法
优点：
- 实现简单
- 公平（先到先得）
缺点：
- 护航效应（Convoy Effect）
- 长任务阻塞短任务
- 平均等待时间长
SJF（最短作业优先）
原理：
- 选择预计运行时间最短的进程
- 可以是抢占式（SRTF）或非抢占式
优点：
- 最优的平均等待时间（理论上）
缺点：
- 无法准确预测运行时间
- 长任务可能饿死
- 不公平
时间片轮转（Round Robin）
原理：
- 每个进程分配固定时间片（如 10ms）
- 时间片用完放到队尾
- 循环调度
时间片选择：
- 太大：退化为 FIFO，响应慢
- 太小：上下文切换开销大
- 经验值：10-100ms
优点：
- 公平性好
- 响应时间可预测
缺点：
- 不区分优先级
- I/O 密集型进程不利
多级反馈队列
设计思想：
- 多个优先级队列
- 进程根据行为动态调整优先级
- 兼顾响应性和公平性
工作机制：
高优先级队列（时间片小）
↓ 用完时间片降级
中优先级队列（时间片中）
↓ 用完时间片降级
低优先级队列（时间片大）
特点：
- I/O 密集型进程（频繁阻塞）保持高优先级
- CPU 密集型进程逐渐降级
- 防止饿死（老化机制）
Linux CFS 调度器
设计哲学
CFS（Completely Fair Scheduler，完全公平调度器）是 Linux 2.6.23 引入的调度器。
核心思想：
- 理想情况下，每个进程应获得 1/n 的 CPU 时间（n 为进程数）
- 记录每个进程的虚拟运行时间（vruntime）
- 总是选择 vruntime 最小的进程运行
虚拟运行时间（vruntime）
计算公式：
vruntime += 实际运行时间 × (NICE_0_LOAD / 进程权重)
关键概念：
- 实际运行时间：进程在 CPU 上的物理时间
- 进程权重：由 nice 值决定，nice 值越低权重越大
- nice 值：-20（最高优先级）到 19（最低优先级）
示例：
进程 A：nice = 0，权重 = 1024
进程 B：nice = 5，权重 = 335
A 运行 10ms：vruntime += 10ms × (1024/1024) = 10ms
B 运行 10ms：vruntime += 10ms × (1024/335) ≈ 30.6ms
B 的 vruntime 增长更快，下次调度时 A 更可能被选中
红黑树调度队列
为什么用红黑树：
- 需要频繁查找最小 vruntime
- 需要频繁插入和删除
- 红黑树提供 O(log n) 的操作复杂度
工作流程：
- 入队：进程进入就绪态，插入红黑树（按 vruntime 排序）
- 选择：选择最左节点（vruntime 最小）
- 运行：进程运行，vruntime 增加
- 出队：进程阻塞或时间片用完，从树中删除
- 重新入队：进程重新就绪，插入树中
时间片计算
CFS 不使用固定时间片，而是动态计算：
调度周期：
- 所有进程轮流运行一次的时间
- 默认：6ms（进程数 ≤ 8）
- 进程数 > 8：进程数 × 0.75ms
进程时间片：
时间片 = 调度周期 × (进程权重 / 总权重)
最小粒度：
- 保证每次至少运行 1ms（默认）
- 防止时间片过小导致频繁切换
组调度
问题：
- 用户 A：1 个进程
- 用户 B：100 个进程
- 每个进程公平 → 用户 B 获得 100 倍 CPU
解决方案：
- 先在用户组间公平分配
- 再在组内进程间公平分配
层次结构：
总 CPU
├─ 用户 A（50%）
│ └─ 进程 A1（50%）
└─ 用户 B（50%）
├─ 进程 B1（0.5%）
├─ 进程 B2（0.5%）
└─ ... (100个进程)
实时调度
实时进程特点
硬实时：
- 必须在截止时间内完成
- 错过截止时间视为失败
- 例：飞行控制、工业控制
软实时：
- 应尽量在截止时间内完成
- 错过截止时间降低服务质量
- 例：音视频播放
Linux 实时调度策略
SCHED_FIFO：
- 先进先出
- 没有时间片限制
- 运行到完成或阻塞或被更高优先级抢占
SCHED_RR：
- 时间片轮转
- 同优先级进程轮流运行
- 保留抢占特性
SCHED_DEADLINE：
- 基于截止时间调度
- 最复杂但最精确
- 保证任务在截止时间前完成
优先级：
实时进程（优先级 0-99）
↓ 高于
普通进程（优先级 100-139）
多核调度
负载均衡
目标：
- 各 CPU 负载均衡
- 减少进程迁移（缓存友好）
时机：
- 定期检查（tick 中断）
- CPU 空闲时
- fork 新进程时
- exec 执行时
CPU 亲和性
概念：
- 进程倾向于在同一 CPU 上运行
- 提高缓存命中率
设置方式：
- 硬亲和性：强制绑定
- 软亲和性：优先但非强制
应用场景：
- 性能敏感应用
- NUMA 系统优化
- 实时系统
NUMA 感知
NUMA（非一致性内存访问）：
- 每个 CPU 有本地内存
- 访问远程内存更慢
调度策略：
- 优先在进程内存所在节点调度
- 减少跨节点内存访问
- 权衡负载均衡和局部性
调度性能分析
关键指标
延迟（Latency）：
- 进程从就绪到运行的等待时间
- 影响响应性
吞吐量（Throughput）：
- 单位时间完成的任务数
- 影响整体效率
公平性（Fairness）：
- 各进程获得 CPU 时间的偏差
- CFS 的核心目标
性能调优
nice 值调整：
- 降低 nice 值提高优先级
- 适用于关键服务
实时优先级：
- 谨慎使用
- 可能导致系统无响应
CPU 亲和性：
- 绑定关键进程到特定 CPU
- 隔离干扰
cgroup 限制：
- 限制进程组 CPU 使用
- 防止资源垄断
调度器的演进
O(1) 调度器（2.6.0-2.6.22）
特点：
- 常数时间调度（O(1)）
- 两个优先级数组（活动和过期）
- 复杂的启发式规则
问题：
- 交互性判断不准确
- 公平性不佳
- 难以维护
CFS（2.6.23-至今）
改进：
- 简单优雅的设计
- 真正的公平调度
- 更好的交互性
持续优化：
- PELT（Per-Entity Load Tracking）
- 频率和能耗感知调度
- 组调度改进
思考题：
- 为什么 CFS 使用虚拟运行时间而非实际运行时间？
- 实时进程优先级高，为什么不会饿死普通进程？
- 多核系统中，如何平衡负载均衡和缓存局部性？