深入剖析 Linux SCHED_DEADLINE：CBS 算法与硬实时调度实战

去年某次线上演出事故中，主控台的音频线程被邻近的日志压缩任务抢占了 80ms——在 48kHz 采样率下，这意味着将近 4 个采样周期的音频数据丢失。事后排查发现，虽然音频线程以 SCHED_FIFO 高优先级运行，但系统中存在另一个高优先级实时线程采用了贪婪的死循环模式，独占 CPU 导致其他实时任务全部饿死。

这是经典的优先级反转与资源预留缺失问题。Linux 早在 3.14 版本就通过 SCHED_DEADLINE 引入了硬实时调度策略，基于 CBS（Constant Bandwidth Server）算法解决了该问题。然而八年过去，生产环境真正用好它的工程师仍然不多。本文从调度器实现细节出发，彻底讲清楚其原理、源码与落地实践。

一、为什么需要 SCHED_DEADLINE

Linux 默认的 CFS（Completely Fair Scheduler）保证公平性，但不提供任何时间保障。SCHED_FIFO 和 SCHED_RR 属于 POSIX 实时调度类，高优先级可抢占低优先级，但无法防止：

• 高优先级任务无限占用 CPU（无带宽隔离）
• 多个实时任务互相抢占导致连锁错过截止时间（deadline miss）
• 无法精确限制任务在一个周期内最多运行多少时间

SCHED_DEADLINE 解决了这些问题。它基于资源预留思想：每个 DEADLINE 任务在创建时声明三个参数——运行时间（Runtime）、截止期限（Deadline）、周期（Period），系统通过准入控制（admission control）确保这些参数之和不超过 CPU 容量后，即提供硬实时保证：任务在每个周期内都能在截止时间前获得声明的运行时间。

用现实类比：CFS 是"先来先服务"的平等食堂；SCHED_FIFO 是 VIP 客户不限量自助餐，旁人饿死不管；而 SCHED_DEADLINE 是分时预订制，每人在特定时段获得精确配给，互不侵犯。

二、理论基石：EDF 与 CBS

2.1 最早截止时间优先（EDF）

SCHED_DEADLINE 的底层调度策略是 EDF：总是选择绝对截止时间最早的任务来执行。对于周期性实时任务，EDF 是最优的单 CPU 调度算法——如果任何调度算法能让所有任务满足截止时间，EDF 也能。EDL 的 CPU 利用率上界为 100%（理论上可达到完全利用）。

2.2 常数带宽服务器（CBS）

纯 EDF 无法隔离行为异常的任务——一个任务如果企图在一个周期内超额运行，会挤占其他任务的 CPU 时间。CBS 正是解决此问题的"带宽隔离器"。

CBS 为每个服务器（即每个 DEADLINE 任务）维护两个状态变量：

• 当前预算（Current Budget / runtime）：任务当前可消耗的 CPU 时间
• 当前截止时间（Current Deadline / deadline）：预算被完全消耗后触发的绝对时间点

CBS 规则如下：

1. 任务到达时（新周期开始或任务被唤醒）：给任务分配一个等于 Runtime 的预算，截止时间 = 当前时间 + Deadline。
2. 任务运行时：从预算中按实际消耗扣减；若预算耗尽，任务被标记为 THROTTLED（挂起），直到下一个周期到来才重新补充。
3. 任务在预算耗尽前阻塞：保存当前预算和截止时间；唤醒后继续执行，直到预算耗尽。
4. 关键规则：Non-Renewal——若任务在当前截止时间之后才被唤醒，说明已经迟到，必须重置预算 = Runtime，Deadline = 当前时间 + 给定 Deadline，重新从完整预算开始。这防止"迟到者"继承旧截止日期从而抢占准时任务。

示意图：

             CBS 时间轴示意（Runtime=4ms, Deadline=6ms, Period=20ms）

