📚 课程目录第4章调度器架构模式

4. 调度器架构模式

就绪列表，说白了就是调度器的核心数据结构。所有等待 CPU 的任务都在里面排队。如果这个列表出了问题，整个系统就乱套了。我见过不少项目，调度器跑着跑着任务就丢了，十有八九是就绪列表的操作有 bug。

这一章，我们就来专门测它。插入、删除、边界条件，一个都不能少。

4.1 就绪列表的基本操作

先明确一下我们要测什么。一个典型的就绪列表，通常支持以下操作：

插入：把一个任务控制块（TCB）放入列表
删除：从列表中移除一个指定的 TCB
查找最高优先级：找到当前就绪态中优先级最高的任务
遍历：检查列表完整性

我个人习惯把测试分成三个维度：功能正确性、边界条件、压力稳定性。这一章我们先搞定前两个。

4.2 插入操作测试用例

插入操作看起来简单，但坑不少。我列几个关键测试点：

测试编号	测试场景	预期结果
TC-INS-001	向空列表插入一个任务	列表不为空，头指针指向该任务
TC-INS-002	插入优先级高于当前头节点	新任务成为头节点
TC-INS-003	插入优先级低于当前尾节点	新任务成为尾节点
TC-INS-004	插入优先级与已有任务相同	按 FIFO 顺序排在同优先级末尾
TC-INS-005	插入 NULL 指针	函数返回错误码，列表不变

核心验证点：插入后，列表的 prev/next 指针必须形成双向闭环。我见过一个案例，插入时忘了更新前一个节点的 next 指针，结果遍历时直接死循环。

代码示例，一个典型的插入测试：

// 测试：向空列表插入任务
void test_insert_into_empty_list(void)
{
    ready_list_t list;
    tcb_t task;

    ready_list_init(&list);
    task.priority = 10;

    // 执行插入
    int ret = ready_list_insert(&list, &task);

    // 验证
    assert(ret == 0);
    assert(list.head == &task);
    assert(list.tail == &task);
    assert(task.next == &task);  // 自环
    assert(task.prev == &task);  // 自环
    assert(list.count == 1);

    printf("[PASS] TC-INS-001: 空列表插入成功\n");
}

4.3 删除操作测试用例

删除比插入更容易出问题。为什么？因为要处理四个指针的更新，少一个就崩了。

测试编号	测试场景	预期结果
TC-DEL-001	删除唯一的节点（列表变空）	head/tail 均为 NULL，count=0
TC-DEL-002	删除头节点	原第二节点成为新头节点
TC-DEL-003	删除尾节点	原倒数第二节点成为新尾节点
TC-DEL-004	删除中间节点	前后节点正确连接
TC-DEL-005	删除不存在的节点	返回错误码，列表不变

我曾经踩过的坑：删除头节点时，忘了检查列表是否只有一个节点。如果只有一个节点，删除后 head 和 tail 都应该置 NULL。我当时没处理这个分支，结果后续插入时直接写野指针，系统随机死机。排查了整整两天。

删除测试代码示例：

// 测试：删除中间节点
void test_delete_middle_node(void)
{
    ready_list_t list;
    tcb_t task1, task2, task3;

    ready_list_init(&list);
    task1.priority = 10;
    task2.priority = 20;
    task3.priority = 30;

    ready_list_insert(&list, &task1);
    ready_list_insert(&list, &task2);
    ready_list_insert(&list, &task3);

    // 删除中间节点 task2
    int ret = ready_list_remove(&list, &task2);

    assert(ret == 0);
    assert(list.count == 2);
    assert(task1.next == &task3);
    assert(task3.prev == &task1);
    assert(task2.next == NULL);  // 已移除，指针清空
    assert(task2.prev == NULL);

    printf("[PASS] TC-DEL-004: 删除中间节点成功\n");
}

4.4 边界条件测试

边界条件，说白了就是测极端情况。我把它分成三类：

4.4.1 空列表边界

从空列表删除任意节点 → 返回错误
从空列表查找最高优先级 → 返回 NULL
连续两次删除同一个节点 → 第二次应失败

4.4.2 满列表边界

对于静态数组实现的就绪列表（比如用位图或固定大小数组），要测：

插入到最大容量时，再插入一个 → 返回错误
满列表删除后，能否继续插入
满列表的遍历是否完整

4.4.3 优先级边界

插入优先级为 0（最高）的任务
插入优先级为 MAX_PRIORITY-1（最低）的任务
所有任务优先级相同

一个小技巧：我习惯在测试用例里故意制造「优先级反转」的场景。比如先插入一个低优先级任务，再插入高优先级，然后删除高优先级，检查低优先级是否恢复为头节点。这个场景能暴露很多指针更新遗漏的问题。

4.5 就绪列表测试框架图

下面这张图，是我自己整理的就绪列表测试框架。每次做新调度器，我都会照着这张表逐项过一遍。

4.6 测试执行与结果验证

测试写好了，怎么跑？我推荐用自动化测试框架。在嵌入式环境里，我常用的是 Unity 或 Ceedling。它们轻量，适合资源受限的平台。

一个典型的测试执行流程：

初始化就绪列表
按测试用例构造前置条件
执行插入/删除操作
遍历列表，验证每个节点的 prev/next 指针
验证 count 计数
验证头尾节点正确性
清理资源，准备下一个用例

关键点：每个测试用例结束后，必须把列表恢复到初始状态。否则用例之间会互相影响，你根本分不清是哪个操作引入的 bug。我早期吃过这个亏，测试报告一片红，排查了一下午才发现是上一个用例没清理干净。

4.7 常见问题与避坑指南

问题现象	可能原因	解决方法
遍历时死循环	指针未正确更新，形成环	插入/删除后立即验证指针完整性
任务丢失	删除时未更新前驱节点的 next	画链表图，逐指针检查
优先级顺序错乱	插入时未按优先级比较	插入函数中增加优先级排序断言
空列表操作崩溃	未检查 head==NULL	所有操作入口增加空列表守卫

我曾经遇到一个特别隐蔽的 bug：在中断服务函数里插入任务到就绪列表，主循环里删除。由于中断嵌套，插入操作被中断打断，导致链表指针处于不一致状态。后来我加了临界区保护，问题才解决。所以，如果你的调度器支持中断嵌套，一定要在测试用例里模拟这种并发场景。

好了，就绪列表的插入删除测试，核心就是这些。记住：指针完整性是生命线，边界条件最容易翻车。下一组测试，我们开始搞压力测试，看看调度器在高频操作下能不能扛得住。