CPU 调度算法：从 FCFS 到 CFS 完全公平调度器

CPU 调度是操作系统最核心的职责之一。它决定了哪个进程在何时使用 CPU，直接影响系统的响应速度、吞吐量和用户体验。本文从经典算法讲起，逐步深入到 Linux CFS 的设计与实现，并覆盖多处理器负载均衡、实时调度和前沿趋势。

一、调度基础

1.1 为什么需要 CPU 调度

在多道程序环境下，CPU 必须在多个进程之间切换。调度器的目标是：

• 最大化 CPU 利用率：减少空闲时间
• 保证公平性：每个进程都能获得合理的 CPU 时间
• 满足交互需求：用户输入需要快速响应
• 优化系统吞吐：单位时间内完成更多任务

1.2 调度评价指标

不同场景优先级不同：批处理系统关注吞吐量和周转时间；交互式系统关注响应时间。

1.3 抢占式 vs 非抢占式

• 非抢占式：进程一旦获得 CPU，会一直运行到完成或主动放弃（如 I/O 请求）
• 抢占式：调度器可以中断正在运行的进程，将 CPU 分配给更高优先级的进程

现代操作系统几乎都采用抢占式调度，以支持实时响应和多任务的公平性。

二、经典调度算法

2.1 FCFS（先来先服务）

最简单的非抢占式算法，按进程到达顺序执行。

示例：P1( burst=24 )、P2( burst=3 )、P3( burst=3 )，到达顺序为 P1、P2、P3

Gantt 图：
| P1           | P2  | P3  |
0              24    27    30

等待时间：P1=0, P2=24, P3=27；平均等待时间 = (0+24+27)/3 = 17

如果顺序变为 P2、P3、P1，平均等待时间变为 (0+3+6)/3 = 3。这就是 护航效应（Convoy Effect）：长进程阻塞了后面的短进程，导致资源利用率低下。

2.2 SJF（短作业优先）

选择 burst time 最短的进程执行，可证明它是最优的平均等待时间算法。

上述例子按 SJF 调度：

Gantt 图：
| P2  | P3  | P1           |
0     3     6              30

平均等待时间 = (0+3+6)/3 = 3。

问题：需要预知 burst time，实际中不可行。常用指数平均法进行估计：

// 指数平均预测
预测值 = α * 实际上次CPU时间 + (1-α) * 上次预测值

但 SJF 仍是非抢占式的。

2.3 SRTF（最短剩余时间优先）

SJF 的抢占式版本。新进程到达时，如果其 burst time 比当前进程的剩余时间更短，则抢占 CPU。

示例：P1(到达0, burst=8)、P2(到达1, burst=4)、P3(到达2, burst=9)、P4(到达3, burst=5)

Gantt 图：
| P1 | P2    | P4   | P1    | P3        |
0    1       5      10      17          26

平均等待时间 = (10-0-8 + 1-1 + 17-2-9 + 5-3-5)/4 = (2+0+6+(-3))/4 = 1.25

2.4 优先级调度

每个进程分配一个优先级数字，调度器总是选择优先级最高的进程。

饥饿问题：低优先级进程可能永远无法获得 CPU。

老化（Aging）：逐渐增加等待时间长的进程的优先级，防止无限期饥饿。

// 老化公式示例：等待时间越长，优先级越高
新优先级 = 原优先级 + 等待时间 / 阈值;

2.5 RR（时间片轮转）

专为分时系统设计。每个进程获得一个时间片（time quantum），用完则排到队列末尾。

示例：P1(burst=24), P2(burst=3), P3(burst=3)，时间片=4

Gantt 图：
| P1 | P2 | P3 | P1 | P1 | P1 | P1 | P1 | P1 |
0    4    7    10   14   18   22   26   30

时间片选取：

• 太长（如无穷大）→ 退化为 FCFS
• 太短（如 1ms）→ 上下文切换开销过大
• 经验值：通常设置为稍大于典型交互式任务所需时间

2.6 多级队列（Multilevel Queue）

将就绪队列划分为多个独立队列，例如：

• 前台队列（交互式）：RR 调度
• 后台队列（批处理）：FCFS 调度