任务运行: ████░░░░░░░░░░░░░░░|████░░░░░░░░░░░░░░░|████
预算变化: 4→3→2→1→0(挂起)     | 4→3→2→1→0(挂起)    |
时间ms:  0    4   6          20   24  26           40
          |    |   |           |   |   |
          开始 耗尽 DDL         再次补充

三、内核实现：sched_dl_entity

SCHED_DEADLINE 在内核中的核心数据结构是 struct sched_dl_entity，定义的简化版本如下（基于 Linux 6.x）：

struct sched_dl_entity {
    struct rb_node    dl_node;            // EDF 红黑树节点
    u64               deadline;           // 绝对截止时间（ns）
    u64               runtime;            // 当前剩余预算（ns）
    u64               period;             // 周期
    u64               runtime_original;    // 原始预算（用于恢复）
    int               dl_throttled:1;     // 是否被带宽限制挂起
    int               dl_yielded:1;       // 是否主动让出
    struct hrtimer    dl_timer;           // 定时器：截止时间超时触发
    struct hrtimer    inactive_timer;     // 非活动定时器：任务阻塞/退出
};

EDF 调度队列由一棵红黑树（rb-tree）维护，以 deadline 为键值（实现最早的在最左侧）。调度选择时，pick_next_task_dl 直接取最左侧节点——时间复杂度 O(log n)。

关键代码路径在 kernel/sched/deadline.c 中：

• enqueue_task_dl — 任务变为可执行时插入 ED 红黑树，若新任务早于当前运行的任务则触发 resched_curr
• dequeue_task_dl — 任务阻塞/退出时从红黑树移除
• update_curr_dl — 每个 tick 或 context switch 时扣减当前任务的 runtime，检测预算耗尽并设置 dl_throttled
• task_tick_dl — tick 中断回调
• start_dl_timer / cancel_dl_timer — 管理高精度定时器跟踪预算耗尽时刻

3.1 预算耗尽处理

当 update_curr_dl 检测到当前任务的 runtime <= 0 时，调用 dl_task_offline 将任务标记为 throttled：

// kernel/sched/deadline.c (简化)
static inline void update_curr_dl(struct rq *rq) {
    struct sched_dl_entity *dl_se = &curr->dl;
    // ...
    dl_se->runtime -= delta_exec;  // 扣减运行时间
    if (dl_se->runtime <= 0) {
        // 预算耗尽，启动 dl_timer 在 deadline 时刻才重新调度
        if (!dl_throttled) {
            dl_se->dl_throttled = 1;
            start_dl_timer(curr);
        }
        resched_curr(rq);  // 请求重新调度
    }
}

注意这里的设计精妙之处：预算耗尽后不会立即唤醒任务，而是通过 dl_timer（hrtimer）在当前截止时间才触发重新调度。即便 CPU 空闲，throttled 任务也必须等到 deadline 之后才能获得新的周期预算——这是 CBS 隔离机制的硬保障。

3.2 准入控制（Admission Control）

新 DEADLINE 任务、或修改参数时，内核调用 dl_overflow 检查：所有 CPU 上 DEADLINE 任务的 Σ(Runtime_i / Period_i) ≤ CPU_capacity。即密度测试（density test）——确保总负载不超过 CPU 容量。

// 准入检查核心逻辑
static int dl_overflow(struct task_struct *p, int policy,
                       const struct sched_attr *attr) {
    struct dl_bw *dl_b = dl_bw_of(...);
    // 计算新增任务后的总带宽
    // 若 total_bw > 1024（即 100% CPU），拒绝设置
    ...
}

四、syscall 接口与编程实践

SCHED_DEADLINE 的 syscall 是通过 sched_setattr / sched_getattr 统一定制接口暴露的。

4.1 基础示例：实时音频处理

#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>

