调度器数据结构：任务控制块(TCB)、任务链表、就绪队列

调度器说到底，就是管理一堆任务的数据结构。你想想看，一个单片机里跑着十几个任务，每个任务都有自己的状态、优先级、栈空间……这些东西怎么组织？靠的就是今天要讲的三个核心结构：任务控制块（TCB）、任务链表和就绪队列。

我刚开始写调度器的时候，觉得TCB就是个结构体嘛，随便定义几个字段就行了。结果第一次跑压力测试，系统直接崩了——栈溢出。后来才明白，TCB里每个字段的设计都是有讲究的。

1. 任务控制块（TCB）——任务的“身份证”

每个任务在系统里都有一个唯一的TCB。它记录了任务的所有关键信息。说白了，调度器不关心你的任务函数长什么样，它只认TCB。

一个典型的TCB结构体长这样：

typedef struct tcb {
    uint32_t    *sp;                // 栈指针（CPU上下文保存位置）
    uint8_t     priority;           // 任务优先级（0最高，数值越小优先级越高）
    uint8_t     state;              // 任务状态：就绪、运行、阻塞、挂起、终止
    uint16_t    delay_ticks;        // 延时计数（用于阻塞延时）
    uint32_t    stack_size;         // 任务栈总大小（字节）
    uint32_t    *stack_base;        // 栈底地址（用于栈溢出检测）
    char        name[16];           // 任务名称（调试用）
    void        (*entry)(void*);    // 任务入口函数指针
    void        *arg;               // 入口函数参数
    struct tcb  *next;              // 链表指针（指向下一个TCB）
} TCB_t;

这里我重点说几个容易踩坑的字段：

• sp（栈指针）：这是调度器切换任务时最关键的一个字段。每次任务切换，CPU的寄存器组都要保存到当前任务的栈里，然后sp指向这个保存位置。我见过有人忘记在任务创建时初始化sp，结果第一次切换就飞了。
• state（任务状态）：别小看这个字段。很多调度bug都是因为状态管理混乱导致的。比如一个任务明明在等信号量，却被调度器当成就绪任务给运行了。
• delay_ticks（延时计数）：这是实现阻塞延时的关键。每次系统滴答中断，调度器会遍历所有任务，把delay_ticks减1。减到0的任务才能回到就绪队列。
• stack_base（栈底地址）：这个字段不是必须的，但我强烈建议加上。做栈溢出检测时，只需要检查sp是否越过了stack_base。我在一个项目里没加这个，结果任务栈悄悄溢出了三天才被发现。

2. 任务链表——把任务串起来

有了TCB，怎么管理它们？最简单的办法就是用链表。每个TCB里都有一个next指针，指向下一个TCB。这样所有任务就串成了一条链。

任务链表通常是一个双向循环链表或者单向链表。我个人偏爱双向循环链表，原因很简单：插入和删除操作都是O(1)的，而且遍历方便。

链表结构示意图：

// 链表头节点（不存储任务信息，仅用于管理）
TCB_t *task_list_head = NULL;

// 插入任务到链表尾部
void task_list_add(TCB_t *tcb) {
    if (task_list_head == NULL) {
        task_list_head = tcb;
        tcb->next = tcb;  // 指向自己，形成循环
    } else {
        tcb->next = task_list_head->next;
        task_list_head->next = tcb;
    }
}

// 从链表中删除任务
void task_list_remove(TCB_t *tcb) {
    // 遍历链表找到前驱节点，然后修改指针
    // 注意处理头节点特殊情况
}

任务链表的作用不仅仅是“把任务串起来”。它还是调度器遍历所有任务的入口。比如：

• 系统滴答中断里，遍历链表更新所有任务的delay_ticks
• 删除任务时，遍历链表找到目标TCB
• 调试时，遍历链表打印所有任务的状态信息

3. 就绪队列——调度器的“候选名单”

任务链表里包含了所有任务，但调度器真正关心的只有那些可以运行的任务。这些任务被放在一个叫“就绪队列”的结构里。

就绪队列的实现方式有很多种，我按复杂度从小到大列一下：