进程固定属于某个队列，不可移动。队列之间也要有调度策略（如固定优先级、时间片比例）。

2.7 多级反馈队列（Multilevel Feedback Queue, MFQ）

最通用的调度算法，允许进程在队列之间移动。特点：

• 新进程进入最高优先级队列
• 用完时间片 → 降一级队列
• 主动放弃 CPU（如 I/O）→ 保持在原队列或升一级
• 低优先级队列通常时间片更长

Windows 调度器就是基于优先级的多级反馈队列实现。

三、Linux CFS 完全公平调度器

从 Linux 2.6.23 开始，CFS 取代了 O(1) 调度器，成为默认的通用调度器。

3.1 设计哲学

CFS 追求比例公平（proportional fairness）：理想情况下，n 个可运行进程，每个进程在任意时间段内应该获得 1/n 的 CPU 时间。

CFS 不使用固定时间片，而是追踪每个进程的虚拟运行时间（vruntime），总是选择 vruntime 最小的进程执行。

3.2 vruntime 概念

vruntime += 实际运行时间 * (调度粒度 / 进程权重)

权重由 nice 值决定。

3.3 红黑树实现

CFS 使用红黑树（rb_tree）维护可运行进程，按键为 vruntime：

• 插入/删除：O(log n)
• 选择下一进程：总是取最左节点，O(1)（通过缓存 leftmost 指针）

// kernel/sched/fair.c 简化示意
struct sched_entity {
    struct rb_node     run_node;
    u64                vruntime;
    u64                exec_start;
    unsigned long      load_weight;
    // ...
};

3.4 nice 值与权重映射

nice 值范围 [-20, 19]，nice 越小优先级越高。CFS 将 nice 映射为一个权重数组：

// kernel/sched/core.c 中的 sched_prio_to_weight[]
// nice 0 → 权重 1024（基准值）
// nice -1 → 权重 1277（约 1.25x 基准）
// nice +1 → 权重 820（约 0.8x 基准）

每差一个 nice 级别，CPU 份额相差约 10%。nice -20 的进程获得的 CPU 时间是 nice 19 的约 1000 倍。

3.5 O(1) pick-next 优化

CFS 在 cfs_rq（每 CPU 的 CFS 运行队列）中缓存最左节点：

struct cfs_rq {
    struct rb_root_cached tasks_timeline;
    // tasks_timeline 的 rb_leftmost 缓存了 vruntime 最小的进程
};

pick_next_task_fair() 直接返回 rb_leftmost，无需遍历整棵树。

3.6 Group Scheduling（cgroups v2）

CFS 支持按控制组（cgroup）分配 CPU 资源。例如将用户进程、系统进程分到不同 cgroup，各自按比例分配 CPU：

# 创建 cgroup 并设置 CPU 份额
mkdir /sys/fs/cgroup/mygroup
echo 512 > /sys/fs/cgroup/mygroup/cpu.weight

内核会为每个 cgroup 创建一个 sched_entity，使其作为一个整体参与调度。

四、多处理器负载均衡

4.1 为什么需要负载均衡

多核系统上，如果所有进程集中在少数 CPU 上运行，其他 CPU 空闲，不仅浪费资源，还会导致热点 CPU 上的进程响应变慢。

4.2 迁移策略

• Push 迁移：周期性检查负载，将进程从过载 CPU 推送到空闲 CPU
• Pull 迁移：空闲 CPU 主动从繁忙 CPU “拉取” 进程

Linux 主要采用 Pull 迁移 结合周期性的 Push 检测。

4.3 Linux 的实现

每个 CPU 维护自己的 runqueue。内核线程 migration/N 和 ksoftirqd/N 配合完成迁移：

1. 调度 tick 到达时，检查当前 CPU 负载是否不平衡
2. 计算 busiest CPU 和 idlest CPU 之间的负载差异
3. 如果超过阈值，从 busiest CPU 拉取一些进程

// kernel/sched/fair.c: load_balance()
static int load_balance(int cpu, struct rq *this_rq,
                         struct sched_domain *sd, enum cpu_idle_type idle,
                         int *continue_balancing)

4.4 CPU 亲和性

使用 taskset 将进程绑定到特定 CPU，减少缓存失效和迁移开销：

