每次调度都要从 64 个任务里立刻找出优先级最高的那个uC/OS-II 不靠循环比较而是靠两张位图和一张 256 字节的表。本文拆解 OSRdyGrp 与 OSRdyTbl 的数据布局、OSUnMapTbl 查表原理、OS_Sched 的完整流程并用优先级 29 和 OSRdyGrp0x34 两个实例把 O(1) 调度背后的关键路径一次推演明白。如果让你在 64 个任务里找出优先级最高的那个第一反应是什么挨个比一遍最坏情况要比较 64 次。uC/OS-II 的回答很干脆固定两次查表一次移位。不管系统里是 8 个任务还是 63 个任务耗时一模一样。这不反直觉吗答案是它把找最高优先级这件大事提前拆解成了一张位图登记表。接上篇 TCB 里的 OSTCBY/X 预计算本篇正式进入 uC/OS-II 内核源码精读系列的调度核心——看它怎么用空间换时间把实时系统的确定性锁死在 O(1)。就绪表一张任务能否运行的登记簿所谓就绪表就是内核用来登记哪些任务已经就绪、可以运行的数据结构。uC/OS-II 用了二级位图一张组表加一张行表。OS_EXT OS_PRIO OSRdyGrp;/* Ready list group */OS_EXT OS_PRIO OSRdyTbl[OS_RDY_TBL_SIZE];/* Table of tasks which are ready to run */OSRdyGrp1 个字节bit0~bit7 分别对应 OSRdyTbl[0]~OSRdyTbl[7] 哪一行里有就绪任务。OSRdyTbl[8]8 个字节每字节的 8 个 bit 对应优先级 0~63。一个任务的优先级 p被拆成两段行 y p 3列 x p 0x07。这就是位图的基本玩法——用 1 个 bit 表示一个任务的就绪状态。拿优先级 29 来说29 3 329 0x07 5。所以它落在 OSRdyTbl[3] 的第 5 位同时 OSRdyGrp 的第 3 位要置 1表示第 3 行非空。置位与清位缓存在 TCB 里的四个字段既然 p 的映射关系固定为什么每次都要做一遍移位和与运算uC/OS-II 的选择是在创建任务时就预计算好运行时直接取用。OSTCBYprio3;/* 行号 y */OSTCBXprio0x07;/* 列号 x */OSTCBBitY1OSTCBY;/* 行掩码如 13 0x08 */OSTCBBitX1OSTCBX;/* 位掩码如 15 0x20 */这四个字段在第 2 篇已经见过当时可能觉得只是缓存索引现在它的价值才真正显现运行期间置位/清位只需要两次或运算/与运算。任务进入就绪态置位OSRdyGrp|ptcb-OSTCBBitY;/* 组位第 y 行非空 */OSRdyTbl[ptcb-OSTCBY]|ptcb-OSTCBBitX;/* 行位优先级 x 就绪 */任务退出就绪态清位OSRdyTbl[y]~ptcb-OSTCBBitX;/* 先清行内位 */if(OSRdyTbl[y]0u){/* 这一行全空了 */OSRdyGrp~ptcb-OSTCBBitY;/* 再清组位 */}注意清位的顺序先清行内位行空了才清组位。反之置位时组位和行位可以同时写。这个细节是理解就绪表一致性的关键组位是行位的摘要摘要必须滞后于明细更新。置位/清位遍布内核各处延时到期置位OSTimeTick、等待事件时清位OS_EventTaskWait、挂起时清位OSTaskSuspend……所有路径用的都是同一套位操作。换优先级OSTaskChangePrio也是同一套规矩先清旧位置的位再置新位置的位——旧位清了行空才清组位新位则组位行位一起置。先摘下来再放上去顺序一步都不能乱。OSUnMapTbl用 256 字节把找最小值变成查表就绪表建好了下一个问题怎么从这张位图里快速找到最小的置位位置所有就绪任务中数值最小的优先级就是最高优先级。在二进制里找最小置位位就是找最低的置 1 位。C 语言里做位扫描要么写循环要么依赖编译器内建函数比如 clz。循环最坏要扫 8 次而且不是常数时间。uC/OS-II 的做法更直接查表。INT8UconstOSUnMapTbl[256]{0u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/* 0x00 to 0x0F */4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/* 0x10 to 0x1F */...};这张表的规律只有一句话OSUnMapTbl[n] n 的最低置 1 位的位位置0 开始。验证几个关键值输入二进制最低置位表值0x010001bit000x020010bit110x040100bit220x0C1100bit220x801000 0000bit770xFF1111 1111bit00注意到没0x02 的低位是 0但最低置位是 bit1所以表值是 1。这张表不看最低位只看最低的置 1 位。一次查表 O(1)与位宽无关——这是整个调度算法的地基。顺便说一下这张表是怎么来的。看前 16 项0,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0——每 16 项一组组首递进0x10 组首是 4、0x20 组首是 5……。其实它不需要背规律就是位操作的自然结果bit0 置位表值必为 0bit0 为 0 而 bit1 置位则表值 1依此类推。奇数输入表值全 0bit0 总是置位偶数输入的值取决于更高位。Micrium 把这 256 项直接展开写死在源码里省去启动时生成读起来也一目了然。有人会问为什么不用链表把就绪任务串成链表找最高优先级从链头拿就行了。问题是插入位置新任务就绪时要按优先级找插入点最坏 O(n)而且每个任务要多两个指针。位图的代价是 9 字节就绪表 256 字节查表换来所有操作 O(1)。这是典型的空间换时间而且换得极其划算——对于实时内核操作耗时与任务数无关本身就是卖点。两步查表0x34 的完整推演有了 OSUnMapTbl找最高优先级任务就变成两次查表。源码 os_core.c 里的 OS_SchedNew 是这么写的yOSUnMapTbl[OSRdyGrp];/* 第一步找非空行得到 y */OSPrioHighRdy(INT8U)((y3u)OSUnMapTbl[OSRdyTbl[y]]);/* 第二步行内找最低位 */第一次查表OSRdyGrp 的最低置位 bit 就是最小的非空行号 y——最小行号对应最高优先级所在的行。第二次查表从那一行里再找最低置位 bit x。最终优先级 y * 8 x。如果 OS_LOWEST_PRIO 配到 63 以上支持 256 个任务OS_SchedNew 走的是另一段#else分支OSRdyGrp 按高 8 位/低 8 位分两步查行内再分两步——多一层查表思路完全一样。默认 64 任务配置下就是上面这两行。来推演一个具体场景。假设当前 OSRdyGrp 0x340x34 0b0011_0100最低置 1 位是 bit2。第一步查表y OSUnMapTbl[0x34] 2。再看第 2 行。假设 OSRdyTbl[2] 0x14 0b0001_0100最低置 1 位是 bit2。第二步查表x OSUnMapTbl[0x14] 2。所以最高优先级 (2 3) 2 18。整个过程两次数组下标访问一次移位一次加法。任务从 8 个涨到 64 个这段代码一行都不用改耗时一模一样。**调度的快慢不由任务数量决定。**这就是 O(1) 的含义。OS_Sched调度器的三道门槛OS_SchedNew 只负责算出来谁是最高优先级。真正决定要不要切的是 OS_SchedvoidOS_Sched(void){OS_ENTER_CRITICAL();if(OSIntNesting0u){/* Schedule only if all ISRs done and ... */if(OSLockNesting0u){/* ... scheduler is not locked */OS_SchedNew();OSTCBHighRdyOSTCBPrioTbl[OSPrioHighRdy];if(OSPrioHighRdy!OSPrioCur){/* No Ctx Sw if current task is highest */OSCtxSwCtr;/* Increment context switch counter */OS_TASK_SW();/* Perform a context switch */}}}OS_EXIT_CRITICAL();}三道门槛一夫当关第一道OSIntNesting 0——不在中断嵌套里。为什么中断服务程序里不会直接切换任务先跑完 ISR退出时由 OSIntExit 统一处理在 ISR 里调用 OS_Sched 属于越权OSIntExit 会调 OS_Sched 但那是中断退出的专属流程。第二道OSLockNesting 0——调度器没被锁。应用可以用 OSSchedLock/OSSchedUnlock 把调度暂时冻结锁可以嵌套计数为零才放行。锁调度器 ≠ 关中断中断照常响应只是不切换任务。什么场景会用锁典型的是想原子地操作共享数据但又不能长时间关中断比如更新一个几十字节的结构体关中断会拉长中断响应时间锁调度器则不影响中断只是把任务切换推迟几微秒。锁了之后记得成对解锁漏一次系统就再也不会切换任务了。第三道OSPrioHighRdy ! OSPrioCur——最高优先级任务不是当前任务。如果算出来还是自己就没必要切换。这一条保证了调度的最小开销空转调度几乎免费。通过三道门槛后OSTCBHighRdy OSTCBPrioTbl[OSPrioHighRdy]从优先级表里取出目标 TCB然后OS_TASK_SW()触发上下文切换。OS_TASK_SW 是宏由 CPU 移植文件定义通常是软中断指令或直接调用 OSCtxSw——真正的寄存器保存与恢复是汇编代码第 4 篇专门拆它。一次抢占的完整推演把前面所有零件拼起来走一个完整的抢占场景。系统里三个任务任务 A 优先级 5正在运行任务 B 优先级 3就绪任务 C 优先级 20在等信号量。当前就绪表OSRdyTbl[0] 的 bit3优先级 3和 bit5优先级 5都是 1即 OSRdyTbl[0] 0x28OSRdyGrp 的 bit0 1第 0 行非空。现在任务 C 等到了信号量。OSSemPost 唤醒它OSRdyGrp | OSTCBBitY2032置 bit2OSRdyTbl[2] | OSTCBBitX2074置 bit4。然后调用 OS_Sched()。三道门槛全过不在中断、调度器没锁。OS_SchedNew 两步查表y OSUnMapTbl[OSRdyGrp]。OSRdyGrp 0x05 0b0101最低置位 bit0 → y 0。x OSUnMapTbl[OSRdyTbl[0]] OSUnMapTbl[0x28]。0x28 0b0010_1000最低置位 bit3 → x 3。OSPrioHighRdy (0 3) 3 3。注意任务 C优先级 20刚就绪最高优先级却是 3——因为任务 B 一直在就绪表里20 3。C 就绪只是改动了 OSRdyTbl[2]不影响查表结果。就绪表找的是所有就绪任务里优先级最高的不是刚被唤醒的那个。最后OSPrioHighRdy(3) ! OSPrioCur(5)触发 OS_TASK_SW()切到任务 B。如果当前运行的就是任务 B 自己OSPrioCur 3算出来还是 3第三道门槛直接放行不了——什么都不做。空转调度几乎免费就靠这一句。调度器什么时候被触发OS_Sched 从不主动跑它只在别人调用它时工作。触发方分四类让出类任务主动等——OSTimeDly、OSSemPend、OSMboxPend、OSQPend 等阻塞自己前调 OS_Sched释放类事件就绪——OSSemPost、OSMboxPost、OSFlagPost 等唤醒别人后调 OS_Sched任务类OSTaskCreate、OSTaskDel、OSTaskSuspend、OSTaskResume、OSTaskChangePrio中断退出OSIntExitISR 末尾第 4 篇展开这里藏着一个设计规律调度是事件驱动的不是定时驱动的。任何可能改变就绪表状态的 API末尾都会看一眼调度器——这就是抢占式内核的随时抢占。一切从清零开始就绪表不是天生就整齐的。OSInit 里有一句 OS_InitRdyList()os_core.c 第 1367 行做的事朴素得很OSRdyGrp 清零、OSRdyTbl 八个字节逐个清零再给 OSPrioCur、OSTCBCur 置初值。系统启动早期还没有任务时OSRdyGrp 保持 0——不过 OS_SchedNew 在 OSStart 之前根本不会被调用所以 OSUnMapTbl[0] 的取值0永远轮不到上阵。收尾确定性来自 9 个字节回顾一下这张图的全部家当OSRdyGrpOSRdyTbl[8]9 个字节登记 64 个任务的就绪状态OSUnMapTbl[256]256 字节只读表把找最低置位变成查表OS_SchedNew两次查表 一次移位 找到最高优先级任务OS_Sched三道门槛 目标 TCB 触发切换整个调度决策路径与系统里有几个任务完全无关。实时系统要的确定性就是这么锁死的。顺便一提OSUnMapTbl 是 const 数组编译后躺在 ROM/Flash 里不占宝贵的 RAMOSRdyGrp OSRdyTbl 的 9 字节才在 RAM 里——整个就绪机制对内存的占用就这么多。下一篇我们跟着 OS_TASK_SW 走进汇编OSCtxSw 是怎么把当前任务挂起来、把新任务扶上台的——那是 uC/OS-II 最后一块拼图。