UCOSIII笔记（十六）就绪列表

🔥作者简介： 一个平凡而乐于分享的小比特，中南民族大学通信工程专业研究生，研究方向无线联邦学习 🎬擅长领域：驱动开发，嵌入式软件开发，BSP开发 ❄️作者主页：一个平凡而乐于分享的小比特的个人主页 ✨收录专栏：UCOS-III，本专栏为UCOS-III学习记录 欢迎大家点赞 👍 收藏 ⭐ 加关注哦！💖💖

UCOSIII笔记（十六）就绪列表

我们来一起深入浅出地剖析一下 uC/OS-III 内核的“心脏”之一——就绪列表。

你可以把整个 uC/OS-III 想象成一个高效的公司，而就绪列表就是公司的“任务调度中心”。这个调度中心的核心工作就是：快速找出当前最重要、最应该被执行的“员工”（任务），然后把CPU资源分配给它。

一、 什么是就绪列表？

通俗理解： 就绪列表是一个数据结构，它用来记录和管理系统中所有已经准备就绪、随时可以运行的任务。当一个任务等待的事件（比如延时、信号量、消息等）发生时，它就会被放入就绪列表。反之，当它开始等待某个事件时，就会被移出就绪列表。

核心目标： 在常数时间 O(1) 内，找出当前优先级最高的就绪任务。 这是实时操作系统的生命线。

二、 就绪列表的“三层架构”

uC/OS-III 的就绪列表的实现非常精巧，它不像一个简单的待办事项清单，而更像一个配备了高效索引系统和分组管理机制的智能任务池。它由三个核心部分构成：

1. 就绪任务位映射表 (OSRdyMap) - “部门总管”
2. 就绪任务组 (OSRdyList) - “部门员工花名册”
3. 优先级就绪表 (OSRdyTbl[]) - “部门分组清单”

下面我们通过一个公司的场景来详细解释这三者如何协同工作。

场景设定：

假设我们的公司（uC/OS-III内核）有 64 个优先级（0-63，优先级0最高，63最低），就像有64个不同等级的职位。每个优先级上只能有一个任务（一个员工）。

1. 就绪任务位映射表 - OSRdyMap (部门总管)

• 数据类型：一个 8 位或 32 位的整数（假设为 8 位，支持最多 64 个优先级）。
• 作用：这是一个宏观索引。它不关心每个优先级上具体是哪个任务，它只关心哪些优先级分组（部门）下面有就绪的任务。

我们把 64 个优先级分成 8 个组（因为 OSRdyMap 是 8 位），每组 8 个优先级。

工作方式：

• 如果某个优先级组中至少有一个任务就绪，那么 OSRdyMap 中对应的位就被置为 1。
• 如果某个优先级组中所有任务都未就绪，对应的位就被清为 0。

举例： 如果 OSRdyMap = 0b00000101（二进制），这意味着：

• 位 0 (0b0000001) 为 1：优先级 0~7 这个组里有就绪任务。
• 位 2 (0b00000100) 为 1：优先级 16~23 这个组里有就绪任务。
• 其他位为 0：其他组里没有就绪任务。

总管的工作：调度器一来，总管 (OSRdyMap) 看一眼就知道该去哪个组（比如 0~7 组）找最高优先级的任务，因为它从位 0 开始找，找到的第一个 ‘1’ 就是最高优先级的组。

2. 优先级就绪表 - OSRdyTbl[] (部门分组清单)

• 数据类型：一个数组，元素是 8 位整数。OSRdyTbl[8]（对应 8 个组）。
• 作用：这是中观索引。它记录了每个优先级组内，具体是哪些优先级上有就绪任务。

每个数组元素 (OSRdyTbl[i]) 对应 OSRdyMap 的一个位，管理 8 个优先级。

工作方式： OSRdyTbl[i] 中的每一位代表该组内的一个优先级。

• 位 0 对应组内最高优先级（如 OSRdyTbl[0] 的位 0 对应优先级 0）。
• 位 7 对应组内最低优先级（如 OSRdyTbl[0] 的位 7 对应优先级 7）。
• 如果某个优先级上有就绪任务，OSRdyTbl[i] 中对应的位就被置 1。

接上例： OSRdyMap = 0b00000101，我们知道 0~7 组和 16~23 组有任务。

• 查看 OSRdyTbl[0] (管理0~7组)，假设其值为 0b00100010。这意味着：
  • 优先级 1 (位1) 上有就绪任务。
  • 优先级 5 (位5) 上有就绪任务。
• 查看 OSRdyTbl[2] (管理16~23组)，假设其值为 0b10000000。这意味着：
  • 优先级 23 (位7) 上有就绪任务。

清单的工作：现在调度器知道了，在最高优先级的组(0~7)里，具体是优先级1和优先级5上有任务。

3. 就绪任务组 - OSRdyList[] (部门员工花名册)

• 数据类型：一个结构体数组，每个元素对应一个优先级。OSRdyList[64]。
• 作用：这是微观管理。它通过一个双向链表，管理着同一个优先级下所有就绪的任务。这是 uC/OS-III 支持时间片轮转调度的基础。

