CFS完全公平调度器——Linux内核CPU调度深度解剖：从vruntime到EEVDF

7 阅读 0 评论 0 点赞

引言

在现代操作系统中，CPU 调度器是内核中最核心的组件之一。它决定哪个进程在何时、在哪个 CPU 核心上运行，直接影响系统的吞吐量、响应时间和公平性。Linux 内核在 2.6.23 版本引入的 CFS（Completely Fair Scheduler，完全公平调度器），彻底取代了之前 O(1) 调度器，至今仍是 Linux 默认的进程调度器。

本文将从调度器的理论基础出发，深入剖析 CFS 的核心数据结构、调度算法、多核负载均衡、组调度以及实时进程管理，并结合性能调优实践，带你全面理解 Linux 内核调度器的运作机制。

一、调度器基础概念

1.1 什么是调度

调度（Scheduling）是操作系统从就绪队列中选择一个进程，将 CPU 控制权交给它的过程。由于 CPU 核心数量远少于运行中的进程数量，调度器需要在多个目标之间做出权衡：

公平性（Fairness）：每个进程应当按其权重比例获得 CPU 时间
响应速度（Latency）：交互式进程应快速响应用户输入
吞吐量（Throughput）：批处理任务应尽快完成
实时性（Realtime）：实时进程必须满足截止时间要求

1.2 Linux 调度器演进

Linux 调度器经历了三代主要演进：

版本	调度器	特点
2.4	简单轮转	O(n) 遍历所有进程，粗糙简单
2.6	O(1) 调度器	Ingo Molnar 设计，优先级数组 + 时间片，O(1) 选择
2.6.23+	CFS	Con Kolivas 启发，红黑树 + vruntime 虚拟时间

1.3 调度策略

Linux 内核支持以下调度策略：

SCHED_NORMAL / SCHED_OTHER：普通分时进程，由 CFS 管理
SCHED_FIFO：先进先出实时进程，不被抢占（除非更高优先级）
SCHED_RR：轮转实时进程，有时间片限制
SCHED_BATCH：批处理型普通进程，更偏向吞吐而非响应
SCHED_IDLE：极低优先级，仅在系统空闲时运行
SCHED_DEADLINE：EDF（最早截止时间优先）策略，3.14+ 引入

二、CFS 核心算法

2.1 虚拟运行时间（vruntime）

CFS 的核心思想是追踪每个进程的 虚拟运行时间（vruntime）。vruntime 根据进程优先级（nice 值）进行加权调整：

// kernel/sched/fair.c
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;

    if (unlikely(!curr))
        return;

    delta_exec = now - curr->exec_start;
    if (unlikely(!delta_exec))
        return;

    curr->exec_start = now;
    curr->sum_exec_runtime += delta_exec;

    // 关键：vruntime 按权重逆加权
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    update_min_vruntime(cfs_rq);
}

calc_delta_fair 的实现逻辑：虚拟时间 = 实际时间 × NICE_0_LOAD / 权重。高权重（低 nice）进程的 vruntime 增长更慢，意味着它们在红黑树中停留更久，获得更多 CPU 时间。

2.2 红黑树数据结构

CFS 使用红黑树（rbtree）组织可运行进程，以 vruntime 作为排序键。最左侧节点即为 vruntime 最小、最"亏欠"的进程，调度器每次选择该进程运行：

// 选择最左侧（vruntime 最小）的进程
static struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = cfs_rq->tasks_timeline.rb_leftmost;
    if (!left)
        return NULL;
    return rb_entry(left, struct sched_entity, run_node);
}

红黑树选择操作时间复杂度为 O(log n)，插入为 O(log n)。但实际上 CFS 通过缓存最左侧节点实现了 O(1) 的选择操作，这是其高性能的关键。

2.3 Nice 值与权重映射

Linux 将 nice 值（-20 ~ 19）映射到权重值，转换公式为：权重 = 1024 / (1.25)^(nice+20)。每差一个 nice 值，CPU 份额相差约 10%：

// kernel/sched/core.c
const int sched_prio_to_weight[40] = {
 /* -20 */ 88761, 71755, 56483, 46273, 36291,
 /* -15 */ 29154, 23254, 18705, 14949, 11916,
 /* -10 */ 9548,  7620,  6100,  4904,  3906,
 /*  -5 */ 3121,  2501,  1991,  1586,  1277,
 /*   0 */ 1024,   820,   655,   526,   423,
 /*   5 */  335,   272,   215,   172,   137,
 /*  10 */  110,    87,    70,    56,    45,
 /*  15 */  36,     29,    23,    18,    15,
};

