1. 抢占式调度器到底解决了什么问题
很多同学在学操作系统时，都能背出“抢占式调度就是可以强行打断当前任务，把CPU交给另一个任务”，但真让他手写一个抢占式调度器，往往无从下手。原因在于：这个概念背后牵扯了一套完整的机制，包括任务状态管理、就绪队列、上下文切换、时钟中断，以及一个不断被触发的调度函数。它不是一个能通过“临时抱佛脚”解决的代码题，要真正理解抢占式调度器，就得在代码层面把这条链路亲手打通。
先说清楚“抢占”(preemption)的含义。非抢占式调度里，任务自己让出CPU，比如主动sleep、等待IO、调用yield。如果某个任务死循环不释放CPU，其他任务只能干等，系统表现就是卡死。抢占式调度的核心价值，就是引入一个“外部强制性力量”——通常是定时器中断，在固定的时间间隔打断正在运行的任务，把控制权交还给调度器，再由调度器决定下一个运行谁。这个过程不受当前任务的主观配合，所以叫抢占。
这样一来，抢占式调度器就解决了实时性和公平性两个问题。实时性是关键任务能及时获得CPU；公平性是每个任务都能分到时间片，不会出现某个任务饿死整个系统的情况。做嵌入式、做RTOS、做通用操作系统内核，都绕不开这一层。我个人体会是：手写一次抢占式调度器，相当于把“进程管理”“中断机制”“队列结构”“汇编级现场切换”这几块知识一次性焊在了一起，比看十遍书都管用。
这篇文章适合谁？两种人。一种是正在学操作系统、想要把理论落地的学生；另一种是做嵌入式或中间件开发，想在项目中自己实现任务调度的从业者。我下面不讲教科书式的推导，直接站在“手写”的视角，把设计的每一步拆开、把关键代码贴出来、把我在实际调试中踩过的坑讲清楚。
2. 动手前先把三件核心组件定下来
写调度器之前，我心里一般先画一张“最小运行链”：时钟中断产生一个节拍，节拍驱动调度器检查当前任务的运行时间，时间片耗尽就从就绪队列挑一个任务，做上下文切换，让新任务开始运行。这套链路里，有三样东西必须提前设计好。
2.1 任务怎么表示：PCB与任务栈
每个任务在调度器眼中不是一段“代码”，而是一个结构体，通常叫PCB（Process Control Block）。PCB至少要记录几类信息：任务的唯一标识、当前状态（就绪/运行/阻塞）、私有栈、保存下来的寄存器现场、剩余时间片、优先级，以及链接指针。
任务栈是容易被忽略、但极其关键的一环。每个任务必须有自己独立的栈空间，因为切换出去之后，局部变量、函数调用链、返回地址都得留在这个栈里。任务栈的大小要提前分配，给大了浪费内存，给小了一旦任务嵌套调用深一点就栈溢出，直接踩坏相邻任务的数据。我做过一个最小系统，任务栈给2KB，外壳代码加打印日志导致溢出，查了半天才发现是栈不够——这类坑后面会细说。
设计PCB时，建议把“空闲态”和“阻塞态”分开。就绪队列里只放能被调度器选中的任务；阻塞任务放等待队列，等IO或事件完成后被唤醒再重新进就绪队列。这一步拆干净，后续扩展多级反馈队列或者事件驱动模型都方便。
2.2 任务怎么排队：就绪队列的数据结构
调度器最常用的数据结构就是就绪队列。最简单的实现是双向链表，每次从头取任务、从尾插入任务，配合时间片轮转刚好合适。为什么不用数组？数组的插入删除要搬移元素，频繁切换时开销大；链表只需要改几个指针。
如果后面要支持优先级调度，就绪队列可以做成多级数组，每一级一个队列；也要考虑优先级翻转问题。但在第一版里，我的建议是先把单队列的时间片轮转跑通，再加复杂度。
typedef struct pcb { uint32_t pid; uint32_t state; // 0=READY 1=RUNNING 2=BLOCKED uint32_t *stack_top; // 私有栈指针 uint32_t time_slice; // 剩余时间片 uint32_t priority; struct pcb *next; } pcb_t; typedef struct { pcb_t *head; pcb_t *tail; } run_queue_t;这是一个最简版的PCB结构。注意stack_top字段，它在上下文切换时用来保存和恢复栈指针，是整个调度器最关键的几十个字节。
2.3 谁来触发切换：定时器与中断入口
抢占式调度和普通函数调用的最大区别，就是“调度器不是被任务主动调用的”，而是被中断驱动的。定时器每产生一次中断，CPU会跳转到中断向量表里注册的入口地址，把当前任务的运行状态打断，然后进入中断处理程序。在这个处理程序里，保存现场、调调度器、恢复现场，一气呵成。
这两件事“保存现场”和“恢复现场”，决定了抢占式调度器能不能稳定工作。保存现场不完整，恢复后寄存器值变了，任务就会在莫名其妙的地方出错；保存现场时压栈顺序错了，返回地址对不上，系统直接崩溃。所以设计阶段就要明确：切换流程定好了，后面就不要轻易改栈操作顺序。
3. 第一步：PCB与就绪队列的实现要点
有了结构体，接下来就要把它们变成可运行的代码。我把第一个阶段的实现拆成三个小步骤：初始化任务、入队出队操作、以及一个基础版的调度函数。
3.1 任务初始化的几个细节
初始化任务时，除了填pid、优先级、时间片，最重要的是把任务栈洗干净并放入“初始上下文”。很多教学代码会在任务栈底部预填一个“任务入口地址”，等第一次切换时，通过恢复现场的ret指令跳进任务的入口函数。这里有一个容易出错的点：CPU压栈和栈生长方向要和汇编里的保存恢复代码严格一致，如果平台栈向下生长，初始化时就要把栈指针移到高地址，然后按“准备弹出的顺序”逆向填入初始寄存器值。
我建议第一版先不要做花哨的栈保护canary，栈顶附近填一个特殊标记值，比如0xDEADBEEF。每次任务切出时检查这个标记还在不在，能很快定位栈溢出。这个习惯我从写RTOS到现在一直在用，排查问题效率很高。
3.2 入队出队操作：老生常谈但必须写对
int enqueue(run_queue_t *rq, pcb_t *task) { if (!rq || !task) return -1; task->next = NULL; if (rq->tail) { rq->tail->next = task; rq->tail = task; } else { rq->head = rq->tail = task; } return 0; } pcb_t *dequeue(run_queue_t *rq) { if (!rq || !rq->head) return NULL; pcb_t *task = rq->head; rq->head = task->next; if (!rq->head) rq->tail = NULL; task->next = NULL; return task; }这段代码看起来简单，实际踩坑点全在边界上：队列为空时head和tail都要更新；队列只有一个元素时，出队后tail必须置空，否则下一次入队会接在野指针后面。我建议每个入队出队操作都写成独立函数，不要图省事在调度循环里直接改指针，否则排查问题时非常痛苦。
3.3 调度函数的最简逻辑
调度函数pick_next决定下一个运行谁。第一版就用最简单的轮转逻辑：从就绪队列头部取一个任务；如果取出来的任务就是当前任务，且时间片还没用完，就继续运行，不切。这个“优化”很实用，因为很多中断产生时，当前任务的时间片并没耗尽，此时没必要做一次无意义的切换。
pcb_t *pick_next(run_queue_t *rq) { if (!rq || !rq->head) return NULL; return rq->head; }把调度函数保持得这么简单是有意的。先让它能跑通，再考虑复杂策略。很多人一上来就写多级反馈队列，优先级计算、动态老化全塞进去，结果出了bug根本分不清是队列问题还是切换问题。我坚持一个原则：第一版只做“能Run”，第二版再做“调度得好”。
4. 第二步：抢占机制——上下文切换与时钟中断
如果说队列是调度器的“骨架”，那么上下文切换就是“心脏”。这一节是整个手写过程的核心，也是和普通“任务管理”代码拉开差距的地方。
4.1 什么是上下文切换
一个正在运行的任务，它的状态不仅包括栈里的数据，还包括CPU寄存器里的值：程序计数器、栈指针、通用寄存器、状态寄存器，甚至浮点寄存器。上下文切换要做的事，就是把当前任务这些寄存器的值保存到它的PCB里，再从目标任务的PCB恢复寄存器。从代码执行视角看，切换完成后，当前任务就像“什么都没发生”一样继续执行。
第一次写上下文切换时，最容易犯的错是“只保存了PC和SP，没保存中间寄存器”。这会导致切回该任务时，某个局部变量的值神秘丢失，程序在后续计算中出错。排查这类问题只能靠单步调试，很费时间，不如一开始就把该保存的寄存器全部保存完整。
4.2 一个可读懂的x86上下文切换写法
下面给出一个教学用途的简化版本，用x86汇编描述的保存/恢复过程。注意真实平台需要按对应ABI补充更多寄存器，但核心思路不变。
; 假设旧任务的sp保存在old->sp，新任务的sp已经放进new->sp save_context: ; eax指向old->sp pusha ; 保存通用寄存器 ; 此时esp指向保存现场后的栈顶 movl %esp, (%eax) ; 把esp存到old->sp load_context: ; ebx指向new->sp movl (%ebx), %esp ; 切到新任务的栈 popa ; 恢复通用寄存器 ret ; 继续执行新任务保存时的位置这段代码的精髓在于：一个任务被抢占时，它的执行流停留在中断入口处；保存现场后把esp存到PCB；之后某一次load_context把esp切到这里；popa把寄存器恢复；ret返回，任务就从之前被打断的位置继续往下走。整个过程对任务本身完全透明。
4.3 定时器中断处理流程
抢占式调度器的“节拍器”是定时器。定时器中断触发后，中断入口要做三件事：
- 保护现场：把被打断任务的寄存器压栈，部分寄存器在进入ISR时CPU会自动压栈，比如返回地址和状态寄存器。
- 调用调度器：当前任务时间片减一；减到0就把它放回队尾，从队头选新任务。
- 恢复现场：先判断这次是否发生了切换，如果切换到了新任务，就恢复新任务的现场；如果没有，就恢复原来任务的现场然后返回。
这里必须特别强调“判断是否切换”这个环节。很多初学者在ISR里不管是否有切换，直接schedule()然后无条件恢复现场，结果就是：明明切到了新任务，恢复现场时却用了旧任务的寄存器，新任务跑飞。我常用的写法是让schedule()返回“是否需要切换”的标志，只有标志为真才去加载新任务现场。
int need_switch = 0; void timer_isr(void) { // 关闭中断，防止嵌套打断调度过程 disable_irq(); current->time_slice--; if (current->time_slice == 0 && dequeue(&rq)) { current->state = READY; enqueue(&rq, current); current = dequeue(&rq); current->state = RUNNING; current->time_slice = TIME_SLICE; need_switch = 1; } if (need_switch) { context_switch(&old_task->sp, &new_task->sp); need_switch = 0; } // 重新开启中断 enable_irq(); }细节上，我加了disable_irq()和enable_irq()。原因是我们正在修改链表和PCB状态，如果又被抢占一次，就绪队列可能被改乱，出现链表环。中断关闭期间只做队列操作和指针切换，不做耗时操作，中断延迟是可控的。
5. 第三步：把调度器跑起来——给出可复现的完整路径
讲真，理解了上面几节，你已经有了抢占式调度器的全部“零件”。但作为实战派，我最讨厌“看起来懂了，跑起来就挂”的教学。所以我给你两条可复现路径：一条是Linux用户态模拟路径，用ucontext模拟上下文切换，适合在普通电脑上实验；另一条是走上真机裸机路径，用定时器中断驱动，贴近真实RTOS。两条路径的核心调度逻辑一样，差异只在“上下文切换”的实现方式。
5.1 在Linux上用ucontext复现抢占效果
ucontext是POSIX提供的一组接口，可以在用户态保存和恢复上下文。这套接口本质上和内核切换寄存器是一个思路，只是封装好了。用它可以让我们不碰汇编，先把调度逻辑调通。
#include <ucontext.h> #include <stdio.h> #include <stdlib.h> #define STACK_SIZE 65536 #define TASK_NUM 3 typedef struct task { ucontext_t ctx; char stack[STACK_SIZE]; int id; int run_count; } task_t; task_t tasks[TASK_NUM]; int current_idx = 0; int tick = 0; void task_entry(int id) { while (1) { tasks[id].run_count++; printf("task %d running, count=%d\n", id, tasks[id].run_count); // 模拟让出CPU swapcontext(&tasks[id].ctx, &tasks[(id+1)%TASK_NUM].ctx); } } int main(void) { for (int i = 0; i < TASK_NUM; i++) { getcontext(&tasks[i].ctx); tasks[i].ctx.uc_stack.ss_sp = tasks[i].stack; tasks[i].ctx.uc_stack.ss_size = STACK_SIZE; makecontext(&tasks[i].ctx, task_entry, 1, i); } // 启动第一个任务 swapcontext(&tasks[current_idx].ctx, &tasks[TASK_NUM-1].ctx); return 0; }这个程序里，每个任务的swapcontext就相当于一次主动让出CPU。你会发现它并不是“抢占”，因为让出是任务自己做的。要模拟真正的抢占，得引入一个“模拟定时器”，比如主进程定期给任务注入切换信号。真正的抢占必须来自外部，这是核心逻辑。你也可以在测试程序里用定时器信号实现，但纯用户态能讲的原理有限。所以我们依然需要下面这条真机路径，才能真正理解抢占。
5.2 真机路径：基于定时器中断的调度器骨架
真机路径下，任务入口函数放在任务栈的初始上下文里。定时器中断一触发，ISR里的schedule()决定是否切换。下面是一个简化的启动流程：
- 初始化定时器，设置中断频率，比如100Hz，那每个时间片就是10ms。
- 创建若干任务：分配栈、填PCB、放入就绪队列。
- 主函数启动调度器，先从就绪队列取第一个任务，切过去。
- 此后，中断不断产生，每个tick递减时间片，到0就切换。
我把这个流程用伪代码形式组织得更工程化一些：
void kernel_main(void) { timer_init(100); // 100Hz，每tick 10ms task_create(task_a, "task_a", PRIORITY_LOW); task_create(task_b, "task_b", PRIORITY_HIGH); isr_register(TIMER_IRQ, timer_isr); // 启动第一个任务 current = dequeue(&rq); current->state = RUNNING; load_context(¤t->sp); }执行完load_context，CPU会跳到第一个任务入口，从此调度器就不再主动使用“main”的流程，而是由中断驱动。很多第一次接触的同学会卡在这个地方：为什么主流程回不去了？因为第一个任务的现场接管了CPU，主流程的栈和现场已经不在执行链路里。理解了这一点，整个抢占式调度就看透了。
5.3 时间片应该选多大
时间片的选择是个系统工程。太小，切换开销大增，可能大半CPU时间都花在保存恢复现场上；太大，抢占式调度的实时性优势发挥不出来。比如一个普通嵌入式MCU，32MHz主频，任务切换一次大约需要几十微秒，如果时间片设置成1ms，切换开销占几十个百分点，影响就不小了。我的建议是，从10ms起步，业务需要再往下调。调小时间片前，先算出一次上下文切换的平均耗时，用这个数值做底线，避免把系统性能浪费在无意义的切换上。
设置时间片还有一个次级问题：每个任务的时间片如果统一，读起来简单，但实际场景里任务A是后台计算，任务B是实时控制，都用10ms就不合理。第一版可以做成全局统一时间片，跑通之后再改成每个任务自带优先级和独立时间片。
6. 踩坑记录、调试方法与后续扩展
这部分内容是我在实际手写过程中积累的实操经验，主要帮助读者少走弯路。
6.1 常见问题速查表
| 现象 | 可能原因 | 排查思路 |
|---|---|---|
| 任务一切换就死机 | 上下文切换保存/恢复寄存器不完整 | 用单步调试检查切出和切入点的寄存器值 |
| 任务运行几秒后内存被破坏 | 任务栈溢出，覆盖相邻任务数据 | 在任务栈顶放魔术字，切出时检查 |
| 调度器偶尔卡死 | 就绪队列指针被中断重入破坏 | 检查ISR是否关闭了中断；检查入队出队边界 |
| 任务时间片耗尽后没有切换 | 定时器中断没触发，或ISR里没有调用schedule | 先验证中断频率，再验证时间片递减逻辑 |
| 新任务打印乱码 | 任务栈初始化时初始上下文顺序错误 | 对照目标平台的ABI，检查预填寄存器的压栈顺序 |
| 切换后返回地址丢失 | 保存现场后没有正确ret | 检查入口地址是否保存在栈顶，ret能否弹出正确地址 |
6.2 调试方法：没有仿真器怎么调
第一版抢占式调度器跑在开发板上时，问题定位特别难，因为一旦栈被破坏，printf都可能卡死。我的做法分三步：
第一步，做一张“调度事件表”。每次切换发生时，在内存里记录切换时间戳、旧任务pid、新任务pid、剩余时间片。崩溃后导出这张表，基本能看出是哪个任务在哪个时间片出了问题。
第二步，把栈标记当成金标准。每个任务栈顶放一个固定值，每次任务切出时检查标记是否还在。这个手段帮我抓住了至少三次任务栈溢出问题，每次都跟我预想的“可能是指针错乱”完全不同。栈溢出真的是抢占式调度器最隐蔽的杀手。
第三步，用共享文件或串口逐条打印关键日志。但日志要克制，一多就会改变时序，问题反而复现不了。更务实的做法是：先尝试在本地模拟器上调试，确定逻辑问题后再上真机。硬件问题搞不清的话，优先怀疑内存布局和中断优先级配置。
6.3 从轮转走向多级反馈队列
把时间片轮转调通后，我建议下一步扩展成多级反馈队列（MLFQ）。思路是这样的：队列有多个优先级等级，新任务进入最高优先级队列；队列内部用时间片轮转，高优先级队列先被调度；一个任务如果时间片耗尽还没做完，说明它可能是CPU密集型任务，就把它降级到低优先级队列；任务主动让出CPU，比如等待IO，则保持原优先级甚至提升优先级。
MLFQ的代码改动量并不大，主要是把单一就绪队列换成queue_array[PRIORITY_LEVELS]，调度策略改成从高到低扫描非空队列。但它的效果立竿见影：交互型任务响应变快，CPU密集型任务也不会饿死。这也是很多通用操作系统内核采用的思路。我把这一步当作“抢占式调度器从玩具走向实用”的关键转折点。
6.4 还有哪些值得继续深挖的方向
等着往下做的方向还有不少：给调度器加一个空闲任务，处理所有任务都在阻塞的稳态；加入阻塞队列和睡眠队列；考虑中断嵌套时如何保存现场；如果上了多核，还要考虑每核本地队列和全局队列的负载均衡。这些方向每加一个，都够再写一篇长文。
以我的实际体会来说，手写调度器最大的收获是建立了一种“系统级的直觉”：看到一行业务代码，你能想象它在哪个任务里运行；看到一次函数调用，你会想它压栈了什么、切出去之后栈里还剩什么。这种直觉，只有亲手把寄存器推来推去之后才能长在身上。如果你按照这篇文章的思路写出了一个能跑的最小抢占式调度器，后续看RTOS源码、看Linux调度器，会觉得很多设计似曾相识，那时你就已经入门了。
