Linux内核CFS调度器与EEVDF深度剖析：从完全公平到最早截止时间优先

一、调度器演进史：为什么需要CFS

Linux调度器的演进是一部"从粗糙到精密"的工程教科书。

1.1 O(n)调度器（Linux 2.4时代）

早期的Linux调度器采用最简单的思路：遍历所有可运行进程，计算每个进程的"优先级值"（称为goodness），选择goodness最大的进程运行。

其本质问题是：每次调度决策的时间复杂度为O(n)，当进程数量增长时，调度器本身成为性能瓶颈。此外，它采用静态时间片分配策略——高优先级进程获得更长的时间片，导致"优先级反转"和"饥饿"问题难以优雅地解决。

1.2 O(1)调度器（Linux 2.6.0 ~ 2.6.22）

Ingo Molnár引入的O(1)调度器解决了时间复杂度问题。核心设计是140个优先级队列（0-139，其中0-99为实时进程，100-139为普通进程），每个优先级对应一个bitmap位。调度时只需找到bitmap中第一个被置位的位，从对应队列中取出第一个进程运行。

O(1)调度器的关键数据结构是活跃数组（active array）和过期数组（expired array）。每个进程被分配一个时间片（time slice），时间片用完后被移到过期数组。当活跃数组为空时，交换两个数组的指针——这个交换本身是O(1)操作。

然而O(1)调度器引入了极为复杂的交互式奖励/惩罚启发式算法：睡眠时间长的进程会获得优先级提升（奖励），消耗CPU多的进程会降低优先级（惩罚）。这套启发式规则代码量大、难以调参，且在高负载场景下交互延迟仍然不稳定。

1.3 CFS完全公平调度器（Linux 2.6.23+）

CFS摒弃了传统的时间片和优先级队列，转而提出一个简洁的核心目标：在真实多核CPU上，每个可运行进程应在"无限小"的理想调度器上获得等量的CPU时间。

---

二、CFS核心原理：理想多处理器调度器

2.1 理想调度器模型

假设有n个优先级相同的可运行进程，理想调度器能在每个时刻将CPU划分为n等份，各进程获得1/n的实际CPU时间。但实际上CPU不可分割，因此目标转化为：最小化每个进程的实际CPU时间与理想CPU时间的偏差。

CFS定义了关键概念——虚拟运行时间（virtual runtime，vruntime）：

$$vruntime_i = \frac{实际运行时间_i \times NICE\_0\_LOAD}{权重_i}$$

其中权重由进程的nice值决定。Linux使用预计算的转换表（sched_prio_to_weight[40]），nice每降低1级（优先级提高），权重乘以约1.25（即获得25%更多CPU时间）。

vruntime的含义：vruntime增长越慢，进程获得的CPU越多。权重越大的进程，vruntime增长越慢。CFS始终选择vruntime最小的进程运行，从而保证"公平"。

2.2 红黑树：O(log n)选择最小vruntime

CFS使用红黑树（Red-Black Tree）来组织所有可运行进程。红黑树是一种自平衡二叉搜索树，保证最坏情况下查找、插入、删除操作均为O(log n)。

• 每个调度实体（sched_entity）作为红黑树的一个节点
• 键值为该实体的vruntime
• 最左侧节点即为vruntime最小的进程（下一个被调度的候选）
• 新唤醒的进程或时间片耗尽需要重新排队的进程被插入树中

关键数据结构关系：

struct cfs_rq {
	struct rb_root_cached  runqueue;    // 红黑树根节点（带最左节点缓存）
	struct rb_node       *rb_leftmost; // 缓存最小vruntime节点
	u64                   min_vruntime; // 当前最小vruntime值
	struct load_weight    load;         // 总权重
	...
};

struct sched_entity {
	struct rb_node  run_node;          // 红黑树节点
	u64             vruntime;          // 虚拟运行时间
	u64             exec_start;        // 开始执行时间戳
	u64             sum_exec_runtime;  // 累计执行时间
	u64             prev_sum_exec_runtime; // 上次切换时的累计时间
	...
};

