手写RTOS调度器：从就绪链表到位图的优先级抢占与时间片轮转

1. 从“谁都能跑”到“谁先跑”调度器要回答的三个问题点灯点得再花哨一旦任务多起来你迟早会撞上一堵墙每个任务都觉得自己该被执行CPU只有一个到底让谁先上裸机时代我们用状态机硬排到了RTOS里这个“排班”的活儿交给了调度器。但调度器也不是凭空决定它背后有一套明确的选择逻辑通俗点说就是连续回答三个问题哪些任务有资格被选中它们凭什么排序什么时候需要重新选这三个问题恰恰对应了RTOS调度机制的三大支柱任务状态管理、优先级策略、调度时机。如果你是跟着这个系列一路手搓过来的前面几篇我们已经把任务控制块TCB、上下文切换、SysTick这些地基打好了这篇的核心就是在这个地基上搭起调度框架。如果你刚看到这篇也没关系我会把涉及的前置概念都串着讲一遍。先抛一个很多人学RTOS时容易绕进去的误区任务调度不是“CPU按顺序挨个问候每个任务”而是“每次切换都直接选出当前最该运行的那个任务”。也就是说调度器本质是一个“选人”机制选完人以后才轮到上下文切换去“换人上台”。很多初学者把注意力全放在切换的汇编代码上觉得能切寄存器就是会写RTOS了实际上切换只是执行力调度策略才是决策力。调度器说切谁上下文切换代码就乖乖切谁调度器没发话切换代码再漂亮也只能原地待命。那这个“选人”过程具体长什么样我以自己手搓的这个小内核为例带你把整个机制拆开看一遍。这个内核的调度策略是优先级抢占 时间片轮转也是绝大多数入门级RTOS采用的经典组合。优先级抢占解决“重要任务不能被耽误”的问题时间片轮转解决“同等重要任务都能分到一口汤”的问题两者配合基本覆盖了嵌入式开发里绝大多数任务的调度需求。任务调度的第一步是搞清楚到底哪些任务“有资格上台”。这可不是一句“所有创建了的任务”就能糊弄过去的实际操作中很多任务虽然被创建了但处于挂起、阻塞、睡眠状态它们是“想上台但没轮到自己”或者“暂时不想上台”的状态。调度器如果连它们也算进去每次选人就得遍历所有TCB纯属浪费时间更麻烦的是还得一个个判断状态逻辑容易出错。一个合格的设计思路是维护一个“就绪链表”。所有状态为就绪的任务按优先级大小挂在这个链表上调度器选人的时候不需要遍历全部任务只需要看就绪链表头部的节点基本就能锁定目标。这个“空间换时间”的做法在我这个内核里是核心设计理解它你就理解了调度器的一半。2. 任务状态机为什么“挂起”和“就绪”之间藏着调度的灵魂先看任务的状态。一个RTOS任务从创建到销毁通常会经历这么几个状态状态含义是否参与调度就绪Ready任务已具备运行条件只等CPU是运行Running任务正在占用CPU执行是本质是从就绪态被选中阻塞Blocked任务在等待某个事件或信号量否挂起Suspended任务被主动暂停否睡眠Sleeping任务在延时等待否这里有个容易模糊的点阻塞、挂起、睡眠这三者有什么区别很多初学RTOS的人一开始会觉得“反正都是不运行区分它干嘛”。实际上这三者的恢复条件完全不同。阻塞是任务在等一个“外部事件”比如等信号量释放、等队列收到消息事件没发生它就一直在那儿等着睡眠本质也是一种阻塞但等的是“时间到了”是一类特殊的阻塞挂起则是被人为叫停只有别的任务调用恢复接口才能让它回到就绪。这三种状态混在一起调度器的判断逻辑就会失控。我在实现状态管理的时候定义的状态是用一个枚举加一组状态位标志来管理的typedef enum { TASK_STATE_READY 0x01, TASK_STATE_RUNNING 0x02, TASK_STATE_BLOCKED 0x04, TASK_STATE_SUSPENDED 0x08, TASK_STATE_SLEEPING 0x10 } task_state_t;每个任务在TCB里都存着一个当前状态调度器扫就绪链表的时候只把状态为READY的任务纳入选择范围。RUNNING在实现层面我个人处理成“READY的升级版”——一个任务被调度器选中后它就从就绪链表里摘下来标记为RUNNING等到时钟节拍或事件触发再次调度时它如果还没把事情干完又会被放回就绪链表重新参与下一轮竞选。这种设计有一个好处调度器永远不需要在多个状态之间平衡取舍只看就绪链表就行。就绪链表是唯一的“候选人名单”谁在这个名单里谁就有戏不在名单里的CPU再怎么空转也不会喊它们上。那任务是怎么从“不在名单”变成“进入名单”的举个例子一个任务调用延时函数task_delay(100)它会把自身状态改为SLEEPING同时调度器会把它从就绪链表里摘除。这时即使它是最高优先级CPU也不会理它。等100个时钟节拍走完系统节拍中断里会检查睡眠链表发现它的延时到期了就把它状态改回READY重新插入就绪链表它就又成了候选人。这个“摘除-等待-重挂”的过程是任务状态管理和调度器交互最频繁的一条路径也是大多数调度bug的藏身之处。后面我会专门讲一个我在这个环节踩进去的坑。3. 就绪链表与优先级位图我用24行C代码实现O(1)级任务查找候选人名单有了接下来就是“排序”问题。每个任务就绪的时候不是随便往链表尾部一挂就完事。调度器必须保证就绪链表头部就是当前最高优先级的那个任务。这样才能做到“看一眼头部就知道派谁上场”。这就引出了两个核心设计链表如何按优先级排序寻找最高优先级任务的过程能不能足够快先说排序。我的内核里优先级数值越小代表优先级越高这是RTOS里最常见的约定如果你用的内核约定相反思路反过来即可。任务从其他状态转入READY时会按优先级从高到低数值从小到大的顺序插入就绪链表。插入逻辑并不复杂从头节点开始往后遍历找到第一个优先级比自己低数值比自己大的节点插到它前面。因为就绪链表本身是有序的所以每次插入最多做一次全链表扫描任务数量不多的时候性能完全可以接受。真正需要花心思的是“找最高优先级任务”这个动作。如果每次调度都从头到尾遍历一遍就绪链表找最小优先级数值任务多了以后调度开销会很感人。我参考了业内一些经典内核的做法引入了一个优先级位图结构。思路极其简单用一个32位的整数或者几个整数构成的数组取决于你支持多少级优先级每个bit代表一级优先级是否就绪。比如第0位代表优先级0该位为1说明当前有优先级为0的任务处于就绪状态。这样“找最高优先级任务”就变成了“找位图里最低的那个置1位”。这个动作在现代Cortex-M处理器上可以用一条硬件指令搞定比如CLZCount Leading Zeros指令配合简单的计算或者在编译器内置函数里找__clz。没有硬件指令的平台上也可以用查表法或逐位判断32级的位图找最高优先级位最多32次判断但平均次数远小于遍历链表。我用的是一个简化版本核心代码如下// priority_bitmap: bit0对应优先级0bit31对应优先级31 // ready_tasks[priority] 指向对应优先级的任务链表头 uint32_t priority_bitmap 0; // 任务进入就绪态 void task_ready_add(task_t *task) { // 按优先级挂入对应的就绪链表 list_add_tail(task-ready_list, ready_tasks[task-priority]); priority_bitmap | (1U task-priority); } // 取当前最高优先级 int sched_get_highest_priority(void) { uint32_t bitmap priority_bitmap; int priority 0; while ((bitmap 1U) 0) { bitmap 1; priority; } return priority; }这个while循环看起来像是在逐位扫描但因为bitmap足够稀疏实际循环次数约等于“当前就绪的最高优先级数值”而最高优先级数值通常都很小。比如系统里只有优先级0、3、5三个任务就绪第一次循环就命中优先级0直接跳出。如果再用__clz优化那就是固定几条指令的事跟链表长度彻底脱钩。链表加位图的组合好处非常直接任务进入就绪态是O(1)的链表尾插取最高优先级任务是接近O(1)的位图操作再从对应优先级的链表头取出任务节点整个“选人”过程可以做到不随任务数量线性增长。对于MCU这种随时可能跑满主频的场景这种确定性的开销是很有价值的——调度延迟稳定你的系统时序才有保障。实现顺序上有两个细节值得注意。第一位图的更新时机要和链表操作保持一致两者必须处在一个临界区内否则调度器可能在“链表已挂好但位图还没更新”的中间态取到错误结果这类bug特别隐蔽排查起来很耗时间。第二同优先级多个任务就绪时链表尾插保证了先进先出的轮转顺序时间片轮转就依赖这个FIFO属性。如果这里用头插同等优先级任务就会被“后来者居上”每个任务获得CPU的机会就不再均等轮转的意义就丢了。4. 调度的两个关键时机任务主动让路与被抢占名单有了排序规则有了最后一个问题就是“什么时候来选”。这个时机的设计直接决定了系统的实时性表现。调度器不可能每行代码都去问“要不要换个任务跑”那不叫调度那叫精神分裂。实际的做法是把调度点收敛到两类场景任务主动让出CPU和外部事件打断当前任务。4.1 主动让路从task_yield到延时阻塞任务主动让路是最好理解的一种方式。当前任务运行到一半发现自己暂时没什么事可干主动调用task_yield()意思就是“我先歇会儿你们谁行谁上”。这个调用会触发一次调度把当前任务重新放回就绪链表尾部如果是同优先级再从链表头部取一个任务来执行。我说“重新放回”可能不太准确——它本来就在就绪链表里只是调度器把它的节点挪了个位置再从头部取出下一个该运行的节点。更常见的主动让路是延时任务调用task_delay(ticks)后调度器把该任务从就绪链表摘除挂入睡眠链表然后立刻执行调度选出下一个就绪任务。这里有个细节如果当前任务是系统里唯一一个就绪任务它延时后系统直接进入空闲任务或者干脆死等很多刚写RTOS的人没认真处理“无任务可调度”的情况系统一跑就挂。内核里必须有一个保底的空闲任务只做一件事死循环。它的优先级最低永远就绪保证调度器任何时候都有一个人选。4.2 被抢占节拍中断与PendSV的配合外部触发调度是RTOS实时性最直观的体现。最典型的场景是有一个高优先级任务在等一个信号量这个信号量由一个中断服务程序在事件到来时释放。中断一来高优先级任务立刻恢复就绪态如果它的优先级比当前被打断的任务高当前任务就必须被“赶下台”。这个“赶下台”的过程在Cortex-M平台上是靠SysTick节拍中断或外部中断配合PendSV可悬起系统调用实现的。我在系列前几篇已经详细讲过上下文切换的汇编实现这里只强调调度器在其中的角色中断服务程序里通过信号量释放接口把高优先级任务置为就绪态后会置上一个“需要调度”的标志比如need_sched true然后在中断退出前检查这个标志。如果为真就触发PendSVPendSV里会先保存当前任务的现场再从就绪链表取最高优先级任务做上下文切换。PendSV的妙处在于它会被硬件自动推迟到所有高优先级中断处理完之后才执行。也就是说即便你在中断里触发了调度真正切换任务的时机也是“当前所有中断都退出”之后不会在中断处理过程中贸然切走上下文避免中断现场被破坏。这个机制是天生的保护伞不需要你额外关中断保护。4.3 节拍驱动时钟中断里的“时间片到点提醒”SysTick在这里还有一个额外作用时间片轮转。当一个任务连续运行达到一个时间片长度比如10ms即10个节拍SysTick中断里会检查当前运行任务是否已经超时。如果超时了把它的“剩余时间片”清零然后触发调度让它回到对应优先级链表的尾部换同一个优先级的兄弟任务上台。这样同等优先级的任务就能轮流获得CPU时间。时间片轮转这里有个边界问题值得注意**高优先级任务就绪时低优先级任务的时间片还没用完怎么办**答案是不管。优先级抢占优先于时间片轮转高优先级任务一旦就绪它就应该立即获得CPU低优先级任务剩多少时间片都不作数。等低优先级任务再次获得CPU时它的时间片重新开始计算。这个优先级优先的语义如果不彻底想清楚实现里很容易出现“低优先级任务硬着头皮把时间片跑完再让位”的错误表现。5. 从零手写调度核心一个最小可运行的调度循环理论说了一堆是时候看看代码了。我整理了一份最小可执行的调度核心配合前几篇实现的TCB和链表基础设施可以直接跑在Cortex-M0/M3/M4这类平台上。代码刻意做了精简结构上保留了“选人”的所有关键动作方便你读懂每一步在干什么。5.1 调度器的初始化与空闲任务调度器初始化的本质是把就绪链表、位图、当前任务指针全部归零然后创建一个空闲任务作为保底。空闲任务的优先级设为最大数值最低优先级状态直接置为READY并挂入就绪链表。void sched_init(void) { int i; for (i 0; i MAX_PRIORITY; i) { list_init(ready_tasks[i]); } priority_bitmap 0; current_task NULL; idle_task task_create(idle, idle_entry, NULL, IDLE_PRIORITY); task_ready_add(idle_task); }idle_entry里就是一个死循环什么也不干顶多加个__WFI()让CPU在没事的时候睡一会儿省电。空转也费电嵌入式产品对功耗敏感的话这一步不能省。5.2 核心调度函数选出下一个任务真正的“选人”动作我把它收敛到sched_select_next这一个函数里。这样设计的好处是调度点唯一排查问题时只需要盯着这一个函数看。task_t *sched_select_next(void) { int priority sched_get_highest_priority(); task_t *next; if (priority 0 || priority MAX_PRIORITY) { // 理论上不该走到这里因为有空闲任务兜底 return idle_task; } next list_first_entry(ready_tasks[priority], task_t, ready_list); return next; }这个函数返回的是“下一个该运行的任务”它自己不做上下文切换。切换动作在task_switch_to(next)里完成也就是汇编的保存/恢复现场这部分在系列前面已经写过这里就不再贴完整汇编了只强调一个接口约定sched_select_next返回任务指针task_switch_to接收指针执行切换二者解耦测试起来非常方便。5.3 第一次启动调度系统启动时第一个任务怎么被选中裸机代码是顺序执行main的但RTOS里main只是一个创建任务的地方真正的运行要交给调度器来“点将”。启动调度的函数长这样void sched_start(void) { current_task sched_select_next(); // 首次启动没有“保存上一个任务现场”一说 // 直接在特权模式下切换到第一个任务的初始栈指针 task_switch_to(current_task); }注意这里有个新手的经典误区首次启动不能走常规的“保存当前任务现场→加载新任务现场”流程因为此刻压根没有“当前任务现场”可保存。你只能做一个“凭空加载”的操作直接从第一个任务初始化的寄存器状态开始跑。这会牵扯到初始栈是怎么伪造的——系列前几篇讲过任务创建时会往栈里铺好和“异常退出帧”一样的寄存器序列这样首次切入就像从一次异常返回一样自然。6. 一个真实的“血案”复盘睡眠任务被提前唤醒根因竟在就绪位图更新顺序前面讲位图的时候我提示过“链表和位图更新顺序不一致会出bug”。这里把这个坑原原本本拆开复盘一遍这是我在实际调试中踩进去、又花了大半天才定位出来的问题很有代表性。场景是这样的系统里有A、B两个任务A优先级3B优先级5数字越大优先级越低这里我用的是我自己内核的约定低数字高优先级。B任务执行到一半调用task_delay(50)把自己挂入睡眠链表。A任务此时正在睡眠等待一个外部事件优先级3的任务在就绪链表里实际上是空的。然后事件来了中断置位A为READY同时因为A优先级更高触发PendSV切换。到这一步一切正常A开始运行。问题出在后续A运行了一会儿也调用task_delay(100)睡眠了。此时系统里只剩下空闲任务在跑。可是诡异的事情发生了——空闲任务跑了不到几个节拍B任务居然提前恢复了就绪态被调度上台执行。但我明明设置的延时是50个节拍不应该这么快到期。我一开始以为是睡眠链表的计时逻辑有问题排查了半天各种打印节拍计数都没有异常。后来才发现问题出在中断里置位A时用的“复位就绪”和“更新位图”的代码顺序上。我当时的task_ready_add逻辑是先操作链表再更新位图但在某个中断路径上我为了“省事”直接写了priority_bitmap | (1U task-priority);就返回了任务节点还没来得及挂进就绪链表。结果就是位图显示优先级3有任务就绪但就绪链表的优先级3链表是空的。调度器sched_select_next从位图得到优先级3然后去链表的优先级3队列里取任务——空的直接返回NULL。我在代码里对NULL的处理是“回到当前任务继续跑”相当于调度失效了一拍。这一拍不要紧恰恰赶上B的延时到期B恢复READY后被正确调度看起来就像是B被提前唤醒了。但实际上B是按正常节拍唤醒的是A的“假就绪”导致A没有被及时调度空闲任务多跑了一个周期观感上就完全错乱了。这个问题的根子在于我破坏了自己定下的“链表和位图必须同步更新”的规则。因为图省事在图里先插了旗队伍却还没排好调度器顺着旗子去找人人不在整个调度就乱了。修复很简单把中断路径里的置位操作统一收口到task_ready_add里先挂链表再置位图两步都被同一个临界区保护。从那以后我再也没有在这个环节翻过车。这个坑想分享的核心经验是调度器的数据结构每一步操作都要能被调度器时刻信任。链表和位图就像记账的“账本”和“摘要”摘要写了几号人到了账本里却找不到对应的人财务对不上账是小事整个系统的运行逻辑错乱是大事。手写RTOS宁可慢一点多几行封装也要保证每个接口的语义是完整一致的。7. 调度点梳理与切换性能的权衡思路把调度机制看全之后再落回工程实际有一个避不开的话题调度点到底该放几个我见过一些人写RTOS恨不得在每一个API里都塞一个调度点结果系统到处都在切换性能惨不忍睹。也见过一些人只保留了task_yield和SysTick两个调度点高优先级任务靠中断抢占系统一样跑得很好。我的实践体会是调度点宁少勿多但要保证覆盖所有“任务状态可能发生改变”的路径。一个任务从就绪变成阻塞、从阻塞变成就绪、优先级发生变化、被删除这些点必须触发调度检查。除此之外什么打印日志、计算CRC这类纯计算逻辑里完全没必要放调度点。调度点本身就是开销每次调度意味着至少一次PendSV切换几十上百个周期的成本在高频调用路径上会被无限放大。另一个值得权衡的点是位图替换链表遍历的收益到底有多大我在任务数少于10个的时候做过实测两种方式几乎没有区别甚至链表遍历因为逻辑更简单编译器优化后性能还略好。但任务数一多或者某个优先级的链表特别长的时候位图的确定性优势就体现出来了。我给出的建议是如果你的内核将来可能要支持几十个任务位图值得引入如果就固定五六个任务跑到底链表直接遍历也完全够用别过度设计。我自己的内核之所以上了位图主要是因为想在调度延迟上做到恒定方便做时序分析而不是因为它“看起来高级”。切换性能这块还有一个容易被忽略的细节编译器优化等级对上下文切换代码的影响。我在调试阶段用-O0编译一切正常切到-O2之后偶尔出现任务运行状态错乱排查了半天最后发现是某个关键变量被编译器优化成了寄存器副本没有在切换点及时写回内存。解决办法是给这些跨调度点存活的变量加上volatile修饰或者在切换汇编代码里显式做内存屏障。这个坑在FreeRTOS等成熟内核里其实也出现过相关的讨论属于手写内核几乎必然会撞上的暗礁。8. 写在最后的实操心得调度器写到这里回头再看“任务怎么被选中”这个问题其实答案已经呼之欲出它经历了“状态过滤—就绪入队—位图索引—取头节点—上下文切换”这五个环节每个环节都不复杂但环环相扣。很多人学RTOS时总想一口吃个胖子上来就啃内核源码结果被各种链表指针和位运算绕晕。我建议的路径是先自己手搓一遍哪怕搓出来的实现很简陋只要跑通了你对调度这件事的理解会比看十遍源码都深。这个系列到这篇为止已经涵盖了TCB管理、上下文切换、时钟节拍、任务调度这几块核心骨架。如果你跟着写到了这里可以试着给内核加一个简单的互斥量或者信号量让任务之间能真正通信起来那会是另一个很有意思的进阶方向。我下一篇大概率会写这一块到时候可以一起聊聊。