深入 Linux 调度程序基本结构:以 Raspberry Pi OS 为例理解 task_struct、调度类与 CFS
深入 Linux 调度程序基本结构:以 Raspberry Pi OS 为例理解 task_struct、调度类与 CFS
导读
本文是 raspberry-pi-os 教程第 4 课《进程调度程序》的第二讲,主题是理解 Linux 内核调度程序所依赖的核心数据结构与算法:task_struct、调度器类(sched_class)、完全公平调度器(CFS)及其背后的运行队列与红黑树。在之前的课程中,我们大多在处理体系结构特定代码和驱动程序代码,而本课第一次深入 Linux 内核核心。读完本文,你将掌握调度程序的"最小知识集":既能看懂 Linux v4.14 调度器源码的骨架,也能对照本仓库中 RPi OS 自己实现的 task_struct、cpu_context 与调度代码(src/lesson04/src/sched.c),理解真实内核与教学内核之间的对应关系,为后续学习任务创建(fork)与调度执行(scheduler)打下基础。
为什么需要先理解这些结构
在学习 Linux 调度器源码之前,必须先熟悉它赖以建立的主要概念。Linux 调度器是一个庞大而复杂的子系统,但它的核心脉络可以压缩为几个关键问题:
- 每个正在运行的任务在内核中是如何被描述的?(
task_struct) - 调度算法是如何做到可扩展、可替换的?(
sched_class调度器类) - 默认对用户任务使用的"完全公平调度器"(CFS)是如何选择下一个任务的?(
vruntime+ 红黑树) - 每个 CPU 如何组织等待运行的任务?(运行队列
rq与cfs_rq) - 中断/异常发生时保存的寄存器如何被描述与复用?(
pt_regs)
本文就围绕这五组问题展开,并在每一节对照 RPi OS 仓库中的实现,让抽象的概念落到可以运行的代码上。
task_struct:内核中最关键的结构之一
task_struct 是 Linux 内核中最重要的结构之一,它包含关于每个正在运行任务(进程/线程)的全部信息。我们在第 2 课已经简要接触过 task_struct,并且 RPi OS 也实现了自己的版本。下面逐一解析与本讨论相关的关键字段。
thread_info:体系结构相关字段的存放处
thread_info 是 task_struct 的第一个字段,包含所有必须由底层体系结构代码访问的字段。它是体系结构特定的——在 arm64 下,它是一个只有几个字段的简单结构:
struct thread_info {
unsigned long flags; /* low level flags */
mm_segment_t addr_limit; /* address limit */
#ifdef CONFIG_ARM64_SW_TTBR0_PAN
u64 ttbr0; /* saved TTBR0_EL1 */
#endif
int preempt_count; /* 0 => preemptable, <0 => bug */
};
flags字段使用非常频繁——它包含当前任务状态信息(是否处于跟踪状态、是否有信号挂起等)。在 Linux v4.14 中,所有可能的标志值定义在arch/arm64/include/asm/thread_info.h(如TIF_NEED_RESCHED、TIF_SIGPENDING等)。preempt_count与抢占密切相关:值为 0 表示任务当前可被抢占,小于 0 表示出现 bug。
对照 RPi OS 仓库,我们自己的 task_struct 也承担了类似职责——把架构相关的上下文切换信息放在结构最前面(偏移 0),这样汇编代码可以直接访问。在 src/lesson04/include/sched.h 中可以看到:
#define THREAD_CPU_CONTEXT 0 // offset of cpu_context in task_struct
struct cpu_context {
unsigned long x19;
unsigned long x20;
unsigned long x21;
unsigned long x22;
unsigned long x23;
unsigned long x24;
unsigned long x25;
unsigned long x26;
unsigned long x27;
unsigned long x28;
unsigned long fp;
unsigned long sp;
unsigned long pc;
};
struct task_struct {
struct cpu_context cpu_context;
long state;
long counter;
long priority;
long preempt_count;
};
注意 THREAD_CPU_CONTEXT 被定义为 0,即 cpu_context 位于 task_struct 的最开头——这与 Linux 中 thread_info 作为第一个字段的思路一脉相承:上下文切换汇编代码通过该固定偏移直接存取被调用者保存寄存器。
state:任务的当前状态
state 描述任务当前状态:是否正在运行、是否在等待中断、是否已退出等。Linux v4.14 中所有可能的任务状态定义在 include/linux/sched.h(如 TASK_RUNNING、TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE、TASK_STOPPED、EXIT_ZOMBIE 等)。RPi OS 目前只实现了一个状态:
#define TASK_RUNNING 0
在 src/lesson04/src/sched.c 的选择逻辑中,只挑选 p->state == TASK_RUNNING 的任务,正对应 Linux 中"可运行队列"的语义。
stack:指向内核栈的指针
在 RPi OS 中,task_struct 始终位于任务栈的底部,因此可以用指向 task_struct 的指针作为指向栈的指针;内核栈大小恒定(RPi OS 中为 THREAD_SIZE 4096,见 src/lesson04/include/sched.h),所以找到栈末端也很容易。早期 Linux 内核采用相同方法;而现在引入了虚拟映射栈(virtually mapped stacks,CONFIG_VMAP_STACK)之后,Linux 的 stack 字段用于存储指向内核栈的指针。在 RPi OS 中,cpu_context.sp 被设置为 (unsigned long)p + THREAD_SIZE,即新任务栈顶,见 src/lesson04/src/fork.c:
p->cpu_context.sp = (unsigned long)p + THREAD_SIZE;
thread:上下文切换时使用的体系结构信息
thread 字段对应另一个重要的体系结构特定结构 thread_struct,它包含上下文切换期间使用的全部信息(如 cpu_context)。RPi OS 实现了自己的 cpu_context,其使用方式与 Linux 原始版本完全相同:保存/恢复被调用者保存寄存器(x19–x28、fp、sp、pc)。汇编实现位于 src/lesson04/src/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
...
ldr x30, [x8]
mov sp, x9
ret
这段代码先保存当前任务(x0 指向 prev)的被调用者保存寄存器,再恢复下一个任务(x1 指向 next)的寄存器,最后通过 ret 跳转到新任务保存的 pc,从而完成真正的上下文切换。这正是 Linux 中 cpu_switch_to 汇编函数的简化复刻版。
sched_class 与 sched_entity:调度算法相关字段
这两个字段用于调度算法,下一节详细展开。在 RPi OS 中尚未引入"调度器类"抽象,而是直接在 src/lesson04/src/sched.c 的 _schedule() 中用循环遍历所有任务并选出 counter 最大的任务,这对应早期 Linux 的"时间片轮转"思路,与 CFS 的 vruntime 思想不同但目标一致。
调度器类(Scheduler Class):可扩展的调度机制
Linux 提供了一种可扩展机制,允许每个任务使用自己的调度算法,该机制基于 sched_class 结构(Linux v4.14 中定义于 kernel/sched/sched.h)。可以把 sched_class 理解为一个接口,定义了一个"调度类"必须实现的所有方法。最重要的方法如下:
| 方法 | 作用 |
|---|---|
enqueue_task |
每次有新任务被添加到某个调度器类时执行 |
dequeue_task |
当任务需要从调度器中移除时调用 |
pick_next_task |
核心调度代码需要决定下一个运行哪个任务时调用 |
task_tick |
在每个计时器滴答(timer tick)时调用,让调度器类有机会测量当前任务的执行时间,并在需要抢占时通知核心调度代码 |
Linux 中存在若干个 sched_class 实现(如 fair_sched_class、rt_sched_class、dl_sched_class 等),其中通常用于所有用户任务的最常用实现是完全公平调度器(CFS)。
对照 RPi OS:本仓库当前只有一个调度类——所有任务都用统一逻辑调度。核心调度入口 schedule() 与 timer_tick() 都在 src/lesson04/src/sched.c 中实现,其中 timer_tick() 的职责与 Linux 的 scheduler_tick() 类似:递减当前任务 counter,当 counter 用尽且允许抢占时触发重新调度:
void timer_tick()
{
--current->counter;
if (current->counter>0 || current->preempt_count >0) {
return;
}
current->counter=0;
enable_irq();
_schedule();
disable_irq();
}
这与 task_tick 的定位(测量当前任务执行时间、必要时触发抢占)完全对应。
完全公平调度器(CFS):以 vruntime 为核心
CFS 算法背后的原理非常简单,只有三条:
- 对系统中的每个任务,CFS 度量已经分配给它多少 CPU 时间,该值存储在
sched_entity结构的sum_exec_runtime字段中; sum_exec_runtime根据任务优先级进行调整,并保存在vruntime字段中;- 当 CFS 需要选择新任务执行时,选择
vruntime最小的那个任务。
这里的关键洞察是:CFS 并不追求"每个任务公平地得到相同时间片",而是模拟"理想的多任务处理器"——每个任务以无限小的粒度同时运行。vruntime 越小,说明该任务"欠"的 CPU 时间越多,因此优先运行。
运行队列:每 CPU 一个
Linux 调度器使用另一个重要数据结构——运行队列(runqueue),由 rq 结构描述(Linux v4.14 中定义于 kernel/sched/sched.h)。每个 CPU 只有一个运行队列实例。当需要选择新任务执行时,只从本地运行队列中选择;但如果有需要,可以在不同 rq 结构之间平衡任务(负载均衡)。
所有调度器类都使用运行队列,而不仅 CFS 使用。所有 CFS 特定信息保存在 cfs_rq 结构中,它被嵌入在 rq 结构内。cfs_rq 有一个重要字段 min_vruntime——这是分配给该运行队列的所有任务中最低的 vruntime 值。min_vruntime 会被赋给新分叉(fork)出来的任务,这确保该任务下一步就会被选中,因为 CFS 始终选择 vruntime 最小的任务。这种方法还能确保新任务在被抢占之前不会运行过长时间。
对照 RPi OS:task[NR_TASKS] 数组(NR_TASKS = 64,见 src/lesson04/include/sched.h)扮演了简易运行队列的角色,nr_tasks 记录当前任务总数。由于目前是单核、无抢占式优先级调度的教学场景,_schedule() 直接线性扫描这个数组:
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();
}
可以看到两个值得注意的细节:其一,当选出的最大 counter 为 0 时(所有任务时间片耗尽),会对所有任务的 counter 按 (counter >> 1) + priority 重新填充,类似早期 Linux 的"重新计算时间片"逻辑;其二,preempt_disable()/preempt_enable() 通过增减 current->preempt_count 实现临界区保护,防止调度过程中被中断再次触发 _schedule()——这正是 Linux preempt_count 语义在教学内核中的体现。
红黑树:tasks_timeline
分配给特定运行队列并由 CFS 跟踪的所有任务保存在 cfs_rq 结构的 tasks_timeline 字段中。tasks_timeline 表示一棵红黑树,可以用来按 vruntime 值排序选择任务。红黑树有一个重要性质:对它的所有操作(搜索、插入、删除)都能在 O(log n) 时间内完成。这意味着即使系统中有成千上万个并发任务,所有调度器方法依然执行得非常快。
红黑树的另一个重要性质是:对树中任何节点,其右子节点的 vruntime 值总是大于父节点,而左子节点的 vruntime 总是小于或等于父节点。这带来一个重要推论:最左边的节点始终是 vruntime 最小的节点,因此 CFS 取下一个任务时只需取最左节点,代价是 O(log n)。
RPi OS 由于任务数上限仅 64(NR_TASKS = 64),采用线性扫描即可,但理解红黑树与 vruntime 对于读懂真实 Linux 的 pick_next_task_fair 是必要的——它本质上就是"取红黑树最左节点",见第 4 课后续文档 docs/lesson04/linux/scheduler.md 对 schedule() 的讲解。
struct pt_regs:描述已保存的寄存器
在之前的课程中,我们已经展示了中断发生时如何将所有通用寄存器保存到栈上——我们探索了该过程在 Linux 内核中的工作原理,并为 RPi OS 实现了类似的过程(kernel_entry 宏)。本课要补充的一点是:在处理中断时操纵这些寄存器是完全合法的;手动准备一组寄存器并把它们放到栈上也是合法的——内核线程被切换到用户模式时正是这样做的(下一课将实现相同功能)。
pt_regs 结构用于描述已保存的寄存器,它的字段顺序必须与 kernel_entry 宏中寄存器的保存顺序一致。
对照 RPi OS 的实现,kernel_entry 宏在 src/lesson04/src/entry.S 中,它先把栈指针下移 S_FRAME_SIZE(272 字节,见 src/lesson04/include/entry.h),然后按 x0–x29、x30(lr)、elr_el1、spsr_el1 的顺序压栈:
.macro kernel_entry
sub sp, sp, #S_FRAME_SIZE
stp x0, x1, [sp, #16 * 0]
stp x2, x3, [sp, #16 * 1]
...
stp x28, x29, [sp, #16 * 14]
mrs x22, elr_el1
mrs x23, spsr_el1
stp x30, x22, [sp, #16 * 15]
str x23, [sp, #16 * 16]
.endm
对应的 kernel_exit 宏则按相反顺序恢复寄存器并执行 eret 返回。本课接下来会看到 pt_regs 结构被实际使用的多个例子(例如 fork 时为子任务准备寄存器状态),届时需要牢记:pt_regs 的布局必须与 kernel_entry 的压栈顺序严格一致,二者是同一块内存的两种视图。
结论
与调度相关的结构、算法和概念远比本文介绍的要多得多,但这里探讨的内容正是理解后续两章所需的最小集合:task_struct(任务的统一描述)、sched_class(调度算法的接口)、CFS 与 vruntime(默认的用户任务调度策略)、运行队列与红黑树(任务的组织与快速选择)、pt_regs(寄存器状态的描述与复用)。RPi OS 仓库中对应的实现文件可以作为最直观的对照物:结构定义在 src/lesson04/include/sched.h,调度与抢占逻辑在 src/lesson04/src/sched.c,上下文切换汇编在 src/lesson04/src/sched.S,异常入口与 ret_from_fork 在 src/lesson04/src/entry.S。
现在是时候看看所有这些概念是如何实际工作的了——请继续阅读下一章,了解任务是如何被创建(fork)并加入调度器的。