Mini2440移植uC/OS-II笔记（一）数据结构分析

关于uC/OS-II的几个Grp、Tbl、List、FreeList、WaitList真是让人头大，于是我们开始分析：

uC/OS-II 的核心调度算法就是依赖以下5个表实现的O(1)时间复杂度的位图（Bitmap）算法。

OSMapTbl[]、OSUnMapTbl[] 、OSRdyGrp[]、OSRdyTbl[]、OSTCBPrioTbl[]

文章分为静态查找表数据展示、动态状态表结构展示、逻辑关系图和具体实例四个部分。

一、静态查找表

这两个表的内容是固定不变的，编译时就已经确定，用于加速位运算，直接查表就行了这就是Bitmap的精髓。

1.OSMapTbl[8](位映射表)

用途： 用于将 0-7 的数字转换为对应的二进制位（第 n 位置 1）。

大小： 8 字节。

2.OSUnMapTbl[256](优先级判定表)

用途： 给定一个 8 位的字节（0-255），快速找出最低位是 1 的位置（即最高优先级的位）。

大小： 256 字节。

如何查表：如果数值是0x56(即0101 0110)，找到行5x和列x6的交叉点，值为1（因为0110最低为 1 的位是 bit 1）。

二、动态状态表

这两个表（变量）是随系统运行动态变化的，记录了当前哪些任务是就绪的。

1.OSRdyGrp(就绪组)

类型： INT8U (8位变量)

作用： 这是一个行索引。如果第 i 位为 1，说明第 i 组（OSRdyTbl[i]）里有任务就绪。

2.OSRdyTbl[8](就绪表)

类型： INT8U 数组 (8个元素)

作用： 这是一个列索引。数组的每一个元素（字节）代表一组（8个）优先级。

3.OSTCBPrioTbl[64](TCB 指针表)

类型： OS_TCB * (指针数组)

作用： 一旦通过上面的表计算出了优先级数值（0-63），因为uc/os ii的优先级是唯一的，优先级就是任务ID，直接用这个优先级数值拿到对应的 OSTCBPtr 指针。

三、逻辑关系图

这5个表构成了一个完整的任务调度流程。

四、具体实例

假设系统中有一个任务，优先级为 11 (Priority 11) ，要变为就绪态，即OSTCBCur、OSPrioCur要指向它。我们需要看它如何改变这些表，以及系统如何反向找到它。

1.数据的拆分

优先级 11 的二进制是 0000 1011。uC/OS-II 将其看作 00 YYY XXX。

• Y (高3位, 组索引):001(即 1) -> 对应OSRdyTbl[1]

• X (低3位, 位索引):011(即 3) -> 对应 Bit 3

2.放入就绪表 (使用OSMapTbl)

代码逻辑：

OSRdyGrp |= OSMapTbl[1]; // OSMapTbl[1] 是 0x02 (0000 0010) OSRdyTbl[1] |= OSMapTbl[3]; // OSMapTbl[3] 是 0x08 (0000 1000)

此时表的状态：

• OSRdyGrp:0000 0010(第 1 位变 1，表示第 1 组有任务)

• OSRdyTbl[1]:0000 1000(第 3 位变 1，表示组内的 3 号偏移有任务)

3.调度器查找最高优先级 (使用OSUnMapTbl)

假设此时没有比 11 更高的优先级（即OSRdyGrp的第 0 位是 0）。

（1）找组 (Y)

查表：y = OSUnMapTbl[OSRdyGrp]，即：y = OSUnMapTbl[0x02]

查看上面的OSUnMapTbl矩阵，Index 0x02 对应的值是 1。结论：Y = 1。

（2）找位 (X)

获取该组的数据：val = OSRdyTbl[y] -> OSRdyTbl[1] -> 0x08。

查表：x = OSUnMapTbl[val]，即：x = OSUnMapTbl[0x08]

查看上面的OSUnMapTbl矩阵，Index 0x08对应的值是 3。结论：X = 3。

（3）合成优先级

Prio = (y << 3) + x即：Prio = (1 * 8) + 3 = 11

4.获取 TCB (使用OSTCBPrioTbl)

拿到 Prio = 11 后：

CurrentTask = OSTCBPrioTbl[11];

这样就拿到了优先级为 11 的任务控制块指针，可以进行上下文切换了。