Linux 进程调度机制：CFS 与实时调度的内核实现原理-171主机测评

Linux 进程调度机制：CFS 与实时调度的内核实现原理

cover

一、进程调度的"公平性"难题：谁该先跑？

Linux 进程调度的核心问题是"公平性"——如何在数百个进程间分配 CPU 时间，既保证交互式进程的响应速度，又不让后台进程饿死。早期的 O(1) 调度器通过优先级数组实现，但在交互式场景下表现不佳——高优先级进程可能独占 CPU，低优先级进程长时间得不到调度。

CFS（Completely Fair Scheduler）从 2.6.23 内核开始成为默认调度器，其核心思想是"完全公平"——每个进程获得的 CPU 时间应该与其权重成正比，通过红黑树维护进程的虚拟运行时间，实现 O(log n) 的调度效率。

二、CFS 调度原理

graph TB
subgraph 核心数据结构
A[红黑树 按vruntime排序] –> B[最左节点 vruntime最小=最该运行]
B –> C[当前进程 从树中取出运行]
end

subgraph 调度逻辑
D[时钟中断] –> E[更新当前进程vruntime]
E –> F{vruntime > 最左节点?}
F –>|是| G[切换到最左节点进程]
F –>|否| H[继续运行]
end

subgraph 公平性保证
I[nice值→权重映射 nice 0=1024] –> J[nice越低权重越高 获得更多CPU时间]
J –> K[vruntime增长越慢 越容易被调度]
end

CFS 的核心概念是虚拟运行时间（vruntime）。每个进程的 vruntime 按实际运行时间增长，但增长速率与进程权重成反比——高优先级进程的 vruntime 增长慢，低优先级进程增长快。红黑树按 vruntime 排序，调度器总是选择 vruntime 最小的进程运行。

三、CFS 内核实现分析

3.1 核心数据结构

// linux/kernel/sched/fair.c（简化版）

struct sched_entity {
struct load_weight load; // 进程权重
struct rb_node run_node; // 红黑树节点
u64 vruntime; // 虚拟运行时间
u64 sum_exec_runtime; // 实际运行总时间
};

struct cfs_rq {
struct rb_root_cached tasks_timeline; // 红黑树根
unsigned int nr_running; // 运行队列中的进程数
u64 min_vruntime; // 队列最小vruntime
struct sched_entity *curr; // 当前运行的进程
};

3.2 vruntime 更新

// 更新当前进程的 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;

if (unlikely(!curr))
return;

// 计算实际运行时间
delta_exec = now – curr->exec_start;

// 更新实际运行总时间
curr->sum_exec_runtime += delta_exec;

// 计算 vruntime 增量：实际时间 × (NICE_0_LOAD / 进程权重)
// 高权重进程的 vruntime 增长慢
curr->vruntime += calc_delta_fair(delta_exec, curr);

// 更新队列最小 vruntime
update_min_vruntime(cfs_rq);
}

// vruntime 增量计算
static u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
if (unlikely(se->load.weight != NICE_0_LOAD))
// 权重 != 1024 时，按比例缩放
delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
return delta;
}

3.3 进程选择与切换

// 选择下一个运行的进程
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq)
{
struct sched_entity *se = NULL;

// 从红黑树中取最左节点（vruntime 最小）
se = rb_entry(cfs_rq->tasks_timeline.rb_leftmost,
struct sched_entity, run_node);

return se;
}

// 进程入队
static void __enqueue_entity(struct cfs_rq *cfs_rq,
struct sched_entity *se)
{
rb_add_cached(&se->run_node, &cfs_rq->tasks_timeline,
__entity_less); // 按 vruntime 排序
}

// 进程出队
static void __dequeue_entity(struct cfs_rq *cfs_rq,
struct sched_entity *se)
{
rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
}

3.4 实时调度

// 实时调度策略：SCHED_FIFO 和 SCHED_RR
// 实时进程优先级高于普通进程，CFS 只在无实时进程时运行

struct rt_rq {
struct rt_prio_array active; // 优先级位图 + 队列数组
unsigned int rt_nr_running; // 实时进程数
};

// SCHED_FIFO：先进先出，不主动让出 CPU 就一直运行
// SCHED_RR：轮转，每个时间片 100ms，用完重新排队

static struct task_struct *pick_next_task_rt(struct rq *rq)
{
// 从最高优先级的队列中取第一个进程
struct rt_prio_array *array = &rq->rt.active;
int idx = sched_find_first_bit(array->bitmap);
struct list_head *queue = array->queue + idx;

return list_entry(queue->next, struct task_struct, rt);
}

四、调度机制的 Trade-offs 分析

CFS 的公平性 vs. 响应性：CFS 保证长期公平，但短期的交互响应可能不如 O(1) 调度器。内核通过"最小粒度"（sched_min_granularity，默认 0.75ms）和"唤醒抢占"机制来改善响应性——新唤醒的交互进程可以抢占当前进程。

实时进程的饿死风险：SCHED_FIFO 实时进程如果不主动让出 CPU，会永久占据 CPU，导致普通进程饿死。Linux 通过 RT throttling 机制限制实时进程的 CPU 占用上限（默认 95%），预留 5% 给普通进程。

红黑树的开销：红黑树的插入和删除是 O(log n)，在进程数极多（>10000）时，调度开销不可忽略。但实际系统中运行队列中的进程数通常在几十到几百，O(log n) 的开销可以忽略。

nice 值的非线性映射：nice 值每降低 1，CPU 时间份额增加约 10%，而非线性增长。nice -20 的进程获得的 CPU 时间约为 nice 0 的 10 倍，nice 19 约为 nice 0 的 1/10。这种设计避免了极端优先级导致的严重不公平。

五、总结

CFS 通过红黑树和虚拟运行时间实现了"完全公平"的进程调度——每个进程获得的 CPU 时间与其权重成正比，调度复杂度 O(log n)。实时调度通过优先级位图实现 O(1) 调度，保证实时进程的确定性延迟。两者协同，既保证了普通进程的公平性，又满足了实时进程的确定性要求。

理解 CFS 的关键在于"虚拟运行时间"概念——它将"谁最该运行"的问题转化为"谁的 vruntime 最小"的排序问题，红黑树天然适合这一场景。

Linux 进程调度机制：CFS 与实时调度的内核实现原理