每次pick_next_task只需取rb_leftmost，O(1)时间。插入和删除操作O(log n)。

2.3 调度粒度与延迟控制

CFA的关键参数：

参数	默认值	含义
sysctl_sched_min_granularity	0.75ms	进程最小调度粒度（不会被抢占的最短连续运行时间）
sysctl_sched_wakeup_granularity	1ms	唤醒抢占粒度（新唤醒进程的vruntime需比当前进程小至少此值才能抢占）
sysctl_sched_latency	6ms	调度周期（所有可运行进程至少运行一轮的时间）

调度周期的计算公式为：sched_latency / 进程数量。若进程数过多（每个进程分到的时间片过小），则使用min_granularity作为下限。这意味着在高并发场景下，CFS会自动增大调度周期，牺牲公平性保证吞吐量。

2.4 唤醒抢占与新进程插入

当一个进程从睡眠中唤醒时，CFS将其vruntime设置为cfs_rq->min_vruntime（而不是保持原有的vruntime）。这样做比直接放回红黑树尾部更公平——睡眠时间长的进程因此获得了"vruntime补偿"，很快就会被调度。

唤醒抢占：如果新唤醒进程的vruntime比当前运行进程的vruntime至少小sysctl_sched_wakeup_granularity，则发生抢占。这个阈值避免了过于频繁的上下文切换。

---

三、调度类与组调度

3.1 调度类（Scheduling Class）

Linux调度框架是可扩展的调度类链表。每个调度类实现一组回调函数（enqueue_task, dequeue_task, pick_next_task, task_tick, etc.），按优先级顺序：

stop_sched_class (最高)
dl_sched_class     (Deadline调度，SCHED_FIFO/SCHED_RR)
rt_sched_class     (实时调度)
fair_sched_class   (CFS，SCHED_NORMAL/SCHED_BATCH/SCHED_IDLE)
idle_sched_class   (最低，idle任务)

pick_next_task()从最高优先级类遍历到最低，第一个返回非NULL的类胜出。因此实时进程总是优先于普通进程。

3.2 组调度（Group Scheduling / cgroup CPU）

CFS支持在组之间分配CPU资源，即cgroup cpu控制器。每个cgroup拥有自己的cfs_rq和带宽配额。组调度的核心机制：

• 每个cgroup分配的CPU份额由cpu.shares控制（默认1024）
• cgroup内的进程共享该cgroup的总配额
• 组间使用虚拟时间对齐（cfs_rq->min_vruntime）

3.3 CFS带宽控制（Bandwidth Control）

cpu.cfs_quota_us和cpu.cfs_period_us定义了一个cgroup在period内可用的CPU时间上限：

quota = cpu.cfs_quota_us （微秒）
period = cpu.cfs_period_us （微秒）

当cgroup内所有进程累计CPU达到quota时，该cgroup被限流（throttled），直到下一个period.start才恢复。限流计数器nr_throttled和throttled_time暴露于cpu.stat文件。

实现要点：

• 全局时钟（cfs_boost或wall clock）追踪当前period进度
• 每个cfs_bandwidth拥有自己的hrtimer，到期时推进period边界并补充quota
• Throttled的tasks从红黑树中摘除（dequeue），直到unthrottle时重新入队

---

四、NUMA感知与负载均衡

4.1 多核调度域

Linux调度器在多核系统中通过调度域（sched_domain）层次结构实现负载均衡：

• DIE域（同一物理CPU内，共享L3缓存的核心）
• MC域（同一物理CPU内，共享L2缓存的核心）
• CPU域（逻辑CPU级别，包含SMT超线程）
• NUMA域（跨节点）

负载均衡从最低层域开始向上尝试，优先在同一NUMA节点内平衡。每个域的负载均衡参数（min_interval/max_interval、` imbalance_pct`）可以独立调优。

4.2 NUMA Balancing

除了主动的负载均衡，Linux还使用NUMA Balancing机制：

