调度器核心数据结构设计：就绪队列、阻塞队列、延时队列与TCB
上一章我们聊了系统时钟节拍怎么产生，这一章咱们来点实在的——调度器肚子里到底装了什么数据结构。说白了，调度器就是个“任务管家”，它得知道哪些任务能跑、哪些在睡觉、哪些在等东西。这些信息怎么存？就是靠队列和TCB。
我个人习惯，设计调度器之前先把数据结构画清楚。数据结构定了，代码逻辑自然就顺了。你想想看，如果连任务控制块里放什么都不清楚，后面写调度算法肯定到处打补丁。
任务控制块（TCB）——任务的“身份证”
每个任务在系统里都有一个TCB。它记录了任务的所有信息，就像你的身份证一样。我见过不少初学者把TCB设计得特别臃肿，什么调试信息、统计信息全塞进去。其实没必要，核心字段就那么几个。
- 任务栈指针——保存任务上下文（寄存器值）的位置
- 任务状态——就绪、阻塞、延时、挂起、运行
- 任务优先级——决定谁先跑
- 任务入口函数——任务代码的起始地址
- 延时/超时计数——用于延时队列和阻塞超时
- 等待事件类型——阻塞原因（信号量、消息队列等）
- 链表节点——把TCB串到各个队列里
下面是我常用的TCB结构体定义，你可以直接拿去用：
typedef struct tcb {
uint32_t *sp; // 栈指针，保存任务上下文
uint8_t state; // 任务状态
uint8_t priority; // 优先级（0最高）
void (*entry)(void *arg); // 任务入口函数
void *arg; // 入口参数
uint32_t delay_ticks; // 延时/超时计数
uint32_t wait_event; // 等待的事件类型
void *wait_obj; // 等待的对象指针
list_node_t node; // 链表节点
} tcb_t;就绪队列——谁准备好了？
就绪队列存放所有“可以运行”的任务。调度器每次选任务，都是从就绪队列里挑一个优先级最高的。
就绪队列的设计有好几种思路。我最早做RTOS时用的是优先级位图法，每个优先级一个bit，配合一个查找表，O(1)就能找到最高优先级的就绪任务。后来项目多了，我发现对于任务数不超过32个的系统，这种方法最稳。
| 设计方法 | 查找复杂度 | 内存开销 | 适用场景 |
|---|---|---|---|
| 优先级位图法 | O(1) | 小（32位即可） | 任务数≤32，硬实时 |
| 双向链表 | O(n) | 中 | 任务数少，实现简单 |
| 多级队列 | O(1)~O(n) | 大 | 任务数多，支持时间片 |
我个人习惯用优先级位图法。每个优先级对应一个就绪链表头，同优先级的任务用时间片轮转。这样既保证了实时性，又实现了公平调度。
// 就绪队列结构
#define MAX_PRIORITY 32
typedef struct {
uint32_t ready_bitmap; // 就绪位图，每个bit对应一个优先级
list_head_t ready_list[MAX_PRIORITY]; // 每个优先级的就绪链表
} ready_queue_t;阻塞队列——在等什么？
任务因为等待某个资源（信号量、消息队列、互斥锁）而无法继续执行时，就会被放入阻塞队列。阻塞队列通常是按优先级排序的，这样当资源释放时，优先级最高的等待者能最先拿到。
阻塞队列的设计有个关键点：每个资源对象都有自己的阻塞队列。比如信号量sema1和sema2，它们各自维护一个阻塞队列。这样当sema1释放时，只需要唤醒sema1的阻塞队列，不会影响到sema2的等待者。
// 阻塞队列（挂载在资源对象上）
typedef struct {
list_head_t block_list; // 阻塞任务链表（按优先级排序）
uint8_t block_count; // 阻塞任务数量
} block_queue_t;插入阻塞队列时，要按优先级从高到低排序。我见过有人直接用尾插法，结果低优先级任务永远排在前面，高优先级任务反而等更久——这明显不合理。
延时队列——睡一会儿
任务调用延时函数（比如task_delay(100)）后，会被放入延时队列。系统时钟节拍每来一次，延时队列里所有任务的计数值减1。减到0的任务，就移到就绪队列。
延时队列的实现有两种主流方式：
- 有序链表：按剩余延时时间从小到大排序。每次tick中断只检查链表头部的任务，效率高。
- 定时器轮（Timer Wheel）：把时间分成多个槽位，每个槽位对应一个延时范围。适合大量任务需要不同延时时间的场景。
我一般用有序链表。对于单片机场景，任务数量通常不超过几十个，有序链表的O(n)插入完全够用。而且实现简单，不容易出bug。
// 延时队列
typedef struct {
list_head_t delay_list; // 按剩余延时时间排序的链表
uint32_t min_delay; // 当前最小延时值（链表头部）
} delay_queue_t;三个队列的协同工作
这三个队列不是孤立的，它们通过调度器紧密配合。下面这张图展示了任务在三个队列之间的流转关系：
临界区保护——别让数据乱掉
队列操作涉及多个任务和中断，不加保护肯定出问题。临界区保护的核心原则是：操作共享数据时，禁止任务切换和中断响应。
我常用的保护方式有两种：
- 关中断：最简单粗暴，但关中断时间不能太长（一般不超过几十微秒）
- 挂起调度器：只禁止任务切换，不关中断。适合中断服务程序里需要操作队列的场景