结构体成员通常包括：

• HeadPtr：指向该优先级就绪链表头任务的指针。
• TailPtr：指向该优先级就绪链表尾任务的指针。
• NbrEntries：该链表中当前有多少个任务。

工作方式：

• 当多个任务处于同一优先级时，它们会被链接到这个优先级的 OSRdyList 链表中。
• 调度时，从链表的头部取出任务来执行。
• 如果启用了时间片轮转，当任务的时间片用完后，它会被移到链表的尾部，下一个任务（链表的头）开始执行，从而实现同一优先级任务的轮流执行。

接上例：

• OSRdyList[1] 这个链表里，可能只有一个任务（比如 Task_A）。
• OSRdyList[5] 这个链表里，可能有三个任务（Task_B, Task_C, Task_D），它们正在以时间片轮转的方式共享 CPU。

4、 优先级的概念与规则

1. 优先级数值

• uC/OS-III 中，优先级使用 数字 表示。
• 数字越小，优先级越高。这是一个关键点！
  • 优先级 0：最高优先级（像是公司CEO）
  • 优先级 1：次高优先级
  • …
  • 优先级 OS_CFG_MAX_PRIO-1：最低优先级（通常是空闲任务）

2. 优先级数量

• 优先级数量在 os_cfg.h 中通过 OS_CFG_MAX_PRIO 进行配置。通常可以是 8, 16, 32, 64, … 最高可达 256 级（但常用 64 级）。
• 优先级 0 和 OS_CFG_MAX_PRIO-1 通常被系统占用：
  • 优先级 0：通常分配给 中断服务管理任务 (OS_IntQTask)，用于处理中断延迟发布，它拥有至高无上的权力。
  • 最低优先级：通常分配给 空闲任务 (OS_IdleTask)，当所有其他任务都无事可做时，它来“摸鱼”，消耗 CPU 时间。

下图展示了 uC/OS-III 中典型的优先级布局：

在这里插入图片描述

三、 三者如何协同工作？—— 调度过程全景图

现在，让我们把“调度中心”的整个工作流程串起来，看看当调度器需要寻找最高优先级任务时发生了什么：

在这里插入图片描述

举例：寻找最高优先级任务

1. 查询总管 (OSRdyMap)：
   • 当前值：0b00000101
   • 从右向左（从低到高）找到第一个为 1 的位是 位0。所以，最高优先级组是 第0组 (优先级 0~7)。
2. 查询清单 (OSRdyTbl[0])：
   • 当前值：0b00100010
   • 从右向左找到第一个为 1 的位是 位1。
   • 计算具体优先级：P = 0 * 8 + 1 = 1。所以，当前最高就绪优先级是 1。
3. 查询花名册 (OSRdyList[1])：
   • 查看该优先级下的链表。
   • 因为优先级1是最高优先级，通常一个系统不会让多个任务共享最高优先级，所以这里很可能只有一个任务。
   • 调度器直接取出 OSRdyList[1].HeadPtr 所指向的任务控制块 (TCB)。
4. 执行：
   • CPU 开始执行这个优先级为 1 的任务。

整个过程通过查表和一两条位运算指令完成，速度极快，是严格的 O(1) 时间复杂度！

四、 核心操作与场景对比

为了让理解更深刻，我们来看两个核心操作：

场景 1：任务从等待变为就绪（例如，延时结束）

假设任务 Task_Player (优先级 20) 的延时时间到了。

1. 计算组和位：
   • 组 Y = 20 / 8 = 2
   • 组内位 X = 20 % 8 = 4
2. 更新就绪表：
   • 将 OSRdyTbl[2] 的第 4 位置 1。
   • 由于 OSRdyTbl[2] 从 0 变成了非 0，所以将 OSRdyMap 的第 2 位置 1。
3. 更新就绪列表：
   • 将 Task_Player 的 TCB 插入到 OSRdyList[20] 链表的尾部。

场景 2：任务从就绪变为等待（例如，请求信号量）

假设任务 Task_Network (优先级 15) 请求一个信号量，但信号量不可用，任务需要挂起等待。

1. 计算组和位：
   • 组 Y = 15 / 8 = 1
   • 组内位 X = 15 % 8 = 7
2. 更新就绪列表：
   • 将 Task_Network 的 TCB 从 OSRdyList[15] 链表中移除。
3. 更新就绪表：
   • 如果 OSRdyList[15] 链表现在为空（NbrEntries == 0），则将 OSRdyTbl[1] 的第 7 位置 0。
   • 如果 OSRdyTbl[1] 现在变成了 0（整个组都没有就绪任务了），则将 OSRdyMap 的第 1 位置 0。

五、 总结对比表格

三者关系总结：

• OSRdyMap 和 OSRdyTbl[] 共同构成了一个两级位图索引系统，用于在常数时间内锁定最高就绪优先级。
• OSRdyList[] 则是在确定优先级后，管理该优先级下多个任务的详细清单，为时间片轮转调度提供了基础设施。

通过这种精妙的分层设计，uC/OS-III 的就绪列表完美地平衡了调度速度和功能灵活性，成为其稳定高效运行的坚实基石。