2.4 调度粒度与延迟控制

CFS 通过 sysctl 参数调控调度行为：

sched_latency（默认 6ms）：每个可运行进程至少轮转一次的周期
sched_min_granularity（默认 0.75ms）：最小调度片，防止过度切换
sched_wakeup_granularity（默认 1ms）：唤醒抢占的阈值

实际调度片 = max(sched_latency / nr_running, sched_min_granularity)。当进程数过大时，总周期 = sched_min_granularity × nr_running，确保不会无限增长。

三、进程入队与出队

3.1 进程入队（enqueue_entity）

当一个进程变为可运行状态（就绪），CFS 将其加入红黑树：

static void enqueue_entity(struct cfs_rq *cfs_rq,
                           struct sched_entity *se, int flags)
{
    bool renorm = !(flags & ENQUEUE_WAKEUP)
                  || (flags & ENQUEUE_MIGRATED);
    bool curr = cfs_rq->curr == se;

    if (renorm && curr)
        se->vruntime += cfs_rq->min_vruntime;
    else
        se->vruntime += cfs_rq->min_vruntime; // 防止饥饿

    update_curr(cfs_rq);
    account_entity_enqueue(cfs_rq, se);

    if (flags & ENQUEUE_WAKEUP)
        place_entity(cfs_rq, se, 0);

    if (!curr)
        __enqueue_entity(cfs_rq, se); // 红黑树插入
    se->on_rq = 1;
}

3.2 进程出队（dequeue_entity）

当进程阻塞（等待 I/O、信号量等）或被抢占时，从红黑树中移除：

static void dequeue_entity(struct cfs_rq *cfs_rq,
                           struct sched_entity *se, int flags)
{
    update_curr(cfs_rq);
    // ... 更新统计信息

    if (se != cfs_rq->curr)
        __dequeue_entity(cfs_rq, se);
    se->on_rq = 0;
    account_entity_dequeue(cfs_rq, se);

    if (!(flags & DEQUEUE_SLEEP))
        se->vruntime -= cfs_rq->min_vruntime;
}

3.3 唤醒补偿（Wakeup Preemption）

当一个新进程被唤醒时，CFS 会做特殊补偿，避免其因 vruntime 落后而长期饥饿：

