2. Linux 内核调度器基础：CFS 调度器原理、vruntime、红黑树

在 Android 系统中，CPU 资源的分配由内核调度器决定。从 Android 4.4 开始，默认调度器为 完全公平调度器（CFS，Completely Fair Scheduler）。理解 CFS 是优化驱动性能、降低调度延迟的前提。

2.1 CFS 设计哲学：理想公平模型

CFS 的核心思想是模拟一个“理想的多任务处理器”。假设系统中有 N 个可运行进程，在理想情况下，每个进程在单位时间内应获得 1/N 的 CPU 时间。CFS 通过 虚拟运行时间（vruntime） 来逼近这一理想模型。

2.2 vruntime：虚拟运行时间

vruntime 是 CFS 调度器的核心度量。其计算考虑了进程的实际运行时间、优先级（nice 值）以及 CPU 频率等因素。

vruntime 计算公式（简化）：

vruntime += 实际运行时间 × (NICE_0_LOAD / 进程权重)

其中 NICE_0_LOAD 是 nice 值为 0 时的基准权重（1024）。进程权重由 nice 值映射得到，nice 值越低（优先级越高），权重越大，vruntime 增长越慢。

2.3 红黑树：高效的就绪队列

CFS 使用 红黑树（Red-Black Tree） 来组织所有可运行进程。红黑树是一种自平衡二叉查找树，其查找、插入、删除操作的时间复杂度均为 O(log N)。

• 键值： 每个节点的键值为该进程的 vruntime。
• 最左节点： 红黑树中最左侧的节点（vruntime 最小）即为下一个要运行的进程。
• 调度决策： 调度器每次选择最左节点，将其从红黑树中摘下，投入运行。
• 重新入队： 进程运行一段时间后，其 vruntime 增加，调度器将其重新插入红黑树，位置可能右移。

2.4 调度周期与最小粒度

CFS 引入了 调度延迟（sched_latency） 和 最小粒度（min_granularity） 两个参数来控制调度频率。

• sched_latency（默认 6ms）： 保证每个可运行进程在至少一个调度周期内都能获得一次 CPU 时间。
• min_granularity（默认 0.75ms）： 进程每次运行的最小时间片，防止过于频繁的上下文切换导致性能下降。

当可运行进程数量 N 较少时，每个进程的时间片 = sched_latency / N；当 N 较大时，时间片被 min_granularity 限制，避免切换开销过大。

2.5 CFS 调度流程总结

1. 时钟中断触发： 周期性调度器（scheduler_tick）更新当前进程的 vruntime。
2. 检查是否需要抢占： 如果当前进程的 vruntime 超过了红黑树最左节点的 vruntime，则设置 TIF_NEED_RESCHED 标志。
3. 主调度器执行： 在返回用户空间或中断返回时，检查 TIF_NEED_RESCHED 标志，调用 schedule() 函数。
4. 选择下一个进程： 从红黑树中摘取最左节点，执行上下文切换。
5. 进程入队： 被换出的进程根据其新的 vruntime 重新插入红黑树。

2.6 CFS 与 Android 调度组（Sched Group）

Android 在 CFS 基础上引入了 调度组（Sched Group） 机制，用于对进程进行分组管理。例如，前台应用组、后台服务组、系统组件组等。调度组之间按权重分配 CPU 时间，组内进程再按 CFS 规则竞争。