int enable_sched_deadline(void) {
    struct sched_attr attr = {
        .size          = sizeof(attr),
        .sched_policy  = SCHED_DEADLINE,
        .sched_runtime =  4 * 1000 * 1000,  //   4 ms
        .sched_deadline=  6 * 1000 * 1000,  //   6 ms
        .sched_period  = 20 * 1000 * 1000,  //  20 ms (50 Hz)
    };
    return sched_setattr(0, &attr, 0);
}

int main(void) {
    if (enable_sched_deadline() < 0) {
        perror("sched_setattr");
        return 1;
    }
    printf("SCHED_DEADLINE enabled: runtime=%uns deadline=%uns period=%uns\n",
           attr.sched_runtime, attr.sched_deadline, attr.sched_period);

    while (1) {
        // 执行实时音频处理工作
        process_audio_buffer();
        // 周期性地重新触发下一个预算周期
        // CBS 自动在 period 边界补充预算
    }
    return 0;
}

编译运行要求：

gcc -O2 -o audio_realtime audio_realtime.c
# 需要 CAP_SYS_NICE 或 root 权限
sudo ./audio_realtime
# 或通过 systemd 的 Architecture=exec + AmbientCapabilities=CAP_SYS_NICE

4.2 关键参数调优原则

1. Runtime < Deadline ≤ Period — 必须满足。Runtime 是实际 CPU 时间需求，Deadline 是允许完成的窗口长度，Period 是两次资源补充的间隔。当 Runtime == Deadline == Period 时，退化为每 Period 时间段内独占 Runtime 时间的模型。

2. Runtime 不宜过紧：留出 5-10% 的容差，应对缓存未命中、中断处理等不可预测延迟。

3. Deadline 通常等于 Period：最保守的设置。若设为小于 Period，内核保证任务在 deadline 时刻前获得 deadline 但注意 Runtime 可以大于 Deadline（CBS 会相应处理）。

4. 启用 RT throttling 后 RB 带宽：/proc/sys/kernel/sched_rt_runtime_us 默认 950000（95%），若设为 -1 则完全解除限制，但普通 RT 任务仍可能被 DEADLINE 抢占。生产环境建议保持 95%，留出 CPU 给 CFS 任务。

五、cgroup v2 集成

SCHED_DEADLINE 与 cgroup v2 的 cpu.max 控制器配合，可以实现容器级别的带宽隔离。关键配置：

# 在 cgroup 目录下挂载 cpu.max
echo "200000 1000000" > /sys/fs/cgroup/mycontainer/cpu.max
# 表示每 1000ms 周期内最多使用 200ms CPU（20% 利用率）

对于 DEADLINE 任务，内核通过 max_bw_to_dl_bw 将 cpu.max 转换为全局带宽上限。这意味着容器的 DEADLINE 任务准入控制会同时受到容器带宽限制和全局带宽限制的双重约束。

实际部署建议：将 DEADLINE 任务的 cgroup 与 CFS 任务分开，避免相互干扰：

# 高优先级：DEADLINE 任务
mkdir /sys/fs/cgroup/audio-dl
echo "max 1000000" > /sys/fs/cgroup/audio-dl/cpu.max

# 低优先级：普通 CFS 任务
mkdir /sys/fs/cgroup/background-work
echo "50000 1000000" > /sys/fs/cgroup/background-work/cpu.max  最多5%

六、追踪与调试

6.1 In-band Tracing

通过 ftrace 追踪 DEADLINE 调度器事件：

cd /sys/kernel/tracing
echo 1 > events/sched/sched_dl_overflow/enable
echo 1 > events/sched/sched_dl_timer/enable
echo 1 > events/sched/sched_switch/enable
cat trace_pipe

典型输出：

      audio-proc-1102  [003] d...   234.567: sched_running:   comm=audio-proc pid=1102 runtime=4000000
      audio-proc-1102  [003] d...   234.571: sched_throttled:  comm=audio-proc pid=1102 budget=0 deadline=234573000000
       <idle>-0      [003] d...   234.573: sched_switch:   prev_comm=audio-proc prev_pid=1102 ... next_comm=swapper

