4. 就绪队列与调度策略：就绪队列数据结构、位图查找算法、基于优先级的抢占式调度

好，咱们今天聊点硬核的。就绪队列和调度策略，这俩东西是操作系统的“心脏起搏器”。你想想看，系统里那么多任务，谁先跑、谁后跑、谁跑一半被踹下来，全看这哥俩怎么配合。

我个人习惯把就绪队列比作“候车室”，调度器就是“检票员”。检票员得知道哪个乘客（任务）优先级高，得优先上车。而且，这个候车室不能乱，得设计得高效，不然检票员找个人都要找半天，那系统性能就完蛋了。

4.1 就绪队列的数据结构：别小看这个“数组”

在鸿蒙的轻量级内核里，就绪队列其实就是一个数组。嗯，你没听错，就是数组。但这不是普通的数组，它是个优先级位图表驱动的数组。

我见过不少初学者，一上来就想着用链表。链表当然也行，但查找和插入的时间复杂度是O(n)。在实时系统里，这太慢了。鸿蒙的做法很巧妙：它用了一个LOS_DL_LIST的双向链表数组，每个优先级对应一个链表头。

// 鸿蒙就绪队列核心结构（简化版）
#define OS_PRIORITY_QUEUE_NUM 32  // 32个优先级

typedef struct {
    LOS_DL_LIST *queue[OS_PRIORITY_QUEUE_NUM]; // 每个优先级一个链表
    UINT32      priorityBitmap;                // 32位位图，标记哪些优先级非空
} ReadyQueue;

你看，priorityBitmap这个位图是关键。它用32个bit，对应32个优先级。哪个优先级上有任务，对应的bit就置1。这样，调度器找最高优先级的就绪任务时，不用遍历整个数组，直接查位图就行。

我的经验： 我在做某个IoT项目时，任务数不多，但优先级层级很关键。当时我图省事用了链表，结果在中断频繁的场景下，调度延迟飙到了几十微秒。后来换成位图+数组，延迟直接降到个位数微秒。别小看这个优化，在实时系统里，这就是天壤之别。

4.2 位图查找算法：O(1)的奥秘

位图查找，说白了就是“找第一个1的位置”。为什么这么快？因为CPU有专门的指令支持。

在ARM Cortex-M系列上，有个CLZ指令（Count Leading Zeros），数一下前面有多少个0。比如位图值是0b0000...1000，CLZ一算，就知道最高位的1在第几位。鸿蒙内核里封装了这个操作：

// 鸿蒙位图查找核心宏
#define OS_BITMAP_FIND_FIRST_1(bitmap) \
    (31 - __builtin_clz(bitmap))       // GCC内置函数，相当于CLZ

// 实际调度时调用
UINT32 OsGetHighestPriority(VOID)
{
    return OS_BITMAP_FIND_FIRST_1(g_readyQueue.priorityBitmap);
}

这个函数返回的就是当前就绪队列中，优先级最高的那个数字。比如返回0，说明优先级0（最高）上有任务在等。整个过程就是几条指令的事，时间复杂度O(1)。

避坑指南： 我曾经在移植鸿蒙到RISC-V平台时，发现RISC-V没有CLZ指令。怎么办？只能用软件模拟。但软件模拟的位图查找，性能会差一些。后来我查了RISC-V的B扩展（位操作扩展），发现里面有CLZ指令。所以，选硬件平台时，一定要确认有没有硬件位操作支持，不然实时性会打折扣。

4.3 基于优先级的抢占式调度：谁强谁上

抢占式调度，说白了就是“后来者可以居上”。一个低优先级的任务正跑着呢，突然来了个高优先级的任务，那低优先级的就得乖乖让出CPU。

鸿蒙的调度策略很直接：优先级高的任务，永远优先执行。同优先级的任务，按时间片轮转。这个策略在实时系统里非常实用，因为紧急任务（比如中断处理、传感器数据采集）需要立刻响应。

