1. 首页
  2. 系统内核
  3. Linux内核
  4. 内存管理

Linux内核CFS调度器与实时调度深度实战：从vruntime到Deadline

3 阅读 0 评论

引言

调度器是操作系统的核心组件，负责在多个可执行实体之间分配CPU时间。Linux内核从O(1)调度器演进到CFS（Completely Fair Scheduler），再到Deadline调度策略，不断在高吞吐与低延迟之间寻求平衡。本文以Linux 6.x内核源码为基础，深入解析CFS的核心数据结构与算法，并介绍实时调度策略的实战应用。

1. CFS完全公平调度器核心原理

1.1 完全公平的理想模型

CFS的核心思想是追求"完全公平"——如果系统中有N个可运行任务，每个任务应当获得1/N的CPU时间。理想情况下，CPU时间应当被无限细分，每个任务轮流执行极短的时间片。但这会带来巨大的上下文切换开销，因此CFS做了现实折中。

1.2 调度实体（sched_entity）与虚拟运行时间（vruntime）

CFS使用struct cfs_rq（CFS运行队列）管理所有普通任务。每个任务通过struct sched_entity加入这个队列，该结构嵌入在task_struct.se中。

struct sched_entity {
    struct load_weight  load;       // 任务权重（由nice值决定）
    struct rb_node      run_node;   // 红黑树节点
    unsigned int        on_rq;      // 是否在运行队列中
    
    u64                 exec_start; // 本次开始执行时间
    u64                 sum_exec_runtime; // 累计执行时间
    u64                 vruntime;   // 虚拟运行时间 ★核心字段
    u64                 prev_sum_exec_runtime; // 上次执行前累计
};

vruntime（虚拟运行时间）是CFS的核心概念，它表示任务"理应消耗"的加权CPU时间。vruntime增长越慢，说明任务优先级越高（权重越大），下次被调度到的机会越大。

1.3 vruntime计算公式

// kernel/sched/fair.c: update_curr()
delta_exec = now - curr->exec_start;           // 实际执行时间（纳秒）
delta_exec_weighted = calc_delta_fair(delta_exec, curr); // 加权时间
curr->vruntime += delta_exec_weighted;

关键转换函数：

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se) {
    // NICE_0_LOAD = 1024 (nice 0的权重)
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
    return delta;
    // 等价于: delta * NICE_0_LOAD / se->load.weight
}

推导：nice值每降低1级（优先级提高），CPU份额增加约10%。权重与CPU份额呈反比，因此低nice值任务增长vruntime较慢，更容易获得调度机会。

2. 红黑树调度数据结构

2.1 为什么选择红黑树

CFS使用红黑树（rbtree）组织所有可运行任务，以vruntime为key。这种选择而非传统runqueue数组的优势在于：

  • O(log n) 插入/删除/查找最左节点：每次pick_next_task只需取最左节点（最小vruntime）
  • 缓存友好性：rb_leftmost指针缓存了最左节点，实际调度是O(1)
  • 动态适应性：任务数量可动态伸缩，无需预分配

2.2 pick_next_task_fair 核心流程

// kernel/sched/fair.c: pick_next_task_fair()
static struct task_struct *pick_next_task_fair(struct rq *rq) {
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    
    // 1. 从红黑树取最左节点（最小vruntime）
    se = pick_next_entity(cfs_rq);
    
    // 2. 设置当前任务的exec_start
    set_next_entity(cfs_rq, se);
    
    // 3. 更新组调度层级
    do {
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);
    
    return task_of(se);
}

2.3 新任务vruntime初始化

新创建的任务不能从vruntime=0开始，否则会长期霸占CPU。CFS使用place_entity()将新任务vruntime设为运行队列的最左节点值（cfs_rq->min_vruntime），让其"追上"已有任务。

// 新任务首次入队（fork后）
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); // 补偿一个时间片
}

3. 调度粒度与最小时间片控制

CFS通过sched_latency和min_granularity两个参数控制调度粒度：

/proc/sys/kernel/sched_latency_ns      = 24_000_000  // 24ms（默认调度周期）
/proc/sys/kernel/sched_min_granularity_ns =  3_000_000  //  3ms（最小时间片）
/proc/sys/kernel/sched_wakeup_granularity_ns = 4_000_000 //  4ms（唤醒抢占粒度）

