深入 Linux 调度程序基本结构:以 Raspberry Pi OS 为例理解 task_struct、调度类与 CFS

原创2026-09-21 13:26:021,455 阅读
文章标签:操作系统教程文档嵌入式系统编程

深入 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 算法背后的原理非常简单,只有三条:

  1. 对系统中的每个任务,CFS 度量已经分配给它多少 CPU 时间,该值存储在 sched_entity 结构的 sum_exec_runtime 字段中;
  2. sum_exec_runtime 根据任务优先级进行调整,并保存在 vruntime 字段中;
  3. 当 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)并加入调度器的。


上一页

4.1 进程调度程序:RPi OS 调度程序

下一页

4.3 进程调度程序:分派任务(Fork)

登录后查看全文
raspberry-pi-os