1. 课程导论与背景

1.1 Linux调度器演进全景

Linux内核调度器经历了从简单到复杂、从粗放到精细的四个主要阶段。每个阶段的更迭都源于对吞吐量、公平性、实时性和功耗控制等维度的更高要求。理解这段演进史，是进行平台移植适配的前提。

1.2 各阶段调度器深度解析

1.2.1 O(n) 调度器：朴素但低效

早期Linux调度器采用全局就绪队列，每次调度时遍历所有进程计算“好度”（goodness）。

• 数据结构： 单一全局链表
• 调度开销： 随进程数线性增长，高负载下CPU空转严重
• 多核问题： 全局锁竞争激烈，SMP扩展性极差
• 交互体验： 无抢占点设计，桌面操作卡顿明显

1.2.2 O(1) 调度器：位图加速的里程碑

Ingo Molnar 在2.6内核中引入了基于优先级位图的O(1)调度器，将调度决策时间降为常数级。

• 双队列结构： active 队列 + expired 队列，时间片耗尽后交换
• 优先级位图： 140级优先级，通过 __ffs() 指令O(1)找到最高优先级进程
• 负载均衡： 引入 per-CPU 运行队列，支持进程迁移
• 实时性： 支持 SCHED_FIFO / SCHED_RR 实时策略

/* O(1) 调度器核心数据结构示意 */
struct prio_array {
    unsigned long bitmap[BITMAP_SIZE];  /* 优先级位图 */
    struct list_head queue[MAX_PRIO];   /* 每优先级链表 */
    int nr_active;                      /* 活跃进程计数 */
};

struct rq {
    spinlock_t lock;
    struct prio_array *active, *expired;
    struct task_struct *curr;
    /* ... */
};

1.2.3 CFS 调度器：公平性的数学表达

Con Kolivas 的“楼梯调度器”思想启发了 CFS（Completely Fair Scheduler），由 Ingo Molnar 在2.6.23中合入。CFS用红黑树替代了优先级数组，以“虚拟运行时间”（vruntime）为核心度量。

• 红黑树： 按 vruntime 排序，最左节点为下一个调度进程
• 虚拟运行时间： vruntime += 实际运行时间 * (NICE_0_LOAD / 进程权重)
• 调度粒度： 默认调度周期 sysctl_sched_latency（6ms），最小粒度 sysctl_sched_min_granularity（0.75ms）
• 组调度： 支持 CPU cgroup，实现进程组级别的公平分配

/* CFS 核心调度实体 */
struct sched_entity {
    struct rb_node      run_node;       /* 红黑树节点 */
    unsigned long       vruntime;       /* 虚拟运行时间 */
    u64                 exec_start;     /* 当前执行开始时间 */
    u64                 sum_exec_runtime; /* 总执行时间 */
    struct load_weight  load;           /* 调度权重 */
    /* ... */
};

1.2.4 EEVDF 调度器：延迟感知的新一代

EEVDF（Earliest Eligible Virtual Deadline First）在Linux 6.6中作为可选调度器引入，旨在解决CFS对延迟敏感型负载（如音视频、游戏）支持不足的问题。

• 虚拟截止时间： 每个进程维护 deadline，调度器选择最早截止时间的进程
• 资格判定： 只有“合格”（eligible）的进程才参与调度，避免饥饿
• 抢占边界： 更精确的抢占点计算，减少不必要的上下文切换
• 兼容性： 与CFS共享红黑树结构，调度策略接口不变

/* EEVDF 调度实体扩展 */
struct sched_entity {
    struct rb_node      run_node;
    unsigned long       vruntime;
    u64                 deadline;       /* 虚拟截止时间 */
    u64                 min_deadline;   /* 子实体最小截止时间 */
    s64                 lag;            /* 滞后量，用于资格判定 */
    /* ... */
};

1.3 ARM64平台特性与调度器移植必要性

1.3.1 ARM64架构关键特性

1.3.2 移植必要性的三个维度

1. 性能维度： x86调度器假设同构核心，ARM64的big.LITTLE架构要求调度器能识别核心类型（通过 cpu_capacity 值），将重负载调度到大核，轻负载调度到小核。未经移植的调度器会导致大核过载或小核浪费。
2. 功耗维度： ARM64移动设备对功耗极度敏感。调度器需与 cpuidle 子系统协同，在CPU空闲时快速进入深度睡眠。CFS/EEVDF的调度周期和粒度直接影响唤醒频率和功耗。
3. 实时维度： ARM64在汽车、工业控制领域广泛应用，需要 PREEMPT_RT 补丁。调度器移植必须确保自旋锁、中断上下文、RCU等机制在ARM64上的实时性符合要求。

1.4 调度器架构与ARM64的映射关系

下图展示了Linux调度器核心组件与ARM64硬件特性的映射关系，帮助理解移植工作的切入点。

1.5 本课程实践路线图

本课程将按照以下路径，逐步完成调度器从x86到ARM64的完整移植适配：

1. 环境准备： 搭建ARM64交叉编译环境，配置QEMU/真实硬件调试环境
2. 内核配置： 分析 arch/arm64/Kconfig 调度相关选项，生成最小配置
3. 拓扑检测： 实现 store_cpu_topology()，正确识别DSU簇和核心类型
4. cpu_capacity 校准： 基于Dhrystone或EEMBC基准测试，计算每个核心的算力值
5. 定时器适配： 校准 arch_timer 频率，确保vruntime/deadline计算准确
6. 上下文切换优化： 优化 cpu_switch_to() 汇编代码，减少寄存器保存/恢复开销
7. 负载均衡改造： 修改 find_busiest_group() 和 find_idlest_cpu() 支持异构核心
8. 电源管理协同： 实现 select_task_rq_fair() 与 cpuidle 的唤醒延迟优化
9. 实时性增强： 移植 PREEMPT_RT 补丁，验证ARM64上的抢占延迟
10. 性能验证： 使用 cyclictest、hackbench、schbench 等工具进行基准测试