调度发生的时机主要有三个：

  • 任务创建时：新任务如果优先级比当前任务高，立刻触发调度。
  • 任务阻塞时：当前任务因为等待信号量、队列等资源而挂起，调度器选下一个最高优先级的任务。
  • 时间片用完时：同优先级任务轮转，或者更高优先级任务就绪时。

我举个例子，你感受一下：

// 假设有三个任务
TaskA: 优先级5，执行打印 "A"
TaskB: 优先级3，执行打印 "B"  
TaskC: 优先级1，执行打印 "C"

// 调度顺序：
// 1. TaskC先跑（优先级最高）
// 2. TaskC阻塞等待消息，TaskB跑
// 3. TaskB跑一半，TaskC收到消息就绪了
// 4. 调度器立刻抢断TaskB，让TaskC继续跑
// 5. TaskC跑完，TaskB继续
// 6. TaskB跑完，TaskA跑

你看，TaskB跑得好好的，突然被TaskC抢了。这就是抢占。在鸿蒙里，这个抢断过程非常快，因为调度器只需要查位图、取链表头节点、切换上下文，一气呵成。

注意： 抢占式调度虽然响应快，但容易引发“优先级反转”问题。比如低优先级任务持有了高优先级任务需要的锁，高优先级任务反而被低优先级任务“拖住”了。鸿蒙提供了优先级继承协议来解决这个问题，后面章节我会详细讲。这里先提个醒，设计任务时一定要考虑锁的粒度。

4.4 调度器的核心流程：三步走

鸿蒙的调度器核心函数是OsSchedResched，它干的事就三步：

  1. 找最高优先级任务：调用OsGetHighestPriority，从位图里拿到优先级数字。
  2. 取任务控制块：从对应优先级的链表里，取出第一个节点（链表头就是任务控制块）。
  3. 切换上下文：保存当前任务的寄存器、栈指针，恢复新任务的寄存器、栈指针。

代码逻辑大致如下：

VOID OsSchedResched(VOID)
{
    UINT32 priority;
    LosTaskCB *newTask, *oldTask;

    // 1. 找最高优先级
    priority = OsGetHighestPriority();

    // 2. 取任务
    newTask = (LosTaskCB *)LOS_DL_LIST_ENTRY(
        g_readyQueue.queue[priority].pstNext, LosTaskCB, pendList);

    oldTask = g_runTask;

    if (newTask != oldTask) {
        // 3. 切换上下文
        OsTaskContextSwitch(oldTask, newTask);
    }
}

嗯，这里要注意，OsTaskContextSwitch是汇编实现的，因为要操作CPU寄存器。鸿蒙在ARM、RISC-V、x86上都做了适配，这部分代码是平台相关的。

我的建议： 如果你要自己写调度器，别急着优化上下文切换。先把位图查找和链表操作搞对。上下文切换的汇编代码，最好直接抄鸿蒙的，因为这里面涉及栈帧对齐、异常返回等细节，自己写容易踩坑。我刚开始写时，就因为没处理好浮点寄存器的保存，导致任务切换后浮点运算结果全乱套了。

4.5 实战中的调度策略选择

鸿蒙支持多种调度策略，但最常用的就是基于优先级的抢占式调度。什么时候用这个？我总结了几条：

场景 推荐策略 原因
传感器数据采集 高优先级抢占 数据必须及时处理，不能等
GUI界面刷新 中等优先级+时间片 需要流畅，但不紧急
后台日志写入 低优先级 可以慢慢来，别影响主业务
中断底半部处理 最高优先级 中断上下文必须快速响应

说白了，优先级就是给任务排个“紧急程度”。紧急的给高优先级，不紧急的给低优先级。但别把太多任务都设成高优先级，否则高优先级队列里一堆任务，调度器也得轮转，实时性反而下降。

我个人习惯是，系统里高优先级任务不超过3个，中优先级5-8个，剩下的全扔低优先级。这样位图查找几乎瞬间完成，调度延迟可控。

好，关于就绪队列和调度策略，今天就聊到这。记住三个核心：位图加速查找、优先级决定顺序、抢占保证实时。下一节，咱们聊聊任务同步与通信，那又是另一番天地了。

← 上一章 📖 返回目录 下一章 →