RTOS内核开发实战(2)：TCB、优先级位图与Ready Queue，把可运行任务集合建起来

把链表打好之后，下一步不是立刻写 PendSV，而是先定义“调度器眼里的任务”到底长什么样。

当前这版代码里，这个问题的答案落在 tcb_t 和 ready_queue_t 两个结构上。

先回答一个问题：调度器看到的任务是什么

先看任务控制块：

typedef struct tcb {
    uint32_t *sp;
    uint32_t *stack_base;
    uint32_t  stack_size;

    task_entry_t entry;
    void       *param;
    const char *name;

    uint32_t magic;
    os_tick_t wake_tick;
    void    *wait_obj;

    uint8_t      priority;
    task_state_t state;
    uint8_t      time_slice;
    uint8_t      time_slice_reload;

    list_node_t sched_node;
    list_node_t event_node;
} tcb_t;

这份定义体现了一个很典型的 RTOS 分层思路：一个任务不是只有“入口函数 + 栈”这么简单，它还必须同时承载运行现场、调度属性和阻塞关系。

其中有三个设计点值得单独拆开说。

tcb_t 里最关键的三个设计点

第一，sp 被放在最前面，而且是调度器和 port 层共同维护的关键字段。对内核来说，任务切换本质上不是“调用另一个函数”，而是切换到另一块栈的执行上下文，所以保存和恢复 sp 才是最底层的任务语义。

第二，magic 明确把“合法 TCB”和“未初始化内存块”区分开了。当前实现用 OS_TASK_MAGIC 做快速校验：

static uint8_t task_is_valid(const tcb_t *task)
{
    if (task == NULL)
    {
        return 0U;
    }

    return (uint8_t)(task->magic == OS_TASK_MAGIC);
}

很多 bug 并不是算法错了，而是调用者拿着一块还没初始化好的结构体就开始参与调度。magic 的意义就在这里，它让调度器在读取 priority、state、sched_node.owner 之前先确认这是不是一个真正完成初始化的任务。

为什么要拆 sched_node 和 event_node

第三，sched_node 和 event_node 分离。为什么不只保留一个链表节点？因为任务在不同子系统里承担的角色并不一样：

1. sched_node 服务于调度相关链表，比如 ready list，未来也可以扩到 sleep list。
2. event_node 服务于事件等待链表，比如队列、信号量、互斥锁的等待队列。

一个任务在某一时刻也许不会同时出现在两类链表里，但把节点提前拆开，可以避免以后做阻塞/唤醒时为了“一个节点重复复用”引入额外状态机复杂度。

ready queue 为什么是“链表数组 + 位图”

再看 ready queue：

typedef struct ready_queue {
    list_t   ready_lists[OS_MAX_PRIORITIES];
    uint32_t ready_bitmap;
} ready_queue_t;

这是一个很工程化的选择。

它没有使用红黑树、堆，也没有做复杂优先队列，而是采用“每个优先级一条链表 + 一个 32 位位图”的经典 RTOS 组织方式。

为什么这样设计？

1. OS_MAX_PRIORITIES 当前被限制在 32 以内，天然适合用一个 uint32_t 表示非空优先级集合。
2. 同优先级任务本来就要支持 round-robin，链表是最直接的表示方式。
3. 最高优先级查找虽然是从 0 到 OS_MAX_PRIORITIES - 1 扫描，但扫描上限固定且很小，对 Cortex-M3 足够友好。

为什么插入时选择尾插

插入 ready queue 的实现把这三个设计点都落了地：

void ready_queue_insert_tail(ready_queue_t *queue, tcb_t *task)
{
    uint8_t priority = 0U;

    if ((queue == NULL) || (task == NULL))
    {
        return;
    }

    priority = task->priority;

    if (ready_queue_priority_is_valid(priority) == 0U)
    {
        return;
    }

    if (list_insert_tail(&queue->ready_lists[priority], &task->sched_node) == 0U)
    {
        return;
    }

    queue->ready_bitmap |= ready_queue_priority_mask(priority);
    task->state = TASK_READY;
}

这里用了“尾插 ready list”的策略。

原因不是偶然，而是为了给时间片轮转打基础。假设同优先级有多个任务，那么当前任务时间片耗尽或主动 yield 时，只要把队头摘下来再插回队尾，下一次调度自然就轮到后面的兄弟任务。

位图扫描为什么已经够用

最高优先级查找同样很朴素：

uint8_t ready_queue_get_highest_priority(const ready_queue_t *queue, uint8_t *priority)
{
    uint8_t current = 0U;

    if ((queue == NULL) || (queue->ready_bitmap == 0U))
    {
        return 0U;
    }

    for (current = 0U; current < OS_MAX_PRIORITIES; current++)
    {
        if ((queue->ready_bitmap & ready_queue_priority_mask(current)) != 0U)
        {
            if (priority != NULL)
            {
                *priority = current;
            }
            return 1U;
        }
    }

    return 0U;
}

这段代码看起来没有“位操作黑科技”，但它反而说明当前实现的取舍很清晰：先把语义和边界做稳，再谈更激进的优化。对于一个刚搭起来的内核，简单、可验证、容易调试，往往比极限性能更重要。

TASK_RUNNING 为什么仍然留在 runnable 集合

当前这版 ready queue 还有一个值得注意的语义：TASK_RUNNING 的任务仍然留在 runnable 集合里。

也就是说，调度器维护的是一个“全体可运行任务集合”，而不是“ready 任务 + 单独摘出来的 current task”两套并行结构。这样做的好处是：

1. 调度器选下一个任务时，直接看最高优先级链表头即可，不需要额外把 current task 拼回去比较。
2. 同优先级 round-robin 的头尾轮转逻辑更自然。
3. current 和 next 的变化，被集中收敛到 task_set_current() 这种状态提交点里，而不是散落在多个地方。

小结

这篇文章讲的是“可运行任务集合怎么建立”。

下一篇会接着讲它怎么真正开始运转：任务创建后如何进入 ready queue，调度器如何只做“决策”不做“切换”，以及时间片和主动让出 CPU 是怎样接上去的。