📚 课程目录第4章 Linux调度器演进

4. Linux调度器演进

理解Android的CPU调度与功耗优化，绕不开Linux调度器的演进史。Android的调度策略、EAS（Energy Aware Scheduling）、厂商的调频调核逻辑，本质上都建立在Linux调度器提供的基础设施之上。本节沿着O(n)、O(1)、CFS、EEVDF四个阶段，梳理其设计思想、关键数据结构，以及它们如何影响Android场景。

一、演进脉络与设计思想

调度器的核心问题始终是：在有限CPU上，如何公平且高效地分配时间给可运行任务。不同时代的硬件约束不同，答案也不同。

O(n)调度器（Linux 2.4及以前）：每次调度遍历整个runqueue，选出优先级最高或时间片剩余最多的任务。任务数n增大时开销线性上升，且交互式任务响应差。
O(1)调度器（Linux 2.6早期）：用两个优先级数组（active/expired）加位图，把选任务变成"找最高非空优先级位"的常数操作。交互任务通过动态优先级奖励获得更好响应，但启发式规则复杂、公平性难保证。
CFS完全公平调度（Linux 2.6.23起）：放弃固定时间片，改用虚拟运行时间vruntime，用红黑树维护，总是选vruntime最小的任务。公平性可量化，交互与批处理统一建模。
EEVDF（Linux 6.6起）：在CFS基础上引入"资格时间"（eligibility）与滞后（lag）约束，用最早合格虚拟截止时间选任务，解决CFS在延迟敏感任务上的公平性与唤醒延迟问题。

演进主线：从"遍历找最优"到"结构加速"，再到"虚拟时间公平"，最后到"带截止时间的公平"。每一步都在回答：公平与延迟如何兼得。

二、关键数据结构对比

数据结构决定了调度器的复杂度与行为特征。下表对比四个阶段的核心结构。

调度器	核心结构	选任务复杂度	公平性模型	典型问题
O(n)	链表runqueue	O(n)	优先级+时间片	扩展性差、交互延迟
O(1)	优先级数组+位图	O(1)	动态优先级启发式	公平性难保证
CFS	红黑树（vruntime为键）	O(log n)	虚拟运行时间	唤醒延迟、组调度复杂
EEVDF	红黑树（eligible+deadline）	O(log n)	滞后约束+截止时间	实现较新、调参需谨慎

CFS的红黑树以vruntime为键，最左节点即下一个运行任务。EEVDF同样用红黑树，但键变为虚拟截止时间，并维护eligible集合，只有合格任务才参与选择。这一变化让延迟敏感任务能更早获得CPU。

三、Android场景适配

Android是典型的交互式移动负载：前台UI线程、渲染线程、音频线程对延迟极敏感，而后台任务可容忍延迟。CFS的vruntime公平在多数场景表现良好，但存在两个痛点：一是唤醒任务可能因vruntime落后而"抢占"过多，导致前台抖动；二是组调度与cgroup配合时，权重分配不够精细。

Android通过以下方式适配：

调度策略与优先级：UI/渲染线程常用SCHED_FIFO或高nice值，音频用RT策略，保证关键路径低延迟。
cgroup与schedtune：将任务分组，给前台组更高CPU份额，后台组限流，实现"体验优先"。
EAS与schedutil：在CFS/EEVDF之上，结合CPU容量与能耗模型，把任务放到能效比最优的核上，并联动调频。
EEVDF的引入：6.6内核后，Android逐步评估EEVDF对唤醒延迟和公平性的改善，尤其在多任务并发时减少前台卡顿。

在Android上观察调度行为，可读取/proc/schedstat、/proc//sched，或用perf sched、systrace查看任务迁移与延迟。

四、案例与实操观察

假设一个前台滑动场景：UI线程被唤醒后需要尽快执行。在CFS下，若其vruntime远小于当前运行任务，会立即抢占；但若多个任务同时唤醒，红黑树选择最左节点，可能引入微秒级抖动。EEVDF通过eligible集合与截止时间，让"已经等待较久"的任务优先，减少这种抖动。

可用如下命令观察调度延迟与迁移：

# 查看进程调度统计
cat /proc/<pid>/schedstat
# 查看调度器版本与特性
uname -r
cat /proc/sys/kernel/sched_* 2>/dev/null
# 用perf观察调度事件
perf sched record -a sleep 5
perf sched latency

在Android设备上，还可通过systrace查看"cpu_frequency"、"sched_wakeup"、"sched_switch"等事件，判断是调度延迟还是调频滞后导致卡顿。

五、常见误区与复盘

误区一：CFS就是绝对公平。CFS公平的是vruntime，不是墙钟时间；权重、nice、cgroup都会改变实际份额。
误区二：O(1)一定比CFS快。O(1)选任务快，但公平性和交互体验未必好；复杂度不是唯一指标。
误区三：EEVDF只是CFS换名。EEVDF引入了资格与截止时间，改变了选任务的语义，对延迟敏感负载更友好。
误区四：调度器决定一切。功耗与体验还受调频、热管理、CPU拓扑、任务放置共同影响，调度只是其中一环。

在Android工程中，不要只盯调度器版本。先确认任务优先级、cgroup分组、CPU亲和性与调频策略，再评估是否需要调整调度参数。

复盘时建议按"负载特征→调度策略→数据结构→延迟/功耗指标"的顺序排查：先看任务是否RT/CFS，再看runqueue与vruntime分布，最后结合systrace与功耗数据定位瓶颈。理解O(n)到EEVDF的演进，能帮助你在Android复杂场景中做出更合理的调度与功耗取舍。