深入 Linux 调度器:scheduler_tick、schedule 与上下文切换——以 RPi OS 调度器实现为对照
深入 Linux 调度器:scheduler_tick、schedule 与上下文切换——以 RPi OS 调度器实现为对照
导读
本文聚焦 Raspberry Pi OS(RPi OS)学习项目课程 4.4「Scheduler」,深入剖析 Linux 内核(v4.14 基线)调度器的两个核心入口点——定时器中断驱动的 scheduler_tick() 与主动/被动触发的 schedule(),并围绕"上下文切换(context switch)"这一高度依赖体系结构的概念,逐层拆解从 CFS 红黑树选任务、__schedule 调度流程到 arm64 汇编级 cpu_switch_to 寄存器保存/恢复的完整链路。通过对照本仓库 src/lesson04 中 RPi OS 自己的调度器实现(sched.c、sched.S、entry.S、timer.c),读者将理解 Linux 调度机制与一个最小化可运行实现之间的映射关系,掌握调度器的工作原理与 arm64 上下文切换的底层细节。
一、调度器的两个入口点与上下文切换
在之前的课程中,我们已经接触了 task_struct、CFS(完全公平调度器)、红黑树运行队列等大量概念(详见 调度程序的基本结构)。为了让整幅图景完整,本章需要研究三个关键对象:
scheduler_tick()—— 在每个定时器中断时被调用的函数,负责更新当前任务的时间统计与运行时信息,并据此决定是否需要抢占。schedule()—— 每当当前任务需要被重新调度(被抢占、主动让出 CPU 等)时被调用的函数。- 上下文切换(Context Switch) —— 挂起当前任务、转而运行另一个任务的过程。这一过程高度特定于体系结构(architecture-specific),与我们在 RPi OS 上所做的工作密切相关。
对照本仓库的 RPi OS 实现,这三个对象分别对应 sched.c 中的 timer_tick()(定时器中断触发)、schedule()/_schedule()(重新调度)以及 sched.S 中的 cpu_switch_to(汇编上下文切换)。下面逐一展开。
二、scheduler_tick:定时器中断里的调度心跳
2.1 为什么 scheduler_tick 重要
scheduler_tick() 的重要性体现在两点:
- 它为调度器提供了一种更新当前任务时间统计信息和运行时信息的途径;
- 这些运行时信息随后被用来判断当前任务是否需要被抢占;如果需要,则调用
schedule()完成切换。
与大多数此前探索过的内核函数一样,scheduler_tick 过于复杂,无法在一篇文章中完全解释清楚,因此我们只强调其最重要的部分。在 Linux v4.14 中,它定义于 kernel/sched/core.c,主要工作被委托给 CFS 调度类的方法。
2.2 task_tick_fair:CFS 的计时器回调
scheduler_tick() 的主要工作发生在 CFS 的方法 task_tick_fair()(kernel/sched/fair.c)内部。该方法会针对当前任务对应的 sched_entity 调用 entity_tick()。
阅读源码时你可能会疑惑:为什么不直接用当前的 sched_entity 调用 entity_tick(),而要借助 for_each_sched_entity 宏?
关键在于:for_each_sched_entity 并不会遍历系统中所有的 sched_entity。它只沿着 sched_entity 的继承树向上遍历到根节点。当任务被分组(task group)时这一设计非常有用——在更新了某个特定任务的运行时信息之后,与之对应的整个任务组的 sched_entity 也会被一并更新,从而让组级别的调度统计保持正确。
2.3 entity_tick:更新统计与抢占判定
entity_tick() 主要做两件事:
(1)调用 update_curr() —— 负责更新任务的 vruntime 以及运行队列的 min_vruntime。这里需要记住的重要一点是:vruntime 始终基于两个因素计算——任务实际被执行了多长时间,以及任务的优先级。优先级越高的任务,其 vruntime 增长得越慢,因此在 CFS 的红黑树中更容易保持在左侧(即更容易被选中)。
(2)调用 check_preempt_tick() —— 检查当前任务是否需要被抢占。抢占发生在两种情况下:
- 情况一:当前任务已经运行了太长时间。注意,此时比较使用的是正常时间(real time)而非
vruntime——这是为了防止一个任务通过某种方式无限期霸占 CPU。 - 情况二:存在一个
vruntime更小的任务,且两者vruntime的差值大于某个阈值。此时说明有"更饥饿"的任务在等待,理应让出 CPU。
在上述两种情况下,当前任务都会通过调用 resched_curr() 函数被标记为需要抢占。
2.4 从标记抢占到真正调度
resched_curr() 的调用后果我们在上一章(分派任务)中已经看到:它会为当前任务设置 TIF_NEED_RESCHED 标志,该标志最终导致 schedule() 被调用。
在 RPi OS 中,与 scheduler_tick 对应的函数是 sched.c 中的 timer_tick()(由定时器中断处理函数 handle_timer_irq 调用,见 timer.c):
void timer_tick()
{
--current->counter;
if (current->counter>0 || current->preempt_count >0) {
return;
}
current->counter=0;
enable_irq();
_schedule();
disable_irq();
}
可以看到,RPi OS 的"抢占判定"远比 Linux 简单:每个定时器 tick 将当前任务的 counter 减 1;只有当 counter 归零且当前没有禁用抢占(preempt_count == 0)时,才重新调度。这里体现了与 Linux 相同的思想——计时器中断是驱动调度决策的心跳。
值得一提的是 enable_irq() 这一行:我们正处在中断处理程序内部,默认情况下中断是被禁用的。在 _schedule() 执行期间启用中断是有意为之的,原因将在下文调度算法一节详述。
三、schedule:看似简单实则精妙的调度函数
3.1 从 schedule 到 __schedule
我们已经见过很多使用 schedule 的示例(kernel_main 中的主动让出、定时器中断里的被动抢占),现在终于可以看看这个函数的真实内部。令人惊讶的是,schedule() 的内部非常简洁。
schedule() 的主要工作都在 __schedule() 函数(kernel/sched/core.c)中完成,其核心执行链如下:
schedule()
└─> __schedule()
├─> pick_next_task() // 选择下一个要运行的任务
│ └─> pick_next_task_fair() // CFS 调度类的方法
│ └─> 从红黑树中选择最左(vruntime 最小)节点
└─> context_switch()
└─> __switch_to() // 体系结构相关准备
└─> cpu_switch_to() // 汇编:切换寄存器与栈
3.2 pick_next_task:谁会是下一个
__schedule 调用 pick_next_task()(kernel/sched/core.c),后者将大部分工作重定向给 CFS 调度类的 pick_next_task_fair() 方法(kernel/sched/fair.c)。
正如你所预料的那样,pick_next_task_fair() 在通常情况下只是从红黑树中选取最左边的元素并返回它——因为 CFS 红黑树的特性决定了:任何节点的左子节点 vruntime 总是小于或等于父节点,因此最左节点就是 vruntime 最小、最"饥饿"的任务,理应被选中。得益于红黑树 O(log n) 的复杂度,即便系统中有成千上万个并发任务,这一选择过程依然非常迅速。
3.3 context_switch 与 __switch_to:体系结构相关部分
选定下一个任务后,__schedule 调用 context_switch()(kernel/sched/core.c)。该函数会做一些准备工作,然后调用体系结构特定的 __switch_to()(arm64 下位于 arch/arm64/kernel/process.c),在这里为切换准备低层、与架构相关的任务参数。
__switch_to 首先切换一些额外的任务组件,例如:
- TLS(Thread-local Storage,线程本地存储);
- 已保存的浮点寄存器与 NEON 寄存器。
这些组件与通用寄存器不同,它们要么有独立的系统寄存器(如 TLS),要么数量庞大且具有独立的启用机制(如 SIMD/FP 寄存器),因此需要单独处理。
3.4 cpu_switch_to:真正的切换发生地
真正的切换发生在汇编函数 cpu_switch_to()(arm64 下位于 arch/arm64/kernel/entry.S)中。这个函数你应该已经很熟悉了,因为 RPi OS 几乎原封不动地复制了它(见 sched.S):
.globl cpu_switch_to
cpu_switch_to:
mov x10, #THREAD_CPU_CONTEXT
add x8, x0, x10
mov x9, sp
stp x19, x20, [x8], #16 // store callee-saved registers
stp x21, x22, [x8], #16
stp x23, x24, [x8], #16
stp x25, x26, [x8], #16
stp x27, x28, [x8], #16
stp x29, x9, [x8], #16
str x30, [x8]
add x8, x1, x10
ldp x19, x20, [x8], #16 // restore callee-saved registers
ldp x21, x22, [x8], #16
ldp x23, x24, [x8], #16
ldp x25, x26, [x8], #16
ldp x27, x28, [x8], #16
ldp x29, x9, [x8], #16
ldr x30, [x8]
mov sp, x9
ret
你可能还记得,这个函数切换被调用者保存(callee-saved)的寄存器和任务堆栈。函数返回之后,新任务将使用自己的内核栈继续运行。
四、RPi OS 视角:调度算法与切换的完整映射
4.1 调度算法:来自 Linux 0.01 的遗产
RPi OS 的 _schedule() 算法几乎是从 Linux 内核第一个发行版(Linux 0.01)中精确复制而来的,全部代码位于 sched.c:
void _schedule(void)
{
preempt_disable();
int next,c;
struct task_struct * p;
while (1) {
c = -1;
next = 0;
for (int i = 0; i < NR_TASKS; i++){
p = task[i];
if (p && p->state == TASK_RUNNING && p->counter > c) {
c = p->counter;
next = i;
}
}
if (c) {
break;
}
for (int i = 0; i < NR_TASKS; i++) {
p = task[i];
if (p) {
p->counter = (p->counter >> 1) + p->priority;
}
}
}
switch_to(task[next]);
preempt_enable();
}
该算法的工作原理如下:
- 第一个内层
for循环遍历所有任务,尝试找到处于TASK_RUNNING状态且counter最大的任务。如果找到的任务counter大于 0,立即跳出外层while循环并切换到该任务。 - 如果找不到这样的任务,说明当前不存在
TASK_RUNNING任务,或所有此类任务的counter均为 0。在实际操作系统中,前者可能发生在所有任务都在等待中断时。此时执行第二个嵌套for循环:对每个任务(无论状态如何)执行counter = (counter >> 1) + priority。这种递增方式非常巧妙:- 任务经过第二个
for循环的迭代次数越多,其counter恢复得越高; - 任务
counter永远不会超过2 × priority。
- 任务经过第二个
- 随后重复整个过程。只要至少有一个任务处于
TASK_RUNNING状态,外层while循环的第二次迭代就会是最后一次(第一次迭代后所有计数器都已非零)。如果没有TASK_RUNNING任务,过程会持续循环,直到某个任务变为TASK_RUNNING。
4.2 为什么调度期间必须启用中断?
一个自然的问题是:在单 CPU 上运行时,如果所有任务都不处于 TASK_RUNNING 状态,那么在这个循环执行期间任务状态如何能够改变?答案是:如果有任务在等待中断,该中断可能在执行 _schedule 函数时到来,而中断处理程序可以改变任务状态。这正解释了为什么在 _schedule 执行期间必须启用中断。
同时,这也揭示了禁用中断与禁用抢占之间的重要区别:
_schedule在整个函数执行期间禁用抢占(通过preempt_disable()),确保在原始函数执行过程中不会出现嵌套的schedule调用;- 但在
_schedule执行期间,中断仍然可能合法发生(timer_tick中显式调用了enable_irq())。
虽然 RPi OS 目前尚未实现"任务等待中断"这一场景,但理解它是必要的——因为这是核心调度算法的一部分,未来会添加类似功能。
4.3 switch_to 与上下文切换的汇编实现
找到 counter 非零的 TASK_RUNNING 任务后,switch_to() 被调用(sched.c):
void switch_to(struct task_struct * next)
{
if (current == next)
return;
struct task_struct * prev = current;
current = next;
cpu_switch_to(prev, next);
}
这里先检查下一个任务是否与当前任务不同;若不同则更新 current 变量,然后把实际工作重定向到汇编函数 cpu_switch_to(prev, next)。
逐行解读汇编(对照 sched.S):
mov x10, #THREAD_CPU_CONTEXT; add x8, x0, x10:THREAD_CPU_CONTEXT常量(定义于 sched.h,值为 0)是cpu_context结构在task_struct内的偏移量;x0是第一个参数——当前(要切出)的task_struct指针。执行后x8指向当前的cpu_context。mov x9, sp保存当前栈指针;随后 7 条stp/str指令按照cpu_context结构中定义的顺序存储被调用者保存寄存器:x19-x28、x29(作为fp帧指针)、sp、x30(链接寄存器,作为pc保存)。add x8, x1, x10:x1是下一个task_struct指针,因此x8现在指向下一个任务的cpu_context。- 接下来 7 条
ldp/ldr指令从下一个cpu_context恢复被调用者保存寄存器,并用mov sp, x9恢复新任务的栈指针。 ret:函数返回链接寄存器(x30)指向的位置。如果是首次切换到某任务,该位置是ret_from_fork(见 entry.S);其余情况则是此前cpu_switch_to保存到cpu_context中的返回位置。
4.4 新任务如何启动:ret_from_fork
在 copy_process 中,新任务的 cpu_context.pc 被设置为 ret_from_fork,x19 = fn(要执行的函数)、x20 = arg(函数参数),sp 指向新分配页面顶部。ret_from_fork 的定义在 entry.S:
.globl ret_from_fork
ret_from_fork:
bl schedule_tail
mov x0, x20
blr x19 //should never return
它首先调用 schedule_tail()(sched.c),其作用仅仅是重新启用抢占(preempt_enable())——因为在 copy_process 中 preempt_count 被显式设置为 1 以禁止中途调度;随后把 x20 中的参数放入 x0,跳转到 x19 指向的函数开始执行。
4.5 调度如何与异常进入/退出协同
上一课中我们已经见过 kernel_entry 和 kernel_exit 宏(entry.S)用于保存和恢复处理器状态。引入调度器后出现了一个新问题:现在完全合法地存在"以某个任务的身份进入中断,却以另一个任务的身份退出中断"的情形。
这是一个问题,因为用于从中断返回的 eret 指令依赖如下事实:返回地址存储在 elr_el1 中,处理器状态存储在 spsr_el1 中。因此,如果在处理中断的过程中切换了任务,就必须把这两个寄存器与所有通用寄存器一起保存和恢复:
.macro kernel_entry
sub sp, sp, #S_FRAME_SIZE
stp x0, x1, [sp, #16 * 0]
...
mrs x22, elr_el1
mrs x23, spsr_el1
stp x30, x22, [sp, #16 * 15]
str x23, [sp, #16 * 16]
.endm
.macro kernel_exit
ldr x23, [sp, #16 * 16]
ldp x30, x22, [sp, #16 * 15]
msr elr_el1, x22
msr spsr_el1, x23
...
eret
.endm
正是 kernel_entry 把 elr_el1 和 spsr_el1 保存到任务栈上(连同 31 个通用寄存器),kernel_exit 在恢复时把它们写回系统寄存器,才使得任务 1 进入中断、任务 2 被切换运行、稍后再切回任务 1 并从中断现场恢复成为可能。
4.6 完整事件序列:从启动到第二次上下文切换
为了把上述异步交互串起来,这里给出从系统启动到第二次上下文切换的事件序列(节选自 RPi OS 调度器实现,那里配有每一步的内存布局图):
- 内核完成初始化并执行
kernel_main;init 任务栈从LOW_MEMORY(4 MB)开始。 kernel_main第一次调用copy_process,分配一个 4 KB 页面,在页面底部放置任务 1 的task_struct。kernel_main第二次调用copy_process,创建任务 2 并加入任务数组。kernel_main主动调用schedule(),决定先运行任务 1。cpu_switch_to把被调用者保存寄存器保存到 init 任务的cpu_context中。cpu_switch_to从任务 1 的cpu_context恢复寄存器:sp指向0x00401000,链接寄存器指向ret_from_fork,x19指向process函数、x20指向字符串"12345"。ret跳转到ret_from_fork,随后以参数"12345"调用process,任务 1 开始执行并向下增长自己的栈。- 定时器中断到来,
kernel_entry把通用寄存器及elr_el1、spsr_el1保存到任务 1 栈底。 - 中断处理中调用
_schedule(),决定运行任务 2。此时任务 1 的栈继续向"中断栈"区域增长。 cpu_switch_to切换到任务 2(与任务 1 相同的步骤),任务 2 开始执行、栈向下增长。注意此时并未从中断返回,但这没关系——因为中断已在timer_tick中通过enable_irq()被重新启用。- 又一个定时器中断到来,
kernel_entry把寄存器保存到任务 2 栈底,任务 2 的中断栈开始增长。 _schedule()观察到所有任务counter均为 0,于是为各任务恢复计数器(counter = (counter >> 1) + priority)。_schedule()选择任务 1(此时 init/任务 1/任务 2 计数器值相等,选择哪个都合法,教程以任务 1 为例)。cpu_switch_to恢复任务 1 此前保存的寄存器——链接寄存器指向上次调用cpu_switch_to的位置(switch_to内部),sp指向任务 1 中断栈底部。timer_tick从_schedule()返回处恢复执行,最终调用kernel_exit;到此时任务 1 的中断栈已折叠为 0。kernel_exit恢复通用寄存器及elr_el1/spsr_el1,elr_el1现在指向process函数中间的某个位置。eret使用elr_el1跳回process函数,任务 1 恢复正常执行。
这串步骤顺序是整个教程中最重要的内容之一。如果理解有困难,可以去做本课练习(见 练习)。
五、Linux 与 RPi OS 调度机制对照总结
| 维度 | Linux(v4.14) | RPi OS(本仓库 lesson04) |
|---|---|---|
| 定时器驱动的调度入口 | scheduler_tick() → task_tick_fair() → entity_tick() |
handle_timer_irq() → timer_tick()(timer.c、sched.c) |
| 运行时统计更新 | update_curr() 更新 vruntime 与 min_vruntime |
counter--(每个 tick 递减) |
| 抢占判定 | check_preempt_tick():运行过久(正常时间)或 vruntime 差超阈值 |
counter == 0 且 preempt_count == 0 |
| 抢占标记 | resched_curr() 设置 TIF_NEED_RESCHED |
直接调用 _schedule() |
| 选择下一个任务 | pick_next_task() → pick_next_task_fair()(红黑树最左节点) |
_schedule() 遍历 task[] 选 counter 最大的 TASK_RUNNING 任务 |
| 调度函数 | schedule() → __schedule() |
schedule() → _schedule() |
| 体系结构准备 | context_switch() → __switch_to()(切换 TLS、浮点/NEON 寄存器) |
switch_to()(更新 current) |
| 最终切换 | 汇编 cpu_switch_to()(callee-saved 寄存器 + 栈) |
汇编 cpu_switch_to(sched.S,几乎原样复制自 Linux) |
| 新任务入口 | ret_from_fork 机制 |
ret_from_fork(entry.S) |
| 中断现场保存 | pt_regs + elr_el1/spsr_el1 |
kernel_entry/kernel_exit 宏保存并恢复 elr_el1/spsr_el1(entry.S) |
可以看到,虽然 RPi OS 的调度器在策略上做了极大简化(用线性扫描 + counter 取代了红黑树 + vruntime),但在机制骨架上——定时器驱动的抢占判定、主动/被动调度的入口、switch_to 包装、汇编 cpu_switch_to 切换 callee-saved 寄存器与内核栈、ret_from_fork 启动新任务、异常进出时保存 elr_el1/spsr_el1——两者保持了高度一致,这正体现了"以 Linux 为蓝本实现教学用 OS"的项目设计思路。
六、结论
至此,我们对 Linux 调度器的探索告一段落。令人欣慰的是,如果只关注最基本的工作流程,调度器似乎并不那么困难:定时器中断定期唤醒 scheduler_tick 更新统计并判定抢占;需要重新调度时,schedule/__schedule 从 CFS 红黑树中选出 vruntime 最小的任务,经由 context_switch、__switch_to 到达汇编层 cpu_switch_to,完成被调用者保存寄存器与内核栈的切换。理解基本工作流之后,你可能还想在调度代码中另辟蹊径、关注更多细节——因为其中值得推敲的地方非常多。
就目前而言,我们对当前的理解已经满意,准备进入下一课——它将描述用户进程与系统调用(对应仓库中 lesson05 的实现)。对 RPi OS 侧调度器完整实现的进一步研读,可参考 RPi OS 调度器(4.1);任务创建机制见 分派任务(4.3);配套练习见 进程调度器练习(4.5)。