第1章：位图调度核心原理
大家好，欢迎来到《RTOS内核之位图调度算法实现》的第一章。
今天咱们聊点硬核的——位图调度。说白了，就是RTOS里怎么快速找到那个“最该跑”的任务。我做了这么多年嵌入式，见过太多调度器翻车的案例，归根结底都是“找最高优先级任务”这一步慢了。
1.1 基于优先级的抢占式调度
先说说抢占式调度。这个概念其实很简单：每个任务都有个优先级，数字越小优先级越高（或者反过来，看你怎么定义）。系统运行时，调度器时刻盯着当前所有就绪任务，一旦有更高优先级的任务出现，立马切换过去。
举个例子：你正在写一个低优先级的后台任务，突然来了个紧急的中断，唤醒了一个高优先级任务。这时候调度器会怎么做？它会毫不犹豫地把当前任务挂起，让高优先级任务先跑。这就是“抢占”的含义。
我在项目中遇到过一个问题：有个同事把两个任务的优先级设反了，结果低优先级的任务一直抢不到CPU，系统直接“假死”。嗯，这里要注意——优先级设计一定要谨慎，否则调度器再快也没用。
1.2 位图如何快速找到最高优先级任务
好，问题来了：假设系统里有32个优先级，你怎么知道当前哪个优先级有任务就绪？
最笨的办法：从优先级0开始，一个一个查。如果最高优先级是31，你得查32次。这在实时系统里是致命的——你想想看，每次调度都要花不确定的时间，这还叫“实时”吗？
位图就是来解决这个问题的。它的思路很巧妙：用一个32位的整数（比如叫ready_bitmap），每一位代表一个优先级。如果优先级3有任务就绪，就把第3位置1。
// 假设优先级0最高，优先级31最低
uint32_t ready_bitmap = 0;
// 优先级3的任务就绪
ready_bitmap |= (1 << 3);
// 优先级7的任务就绪
ready_bitmap |= (1 << 7);
// 现在 ready_bitmap 的二进制是：0b00000000_00000000_00000000_10001000
// 最高优先级是3（因为第3位是1，且比第7位更靠右？等等，这里要看你的定义）等等，这里有个细节：如果优先级0最高，那么位0就是最高位。但实际编码中，我们通常用“位0表示优先级0”，然后通过查找最低置位位（LSB）来找到最高优先级。
我个人习惯用__builtin_ctz（Count Trailing Zeros）这个内置函数。它能直接返回最低位1的位置，一条指令搞定。
// 找到最高优先级（假设优先级值越小优先级越高）
int highest_prio = __builtin_ctz(ready_bitmap);
// 如果 ready_bitmap = 0b10001000，返回3你看，原来需要循环32次的操作，现在一条指令就解决了。这就是位图的威力。
1.3 时间片轮转与位图的结合
讲完优先级调度，咱们再聊聊时间片轮转。这个机制是为了解决“同优先级任务怎么公平共享CPU”的问题。
我记得有一次做物联网网关，多个传感器采集任务优先级相同。如果没有时间片轮转，第一个任务会一直占着CPU，后面的任务永远没机会跑。这显然不合理。
时间片轮转的思路：每个任务分配一个固定时间片（比如10ms），时间到了就切换到下一个同优先级任务。但这里有个问题——怎么知道当前优先级下有哪些任务？
答案还是位图。我们可以为每个优先级维护一个就绪任务链表，然后用位图标记哪些优先级有任务。调度时：
- 用位图找到最高优先级
- 从该优先级的任务链表中取出第一个任务
- 运行一个时间片后，把任务放回链表尾部
- 重复步骤1
这样，位图负责“找优先级”，链表负责“轮转同优先级任务”，两者完美结合。
// 简化的调度循环
void scheduler(void) {
while (1) {
// 用位图找到最高优先级
int prio = __builtin_ctz(ready_bitmap);
// 从该优先级的链表中取出一个任务
task_t *task = get_next_task(prio);
// 运行任务（一个时间片）
run_task(task);
// 时间片用完，把任务放回链表尾部
put_task_back(task);
}
}1.4 位图调度的实际考量
讲到这里，你可能觉得位图调度已经完美了。但实际项目中，有几个坑要注意：
- 优先级数量限制：32位整数最多支持32个优先级。如果你需要更多，得用64位或者多个位图组合。
- 位图操作是原子的吗？在多核系统中，多个CPU可能同时修改位图，必须用原子操作或关中断保护。
- 空位图检查：如果
ready_bitmap == 0，说明没有任务就绪，这时候要跑空闲任务。
我曾经在一个项目中，因为忘记检查空位图，导致__builtin_ctz(0)返回了一个未定义值，系统直接跑飞。嗯，从那以后我每次都用if (ready_bitmap == 0) goto idle_task;来兜底。
下一章，咱们会深入代码，手把手实现一个完整的位图调度器。到时候你会看到，这些原理怎么变成实实在在的C代码。
好，今天就到这里。有什么问题，欢迎在评论区交流。