任务调度基础：调度器的工作原理、调度策略分类与调度队列模型

各位同学，今天我们来聊聊任务调度最核心的那点事。说实话，调度器这东西，你把它理解成操作系统的「交通指挥中心」就对了。CPU 就一个（或者几个核心），但任务有成百上千个在排队等着跑。谁先上、谁后上、谁可以插队、谁得靠边站——这些规则，就是调度策略。

我刚开始做嵌入式系统时，总觉得调度嘛，不就是轮着来呗？结果有一次产品在现场频繁卡顿，排查了三天才发现是调度策略选错了。嗯，从那以后我再也不敢轻视这个模块了。

调度器的工作原理

调度器的工作流程，说白了就三步：选任务 → 切上下文 → 跑任务。但每一步都有讲究。

1. 就绪队列扫描：调度器从就绪队列里挑一个优先级最高（或最紧迫）的任务。
2. 上下文切换：保存当前任务的寄存器、栈指针、程序计数器，再恢复新任务的这些信息。
3. 任务执行：CPU 开始跑新任务，直到它主动让出 CPU 或被更高优先级的任务打断。

这里有个关键点——调度时机。什么时候触发调度？我归纳了三种常见情况：

• 任务主动阻塞：比如等 I/O、等信号量，任务自己说「我先歇会儿」。
• 时间片耗尽：时钟中断来了，当前任务的时间片用完了，强制换人。
• 外部事件唤醒：中断处理完后，发现有个更高优先级的任务就绪了，立马抢 CPU。

我个人习惯把调度器拆成两个模块来看：调度策略模块（决定选谁）和上下文切换模块（决定怎么换）。前者是算法问题，后者是工程问题。很多新手只盯着算法，忽略了上下文切换的开销——我见过一个项目，调度策略写得花里胡哨，结果每次切换要保存 200 多个寄存器，性能直接崩了。

调度策略分类：抢占式 vs 非抢占式

这是调度领域最基础、也最重要的二分法。你想想看，一个任务正在跑，另一个更高优先级的任务就绪了——这时候能不能打断当前任务？

特性	抢占式调度	非抢占式调度
打断条件	高优先级任务就绪时立即打断	当前任务主动让出 CPU 才切换
响应时间	可预测，实时性好	不可预测，可能被长任务阻塞
上下文切换开销	较高，可能频繁切换	较低，切换次数少
适用场景	实时系统、交互式系统	批处理系统、简单嵌入式系统
典型算法	优先级抢占、多级反馈队列	先来先服务、短作业优先

抢占式调度，说白了就是「谁急谁上」。我在做工业控制器时，电机控制任务必须每 1ms 响应一次，这时候只能用抢占式——哪怕后台在跑日志打印，电机控制信号一来，CPU 必须立刻让路。

非抢占式调度，则是「排队办事，不插队」。任务一旦开始跑，除非它自己结束或阻塞，否则没人能抢它的 CPU。这种策略实现简单，但有个致命问题——如果一个任务死循环了，整个系统就挂了。我曾经在一个低功耗传感器节点上用过非抢占式，因为任务都很短，切换开销反而成了瓶颈。

调度队列模型

调度队列，就是任务排队的地方。但实际系统里不止一个队列，而是多级队列协同工作。我画了一张图，帮你理清这个结构。

这张图展示了三个核心队列组的关系：

• 就绪队列：任务已经万事俱备，只差 CPU。通常按优先级分成多个子队列，同一优先级内用 FIFO 或轮转。
• 等待队列：任务因为等某个资源（信号量、I/O、消息）而阻塞。注意，等待队列是按事件类型分的——等 A 信号量的在一队，等 B 信号量的在另一队。
• CPU 核心：当前正在运行的任务。它可能因为时间片耗尽回到就绪队列，也可能因为主动阻塞进入等待队列。

实际工程中，队列模型还有几个变种：

• 单就绪队列：所有任务排一条队，实现简单但无法区分优先级。适合任务数少的简单系统。
• 多级就绪队列：每个优先级一条队列，调度器先看高优先级队列是否为空。这是 RTOS 的主流方案。
• 位图就绪队列：用位图标记哪些优先级有就绪任务，查找时间复杂度 O(1)。我特别喜欢这个方案——在 uC/OS-III 和 FreeRTOS 里都用到了类似思路。

调度队列的工程实现要点

光知道模型还不够，落地时有几个坑必须注意：

1. 队列操作必须是原子操作：调度器可能在中断上下文被调用，如果队列操作不加锁，数据竞争分分钟教你做人。我一般用关中断来实现临界区，简单粗暴有效。
2. 队列长度要静态分配：动态分配在调度器里是禁忌——万一分配失败，系统就挂了。我习惯在编译时就确定最大任务数，用静态数组实现队列。
3. 优先级反转要提前预防：低优先级任务占着锁，高优先级任务等锁——这时候中间优先级的任务反而能跑，导致高优先级任务被「反转」阻塞。解决方案是优先级继承或优先级天花板协议。

/* 一个简化的就绪队列实现（位图方式） */
#define MAX_PRIORITY 32

typedef struct {
    uint32_t ready_bitmap;          /* 位图，每位代表一个优先级 */
    task_t *ready_list[MAX_PRIORITY]; /* 每个优先级的任务链表头 */
} ready_queue_t;

/* 查找最高优先级的就绪任务 */
task_t *sched_find_highest(ready_queue_t *rq) {
    uint32_t highest_prio = __builtin_clz(rq->ready_bitmap);
    /* __builtin_clz 返回前导零个数，即最高优先级 */
    return rq->ready_list[highest_prio];
}

/* 将任务加入就绪队列 */
void sched_enqueue(ready_queue_t *rq, task_t *task) {
    rq->ready_bitmap |= (1U << task->priority);
    /* 将任务插入对应优先级的链表尾部 */
    list_add_tail(&rq->ready_list[task->priority], &task->list_node);
}

这段代码展示了位图就绪队列的核心逻辑。`__builtin_clz` 是 GCC 内置函数，一条指令就能找到最高优先级的任务。你想想看，如果不用位图，你得遍历整个优先级数组——32 个优先级还好，256 个优先级就有点疼了。