当可运行任务数量超过 sched_latency / min_granularity 时，每个任务的时间片会被扩大，避免过度上下文切换。

// 计算每个任务的时间片
static u64 sched_period(unsigned long nr_running) {
    if (nr_running > sched_latency / min_granularity)
        return nr_running * min_granularity;
    return sched_latency;
}

3.1 唤醒抢占（wake preemption）

当唤醒一个新任务时，检查其vruntime是否比当前任务小超过阈值：

// check_preempt_wakeup()
if (delta < 0 || (delta > 0 && delta < sysctl_sched_wakeup_granularity))
    resched_curr(rq); // 抢占当前任务

4. NUMA感知与负载均衡

4.1 NUMA复亲和调度

CFS在NUMA系统中加入了NUMA拓扑感知：

  • select_task_rq_fair：选择最优运行队列（首选相同NUMA节点）
  • NOCSD（No-Cache Sharing Domains）：检测共享LLC的CPU组
  • sched_numa_balancing：周期性扫描进程地址空间，将进程迁移到靠近其内存的NUMA节点

4.2 负载均衡算法

多核系统中的负载均衡分为：

  1. PMC级（每个tick）：检查是否需要迁移任务
  2. SD级（调度域）：从MC→DIE→NUMA逐级拉伸不平衡
  3. IDLE级：空闲CPU主动拉任务
// 负载均衡核心入口
static int load_balance(int this_cpu, struct rq *this_rq,
                        struct sched_domain *sd, enum cpu_idle_type idle) {
    // 1. 找到最繁忙的组
    // 2. 从最繁忙的CPU拉取任务
    // 3. 执行负载转移
}

5. 组调度（Group Scheduling）

5.1 CFSBandwidth控制

CFS组调度带宽控制允许为每个cgroup设置CPU使用上限：

// 创建cgroup并设置CPU带宽
mkdir /sys/fs/cgroup/cpu/myapp
echo 100000 > /sys/fs/cgroup/cpu/myapp/cpu.cfs_period_us   // 100ms周期
echo  50000 > /sys/fs/cgroup/cpu/myapp/cpu.cfs_quota_us    // 50ms配额 = 0.5核
echo $PID > /sys/fs/cgroup/cpu/myapp/cgroup.procs

5.2 带宽机制实现

struct cfs_bandwidth {
    ktime_t period;          // 周期
    u64     quota;           // 配额
    u64     runtime;         // 剩余运行时间
    struct hrtimer period_timer; // 周期定时器
};

static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b) {
    // 周期结束时补充quota
    cfs_b->runtime = cfs_b->quota;
    // 唤醒所有throttle的任务
    unthrottle_cfs_rq(cfs_rq);
}

当cgroup中的任务用完配额时，throttle_cfs_rq()将任务移出红黑树，直到下个周期补充。

6. 实时调度策略

6.1 SCHED_FIFO — 先进先出实时策略

SCHED_FIFO是抢占式的FIFO策略，用于硬实时任务：

  • 优先级1-99（99最高）
  • 一旦获得CPU，一直运行直到：主动yield、阻塞、或被更高优先级抢占
  • 同优先级之间FIFO轮转
  • 无时间片限制——低优先级任务可能被饿死
// 设置SCHED_FIFO优先级50
struct sched_param param = { .sched_priority = 50 };
sched_setscheduler(pid, SCHED_FIFO, &param);

6.2 SCHED_RR — 轮询实时策略

SCHED_RR在SCHED_FIFO基础上增加了时间片：

  • 同优先级任务按时间片RR轮转
  • 时间片默认为100ms（RR_TIMESLICE）
  • 适合需要公平共享实时优先级的场景
sysctl -w kernel.sched_rr_timeslice_ms=100

6.3 SCHED_DEADLINE — 全局最早截止时间优先（EDF）

SCHED_DEADLINE是Linux 3.14+引入的基于EDF的实时调度策略，适合有明确截止时间要求的实时任务。

// SCHED_DEADLINE参数
struct sched_attr {
    .size = sizeof(struct sched_attr),
    .sched_policy = SCHED_DEADLINE,
    .sched_runtime  =  10_000_000,  // 10ms（每个周期内运行时间）
    .sched_deadline =  20_000_000,  // 20ms（相对截止时间）
    .sched_period   =  20_000_000,  // 20ms（周期）
};