• 周期性扫描进程的内存页面，通过缺页异常统计哪些页面被远程访问
• 当远程访问率超过阈值，将进程迁移到目标NUMA节点
• 也可通过migratepages工具或set_mempolicy()手动迁移

参数：

• numa_balancing：开启/关闭自动NUMA均衡
• numa_balancing_scan_delay_ms：新进程启动后多久开始扫描
• numa_balancing_scan_period_min_ms/max_ms：扫描频率

---

五、EEVDF：下一代调度器的实时化

5.1 CFS的公平性偏差

CFS虽然保证了长时公平，但在短时延迟方面存在固有局限。当系统中存在大量需要低延迟响应的进程时（如音频处理、实时视频编解码），均匀分配CPU的策略会导致这些进程的响应时间无法得到保障。

为此，Linux 3.x引入了SCHED_DEADLINE调度策略（基于Earliest Deadline First），但它是独占式的，普通应用的交互需求无法从中受益。

5.2 EEVDF算法原理

EEVDF（Earliest Eligible Virtual Deadline First）于2023年被提出并作为CFS的替代方案讨论（Peter Zijlstra，Linux内核维护者），于Linux 6.6可选支持（CONFIG_SCHED_CORE）。

核心思想：为每个调度实体引入虚拟截止时间（virtual deadline，VD）：

• 每个进程的理想调度时间被表示为一个"截止时间"
• 进程必须在该截止时间之前运行，否则产生"延迟"
• 调度器选择VD最小的进程运行
• VD的计算基于请求运行时间（request duration）和权重分配

与CFS相比的关键区别：

特性	CFS	EEVDF
选择依据	最小vruntime	最小VD
公平性保证	长时公平	短时延迟保证
延迟控制	隐式（通过min_granularity）	显式（VD边界）
饥饿防护	通过lag补偿	通过lag和eligible检查
复杂度	O(log n)	O(log n)

5.3 Lag与Eligible机制

EEVDF的核心新概念是Lag和Eligibility：

Lag = 进程应得的虚拟运行时间 - 实际虚拟运行时间。

• Lag > 0：进程欠调度（应补偿）
• Lag < 0：进程超调度（应抑制）
• Lag = 0：完全公平

EEVDF在选取进程时有两个检查：

1. Eligibility：只有Lag >= 0的进程才有资格被调度
2. VD最小值：在eligible进程中选VD最小的

这保证了：一个进程只有在"公平份额内"才能被调度。如果进程已经超出公平份额（Lag < 0），它的VD会被推迟到lag补偿完之后才成为"eligible"。

5.4 虚拟运行时间与截止时间的关系

请求运行时间(requested time slice) = latency / n （进程数）

虚拟运行时间(vruntime)  request_ratio  =  nice0_weight / weight_i

虚拟截止时间(virtual deadline) = vruntime + requested_time_slice * request_ratio

EEVDF的关键性质：所有eligible进程在任意时间窗口内的lag之和为零。这意味着系统始终处于"动态平衡"状态，没有任何进程可以长期占优或长期被剥夺。

5.5 EEVDF在Linux内核中的实现

Linux 6.6引入了EEVDF作为CFS的可选替代（通过sched_class切换或内核参数sched_poll），主要改动：

1. sched_entity新增字段：

• virtual_deadline (u64) —— 虚拟截止时间
• lag (s64) —— 正/负延迟量

1. 红黑树键值改变：不再按vruntime排序，而是按virtual_deadline排序

1. elapse逻辑：每次tick或调度决策时，基于wall clock计算进程的lag变化，更新eligible状态

1. Lag补偿：当一个进程从睡眠中唤醒时，需要计算其应得的lag（基于睡眠时间内的其他调度实体的变化）

性能对比数据（来自Peter Zijlstra的基准测试，Phoronix数据库）：

