4. SMP调度器数据结构剖析

在VxWorks的SMP（对称多处理）内核中，调度器的性能与确定性，很大程度上取决于其底层数据结构的设计。理解这些结构，是分析调度延迟、排查优先级反转、评估负载均衡开销的前提。本节将逐一剖析就绪队列的组织方式、优先级位图的加速机制、负载均衡的触发条件，以及每CPU运行队列与全局队列之间的工程取舍。

就绪队列的组织：从单链表到每CPU队列

在单核VxWorks中，就绪队列通常是一个按优先级索引的数组，每个优先级对应一条双向链表，所有就绪任务挂在对应优先级的链表上。调度器只需找到最高非空优先级，取出链表头任务即可。进入SMP后，如果仍然只维护一条全局就绪队列，所有CPU在每次调度时都要竞争同一把队列锁，核数越多，锁争用越严重，调度延迟随核数增加而恶化。

因此，VxWorks SMP采用每CPU运行队列（per-CPU run queue）为主的结构：每个CPU拥有自己的就绪队列数组，任务被分配到某个CPU的队列上，该CPU的调度器只操作本地队列，绝大多数情况下无需跨核加锁。全局层面只保留必要的同步信息，例如任务与CPU的绑定关系、负载统计和迁移请求。

每CPU队列的核心字段通常包括：按优先级索引的队列头数组、每个优先级的任务计数、当前最高非空优先级缓存、队列自旋锁，以及指向该CPU当前运行任务的指针。任务控制块（TCB）中则记录其所属CPU、就绪状态标志和队列挂接指针。这种设计把“找最高优先级任务”和“取任务”两个动作都限制在本地，显著降低了缓存行 bouncing。

优先级位图：O(1)查找最高优先级

如果每次调度都从最高优先级向下线性扫描，最坏情况要检查256个优先级（VxWorks默认优先级范围0～255，数值越小优先级越高）。为把查找降到常数时间，VxWorks使用优先级位图（priority bitmap）配合前导零计数指令。

位图把每个优先级映射为一个bit：该优先级有就绪任务则置1，否则置0。查找最高非空优先级时，只需对位图取“最高有效位”位置。在32位或64位字上，通常用多级位图：第一级每个bit代表一个32位字是否有非零位，第二级才是具体的优先级bit。这样一次前导零计数即可定位到字，再一次前导零计数定位到具体优先级，整体为O(1)。

下面给出一个简化的位图查找示意（以32个优先级为例，实际VxWorks为256级）：

/* 假设 readyBitmap 为 32 位，bit0 对应优先级0（最高） */
unsigned int readyBitmap = 0x00000000;

/* 任务就绪：置位 */
readyBitmap |= (1u << prio);

/* 任务阻塞：清位（需确认该优先级无其他就绪任务） */
readyBitmap &= ~(1u << prio);

/* 查找最高优先级：前导零计数，bit0为最高优先级 */
int highestPrio = __builtin_clz(readyBitmap);  /* 返回前导零个数 */
/* 若 readyBitmap 非零，highestPrio 即为最高非空优先级 */

在每CPU队列中，位图是每CPU一份的，因此查找过程完全本地化。需要注意的是，位图只反映“该优先级是否有就绪任务”，具体取哪个任务仍由该优先级链表决定，通常采用FIFO或轮转策略。

负载均衡的触发条件

每CPU队列带来低锁开销的同时，也带来负载不均的风险：某个CPU可能空闲，而另一个CPU的队列上堆积了大量就绪任务。VxWorks SMP的负载均衡并非持续运行，而是在特定条件下触发，以控制迁移开销。

常见的触发条件包括：

• 空闲CPU主动拉取：当某CPU本地队列为空、即将进入空闲循环时，它会尝试从其他CPU的队列“偷取”一个就绪任务。这是最自然的均衡时机，因为空闲CPU本来就没有有效工作。
• 新任务创建或任务就绪：当任务被创建或从阻塞态变为就绪态时，调度器根据当前各CPU负载，决定将其放入哪个CPU的队列，而不是简单放回原CPU。
• 周期性负载采样：内核可周期性统计各CPU队列长度，当最大队列长度与最小队列长度之差超过阈值时，触发任务迁移。
• 优先级抢占引发的再平衡：高优先级任务就绪导致某CPU频繁抢占时，若该CPU队列中同优先级任务过多，可触发向其他CPU迁移。

负载均衡的代价包括：跨核队列加锁、任务TCB在CPU间迁移导致的缓存失效、以及迁移后可能破坏任务与CPU的亲和性。因此，触发条件的设计目标是在“均衡收益”和“迁移开销”之间取得平衡。

每CPU运行队列与全局队列的取舍

这是SMP调度器设计中最核心的权衡之一。两种极端方案各有明显优劣：

VxWorks SMP实际采用的是以每CPU队列为主、辅以受控迁移的混合策略。它既避免了全局队列的锁瓶颈，又通过空闲拉取和阈值触发迁移来防止长期负载倾斜。工程上需要关注的参数包括：迁移阈值、采样周期、是否允许跨核迁移、以及任务CPU亲和性设置。对于硬实时任务，通常建议绑定到特定CPU，避免迁移带来的抖动；对于吞吐型任务，则可放宽亲和性，让负载均衡发挥作用。

从图中可以直观看到：每个CPU拥有独立的就绪队列和位图，调度查找完全本地化；全局结构只保留绑定关系、负载计数和迁移标志，不承载完整队列；负载均衡在空闲拉取、新任务就绪、周期采样和抢占再平衡四种条件下触发，迁移时通过全局元数据协调。这种“本地为主、全局为辅”的布局，正是VxWorks SMP在可扩展性与实时性之间取得平衡的关键。