4、就绪列表与调度决策：g_readytorun列表的结构与维护、优先级队列的插入与删除操作、调度器如何选择下一个任务
好，咱们今天聊点硬核的。就绪列表，说白了就是调度器的“待办事项清单”。NuttX 里这个清单叫 g_readytorun，它直接决定了下一个该谁上 CPU 跑。我当年刚啃 NuttX 源码时，第一反应是：这玩意儿不就是个链表吗？后来发现，事情没那么简单。
4.1 g_readytorun 列表的结构
g_readytorun 是一个全局的双向链表。每个就绪的任务，都会挂在这个链表上。但注意，它不是普通的链表——它是一个优先级队列。
链表里的节点，按优先级从高到低排列。最高优先级的任务，永远在链表头部。调度器选任务时，直接取头节点就行。嗯，这里要注意：NuttX 是优先级抢占式调度，所以这个顺序至关重要。
核心结构：
g_readytorun.head：指向最高优先级任务g_readytorun.tail：指向最低优先级任务- 每个任务节点有
flink（前向指针）和blink（后向指针）
我见过有人把就绪列表画成一排排队的人，优先级高的插队到前面。这个比喻挺形象，但实际代码里，插入和删除操作要严谨得多。
4.2 优先级队列的插入操作
当一个任务变成就绪态（比如从阻塞中醒来，或者新创建），调度器会把它插入到 g_readytorun 中。插入的核心逻辑是：找到合适的位置，保持优先级降序。
伪代码大概是这样：
void sched_addreadytorun(FAR struct tcb_s *tcb) {
// 从头部开始遍历，找到第一个优先级比当前任务低的节点
FAR struct tcb_s *next = g_readytorun.head;
while (next != NULL && next->sched_priority >= tcb->sched_priority) {
next = next->flink;
}
// 插入到 next 节点之前
if (next == NULL) {
// 插到尾部
dq_addlast(tcb, &g_readytorun);
} else {
dq_addbefore(tcb, next);
}
}
你想想看，这个遍历在最坏情况下是 O(n) 的。但 NuttX 的任务数通常不多（几十个顶天了），所以实际性能可以接受。我在一个物联网网关项目里，同时跑 20 多个任务，插入延迟从来没成为瓶颈。
我的经验：如果你在搞实时系统，任务数超过 100 个，建议考虑用位图或跳表优化。NuttX 的默认实现是为嵌入式场景设计的，别拿它跟 Linux 的 O(1) 调度器比。
4.3 优先级队列的删除操作
删除操作相对简单。任务被删除（比如退出）或者从就绪态变成其他状态时，直接从链表里摘掉就行。
void sched_removereadytorun(FAR struct tcb_s *tcb) {
dq_remove(tcb, &g_readytorun);
tcb->flink = NULL;
tcb->blink = NULL;
}
这里有个坑：删除后要检查是否影响了当前运行的任务。如果删除的是当前正在运行的任务（比如它自己调用了 task_delete），那调度器必须立刻重新选一个任务出来跑。
我曾经踩过的坑：有一次在中断服务程序里直接调用了 task_delete，结果删完任务后没触发重新调度，系统直接跑飞了。后来才意识到，中断退出时才会检查是否需要重新调度。所以，不要在 ISR 里直接操作任务生命周期，用信号量或消息队列通知一个高优先级任务去处理。
4.4 调度器如何选择下一个任务
调度决策的核心函数是 sched_switch 或 up_block_task 这类底层接口。但不管怎么封装，最终逻辑就一句话：
从 g_readytorun 头部取出第一个任务，它就是下一个要运行的。
具体流程：
- 检查当前任务是否还在就绪列表里（可能被删了）
- 如果当前任务不在就绪列表，直接取头部任务
- 如果当前任务在就绪列表，比较它和头部任务的优先级
- 如果头部任务优先级更高，就切换过去
- 如果当前任务优先级仍然最高，继续运行它
这里有个细节：同优先级任务怎么处理？ NuttX 默认是时间片轮转。同优先级的任务，按 FIFO 顺序轮流跑。每次时钟中断时，调度器会检查当前任务是否用完了时间片，如果是，就把它挪到链表尾部，让下一个同优先级任务上。
调度决策的简化伪代码：
FAR struct tcb_s *sched_pick_next(void) {
FAR struct tcb_s *next = g_readytorun.head;
if (next == NULL) {
// 没有就绪任务？跑空闲任务
return &g_idletcb;
}
return next;
}你看，就这么简单。但实际工程里，要考虑的事情多得多：
- 如果当前任务持有锁（比如
sched_lock），即使有更高优先级任务，也不能立即切换 - 中断嵌套时，调度决策会被延迟到中断完全退出后
- 多核情况下，每个 CPU 核心有自己的
g_readytorun（或者共享一个加锁访问）
我个人习惯把调度决策理解成“选班长”。就绪列表就是排队的学生，优先级高的站前面。每次上课（时间片）结束，班长换人。但如果有学生突然有急事（高优先级任务就绪），他可以插队到前面。嗯，这个比喻虽然不完美，但够用了。
4.5 实际项目中的注意事项
最后，分享几个我在项目中积累的经验：
| 场景 | 建议 |
|---|---|
| 任务数量少（<10） | 直接用默认链表，简单可靠 |
| 任务数量中等（10-50） | 考虑用优先级位图加速查找，NuttX 有 CONFIG_SCHED_BITMAP 选项 |
| 高频率创建/删除任务 | 注意链表操作的原子性，关中断保护 |
| 多核系统 | 每个核心维护独立就绪列表，避免锁竞争 |
避坑指南：我曾经在一个项目里，为了“优化性能”，把就绪列表改成了红黑树。结果任务切换开销反而变大了——因为嵌入式场景下，链表遍历的 O(n) 在 n 很小时比红黑树的 O(log n) 更快（常数项小）。所以，别盲目优化，先测量。
好了，关于就绪列表和调度决策，核心内容就这些。记住一句话：调度器的本质，就是维护好这个优先级队列，然后每次选头节点。剩下的，都是工程细节。