6.2 错过截止时间监控

当 DEADLINE 任务错过截止时间时，内核会记录一条信息：

sched: [dl_task_timer] task X missed its deadline by Y ns

通过 /proc/sched_debug 查看 DEADLINE 运行队列状态：

cat /proc/sched_debug | grep -A 20 "dl_rq"

6.3 关键 tracepoint 速查

Event	含义
sched_dl_overflow	准入控制失败（带宽超限）
sched_dl_timer	dl_timer 触发（当前切回 throttled 任务）
sched_running	DEADLINE任务开始/恢复运行
sched_throttled	任务被 CBS 挂起
sched_deadline_yield	任务主动 yield（sched_yield()）

七、与 SCHED_FIFO / PREEMPT_RT 对比

特性	SCHED_FIFO	PREEMPT_RT + SCHED_FIFO	SCHED_DEADLINE
优先级	静态 1-99	静态 1-99（RT 内核增加优先级继承等）	动态 EDF
带宽隔离	无	有限（RT throttling）	硬隔离（CBS）
准入控制	无	无	有
优先级反转	无（但互相饥饿）	部分解决（优先级继承 mutex）	无（运行时间隔离）
利用率上界	无保证	无保证	理论 100%
适用场景	确定性低的简单 RT	低延迟需求为主	严格截止时间+多任务

选择原则： - 系统只有 1-2 个 RT 任务，且对延迟要求不苛刻 → SCHED_FIFO 足够 - 多个 RT 任务共存，需要防止相互影响 → SCHED_DEADLINE - 需要最低延迟、可控中断线程化 → PREEMPT_RT + SCHED_FIFO/SCHED_RR - 需要多任务截止时间保证 → SCHED_DEADLINE 是唯一选择

八、生产环境部署注意事项

8.1 避免 CPU 竞争

SCHED_DEADLINE 在不同 CPU 上独立运行，但全局准入控制基于所有 CPU 上的总和。生产部署的三个模式：

1. 独占核（CPU isolation）：通过 isolcpus 内核参数隔离出专用核，仅在其上运行 DEADLINE 任务。
2. cgroup 约束：通过 cpuset.cpus 限制 DEADLINE 任务只能运行在特定核上。
3. 全局共享：多个 DEADLINE 任务共享全核，接受准入控制。

8.2 锁定内存防止换出

DEADLINE 任务的代码段和工作集换出到磁盘会导致毫秒级延迟，必须锁定：

#include <sys/mman.h>
mlockall(MCL_CURRENT | MCL_FUTURE);  // 锁定当前和未来所有内存

8.3 避免系统调用阻塞

在 DEADLINE 任务运行期间，需避免可能触发磁盘 I/O、堆分配的系统调用。建议在初始化阶段完成所有资源分配。

总结

SCHED_DEADLINE 是 Linux 内核中被低估的关键能力。它将实时调度的理论保证——CBS 算法，通过严谨的红黑树实现和准入控制，生产级别地集成进通用操作系统。理解 CBS 的四个核心规则耗尽-挂起-补充-重置需要 10 分钟；而能在大规模异构系统中稳健地部署、调优 DEADLINE 任务，则是区分普通运维与系统架构能力的分水岭。

在音频处理、工业控制、自动驾驶感知流水线、高频交易等场景中，SCHED_DEADLINE 能以最小成本获得硬实时保障。下一次当你面对"如何让实时任务不被其他进程意外饥饿"的问题时，不妨从 CBS 的视角重新审视——它可能正是你一直在寻找的解法。

---

参考文档： - man 7 sched — Linux scheduling overview - man 2 sched_setattr - Linux kernel source: kernel/sched/deadline.c - Baruah, S. K. et al., "The Constant Bandwidth Server", IEEE RTSS 1995 - Linux RT wiki: https://wiki.linuxfoundation.org/realtime/start