Linux 进程调度机制：CFS 与实时调度的内核实现原理
一、进程调度的"公平性"难题：谁该先跑？
Linux 进程调度的核心问题是"公平性"——如何在数百个进程间分配 CPU 时间，既保证交互式进程的响应速度，又不让后台进程饿死。早期的 O(1) 调度器通过优先级数组实现，但在交互式场景下表现不佳——高优先级进程可能独占 CPU，低优先级进程长时间得不到调度。
CFS（Completely Fair Scheduler）从 2.6.23 内核开始成为默认调度器，其核心思想是"完全公平"——每个进程获得的 CPU 时间应该与其权重成正比，通过红黑树维护进程的虚拟运行时间，实现 O(log n) 的调度效率。
二、CFS 调度原理
graph TB subgraph 核心数据结构 A[红黑树<br/>按vruntime排序] --> B[最左节点<br/>vruntime最小=最该运行] B --> C[当前进程<br/>从树中取出运行] end subgraph 调度逻辑 D[时钟中断] --> E[更新当前进程vruntime] E --> F{vruntime > 最左节点?} F -->|是| G[切换到最左节点进程] F -->|否| H[继续运行] end subgraph 公平性保证 I[nice值→权重映射<br/>nice 0=1024] --> J[nice越低权重越高<br/>获得更多CPU时间] J --> K[vruntime增长越慢<br/>越容易被调度] endCFS 的核心概念是虚拟运行时间（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 最小"的排序问题，红黑树天然适合这一场景。
