4. embOS就绪表与优先级位图算法

在上一节中我们已经知道，embOS 的调度器在每次任务切换时，都要从所有“就绪”的任务中挑出优先级最高的那一个来运行。如果每次切换都遍历整个任务列表去比较优先级，那么任务数越多、优先级越多，调度耗时就越长，实时性也就越差。embOS 解决这个问题的核心手段，就是就绪表（Ready List）配合优先级位图（Priority Bitmap），把“找最高优先级就绪任务”这件事压缩成几条指令，实现 O(1) 的常数级查找。

就绪表：按优先级分桶的任务集合

embOS 为每一个优先级维护一个就绪链表，通常称为“就绪表”。当某个任务被创建并进入就绪态时，它会被挂到对应优先级的链表上；当它因为等待事件、延时或被挂起而离开就绪态时，就从该链表摘除。于是，调度器要做的第一件事，不是扫描所有任务，而是先判断“哪些优先级当前有就绪任务”。

如果系统支持 32 个优先级，那么“哪些优先级有任务”这件事就可以用一个 32 位的整数来表示，每一位对应一个优先级：位为 1 表示该优先级有就绪任务，位为 0 表示没有。这个整数就是优先级位图。例如位图的 bit5 为 1，就说明优先级 5 上有任务处于就绪态。这样，查找最高优先级就等价于：在这个 32 位整数中，找到最高位的 1所在的位置。

优先级编码：从位图到优先级号

假设 embOS 约定优先级数值越小、优先级越高（这是 embOS 的常见约定，本节全文与图示均采用这一约定）。那么“最高优先级”就对应位图中最低编号的置位位。如果位图从 bit0 开始编号，bit0 对应优先级 0，bit31 对应优先级 31，那么我们要找的就是最低位的 1。

这里需要特别说明参照约定：很多教材讲“前导零”时，是从最高位往低位数。为了与 CLZ 指令直接对应，embOS 通常把位图组织成“高优先级放在高位”的形式，即优先级 0 放在 bit31，优先级 31 放在 bit0。这样，位图中最高位的 1 就正好对应最高优先级，而“最高位 1 之前有多少个 0”就是该优先级的编号。这个“数前导零”的操作，正是 CLZ 指令的用武之地。

CLZ 指令：一条指令完成优先级编码

CLZ（Count Leading Zeros）是 ARM Cortex-M 等处理器提供的硬件指令，它返回一个 32 位操作数中从最高位开始连续 0 的个数。若操作数为 0，结果通常为 32。把就绪位图直接送入 CLZ，得到的结果恰好就是最高优先级任务的优先级号（在“优先级 0 占 bit31”的约定下）。

下面是一段示意性的伪代码，用于说明这一过程（数值为教学示例，非实测数据）：

// 约定：bit31 对应优先级 0，bit0 对应优先级 31
// readyBitmap 中为 1 的位表示该优先级有就绪任务

uint32_t readyBitmap = 0x0000A000; // bit15 与 bit17 置位
// 即优先级 16 与优先级 14 上有就绪任务

uint32_t prio = __CLZ(readyBitmap); // 结果 = 14
// 14 即当前最高优先级，直接用于索引任务控制块

OS_Task* next = ReadyList[prio];   // O(1) 取出待运行任务

可以看到，从位图到优先级号只用了一条 CLZ 指令，再从就绪表数组按下标取出任务，整个过程与任务总数、优先级总数无关，这就是 O(1) 调度查找的含义。

就绪表查找的完整链路

把上述环节串起来，一次调度查找的完整链路是：任务状态变化时更新对应优先级的就绪链表，同时置位或清位位图；调度时读取位图，用 CLZ 得到最高优先级号，再用该优先级号索引就绪表取出任务控制块，最后切换上下文。下图给出了这一链路的信号与数据流向。

不同优先级数量对调度开销的影响

位图的宽度决定了系统能支持的优先级数量。embOS 允许在配置时选择优先级数量，常见的有 8、16、32 等档位。位图越宽，单次 CLZ 或查表操作本身仍然是常数时间，但会带来两方面影响：一是位图变量占用的存储从 1 字节变为 2 字节或 4 字节；二是当优先级数量超过 32 时，单个 32 位整数不够用，需要多个位图字，查找时就要先判断高位字是否非零，再对非零的那个字做 CLZ，查找步数会随“位图字数”增加，但仍然是常数级，只是常数变大。

因此，优先级数量并不是越多越好。对于大多数中小型嵌入式项目，16 或 32 个优先级已经足够；如果确实需要更多优先级，应评估调度查找的额外开销是否仍在实时预算之内。下面这张表给出不同优先级档位下的典型差异（数值为教学示例，用于说明趋势，非实测结果）：

实践中的配置与验证要点

在实际工程中，配置优先级数量通常通过 embOS 的配置宏完成，例如在 OS_CFG.h 中设置优先级数量相关的宏。配置完成后，建议做三件事来验证就绪表与位图工作正常：

• 检查位图与就绪表一致性：在调试器中观察位图变量，确认某优先级有就绪任务时对应位为 1，任务全部离开就绪态后该位被清零。
• 验证最高优先级选择：构造两个不同优先级的就绪任务，确认调度器总是先运行优先级数值更小的那个。
• 测量调度耗时：用 GPIO 翻转或周期计数方式，在任务切换前后打点，比较不同优先级档位下的切换耗时，确认仍在实时预算内。

需要强调的是，就绪表与位图是 embOS 调度器的“索引结构”，它把“找最高优先级”从线性搜索变成了位运算。理解位图的位序约定、CLZ 的语义以及优先级数量对查找常数的影响，是后续分析任务切换耗时、优化实时响应的重要基础。