实现方式	原理	时间复杂度	适用场景
简单数组队列	固定大小的数组，按FIFO顺序存放就绪任务	O(n)查找最高优先级任务	任务数少（<10），优先级简单
优先级位图+链表	每个优先级一个链表，用位图标记哪些优先级有就绪任务	O(1)查找最高优先级任务	任务数中等（10~50），优先级层级多
红黑树/堆	按优先级排序的树形结构	O(log n)插入和删除	任务数很多（>50），实时性要求高

在单片机场景下，我推荐使用优先级位图+链表的方式。为什么？因为它是真正的O(1)调度——不管有多少个任务，找到最高优先级的就绪任务只需要几条指令。

实现思路是这样的：

#define MAX_PRIORITY 32  // 假设支持32级优先级

// 每个优先级对应一个链表头
TCB_t *ready_list[MAX_PRIORITY];

// 位图：标记哪些优先级有就绪任务
uint32_t ready_bitmap = 0;

// 将任务加入就绪队列
void ready_queue_add(TCB_t *tcb) {
    uint8_t prio = tcb->priority;
    // 将任务插入对应优先级的链表尾部
    list_add_tail(&ready_list[prio], tcb);
    // 设置位图对应位
    ready_bitmap |= (1 << prio);
}

// 获取最高优先级的就绪任务
TCB_t* ready_queue_get_highest(void) {
    // 使用CLZ指令（前导零计数）找到最高优先级
    uint8_t highest_prio = __CLZ(ready_bitmap);
    if (highest_prio >= MAX_PRIORITY) {
        return NULL;  // 没有就绪任务
    }
    // 从对应链表中取出第一个任务
    return list_remove_head(&ready_list[highest_prio]);
}

4. 三者的关系——一张图说清楚

TCB、任务链表、就绪队列，这三者不是孤立的。它们共同构成了调度器的数据骨架。我画了一张图来展示它们的关系：

从这张图可以看得很清楚：

• 任务链表是“全集”，包含所有创建的任务，不管它们当前是什么状态
• 就绪队列是“子集”，只包含state=就绪的任务
• 调度器只跟就绪队列打交道，从里面挑一个优先级最高的任务来运行
• 任务状态变化时（比如从阻塞变成就绪），调度器负责把它从任务链表“移动”到就绪队列

5. 实际项目中的设计考量

讲完理论，说说我在实际项目里是怎么选型的。

场景一：小资源单片机（比如STM32F103，64KB Flash，20KB RAM）

任务数不超过10个，优先级不超过8级。我直接用简单数组+单向链表。TCB里只保留最核心的字段：sp、priority、state、delay_ticks、next。name字段用指针指向Flash里的字符串常量，不占RAM。

场景二：中等资源单片机（比如STM32F407，1MB Flash，192KB RAM）

任务数20~30个，优先级16级。我用优先级位图+双向循环链表。TCB里加上stack_base做栈溢出检测，name字段直接放16字节的数组，调试方便。

场景三：资源丰富的MPU（比如Cortex-A系列，跑Linux或RTOS）

这种情况我直接上红黑树。任务数可能上百个，优先级层级多，红黑树的O(log n)性能完全够用。而且Linux内核的调度器就是这么干的。

6. 避坑指南

最后，分享几个我亲身踩过的坑：

• TCB内存对齐：ARM Cortex-M要求栈指针必须8字节对齐。创建任务时如果忘了对齐，第一次压栈就触发硬件错误。我曾经因为这个查了整整一天。
• 链表操作的原子性：中断里和主循环里都可能操作链表。不加保护的话，链表指针随时可能被破坏。最简单的办法：操作前关中断，操作后开中断。
• 就绪队列的优先级反转：低优先级任务持有高优先级任务需要的资源，导致高优先级任务无法运行。这个问题要靠优先级继承或优先级天花板协议来解决，不是数据结构本身能搞定的。
• 任务栈大小的估算：TCB里的stack_size字段不是随便填的。我一般用“最大嵌套调用深度×每个函数栈帧大小+中断嵌套栈大小”来估算，然后加30%的安全余量。