手写RTOS：从零实现任务调度器核心机制与代码解析

先把结论放这儿如果把一个 RTOS 比作一台永不落幕的舞台那任务就是台下的演员而调度器就是那个举着剧本、时刻在喊“下一个准备”的导演。你写的每一个任务能不能上台、什么时候上台、上台演多久全看这位导演怎么安排。明白了这个机制你就不会再对着vTaskDelay和osDelay发呆也不会再奇怪为什么两个任务明明“同时”在跑日志却是一段一段输出的。这篇是这个“手搓操作系统”系列的第 6 篇前面我们搞定了任务怎么创建、怎么保存现场、怎么切换上下文。今天要解决的是整个 RTOS 里最核心、也最容易被低估的一个环节——任务调度。我会从调度器的职责讲起把“任务是怎么被选中上台的”这件事彻底拆开再手把手带你把一个可用的调度器写出来。1. 调度器到底在做什么一场永不停歇的“舞台剧”1.1 单核 CPU 的真相没有真正的“同时运行”先打个比方。你在食堂打饭一个窗口一个阿姨。前面排了 10 个人阿姨不可能同时给 10 个人打菜她只能一个一个来A 打完打 BB 打完打 C。CPU 就是这个阿姨任务就是排队的学生。所谓“多任务并行”在单核 CPU 上其实是假象——它只是把时间切成了很多小片每个任务轮流用一小片切换得足够快看起来像是在同时运行。这就引出了任务调度的本质在任意一个时刻CPU 只能运行一个任务调度器要做的就是决定“这一刻到底该运行谁”。很多人刚接触 RTOS 时会有个误区以为任务调度就是“谁优先级高谁就一直跑”。其实远不止这么简单。调度不仅决定“选谁”还要决定“什么时候重新选”以及“选完之后旧任务怎么办”。这三件事合在一起才构成完整的调度机制。1.2 从“手搓”视角看没有调度器会怎样先回到裸机开发的思路帮我们理解调度器解决了什么痛点。裸机程序通常是一个while(1)大循环加几个中断。问题是如果循环里某个函数执行时间太长其他功能就会被卡住。比如你做一个温湿度传感器采集采集函数里有个延时等待传感器响应这期间按键扫描、LED 刷新全都停了。你可能会说“那我把采集放到中断里不就行了”但中断里不能做耗时操作否则会破坏实时性。RTOS 的思路完全不同每个功能封装成一个独立任务每个任务都有自己的栈和优先级。调度器按规则给它们分配 CPU 时间。某个任务要等传感器响应那它主动“睡觉”把 CPU 让出来给别的任务用。这样一来CPU 永远在干活永远不会因为某个任务卡住而整体停滞。所以调度器不是“锦上添花”的功能它是 RTOS 的发动机。发动机的转速和换挡逻辑直接决定了整台车的性能表现。1.3 调度器必须回答的四个问题把调度器抽象一下它其实只需要回答四个问题有哪些任务在等着运行就绪队列的维护在这些任务里应该选哪一个调度算法的决策被选中的任务怎么开始跑上下文切换什么时候重新做一次选择调度触发时机这四个问题环环相扣任何一个环节设计得不合理都会导致系统出现“饿死”“抖动”或者“响应延迟”的问题。后面每一节我都会结合手写代码逐个拆解。2. 调度算法的选型为什么“优先级抢占”是主流答案2.1 先看几种经典调度算法的取舍在动手写代码之前得先搞清楚我们到底要实现哪种调度策略。工业界常见的调度算法大致有这几类先来先服务FCFS按照任务就绪的先后顺序排队先到的先执行执行完或主动让出后再执行下一个。这种算法实现最简单但缺点很明显如果一个长任务卡在前面后面的短任务就会等很久实时性完全没保证。它适合不需要实时性的批处理场景做 RTOS 不合适。时间片轮转Round-Robin给每个任务分配固定大小的时间片时间片用完后强制切换到下一个任务。大家轮流上台谁也不会饿死。问题在于所有任务优先级一样紧急任务没法“插队”。如果系统里有个报警处理任务它和 LED 刷新任务享有同等地位那报警就可能在队列里排半天。优先级抢占Priority-Based Preemptive每个任务分配一个优先级调度器永远选择“就绪态中优先级最高”的任务执行。高优先级任务一旦就绪可以立刻抢占preempt正在运行的低优先级任务。这是绝大多数商用 RTOSFreeRTOS、RT-Thread、μC/OS采用的核心策略。我实现自己的 RTOS 时选的也是优先级抢占原因很简单它能直观地满足实时系统的需求——最重要的任务必须最先被执行。而且它也是目前可查资料最多、面试最爱考的一种调度策略。2.2 优先级抢占的“副作用”和解决方案但优先级抢占不是没有代价。它带来两个经典问题第一个是优先级翻转。假设任务 A 优先级最高任务 B 优先级最低任务 C 优先级居中。运行顺序是B 先拿到某个共享资源的锁然后 A 就绪抢占了 BA 也想用同一个资源但发现锁被 B 占着只能阻塞等待。此时实际运行顺序变成了“A 在等 B”也就是说高优先级任务反而被低优先级任务阻塞了优先级关系被“翻转”。这个问题我们后面讲到互斥量时会专门处理今天只要心里有数。第二个是调度抖动jitter。如果抢占点不确定高优先级任务每次从“就绪”到“真正开始执行”的间隔时间不一致就会导致任务的响应时间不稳定。这在电机控制、音频采集这类对时序敏感的场景里是致命的。缓解办法是减少关中断的时间、保持调度器代码路径尽量短。2.3 为什么 FreeRTOS 用“优先级时间片”组合现在你去看 FreeRTOS会发现它的调度策略是最高优先级的就绪任务先跑如果有多个同优先级任务则按时间片轮转。这是一种很实用的组合策略。它把“紧急响应”交给优先级解决把“多任务公平”交给时间片解决。比如两个串口数据处理任务都是中等优先级它们之间用时间片轮流跑谁也不独占 CPU而一个最高优先级的告警任务随时可以打断它们。我手搓的系统也打算采用这个组合。核心结构就两块一个描述任务控制块的TCBTask Control Block一个就绪列表Ready List。3. 就绪队列的数据结构调度效率的胜负手3.1 朴素方案就是遍历一遍数组选最大优先级第一次实现调度器的时候最容易想到的方案是维护一个任务数组遍历所有任务找出“状态为就绪、且优先级最高”的那个。伪代码如下task_t *get_highest_ready_task(void) { task_t *best NULL; for (int i 0; i MAX_TASKS; i) { if (task_list[i].state TASK_READY) { if (best NULL || task_list[i].priority best-priority) { best task_list[i]; } } } return best; }注意这里我约定priority数值越小优先级越高。遍历一遍的逻辑理解起来很容易也能跑。但问题在于每做一次调度决策时间复杂度是 O(n)n 是任务总数。如果系统里只有 3、5 个任务这点开销无所谓。但如果任务数量上到几十个调度器本身就会成为性能瓶颈。调度器的代码是系统里最“热”的路径每次上下文切换都要跑一遍必须尽可能轻量。3.2 提升方案就绪位图 链表把 O(n) 变成 O(1)更好的办法是使用“就绪位图ready bitmap 优先级链表”的组合结构。思路是这样的每个优先级对应一个 bit如果该优先级下有任务就绪对应 bit 置 1。每次调度时用一条高效的 CPU 指令比如 CLZCount Leading Zeros从位图里找出最高优先级。每个优先级维护一个任务链表同优先级的任务通过双向链表链接时间片轮转时从链表头取任务即可。这套方案把“找最高优先级任务”的时间复杂度降到了 O(1)不管系统里有多少任务查找时间都一样短。在 32 位处理器上如果你的系统最多支持 32 个优先级一个 32 位的整型变量就能当位图用uint32_t ready_priority_bitmap; // bit 0 对应优先级 0bit 31 对应优先级 31找出“最高优先级”就变成int highest_priority 31 - __builtin_clz(ready_priority_bitmap);GCC 的__builtin_clz会直接编译成硬件指令效率极高。ARM Cortex-M 内核也有对应的 CLZ 指令一条指令搞定。3.3 双向链表让任务插入和删除都变得很便宜接下来要实现的是一个轻量级双向链表。链表节点被直接嵌入 TCB 结构体还是单独分配内存这里有个很重要的设计决策我想让这个系统尽量简单所以选择把链表节点直接放进 TCB 里。TCB 结构大体长这样typedef struct tcb { uint32_t *stack_ptr; // 当前栈指针上下文切换时保存 uint8_t priority; // 任务优先级数值越小优先级越高 uint8_t state; // 任务状态READY / BLOCKED / SUSPENDED uint32_t slice_ticks; // 时间片长度单位tick uint32_t remaining_ticks; // 本时间片剩余 tick struct tcb *ready_next; // 就绪链表下一个节点 struct tcb *ready_prev; // 就绪链表上一个节点 // ... 其他字段 } tcb_t;每个优先级一个链表头typedef struct { tcb_t *head; tcb_t *tail; uint32_t count; // 该优先级下就绪任务数量 } ready_list_t; ready_list_t ready_lists[32];当任务 A 进入就绪态调度器把它挂到对应优先级的链表末尾当任务 A 被选中执行调度器把它从链表头摘下来。核心操作都是指针操作速度快到可以忽略不计。3.4 从“朴素数组”到“位图链表”我用过之后的一些感受说点实操心得。我在第一个版本用的是数组遍历法跑三四个任务完全没问题代码也好理解。但后来加了 8 个任务之后调试串口输出时能明显感觉到调度间隔不稳定——倒不是系统崩了而是同样的延时逻辑任务切换的节奏变得不可预测。换成位图链表结构后调度器的开销稳定在几十条指令以内整个系统的时序表现立刻“干净”了很多。所以我的建议是如果你只是学习数组遍历法帮助你理解逻辑如果你准备在真实项目里用请一步到位实现位图链表。后者的代码量和前者差不了太多但性能和扩展性完全是两个量级。4. 手写调度器核心代码从零搭一个可用的调度框架4.1 基础设施我们手头有什么动手写调度器之前先得确认我们手头有哪些基础设施。本系列前面几篇已经实现了任务创建函数task_create()能分配任务栈、初始化上下文。SysTick定时器中断每 1ms 触发一次提供系统时基。底层的上下文切换原语保存/恢复寄存器现场。有了这三样调度器就只负责“决策”和“触发切换”不用管硬件细节。这个分层很重要你的调度器代码应该尽量做到硬件无关方便移植到不同的 MCU 上。4.2 核心调度函数schedule()调度器的“心脏”是schedule()函数。它的职责是从就绪位图里找到最高优先级再从该优先级的链表头取出下一个任务然后触发上下文切换。void schedule(void) { int highest_prio find_highest_ready_priority(); tcb_t *next_task get_next_ready_task(highest_prio); tcb_t *current_task current_tcb; if (next_task ! current_task) { current_tcb next_task; context_switch(current_task-stack_ptr, next_task-stack_ptr); } }这里有个关键优化如果next_task就是当前正在运行的任务就不需要切换直接返回。避免无谓的上下文切换开销。find_highest_ready_priority()就是上一节讲的位图扫描int find_highest_ready_priority(void) { if (ready_priority_bitmap 0) { return -1; // 没有就绪任务系统应执行 idle 任务 } return 31 - __builtin_clz(ready_priority_bitmap); }4.3 时间片轮转让同优先级任务“轮流上台”前面说过同优先级任务要配合时间片轮转。实现方式是在每次 SysTick 中断里对当前任务的时间片计数减一减到零就触发一次调度。void sys_tick_handler(void) { // ... 更新系统 tick 计数 tcb_t *current current_tcb; if (current-remaining_ticks 0) { current-remaining_ticks--; } if (current-remaining_ticks 0) { // 时间片用完把当前任务挪到链表末尾并触发布置 move_current_to_end_of_ready_list(); current-remaining_ticks current-slice_ticks; schedule(); } }需要注意一个细节时间片计数到 0 后是先把任务挪到链表尾部再重新执行调度。这样下一次get_next_ready_task()取到的就是同优先级的下一个任务完成轮转。4.4 主动让出 CPUyield() 的两种实现层次除了时间片强制切换任务还可以主动让出 CPU。这个操作就是task_yield()。实现方式很直接把当前任务从链表头挪到链表尾然后触发调度。void task_yield(void) { // 关中断或进入临界区防止调度器被并发访问 uint32_t key enter_critical_region(); move_current_to_end_of_ready_list(); schedule(); exit_critical_region(key); }为什么要在yield()里关中断因为move_current_to_end_of_ready_list()操作的链表很可能正被 SysTick 中断里的调度逻辑同时访问。如果不加保护链表结构会被破坏系统迟早死机。这种“调度器数据结构的并发保护”是很多新手容易忽略的坑。4.5 阻塞与唤醒调度的“另一只手”前面讲的都是“谁最快能跑”但实际任务经常要等待某个事件——延时、信号量、消息队列。当一个任务等事件时它不能留在就绪链表里否则调度器还是会选它。因此任务状态机里必须有 BLOCKED 状态。阻塞操作的流程是把任务从就绪链表摘下。把任务状态改为 BLOCKED。把任务挂到对应事件的等待链表上。触发调度让出 CPU。void task_block_on(wait_queue_t *wq) { uint32_t key enter_critical_region(); // 从就绪链表摘下 remove_from_ready_list(current_tcb); current_tcb-state TASK_BLOCKED; // 挂到等待队列 wq_push(wq, current_tcb); schedule(); // 让出 CPU exit_critical_region(key); }注意schedule()之后的代码不是马上执行而是等这个任务被唤醒、重新获得 CPU 后才会从schedule()返回。这正是上下文切换的“非线性”表现初学时会觉得很绕但理解之后就会明白这就是多任务系统的核心魔力。唤醒操作则是反向流程把任务从等待队列摘下重新挂回就绪链表状态改为 READY。如果唤醒的任务优先级比当前运行的任务高应该立刻触发调度强制执行抢占。void task_wake_up(tcb_t *task) { uint32_t key enter_critical_region(); wq_remove(task); add_to_ready_list(task); task-state TASK_READY; // 如果被唤醒的任务优先级更高立即抢占 if (task-priority current_tcb-priority) { schedule(); } exit_critical_region(key); }4.6 空闲任务系统里的“替补演员”当所有任务都在阻塞等待时必须有一个任务在跑。这个任务叫 idle 任务空闲任务优先级最低。它的唯一职责是什么都不干或者执行一些清理操作、低功耗休眠。我的实现会在启动调度器时自动创建 idle 任务void scheduler_start(void) { // 创建 idle 任务 task_create(idle_task_entry, NULL, IDLE_TASK_PRIORITY, idle_stack, IDLE_STACK_SIZE); // 从就绪任务里选第一个 current_tcb get_highest_ready_task(); // 触发第一次上下文切换 first_task_start(); }idle 任务看起来“浪费”其实作用很大它保证了调度器永远能选到一个可运行任务不需要对“无任务可跑”这种情况做特殊处理。而且很多低功耗设计就是在 idle 任务里执行WFIWait For Interrupt指令让 CPU 在无事可做时进入休眠。4.7 我踩过的坑调度器里最隐蔽的三个 bug写调度器最容易出的问题我几乎都踩过一遍。整理出来供你避坑。第一个坑是没有关中断就操作就绪链表。我在早期代码里加日志时曾在调度路径里调用串口输出结果串口输出本身耗时长中间又被 SysTick 打断导致链表节点被重复插入系统直接 HardFault。排查了很久才意识到是临界区保护的问题。现在的原则是凡是涉及就绪链表、TCB 状态修改的代码全部要进出临界区日志输出绝不放调度路径里。第二个坑是切换前没保存现场。上下文切换的本质是“保存当前任务现场 恢复新任务现场”很多移植示例代码能跑简单 demo但跑复杂任务就随机崩溃大多是保存现场的寄存器没保存全。尤其要检查的是PSP进程栈指针和LR的特殊值ARM Cortex-M 上还要处理EXC_RETURN的恢复。这个我在后面讲移植的章节专门细说。第三个坑是时间片计数在阻塞任务上还在减。如果你在task_block_on()里没把任务从就绪链表摘干净SysTick 仍然会给这个“假就绪”的任务减时间片导致它被当作超时任务重新插入。症状是任务被提前唤醒时序错乱。解决方法是把时间片计数逻辑和任务状态关联起来——只有当前任务状态是 READY 且正在运行时才减计数。5. 调度全流程追踪两个任务切换的现场还原5.1 场景设定LED 与按键为了把调度流程讲透我构造一个简单场景系统里有三个任务任务 A优先级 1每 500ms 翻转一次 LED。任务 B优先级 2每 1s 读取一次按键。任务 C优先级 3每 100ms 向串口输出一个字符。优先级数值越小越优先所以 A 最高C 最低。启动后三个任务都就绪。我们用时间线来追踪从系统启动后的第 0ms 到 300ms调度器都做了什么。5.2 时间线推演T0ms调度器启动选择就绪队列里优先级最高的任务 A装载它的上下文PC 跳到任务 A 的入口LED 初始化完成。此时任务 A 开始执行。T0~10ms任务 A 执行完初始化代码调用task_delay(500)。这时调度器把 A 从就绪链表摘下挂到延时等待队列然后执行schedule()。就绪队列里剩余 B优先级 2和 C优先级 3所以选中 B。T10~250ms任务 B 执行按键扫描调用task_delay(1000)。调度器把 B 摘下来就绪队列只剩 C所以选中 C 执行。T250~350ms任务 C 开始执行它每次循环把串口写一个字符然后task_delay(100)。延时期间没有其他就绪任务调度器只能选择 idle 任务。T500ms任务 A 的延时到了SysTick 中断里唤醒 A。A 的优先级最高调度器立刻抢占当前正在运行的 C 或 idle切回 A 执行。注意C 可能只运行到一半就被抢占了它的现场保存在自己的栈里等下次轮到它时继续跑。T500~1000msA 翻转 LED 后再次延时 500ms让出 CPU。B 恢复运行继续扫描按键。C 在间隙里继续串口输出。从时间线能看出几个关键点抢占发生在任意指令边界不是任务“合作”换人。A 抢 C 时C 可能正执行到一条str指令这没关系现场保存在栈里恢复后 C 无感知。idle 任务是最底层的“兜底”所有任务都阻塞时它出来跑避免 CPU 空转到未知状态。时间片轮转只在同优先级之间生效这里优先级各自不同所以没有用到时间片C 被抢占也不能立刻抢回来必须等更高优先级的任务主动让出。5.3 重点理解上下文切换的三层“舞台机关”很多人看调度源码时最容易卡在context_switch()上。你只需要抓住三个层次第一层代码层次。context_switch(from_stack_ptr, to_stack_ptr)的职责是先把当前 CPU 寄存器压入当前任务栈更新from_stack_ptr指向新栈顶然后从新任务栈里弹出寄存器恢复PC和LRCPU 就跑到了新任务的世界里。第二层内存层次。每个任务有自己的栈自己的 TCB。栈里保存着“这个任务上次被切走时的快照”。只要快照完整任务就能无缝续跑。第三层时间层次。任务 A 调用task_delay(500)后它就“睡着了”。等 500ms 后 SysTick 唤醒它高优先级让它立刻抢占 CPU。从 A 的视角看自己只是调用了task_delay然后过了一会儿返回了完全感知不到 B/C/idle 的存在——这就是 RTOS 对任务最大的“欺骗”。6. 常见调度问题排查与实测避坑6.1 现象一高优先级任务饿死低优先级任务症状低优先级任务比如串口日志偶尔卡顿长时间不输出但系统没死。原因高优先级任务一旦就绪就永远占着 CPU。如果它在循环里不断执行工作且从不主动阻塞或延时低优先级任务永远没有机会运行。验证方法在低优先级任务里放个计数器每秒通过调试器看看计数器是否在增长。如果一直不变基本可以确认是被饿死了。解决方案在高优先级任务里加适度的阻塞延时让它“周期性”休眠。或者使用事件驱动模型高优先级任务只有在事件发生时激活平时处于阻塞态。不要用while(1)忙等替代延时。6.2 现象二频繁切换导致 CPU 利用率不高症状功能上没问题但用示波器测某个 GPIO 翻转频率发现比预期慢很多。原因调度器本身也吃 CPU 时间。如果时间片设得太短比如 1ms每个时间片都要执行一次“保存现场切换新任务”上下文切换的开销占比就很大。实测参考某 ARM Cortex-M0 平台上一次裸的上下文切换只切寄存器不跑调度算法大约需要几十微秒如果加上调度算法和链表操作可能在 100 微秒量级。时间片设成 1ms切换开销就占 10%眼见着系统“变慢”。对策合理设置时间片长度一般在 5ms~20ms 比较合适。能阻塞就别轮询减少不必要的就绪任务数量。关中断临界区尽量短降低调度延迟对实时性的影响。6.3 现象三优先级反转触发看门狗复位症状系统偶尔触发看门狗复现很难。最后定位到是低优先级任务长时间霸占共享资源导致高优先级任务超时。这是嵌入式相关网络热词里反复提到的“xxl-job 分布式任务调度平台”面向的场景吗不是那是互联网后端的技术栈但它的核心思想——用合理的调度策略避免任务饥饿和优先级反转——和 RTOS 调度器是相通的。嵌入式里的优先级反转经典对策是优先级继承或优先级天花板协议。这些我们在实现互斥量时再深入这里先知道概念。6.4 现象四SysTick 里做复杂操作导致死锁症状系统跑一段时间后在某个中断里卡死调试发现 SysTick 中断和任务代码同时在修改同一个链表。原因调度器代码在 SysTick 里也会操作就绪链表如果任务代码在操作链表时没有关中断就被 SysTick 打断两个上下文同时改同一个节点。解决办法所有就绪链表、等待队列的操作必须放在临界区里关中断或使用调度器锁。临界区内禁止调用任何会触发阻塞的函数防止死锁。使用 Tracealyzer 这类工具记录上下文切换事件能快速定位是哪个任务在破坏结构。7. 总结一下我的实操体会这个手搓操作系统的系列写到这里调度器这块算是真正立起来了。回过头看从最初的“数组遍历选最大值”到后来的“位图双向链表”不只是一次数据结构的优化更是一次思考方式的转变——写实时系统的核心不是把功能跑起来而是把每种极端情况下的行为都想清楚。再分享一个经验之谈调调度器的时候不要一上来就写全部功能。先把“两个任务、一个延时、一个抢占”这组最小场景调通再加“三个优先级”、再加“同优先级轮转”、再加“阻塞唤醒”。每个阶段都确保能稳定跑一个小时以上再进下一步。这样定位问题会容易很多心态也不会崩。最后留个思考题如果任务 A 在临界区里调用了task_delay(500)调度器会怎么处理这个操作会导致什么后果在你的系统里应该用什么机制来防止这种使用方式想明白这个你对 RTOS 调度的理解就又深了一层。