# 将进程绑定到 CPU 0
taskset -cp 0 <pid>

# 启动新进程并绑定到 CPU 2,3
taskset -c 2,3 ./myapp

适用场景：

• 需要最大化缓存命中率的计算密集型任务
• 需要减少 NUMA 远程内存访问的场景
• 实时任务需要避免迁移抖动

五、实时调度

Linux 提供三种主要的调度策略：

5.1 SCHED_FIFO

• 先到先服务的实时策略
• 同优先级内不可抢占，高优先级可抢占低优先级
• 一旦获得 CPU，会一直运行到阻塞或主动放弃

5.2 SCHED_RR

• 同优先级之间使用时间片轮转
• 优先级范围 1-99，数字越大优先级越高
• 时间片固定，用完排到同优先级队列末尾

5.3 SCHED_OTHER（CFS）

• 普通进程默认策略
• 使用 nice 值在 [-20, 19] 范围内调整优先级

5.4 chrt 命令

# 查看进程调度策略和优先级
chrt -p <pid>

# 将进程改为 SCHED_FIFO，优先级 50
chrt -f -p 50 <pid>

# 以 SCHED_RR 优先级 10 启动程序
chrt -r 10 ./realtime_app

注意：使用 SCHED_FIFO/SCHED_RR 需要 root 权限或 CAP_SYS_NICE 能力。

六、现代趋势

6.1 eBPF 调度器（sched_ext）

Linux 6.x 引入了 sched_ext，允许用 eBPF 编写自定义调度器，无需修改内核代码：

// 用户可以用 eBPF/C 编写调度逻辑
// 内核提供回调：select_cpu, enqueue, dequeue, dispatch, runnable, running, stopping...

这为调度算法的研究和特定场景的优化提供了极大便利。例如 Meta 已经用 sched_ext 实现了针对大规模数据中心的调度器。

6.2 Core Scheduling

超线程（SMT）环境下，同一核心上的两个逻辑 CPU 共享微架构状态。Core Scheduling 确保互不信任的进程不会被调度到同一核心的兄弟线程上， mitigate L1TF 等侧信道攻击。

6.3 能耗感知调度（EAS）

ARM big.LITTLE 架构下，CPU 分为高性能核心（big）和能效核心（LITTLE）。Linux 的 Energy Aware Scheduling（EAS）在调度决策时考虑能量消耗：

任务负载轻 → 放到 LITTLE 核心
任务负载重 → 放到 big 核心或集群
始终在满足性能的前提下最小化能耗

Android 设备广泛使用此技术来平衡性能和续航。

七、实践调试

7.1 nice / renice

# 降低优先级（给系统腾出更多 CPU）
nice -n 19 ./background_job

# 调整运行中进程的 nice 值
renice +10 -p <pid>

7.2 查看调度统计

# 查看进程的调度器内部统计
cat /proc/<pid>/sched

# 输出示例：
# se.vruntime        :    12345678.123456
# se.sum_exec_runtime :    1000.234567
# nr_switches         :    5000
# nr_voluntary_switches:  3000

7.3 perf sched 分析

# 记录调度事件
perf sched record -- sleep 10

# 生成调度延迟报告
perf sched latency

# 可视化调度时间线
perf sched map

# 查看上下文切换详情
perf sched script

perf sched 可以帮助诊断调度延迟问题，例如：

• 哪个进程等待时间最长
• 是否存在不必要的上下文切换
• 负载在各个 CPU 上的分布

结语

从 FCFS 到 CFS，调度算法的发展映射了操作系统从批处理到分时、从单核到多核的演进。CFS 用红黑树和 vruntime 实现了优雅的公平性保证，而 sched_ext 的出现标志着调度器进入了可编程时代。理解这些机制不仅能帮助我们优化应用程序性能，也为深入内核开发奠定了坚实基础。

参考

• 《Operating System Concepts》（Silberschatz, Galvin, Gagne）
• Linux Kernel Documentation: Documentation/scheduler/
• Kernel Source: kernel/sched/fair.c, kernel/sched/core.c
• BPF_SCHED_EXT: Documentation/scheduler/sched-ext.rst