1. 首页
  2. 系统内核

Linux 内核调度器演进：CFS 完全公平调度器到 EEVDF 的深度解析

1 阅读 0 评论

引言

进程调度是操作系统最核心的职能之一。Linux 内核调度器经历了从 O(n) 到 O(1)，再到 CFS（Completely Fair Scheduler），最终在 2023 年迎来了革命性的 EEVDF（Earliest Eligible Virtual Deadline First）调度器。本文将深入解析这三种调度算法的架构设计、核心机制以及在实际生产环境中的性能表现。

一、O(n) 与 O(1)：调度器的早期探索

1.1 O(n) 调度器（Linux 2.4 之前）

最早的 Linux 调度器采用最简单的线性扫描方式：

  • 时间片分配：每个进程获得固定的时间片，通过遍历所有可运行进程来选择下一个执行的进程
  • 时间复杂度：O(n) —— 系统中的进程越多，调度开销越大
  • 问题：当进程数量增加时，调度器本身成为系统瓶颈

1.2 O(1) 调度器（Linux 2.6）

Ingo Molnar 引入的 O(1) 调度器使用了两个关键数据结构：

  • Active 数组：存放时间片未用完的进程
  • Expired 数组：存放时间片已耗尽的进程
  • 140 级优先级：0-99 为实时进程，100-139 为普通进程
  • 时间复杂度：O(1) —— 无论进程数量多少，调度决策耗时恒定

O(1) 调度器在服务器和高负载场景下表现出色，但其交互性测度和优先级计算方式存在固有缺陷，难以区分 I/O 密集型与 CPU 密集型进程。

二、CFS：完全公平调度器（Linux 2.6.23+）

2.1 设计哲学

CFS 的核心思想极其优雅：不分配时间片，而是分配 CPU 时间的比例。CFS 试图模拟一个 "理想多任务处理器"（Ideal Multitasking Processor），让每个进程获得完全公平的 CPU 时间份额。

// 核心数据结构：CFS 运行队列
struct cfs_rq {
    struct load_weight load;           // 队列中进程的总权重
    unsigned long runnable_weight;     // 可运行进程的总权重
    unsigned int nr_running;           // 可运行进程数量
    u64 min_vruntime;                  // 队列中的最小 vruntime
    
    struct rb_leftmost_t *rb_leftmost; // 红黑树最左节点（下一个被调度的进程）
};

// 调度实体
struct sched_entity {
    struct load_weight load;           // 进程权重
    struct rb_node run_node;           // 红黑树节点
    u64 vruntime;                      // 虚拟运行时间
    u64 exec_start;                    // 当前执行开始时间
    u64 sum_exec_runtime;              // 总执行时间
};

2.2 虚拟运行时间（vruntime）

CFS 的核心创新在于引入虚拟运行时间的概念：

// 更新当前进程的 vruntime
static void update_curr(struct cfs_rq *cfs_rq) {
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec;
    
    delta_exec = now - curr->exec_start;
    curr->sum_exec_runtime += delta_exec;
    
    // 关键公式：vruntime = 实际运行时间 × (NICE_0_LOAD / 进程权重)
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    
    // 更新队列的 min_vruntime（单调递增）
    update_min_vruntime(cfs_rq);
}

nice 值为 0 的进程权重为 1024，每降低一个 nice 级，权重增加约 25%（乘以 1.25），意味着获得更多 CPU 时间；每升高一个 nice 级，权重减少约 20%。

2.3 红黑树调度结构

CFS 使用红黑树（Red-Black Tree）组织所有可运行进程：

  • 键值：进程的 vruntime
  • 最左节点：vruntime 最小的进程 = 最"亏欠" CPU 的进程 = 下一个被调度
  • 插入操作：O(log n)
  • 选择操作：O(1)（通过缓存 rb_leftmost 指针）

2.4 CFS 调度决策流程

schedule() → pick_next_task_fair()
    │
    ├─ 获取 cfs_rq->rb_leftmost（vruntime 最小的进程）
    │
    ├─ 进程抢占检查：
    │   如果新唤醒进程的 vruntime < 当前进程的 vruntime
    │   → 唤醒抢占（Wakeup Preemption）
    │
    └─ 上下文切换：设置 exec_start，切换到选中进程

2.5 组调度与层级 CFS

CFS 支持多级调度层级：

  • 任务组（Task Group）：每个 cgroup 拥有自己的 cfs_rq
  • 组间公平：每个组获得的 CPU 时间按权重分配
  • 组内公平：组内每个进程再公平分配

2.6 CFS 的局限