• 桌面交互延迟：EEVDF在高负载下99th percentile延迟降低约30%
• 编译负载：总完成时间与CFS基本持平（差异<2%）
• 实时音频处理：EEVDF无xrun（缓冲区欠载），CFS偶发
• 游戏帧率稳定性：1% low FPS提升15-25%

---

六、sched_ext：可编程调度器框架

6.1 背景

虽然CFS和EEVDF提供了优秀的通用调度策略，但越来越多的场景需要定制化的调度逻辑：

• GPU计算任务与CPU的协同调度
• 容器密度的极限优化
• 异构大小核（如Intel Hybrid）的智能任务分配
• AI推理的批处理调度

传统的"修改内核"方式成本高、风险大，且每个场景的修改互相冲突。为此，Linux 6.12引入了sched_ext（Scheduler Extending），允许用户态程序加载自定义调度器。

6.2 工作原理

sched_ext调度器作为eBPF-like的用户态调度器进程运行，使用内核提供的BPF程序接口：

1. BPF程序定时从内核获取可运行任务列表
2. 用户态决策逻辑决定下一个运行哪个任务、运行多长时间
3. 调度结果通过系统调用接口提交给内核
4. 内核fallback机制：如果用户态调度器崩溃或无响应，自动回退到CFS

6.3 调度层级

sched_ext插入在CFS之上（成为更高优先级的sched_class），因此可以随时抢占CFS的调度决策。内核保证每个CPU有一个活跃的sched_ext调度器实例。

6.4 现有实现

主要的sched_ext调度器实现包括：

名称	用途	特点
scx_rust	通用Rust实现	平衡延迟与吞吐
scx_lavd	Latency-criticality Aware	自动感知任务优先级
scx_rlfifo	简易FIFO	学习/测试用
scx_central	集中式调度器	单CPU全局决策
scx_flatcg	扁平cgroup调度	容器优化
scx_nest	NUMA自适应	感知拓扑结构
scx_pair	配对调度	大小核异构优化
scx_qmap	队列映射	自定义队列策略
scx_simple	简单示例	入门参考
scx_userland	用户态定制	可嵌入自定义逻辑

---

七、实时调度类详解

7.1 SCHED_FIFO

SCHED_FIFO是可抢占的固定优先级调度策略：

• 优先级1-99（99最高）
• 高优先级进程总是抢占低优先级
• 同优先级进程按FIFO顺序运行
• 除非主动yield或阻塞，否则一直运行直到时间片用完

注意：SCHED_FIOR没有时间片概念。如果一个SCHED_FIFO进程不主动放弃CPU，低优先级进程将永远得不到运行（优先级反转的经典场景）。

7.2 SCHED_RR

Round-Robin变体：与SCHED_FIFO类似，但同优先级进程有时间片，轮转发运行。时间片默认为100ms（sched_rr_timeslice，可通过sched_rr_get_interval调整）。

7.3 SCHED_DEADLINE

Linux 3.14引入的基于EARLIEST DEADLINE FIRST的硬实时策略：

• 进程声明运行时预算（runtime）和周期（period）及截止时间（deadline）
• 内核验证调度可行性（CBS算法 + 全局EDF）
• 超过预算时被throttled直到下一个period
• 适用于工业控制、音视频处理等需要延迟保障的场景

7.4 RT throttling

为了防止实时进程耗尽CPU导致系统hung死，Linux提供了RT throttling机制：

• sched_rt_period_us（默认1000000μs = 1s）
• sched_rt_runtime_us（默认950000μs = 950ms）

实时调度类在period内最多使用runtime的CPU，剩余时间保留给普通进程。可通过设置sched_rt_runtime_us = -1关闭throttling（不推荐生产环境）。

---

八、调度参数与调优实践

8.1 Nice值与CPU权重

Linux的nice值范围-20到19，-20优先级最高，最低19。权重映射关系：

Nice值	权重	CPU份额比例(2进程时)
-20	88761	99.9%
-10	1576	86.5%
0	1024	50%

+10 | 151 | 13.4% |

19	3	0.15%

8.2 taskset与CPU亲和性