static void place_entity(struct cfs_rq *cfs_rq,
                         struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;

    if (initial)
        vruntime += sched_vslice(cfs_rq, se);   // 新进程偏移
    else
        vruntime += sysctl_sched_latency / 2;   // 唤醒补偿半周期

    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

通过将唤醒进程的 vruntime 设置为最少 min_vruntime + 半周期，确保新唤醒的交互式进程（如编辑器）能迅速获得 CPU。

四、多核 SMP 与负载均衡

4.1 域与层次结构

Linux 使用调度域（sched_domain）描述 CPU 拓扑层次，从低到高依次为：

MC（Multi-core）域：同一物理核心上的逻辑 CPU（SMT/超线程）
PKG（Package）域：同一插槽上的所有核心
DIE 域：同一裸片上的所有 CPU
NUMA 域：跨 Socket 的内存节点

迁移到同域内成本低（L2 共享），跨 NUMA 域迁移需重新访问远端内存，延迟可达本地 1.5~2 倍。

4.2 负载均衡时机

负载均衡在以下情况触发：

tick 中断：每个 CPU 定期检查相邻调度组是否过载/空闲
CPU 空闲：即将 idle 时立即从繁忙组拉取任务
fork/exec：新进程选择最空闲的 CPU（select_task_rq_fair）
IPI 中断：空闲 CPU 向繁忙 CPU 发送 UPDATE_NO_HZ_IPI 强制均衡

4.3 PELT 负载追踪

Linux 使用 PELT（Per-Entity Load Tracking） 追踪每个进程的 CPU 利用率：

load_avg = load_avg × y + load × (1 - y)
// y = 0.978572 ≈ 0.5^(1/32)，每 32ms 衰减一半

这是指数加权移动平均（EWMA），越近期的活动权重越高。例如一个进程在前 32ms 内跑满一个核心，其 load_avg 约等于 1024（即一个核心利用率）。

Google 在 Android 引入了 WALT（Window Assisted Load Tracking），基于固定时间窗口，对突发负载更敏感。5.10+ 已合并为 UCLAMP 机制。

4.4 NUMA 平衡

NUMA 架构下，跨节点访问内存代价昂贵。Linux 通过自动 NUMA 平衡：

NUMA Hint Fault：内核定期扫描进程页表，识别在哪节点上被访问
迁移决策：将进程+内存一起迁移到 home 节点
Lazy 迁移：通过 idle 平衡逐步收敛，避免抖动

可通过 /proc/sys/kernel/numa_balancing 控制，数据库场景建议关闭以换取确定性。

五、组调度（cgroups 调度）

5.1 CPU cgroup 权重

CFS 支持组调度，允许按容器、服务组分配 CPU 份额：

# cgroup v1 设置 CPU 份额
/sys/fs/cgroup/cpu/myapp/cpu.shares          # 默认 1024，可比例调整
/sys/fs/cgroup/cpu/myapp/cpu.cfs_quota_us    # 每周期最大 CPU 时间
/sys/fs/cgroup/cpu/myapp/cpu.cfs_period_us   # 周期长度（默认 100ms）

# 示例：限制最多使用 0.5 核
echo 50000 > cpu.cfs_quota_us
echo 100000 > cpu.cfs_period_us

这是 Docker/K8s CPU limit 的基础实现。当所有组 shares 相同时，CFS 内部按权重比例分配。

5.2 CFS Bandwidth Control

cfs_bwc 机制：

配额（quota）：period 内可用的总 CPU 时间
周期（period）：配额统计滚动窗口
节流（throttle）：超出时将组内进程移入 throttled_list
全局计时器：每个 CPU 独立的 runtime 配额跟踪

5.3 UCLAMP（利用率夹具）

Linux 5.4+ 引入 UCLAMP，设置任务的最小/最大利用率：

/sys/fs/cgroup/cpu/mygroup/cpu.uclamp.min   # 0~10000
/sys/fs/cgroup/cpu/mygroup/cpu.uclamp.max   # 0~10000

Android 中前台应用 min=50（至少感知 50% 利用率），后台 min=0 max=100。保障交互体验同时限制后台抢跑。

六、实时调度器

6.1 SCHED_FIFO

SCHED_FIFO 是严格的优先级排队调度器。高优先级 FIFO 进程立即抢占低优先级。支持 1~99 级（99 最高）。

优先级反转风险：低优先级进程持有锁 → 高优先级进程等待 → 中等优先级进程抢占 → 高优先级永远阻塞。Linux 通过 rt_mutex 优先级继承机制解决。

6.2 SCHED_DEADLINE（EDF）

3.14+ 引入的全局最早截止时间优先调度器：

struct sched_attr attr = {
    .size = sizeof(attr),
    .sched_policy = SCHED_DEADLINE,
    .sched_runtime  = 20 * 1000 * 1000,  // 20ms 实际运行
    .sched_deadline = 50 * 1000 * 1000,  // 50ms 截止窗口
    .sched_period   = 50 * 1000 * 1000,  // 50ms 周期
};
sched_setattr(0, &attr, 0);

准入条件：Σ(runtime_i / period_i) ≤ 1.0。过载时 sched_setattr 返回 EBUSY。用于音视频采集、工业控制等严格实时场景。

七、抢占与上下文切换

7.1 抢占时机

内核在以下时刻检查 need_resched 标志：

更高优先级进程就绪（实时唤醒）
调度片耗尽（update_curr 发现）
系统调用/中断返回用户态前（ret_to_user）

7.2 上下文切换成本

开销项	典型耗时
寄存器保存/恢复	~0.5μs
TLB 刷新（无 PCID）	1~5μs
FPU/SIMD 保存	~1μs（仅首次）
Cache 污染	数个周期
合计	1~10μs

7.3 PCID 与 Lazy TLB

Intel PCID 在 CR3 中嵌入 12 位进程标识符，允许 TLB 保留多个地址空间的映射。Linux 采用 Lazy TLB：内核线程切换时不刷新 TLB，只在真正切换用户地址空间时按需 INVLPG，大幅降低了频繁抢占的代价。

八、性能调优实践

8.1 关键 sysctl 参数

参数	默认值	适用场景
sched_min_granularity_ns	750000 (0.75ms)	数据库建议 10ms+（提升吞吐）
sched_wakeup_granularity_ns	1000000 (1ms)	建议 15ms+（减少唤醒抢占）
sched_migration_cost_ns	500000 (0.5ms)	绑核场景设为 9999999（禁止迁移）
sched_autogroup_enabled	1	桌面交互必开，服务器可关闭
sched_numa_balancing	1	NUMA 数据库建议关闭

8.2 绑核策略

# 命令级绑核
taskset -c 2-3 ./network_engine

# cgroup cpuset
echo "2-3" > /sys/fs/cgroup/cpuset/myapp/cpuset.cpus

# 内核代码
cpumask_clear(&mask);
cpumask_set_cpu(2, &mask);
cpumask_set_cpu(3, &mask);
sched_setaffinity(pid, &mask);

不同场景策略：网络中断绑定独享核心、HPC 隔离计算核心、数据库 NUMA 内绑核 + 大页。

8.3 RT Throttling

# 实时进程每 1s 最多占 0.95s，保留 5% 给普通进程
echo 1000000 > /proc/sys/kernel/sched_rt_period_us
echo 950000  > /proc/sys/kernel/sched_rt_runtime_us

防止实时进程死循环锁死系统。SCHED_DEADLINE 自带准入控制，无需额外 throttle。

8.4 perf 与 ftrace 观测

# 记录调度事件 10 秒
perf record -e 'sched:sched_switch,sched:sched_wakeup' -a sleep 10
perf script

# ftrace 追踪上下文切换
trace-cmd record -e sched_switch -e sched_wakeup
kernelshark trace.dat

# 查看进程调度统计
cat /proc/$$/sched
# se.vruntime :  123456.789  ← vruntime (ns)
# nr_migrations:  42          ← 迁移次数
# nr_voluntary_switches: 123   ← 主动放弃 CPU
# nr_involuntary_switches: 456 ← 被抢占次数

九、踩坑指南

9.1 优先级反转（Priority Inheritance 未启用）

现象：高优先级实时线程等待低优先级锁，被中等优先级线程插队。

解决：启用 CONFIG_RT_MUTEXES，使用带 PTHREAD_PRIO_INHERIT 的互斥锁，或使用 SCHED_DEADLINE。

9.2 Cache 抖动（Cache Thrashing）

现象：同一线程在核心间反复迁移，L1/L2 缓存不断失效。

解决：绑核（sched_setaffinity/cpuset），增大 sched_migration_cost_n，或关闭 NUMA 自动平衡。

9.3 CFS 配额与节流误用

现象：容器在高峰期 CPU 被限制，但低谷期又不能回收配额。

解决：理解 cfs_quota_us 是硬上限而非"保留"。建议 burst 配额 + cpulimit 监控，或迁移到 cgroup v2 cpu.max。

十、未来展望：EEVDF 与 sched_ext

Linux 调度器正在经历重要变革：

EEVDF（Earliest Eligible Virtual Deadline First）：Linux 6.6（2023.10）起替代 CFS 作为默认调度器。引入 eligibletime 概念解决 CFS 边界条件问题（新进程延迟 vs 公平性平衡点）。核心改动：remove tasks_timeline 红黑树，改为按 deadline 排序；每个任务显示 lateness 窗口。
sched_ext：Linux 6.12+ 引入的 BPF 可编程调度器框架。允许用户态编写自定义调度策略加载到内核，使用 BPF map 和 kfunc，附带安全沙箱。最终目标是让 CFS 成为可替换模块，按需定制缓存亲和性、延迟敏感等特性。
UCLAMP + PD（Performance Domain）：ARM 引入性能域调度，感知 CPU 频率变化更高效地选核。

EEVDF 的设计核心是将公平性转化为截止时间保证：每个进程的 deadline = vruntime + 最小粒度。当系统负载增加，无进程推迟超过延迟目标。这解决了 CFS 在极端负载下延迟不可预测的问题，是向实时调度融合的重要一步。

总结

CFS 作为 Linux 最广泛使用的调度器，其设计哲学——虚拟运行时间加权公平 + 红黑树高效管理 + 分层域负载均衡——在 20 年中展现了强大生命力。理解 CFS 不仅能帮助开发更高效的应用，也为系统调优和性能问题排查提供理论基础。从 vruntime 计算、红黑树操作、NLB 组调度、实时抢占，到 EEVDF 的 deadline 保证，掌握这些核心概念，将使你在面对复杂业务负载时，有能力做出精准的调优决策。

点赞(0) 打赏

本文分类：进程调度
本文标签：Linux内核 CPU调度器 CFS vruntime EEVDF 实时调度性能优化
浏览次数：7 次浏览
发布日期：2026-10-08 03:23:45
本文链接：https://www.ybb.press/kernel-sched/15810.html

上一篇 > Linux 进程调度深度实战：CFS 完全公平调度器全链路解析
下一篇 > Linux 内核 CFS 完全公平调度器：从理论到实战