尽管 CFS 设计优雅，但在某些场景下存在问题：

  • 延迟敏感型应用：新创建的进程 vruntime 被设为 min_vruntime，导致初始阶段"饥饿"以获得补偿，对延迟不友好
  • 唤醒抢占不精确：由于 vruntime 的平滑特性，关键进程可能无法及时抢占
  • NUMA 感知有限：跨 NUMA 节点的迁移决策不够智能
  • 大规模系统扩展性：在数千核的红黑树操作开销增加

三、EEVDF：最早合格虚拟截止时间优先调度器

3.1 设计动机

2023 年，长期从事 CFS 优化的开发者 Peter Zijlstra 提出了 EEVDF 调度器，目标是：

  • 精确保留 CFS 的公平性语义
  • 消除 vruntime 的平滑延迟效应
  • 提供更精确的延迟控制
  • 简化调度器核心逻辑

Linux 6.6 正式合入主线，成为默认的 CFS 替代方案。

3.2 核心概念

EEVDF 引入三个新时间量：

概念符号含义
Runtimer实际已运行的虚拟时间
Deadlined = r + q必须在此时间前运行完 Quantum
Eligible Timee ≥ min(r, lag_start)有资格开始调度的最早时间

关键区别：EEVDF 不追踪 vruntime 的累积值，而是用截止时间来决定优先级——截止时间越早的进程越优先调度。

// EEVDF 调度实体
struct sched_entity {
    struct rb_node run_node;    // 红黑树节点（按 deadline 排序）
    u64 deadline;               // 虚拟截止时间
    u64 vruntime_base;          // 基础 vruntime
    slice;                      // 时间片（不再累积，每次重置）
    lag;                        // 公平性偏移量
};

3.3 Lag 与公平性维护

EEVDF 通过 lag 概念实现精确公平：

// 计算进程的 lag（相对于理想公平份额的偏移）
function update_lag(se):
    ideal_slice = sysctl_base_slice * (se.weight / cfs_rq.total_weight)
    se.lag += se.sum_exec_runtime - ideal_slice
    se.sum_exec_runtime = 0  // 重置，不再累积

// Eligible 时间计算
function calc_eligible(se):
    if se.lag >= 0:
        return current_time
    else:
        // lag 为负（被过度服务），需要等待
        return current_time + abs(se.lag)

// Deadline 计算
function calc_deadline(se):
    return max(calc_eligible(se), se.vruntime_base) + se.slice

lag 机制确保：

  • lag 为正（被亏欠 CPU）→ eligible 立即 → deadline 更早
  • lag 为负（被过度服务）→ eligible 延迟 → deadline 更晚（让位给他人）
  • lag = 0 → 完全公平，按标准份额运行

3.4 量子（Quantum）与切片

EEVDF 使用固定量子（quantum）而非动态时间片：

  • 默认量子：由 sysctl_sched_base_slice 控制（通常 3ms）
  • 按比例缩放：进程实际获得的 slice = quantum × (weight / total_weight)
  • 切片重置：每次调度后切片重新计算，不累积
  • 优势：简化了公平性计算，避免 vruntime 累积误差

3.5 EEVDF 调度流程

ee_schedule() → pick_next_task()
    │
    ├─ 从红黑树中移除最左节点（earliest deadline）
    │
    ├─ 检查当前进程是否仍有资格运行：
    │   if current.deadline < picked.deadline → 继续运行当前进程
    │
    ├─ 设置 timer 在 deadline 处触发（用于精确抢占）
    │
    └─ 上下文切换到 picked 进程

3.6 EEVDF 的优势

  • 精确延迟控制：通过 deadline 精确知道何时需要切换上下文
  • 消除初始饥饿：新进程的 deadline 基于当前时间 + slice，不会饿死
  • 简化逻辑：移除 vruntime 的平滑机制和 min_vruntime 追踪
  • 更好的实时性：hrtimer 驱动精确抢占点
  • NUMA 友好：deadline 驱动的迁移决策更直接

四、CFS vs EEVDF 对比

维度CFSEEVDF
核心机制vruntime 累积 + 红黑树deadline 驱动 + 红黑树
公平性渐进式（ vruntime 平滑）精确式（lag 计算）
新进程行为从 min_vruntime 开始（先吃后补）立即给 deadline（无初始饥饿）
抢占精度基于时间片耗尽hrtimer 在 deadline 精确触发
延迟敏感平滑导致唤醒延迟eligible 机制保证及时响应
复杂度vruntime 平滑 + min_vruntime 追踪lag + deadline 计算（逻辑更清晰）
成熟度20+ 年生产验证Linux 6.6+（2023）

五、生产环境实战调优

5.1 关键 sysctl 参数

# 查看当前调度器
cat /sys/kernel/debug/sched/features

# EEVDF 相关调整（Linux 6.6+）
sysctl kernel.sched_base_slice_ns=3000000    # 基础量子 3ms
sysctl kernel.sched_child_runs_first=0       # 子进程优先（0=关闭）
sysctl kernel.sched_min_granularity_ns=300000 # 最小粒度 300μs