taskset可将进程绑定到特定CPU核心：

# 绑定到CPU 0和1
taskset -c 0,1 ./my_process

# 绑定到NUMA node 0的所有核心
taskset -c $(lscpu | grep 'NUMA node0' | awk '{print $4}') ./my_process

# 查看当前亲和性
taskset -p <pid>

CFS也支持通过sched_setaffinity()系统调用程序化设置亲和性。注意：硬亲和性会绕过负载均衡，可能导致热点。软亲和性通过sched_domain中的preferred位置提示调度器。

8.3 chrt：设置策略与优先级

# 启动一个SCHED_FIFO进程，优先级50
chrt -f 50 ./realtime_task

# 修改已运行进程的策略
chrt -o 0 <pid>     # 改为SCHED_OTHER（CFS）
chrt -r 30 <pid>    # 改为SCHED_RR优先级30

# 查看进程调度信息
chrt -p <pid>

8.4 延迟监控

通过perf sched工具可以分析调度事件：

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

# 查看延迟直方图
perf sched latency

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

# 重建调度历史
perf sched replay

`/proc//sched`提供进程级统计：

nr_switches          :                 1024     # 上下文切换次数
nr_voluntary_switches :                  800     # 自愿切换（I/O等待）
nr_involuntary_switches:                  224   # 非自愿切换（时间片耗尽）
se.vruntime          :         1234567890123    # 当前vruntime
se.sum_exec_runtime  :          98765432109     # 累计实际运行时间
prio                 :                  120     # 动态优先级（120为nice 0）
clock-delta : 8    # 与sched_clock的偏差（TSC不同步时）

8.5 调优指南

场景	推荐配置
低延迟交易系统	isolcpus=2-7 + nohz_full=2-7 + rcu_nocbs=2-7 + SCHED_FIFO
Web服务器（高并发）	CFS，适当提高sched_min_granularity
批处理/编译	SCHED_BATCH + nice 19
音频工作站	RT throttling 关闭 + PREEMPT_RT + SCHED_FIFO
容器平台	cgroup v2 cpu.weight + cpu.max带宽控制
游戏	EEVDF（Linux 6.6+）或SCHED_RR
GPU计算	cgroup限制 + CPU亲和性绑定

---

九、内核抢占模型

9.1 自愿抢占 vs 非自愿抢占

• 非自愿抢占（Preemptive）：时间片到期或被更高优先级进程抢占，无需进程主动配合。由scheduler_tick()在tick中断中检查need_resched标志触发。
• 自愿抢占（Voluntary）：进程在用户态主动调用可能阻塞的操作（如schedule(), cond_resched()），内核在该点进行抢占检查。内核编译选项CONFIG_PREEMPT_VOLUNTARY开启。

9.2 CONFIG_PREEMPT三种模式

模式	抢占点	延迟	适用
CONFIG_PREEMPT_NONE	用户态返回/系统调用退出	~10ms+	吞吐量优先
CONFIG_PREEMPT_VOLUNTARY	上述 + 显式抢占点	~1-5ms	桌面通用
CONFIG_PREEMPT (亦称fully preemptible)	上述 + 中断返回也可抢占	~100-500μs	低延迟
PREEMPT_RT (patch)	几乎处处可抢占	~10-50μs	硬实时

9.3 临界区保护

抢占只发生在非临界区。内核通过计数器preempt_count判断当前是否在临界区：

• bit 0-7：抢占禁用计数（preempt_disable()）
• bit 8-15：软中断禁用
• bit 16-23：硬中断（IRQ）上下文
• bit 24-31：NMI上下文

只有当preempt_count == 0时，抢占才会真正发生。cond_resched()会检查need_resched标志并在安全时主动调度。

---

十、生产环境实战案例

10.1 数据库服务器优化

以PostgreSQL为例的调度优化：

# 1. 绑定PostgreSQL到特定核心（避开核心0-3给系统和其他服务）
taskset -c 4-15 /usr/lib/postgresql/bin/postgres

