3. 就绪列表与调度器：数据结构与选任务机制
好，咱们接着聊。上一章我们把任务的状态切换理清楚了，这一章我带你深入看看FreeRTOS的“心脏”——就绪列表和调度器。说白了，调度器就是那个决定“下一个该谁跑”的裁判，而就绪列表就是裁判手里的花名册。
我个人习惯把就绪列表比作一个“多级抽屉柜”。每个优先级是一个抽屉，抽屉里放着一条链表，链着所有该优先级的就绪任务。调度器选任务时，先看哪个优先级最高的抽屉里有任务，再从那个抽屉里挑一个出来跑。
3.1 就绪列表的数据结构
FreeRTOS的就绪列表，核心是两个东西：优先级位图和链表。这两个配合起来，效率极高。
3.1.1 优先级位图
你想想看，如果系统支持32个优先级，调度器每次选任务时，难道要从优先级0到31挨个查一遍吗？那太慢了。FreeRTOS用了一个位图来加速。
位图其实就是一个32位的整数。每一位代表一个优先级。比如bit0代表优先级0，bit1代表优先级1，以此类推。如果某个优先级上有就绪任务，对应的位就置1。
代码里是这样定义的：
/* 在 task.c 中 */
#define portMAX_8_BIT_VALUE ((uint8_t)0xff)
#define portMAX_16_BIT_VALUE ((uint16_t)0xffff)
#define portMAX_32_BIT_VALUE ((uint32_t)0xffffffffUL)
/* 优先级位图变量 */
#if ( configUSE_PORT_OPTIMISED_TASK_SELECTION == 1 )
/* 使用硬件指令优化的版本 */
#define taskSELECT_HIGHEST_PRIORITY_TASK() ...
#else
/* 通用版本，使用软件查找 */
static volatile UBaseType_t uxTopReadyPriority; /* 记录当前最高就绪优先级 */
static volatile UBaseType_t uxTopReadyPriority; /* 位图变量 */
#endif嗯，这里要注意：uxTopReadyPriority这个变量，它记录的是当前所有就绪任务中，最高的优先级是多少。调度器不用遍历所有优先级，直接看这个变量就知道该从哪个抽屉里拿任务。
核心思想：用空间换时间。一个32位的整数，就能知道所有优先级的就绪情况。查找最高优先级时，用一条指令就能找到最高位的1在哪。
3.1.2 就绪链表
每个优先级对应一条链表。链表的节点就是任务控制块（TCB）。同一个优先级的多个任务，按时间片轮转的方式挂在链表上。
数据结构是这样的：
/* 就绪列表的定义 */
typedef struct xLIST
{
UBaseType_t uxNumberOfItems; /* 列表中任务的数量 */
ListItem_t * pxIndex; /* 用于遍历的索引指针 */
MiniListItem_t xListEnd; /* 列表结束标记 */
} List_t;
/* 每个优先级一个列表 */
static List_t pxReadyTasksLists[ configMAX_PRIORITIES ];你看，pxReadyTasksLists是一个数组，数组的每个元素是一条链表。比如pxReadyTasksLists[5]就是优先级5的就绪任务链表。
我在项目中遇到过一个问题：某个高优先级任务一直占着CPU，低优先级任务饿死了。后来排查发现，是同一个优先级下多个任务没有正确使用时间片轮转。嗯，这里要提醒你，同优先级任务默认是时间片轮转的，但如果你把时间片设得太大，或者任务里加了阻塞延时，轮转效果就会打折扣。
3.2 调度器如何选任务
调度器选任务的过程，我总结为三步：查位图 → 找链表 → 取任务。
3.2.1 查位图：找到最高优先级
调度器先看uxTopReadyPriority这个变量。如果它等于5，说明优先级5是当前最高的就绪优先级。
但这里有个细节：uxTopReadyPriority是怎么更新的？每次任务进入就绪态时，如果它的优先级比当前记录的uxTopReadyPriority高，就更新这个变量。同样，当任务离开就绪态时，如果那个优先级上没任务了，就要重新计算最高优先级。
重新计算最高优先级，用的是位图查找算法。通用版本是软件循环查找：
/* 通用版本：软件查找最高优先级 */
#define taskRECORD_READY_PRIORITY( uxPriority ) \
{ \
if( ( uxPriority ) > uxTopReadyPriority ) \
{ \
uxTopReadyPriority = ( uxPriority ); \
} \
}
#define taskSELECT_HIGHEST_PRIORITY_TASK() \
{ \
UBaseType_t uxTopPriority = uxTopReadyPriority; \
/* 从最高优先级开始，向下查找第一个非空链表 */ \
while( listLIST_IS_EMPTY( &( pxReadyTasksLists[ uxTopPriority ] ) ) ) \
{ \
--uxTopPriority; \
} \
/* 从该链表中取出第一个任务 */ \
pxCurrentTCB = listGET_OWNER_OF_HEAD_ENTRY( \
&( pxReadyTasksLists[ uxTopPriority ] ) ); \
uxTopReadyPriority = uxTopPriority; \
}如果硬件支持CLZ（Count Leading Zeros）指令，那就更快了。ARM Cortex-M3/M4都支持，一条指令就能找到最高优先级的位。
我的建议：如果你的芯片支持CLZ指令，一定要开启configUSE_PORT_OPTIMISED_TASK_SELECTION这个宏。选任务的时间从O(n)变成O(1)，实时性提升很明显。
3.2.2 找链表：取出任务控制块
找到最高优先级后，就从对应的链表中取出第一个任务。注意，这里取的是链表头部的任务。因为同优先级任务采用时间片轮转，每次调度都会把当前任务移到链表尾部，然后取新的头部任务。
代码里是这样做的：
/* 从就绪链表中取出最高优先级的任务 */
pxCurrentTCB = listGET_OWNER_OF_HEAD_ENTRY(
&( pxReadyTasksLists[ uxTopReadyPriority ] ) );listGET_OWNER_OF_HEAD_ENTRY这个宏，就是获取链表头部节点所属的任务控制块。说白了，就是拿到那个任务的TCB指针。
3.2.3 切换上下文：让任务跑起来
拿到TCB指针后，调度器就调用portYIELD()或者taskYIELD()触发PendSV中断，在中断里完成上下文切换。这部分我们后面章节会详细讲，这里先记住：选任务只是第一步，真正让任务跑起来的是上下文切换。
我曾经踩过的坑：有一次我在中断服务函数里调用了taskYIELD()，结果系统直接死机了。后来发现，中断里调用taskYIELD()需要特别小心，因为中断上下文和任务上下文不一样。正确的做法是在中断里设置一个标志，然后在任务里检查这个标志再调用taskYIELD()。
3.3 调度器的触发时机
调度器不是一直在跑的，它只在特定时刻被触发。我总结了一下，主要有这几个时机：
- 任务主动让出CPU：比如调用
taskYIELD()或vTaskDelay() - 时间片用完：SysTick中断触发，检查当前任务的时间片是否用完
- 更高优先级任务就绪：比如中断里释放了信号量，唤醒了一个高优先级任务
- 任务被阻塞或挂起：当前任务主动进入阻塞态，调度器立刻选下一个任务
你想想看，如果调度器每时每刻都在跑，那CPU就全浪费在调度上了。所以FreeRTOS的设计是“按需调度”，只在必要的时候才触发调度。
3.4 一个完整的调度流程示例
假设系统有三个任务：
| 任务名 | 优先级 | 当前状态 |
|---|---|---|
| TaskA | 5 | 就绪 |
| TaskB | 3 | 就绪 |
| TaskC | 5 | 就绪 |
调度流程是这样的：
- 调度器查看
uxTopReadyPriority，发现最高优先级是5 - 从
pxReadyTasksLists[5]链表中取出头部任务 - 假设头部任务是TaskA，那么
pxCurrentTCB指向TaskA - 触发PendSV中断，保存TaskB的上下文，恢复TaskA的上下文
- TaskA开始运行
- TaskA的时间片用完后，SysTick中断触发，调度器再次运行
- 调度器把TaskA移到链表尾部，取出TaskC作为下一个运行任务
- 切换上下文，TaskC开始运行
你看，整个过程非常清晰。优先级5的两个任务轮流跑，优先级3的TaskB只能等优先级5的任务都阻塞了才有机会。
总结一下：就绪列表用位图+链表的结构，实现了O(1)时间复杂度的任务选择。调度器只在必要时触发，选任务的过程就是“查位图→找链表→取任务”三步。理解了这个，你就掌握了FreeRTOS调度的核心。
下一章，我会带你看看任务切换的具体实现——那个神秘的PendSV中断里到底发生了什么。