# NUMA 平衡
sysctl kernel.numa_balancing=1               # 开启 NUMA 自动平衡
sysctl kernel.numa_balancing_scan_delay_ms=1000

5.2 延迟敏感型服务（如 Redis）

# 使用 chrt 设置 FIFIO 实时调度
sudo chrt -f 50 redis-server /etc/redis/redis.conf

# 或使用 scheduler group
sudo systemctl set-property redis.service CPUWeight=10000

# 实时进程的 EEVDF 调度
# 实时调度类（SCHED_FIFO/SCHED_RR）在 EEVDF 之上运行

5.3 容器化环境（Kubernetes）

# cpu.shares 映射到 cgroup cpu.weight（CFS/EEVDF 共享）
# cpu.cfs_quota_us 映射到 cpu.max（带宽控制）

apiVersion: v1
kind: Pod
spec:
  containers:
  - name: api-server
    resources:
      requests:
        cpu: "2"          # 权重基础值
      limits:
        cpu: "4"          # 带宽上限
    # 对于延迟敏感的 Pod，使用 static 策略
    # kubelet --cpu-manager-policy=static

5.4 监控与诊断

# 查看进程调度统计
cat /proc/{pid}/sched | grep -E "nr_switches|wait_sum|exec_start"

# 使用 perf sched 追踪调度延迟
sudo perf sched record -a sleep 10
sudo perf sched latency --sort max

# BPF 工具：runqlat (BCC)
sudo /usr/share/bcc/tools/runqlat -m  # 显示毫秒级运行队列延迟

# 调度器直方图
sudo /usr/share/bcc/tools/runqlat 1 10  # 采样 10 秒

六、调度器源码架构（Linux 6.8+）

kernel/sched/
├── core.c           # 核心调度框架（schedule(), __schedule()）
├── fair.c           # CFS 调度类实现
├── sched.h          # 调度实体、调度类、调度域定义
├── deadline.c       # SCHED_DEADLINE 调度类
├── rt.c             # 实时调度类（FIFO/RR）
├── stop_task.c      # STOP 调度类（最高优先级）
├── idle.c           # IDLE 调度类
├── cpufreq_schedutil.c  # 调度器驱动的 CPU 频率调节
├── autogroup.c      # 自动任务组
├── debug.c          # debugfs 调度统计
├── stats.c          # procfs 统计输出
├── topology.c       # 调度域（Sched Domain）和调度组（Sched Group）
└── pelt.c           # Per-Entity Load Tracking（PELT 负载估算）

EEVDF 合入后，fair.c 中的 pick_next_task_fair 被 ee_vdf 替代，但调度类框架（sched_class）保持不变。核心变化仅在于如何选择下一个进程——CFS 按 vruntime 排序，EEVDF 按 deadline 排序。

七、未来展望

调度器仍在持续演进，值得关注的方向：

  • scx（Sched eXtensible）：允许用户态 BPF 程序自定义调度策略，已在 Linux 6.8 引入作为模块化调度框架
  • 异构感知调度（HMP/eAS）：针对 ARM big.LITTLE / Intel P+E 混合架构的智能任务分配
  • NUMA 拓扑感知：随着 CXL 内存扩展，跨节点访问延迟对调度决策愈发重要
  • 调度器热补丁：基于 Livepatch 技术在不重启内核的情况下修复调度器 bug

总结

从 O(n) 到 O(1)，从 CFS 到 EEVDF，Linux 内核调度器 20 年的演进始终围绕两个核心目标：公平性与响应性。EEVDF 的成功在于它用最简洁的数学形式——截止时间——解决了 CFS 用了 20 年逐步修补仍未完美解决的问题。对于运维工程师和系统开发者而言，理解 EEVDF 的核心机制不仅有助于调优生产环境，更能深入理解现代操作系统内核的设计哲学。

点赞(0) 打赏
发酵的科学与艺术：从一坛泡菜到微生物世界的奇妙旅程
发酵的科学与艺术：从一坛泡菜到微生物世界的奇妙旅程
零信任架构下的身份认证实战：从边界防御到持续验证的工程演进
零信任架构下的身份认证实战：从边界防御到持续验证的工程演进
深入理解 Rust 内存管理：从所有权模型到智能指针的工程实践
深入理解 Rust 内存管理：从所有权模型到智能指针的工程实践
系外行星探索的新发现：从JWST到寻找第二个地球
系外行星探索的新发现：从JWST到寻找第二个地球

评论列表 共有 0 条评论

暂无评论
立即
投稿

微信公众账号

微信扫一扫加关注

 发表
评论 返回
顶部