# 2. 为PostgreSQL进程设置SCHED_OTHER但使用最高nice
nice -n -10 /usr/lib/postgresql/bin/postgres

# 3. cgroup限制其他容器不能占满CPU
# /sys/fs/cgroup/db/cpu.max: 800000 1000000 (80% quota)

# 4. 关闭NUMA自动均衡（NUMA架构下）
echo 0 > /proc/sys/kernel/numa_balancing

# 5. 使用SCHED_IDLE给备份任务
chrt -i 0 pg_dump  # nice 19的效果类似

10.2 容器平台调度策略

Kubernetes中的Linux调度器交互：

• requests.cpu → cgroup v2 cpu.weight（或cfs_shares）
• limits.cpu → cpu.max quota + period
• Guaranteed Pod：quota = period × cores
• Burstable Pod：quota > requests
• BestEffort Pod：SCHED_IDLE

cgroup v2中的cpu.weight默认范围为1-10000，对应cgroup v1的cpu.shares（默认1024）。

10.3 音频工作站（PREEMPT_RT + SCHED_FIFO）

# 加载snd_hrtimer模块
modprobe snd_hrtimer

# JACK音频服务器运行在SCHED_FIFO优先级90
jackd -R -P 90 -d alsa -d hw:0

# 音频处理线程通过pthread设置SCHED_FIFO
chrt -f 80 ./audio_processor

# 监控xrun（缓冲区欠载）
watch -n 1 'cat /proc/xruns'

---

十一、Linux调度器数据结构全景图

                          ┌─────────────────────────┐
                          │    task_struct          │
                          │  ┌───────────────────┐  │
                          │  │ sched_entity (CFS) │  │
                          │  │  vruntime          │  │
                          │  │  run_node (RB)     │  │
                          │  │  virtual_deadline   │  │
                          │  │  lag                │  │
                          │  └───────────────────┘  │
                          │  prio, static_prio      │
                          │  policy (sched class)    │
                          │  cpus_ptr (affinity)    │
                          └─────────┬───────────────┘
                                    │ belongs to
                                    ▼
                          ┌─────────────────────────┐
                          │    cfs_rq (per-CPU)     │
                          │  ┌───────────────────┐  │
                          │  │  runqueue (RB)    │  │
                          │  │    rb_leftmost  ───┼──┼──► pick_next
                          │  │  min_vruntime      │  │
                          │  │  load (总权重)      │  │
                          │  └───────────────────┘  │
                          │  throttle_count          │
                          │  cfs_bandwidth           │
                          └─────────────────────────┘
                                    │  ▲
                          enqueue ──┘  └── dequeue
                                    ▼
                   ┌────────────────────────────────┐
                   │      rq (runqueue per-CPU)      │
                   │  clock, clock_task,            │
                   │  nr_running, curr              │
                   │  cfs, rt, dl, idle sched_rqs   │
                   └────────────────────────────────┘

---

十二、总结

Linux调度器的演进史是一部"工程权衡"的完美案例：

1. 时间/空间效率：O(n) → O(1) → O(log n)，每一步都在降低调度决策本身的开销
2. 公平性/延迟：CFS实现了优雅的长时公平，但短时延迟有短板；EEVDF显式引入了延迟保证
3. 通用性/可定制性：从CFS的"万能"设计，到sched_ext的用户态可编程
4. 实时/非实时：通过调度类分层，硬实时、软实时、批处理、交互各得其所

理解调度器不仅需要掌握数据结构（红黑树、调度域链表），更需要理解其背后的设计哲学：在任何足够复杂的系统中，没有放之四海皆准的最优策略，只有对特定工作负载的最优权衡。

---

本文基于Linux 6.6+内核源码与相关论文撰写，涵盖从2.4到6.12的调度器演进历程。

参考资料：Linux kernel source (kernel/sched/), "Completely Fair Scheduler" (Linux 2.6.23), Peter Zijlstra "EEVDF"系列patch, Linux Kernel Documentation。