6.4 EDF调度可行性判定

SCHED_DEADLINE在任务准入时使用Constant Bandwidth Server (CBS)算法验证：

// 可行性检查条件
Σ (runtime_i / deadline_i) <= 1.0

// 示例：3个DL任务
// Task A: runtime=3ms, deadline=10ms → 0.3
// Task B: runtime=4ms, deadline=20ms → 0.2
// Task C: runtime=2ms, deadline=15ms ≈ 0.133
// 总和 = 0.633 < 1.0 ✓ 可行

当CPU利用率超过100%时，sched_setattr()返回-EBUSY。

7. 调度器性能调优

7.1 减少上下文切换

对于延迟敏感型应用：

# 提高sched_min_granularity_ns减少抢占
echo 10000000 > /proc/sys/kernel/sched_min_granularity_ns  # 10ms

# 降低wakeup_granularity减少唤醒抢占
echo 10000000 > /proc/sys/kernel/sched_wakeup_granularity_ns

7.2 CPU亲和性绑定

// 使用taskset或sched_setaffinity绑定到特定CPU
cpu_set_t cpuset;
CPU_ZERO(&cpuset);
CPU_SET(2, &cpuset);
CPU_SET(3, &cpuset);
sched_setaffinity(pid, sizeof(cpuset), &cpuset);

7.3 禁用NUMA自动均衡

对于单节点内存密集型应用：

echo 0 > /proc/sys/kernel/numa_balancing
# 或使用sysctl
sysctl kernel.numa_balancing=0

7.4 实时隔离

使用isolcpus内核参数隔离CPU给实时任务：

# GRUB配置
isolcpus=4-7 nohz_full=4-7 rcu_nocbs=4-7

# 将实时任务绑到隔离CPU
chrt -f 99 taskset -c 4 ./realtime_task

7.5 监控与诊断

# 查看调度器统计
cat /proc/${PID}/sched | head -30

# 使用perf分析调度延迟
perf sched record -a sleep 10
perf sched latency

# 使用ftrace跟踪调度事件
echo 1 > /sys/kernel/debug/tracing/events/sched/enable
cat /sys/kernel/debug/tracing/trace_pipe | head -50

8. 调度策略选择指南

场景推荐策略理由
桌面交互应用CFS + nice调整公平共享，避免饿死
Web服务器CFS默认高吞吐，自动均衡
音视频编码SCHED_RR实时性+公平性
工业控制（硬实时）SCHED_FIFO高优先级确定性延迟，不超调
自动驾驶/机器人SCHED_DEADLINE可证明的截止时间保证
后台批处理SCHED_BATCH低优先级，防止干扰交互

结论

Linux内核CFS调度器通过虚拟运行时间和红黑树的巧妙组合，在公平性和效率之间取得了出色的平衡。理解CFS的vruntime计算机制、红黑树数据结构、粒度控制、NUMA感知和组调度，是进行系统级性能优化的基石。对于实时场景，SCHED_FIFO提供硬实时抢占能力，SCHED_DEADLINE则通过EDF算法提供可证明的截止时间保证。在实际部署时，需要结合具体应用特征，合理选择调度策略并进行系统级调优。

  • 源码参考：kernel/sched/fair.c、kernel/sched/rt.c、kernel/sched/deadline.c
  • 配置文档：Documentation/scheduler/
  • 调试工具：perf sched、ftrace sched_*、/proc/<pid>/sched
点赞(0) 打赏
Linux内核内存分配器深度实战：SLAB/SLUB/SLOB完全解析
Linux内核内存分配器深度实战：SLAB/SLUB/SLOB完全解析
Linux内核同步原语深度实战：从spinlock到RCU
Linux内核同步原语深度实战：从spinlock到RCU
Linux内核CFS调度器与实时调度深度实战：从vruntime到Deadline
Linux内核CFS调度器与实时调度深度实战：从vruntime到Deadline
Linux内核同步与并发深度实战：从Spinlock到RCU内存锁
Linux内核同步与并发深度实战：从Spinlock到RCU内存锁

评论列表 共有 0 条评论

暂无评论
立即
投稿

微信公众账号

微信扫一扫加关注

 发表
评论 返回
顶部