📚 课程目录第3章常见调度算法

3. 常见调度算法

任务控制块，简称 TCB，是调度器的心脏。说白了，每个任务在系统里都有一个身份证，TCB 就是这张身份证。我见过不少初学者，上来就写调度算法，结果 TCB 结构体里字段对不上，跑起来全是玄学 bug。所以这一章，咱们先把 TCB 的单元测试做扎实。

3.1 TCB 结构体定义与初始化测试

先看一个典型的 TCB 结构体。我个人习惯把状态、优先级、栈指针、任务入口这几个字段放在最前面，方便调试时一眼扫过去。

typedef struct {
    uint8_t     task_id;        // 任务ID，从0开始
    uint8_t     priority;       // 优先级，0最高
    uint8_t     state;          // 当前状态
    uint32_t    *stack_ptr;     // 当前栈指针
    uint32_t    *stack_base;    // 栈底地址
    uint32_t    stack_size;     // 栈大小（字）
    void        (*entry)(void); // 任务入口函数
    uint32_t    timeout_ticks;  // 延时/超时计数
} TCB_t;

单元测试第一步：验证初始化后的默认值。我建议写一个 TCB_Init() 函数，把所有字段清零或设为安全初值。

void TCB_Init(TCB_t *tcb, uint8_t id, uint8_t prio, void (*entry)(void)) {
    tcb->task_id      = id;
    tcb->priority     = prio;
    tcb->state        = TASK_READY;   // 初始化为就绪态
    tcb->stack_ptr    = NULL;
    tcb->stack_base   = NULL;
    tcb->stack_size   = 0;
    tcb->entry        = entry;
    tcb->timeout_ticks = 0;
}

测试用例要覆盖：

正常初始化后，state 是否为 TASK_READY
priority 是否与传入值一致
stack_ptr 是否为 NULL（还没分配栈）
传入非法 ID（比如 0xFF）时，函数是否做边界检查

    关键点：初始化后的 TCB 必须处于确定状态。我曾经在一个项目里发现，某次复位后 TCB 的 state 字段是随机值，调度器直接把它当成运行态任务去切换，结果栈指针乱飞。从那以后，我坚持在 Init 里显式赋值，绝不依赖 .bss 段的零初始化。

3.2 状态机转换测试

任务状态机是调度器的骨架。常见的状态有：READY、RUNNING、BLOCKED、SUSPENDED、DORMANT。状态转换必须严格受控，不能出现非法跳转。

我画了一张状态转换图，方便大家对照测试用例设计。

测试状态转换时，我习惯用表格列出所有合法转换和非法转换，然后逐条写测试用例。

当前状态	触发动作	目标状态	是否合法
READY	调度器选中	RUNNING	合法
RUNNING	时间片耗尽	READY	合法
RUNNING	等待信号量	BLOCKED	合法
BLOCKED	超时/资源就绪	READY	合法
RUNNING	挂起调用	SUSPENDED	合法
SUSPENDED	恢复调用	READY	合法
BLOCKED	直接挂起	SUSPENDED	合法（部分实现）
READY	直接删除	DORMANT	合法
BLOCKED	直接删除	DORMANT	合法（需先清理资源）
BLOCKED	调度选中	RUNNING	非法
SUSPENDED	调度选中	RUNNING	非法
DORMANT	任何动作（除创建）	—	非法

避坑指南：我曾经在测试 BLOCKED→SUSPENDED 转换时，忘了检查该任务是否持有互斥锁。结果挂起后锁没释放，导致其他任务死等。所以状态转换测试不仅要测状态字段，还要测副作用——比如释放资源、从就绪队列移除等。

3.3 优先级校验测试

优先级是调度决策的核心依据。优先级校验要覆盖三个维度：范围、唯一性、动态调整。

3.3.1 优先级范围校验

假设系统支持 0~31 级优先级，0 最高，31 最低。测试用例：

合法值：0、15、31 都能正常设置
边界值：设置优先级 32 应返回错误码
负值（如果参数是 int）：应被截断或报错

// 测试用例示例
void test_priority_range(void) {
    TCB_t tcb;
    // 合法优先级
    TEST_ASSERT_EQUAL(ERR_OK, TCB_SetPriority(&tcb, 0));
    TEST_ASSERT_EQUAL(ERR_OK, TCB_SetPriority(&tcb, 15));
    TEST_ASSERT_EQUAL(ERR_OK, TCB_SetPriority(&tcb, 31));
    // 非法优先级
    TEST_ASSERT_EQUAL(ERR_INVALID_PRIO, TCB_SetPriority(&tcb, 32));
    TEST_ASSERT_EQUAL(ERR_INVALID_PRIO, TCB_SetPriority(&tcb, 255));
}

3.3.2 优先级唯一性校验（可选）

有些调度器要求每个优先级只能有一个任务。这种情况下，创建任务时要检查该优先级是否已被占用。

我的经验：在非抢占式调度器里，优先级唯一性不是必须的。但在抢占式调度器里，如果两个任务同优先级，你就要决定是用时间片轮转还是固定顺序。我个人更倾向于时间片轮转，这样不会饿死任何一个同优先级任务。

3.3.3 动态优先级调整测试

运行时修改优先级，需要重新计算就绪队列。测试要点：

降低优先级后，任务是否被抢占
提高优先级后，任务是否立即获得 CPU
如果当前任务修改自己的优先级，调度器能否正确处理

void test_dynamic_priority_change(void) {
    TCB_t low_task, high_task;
    TCB_Init(&low_task,  0, 10, task_func);
    TCB_Init(&high_task, 1, 5,  task_func);

    // 假设 low_task 正在运行
    // 将 low_task 优先级提升到 3（高于 high_task）
    TCB_SetPriority(&low_task, 3);
    // 此时调度器应重新调度，让 low_task 继续运行（因为它优先级更高）
    // 验证当前运行任务是否为 low_task
    TEST_ASSERT_EQUAL(&low_task, scheduler_get_current());
}

    核心原则：优先级校验的测试，本质是在验证调度器的公平性和实时性。我见过一个案例，动态调整优先级后忘了更新就绪队列的排序，结果高优先级任务永远跑不上。所以测试一定要覆盖「修改后立即触发重新调度」这个路径。

3.4 综合测试：TCB 全生命周期

最后，我建议写一个综合测试用例，模拟 TCB 从创建到删除的完整生命周期：

创建 TCB，验证初始状态为 READY
调度器选中，状态变为 RUNNING
任务等待信号量，状态变为 BLOCKED
信号量释放，状态回到 READY
再次调度，状态变为 RUNNING
任务删除，状态变为 DORMANT
再次尝试调度 DORMANT 任务，应返回错误

这个综合测试能一次性暴露状态机、优先级、队列操作中的大部分问题。我在项目中每次修改调度器核心代码后，都会先跑一遍这个用例，再跑其他专项测试。

嗯，TCB 单元测试做到这个程度，调度器的基础就稳了。下一层，咱们再聊就绪队列的管理和测试。