uCOS II 之查找最高优先级任务

我们知道在u/COS II中，一个任务只有一个优先级，并且这个优先级在整个系统是唯一的，也就是一个任务也是对应一个优先级。优先级即任务，任务即优先级。我们只需通过优先级就可以找到所有和该任务相关的资源。现在问题是就绪表中有那么多任务处于就绪态，如何从中找到其中最高优先级。方法有很多，其中一个就是for循环找优先级，遍历所有就绪表，从中找到最高优先级，但这里有一个问题，如果就绪表中处于就绪的这个优先级比较低，那么搜索时间肯定比在高优先级的情况下搜索时间长，这就不符合系统运行时间是确定的要求。所以 u/COS II 采用了空间换时间的方法，事先将一个字节的所有情况记录下来，然后从中找就行了。这就是OSUnMapTbl[256]。

INT8U const OSUnMapTbl[256]={
0u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x00to0x0F*/
4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x10to0x1F*/
5u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x20to0x2F*/
4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x30to0x3F*/
6u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x40to0x4F*/
4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x50to0x5F*/
5u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x60to0x6F*/
4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x70to0x7F*/
7u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x80to0x8F*/
4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x90to0x9F*/
5u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0xA0to0xAF*/
4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0xB0to0xBF*/
6u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0xC0to0xCF*/
4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0xD0to0xDF*/
5u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0xE0to0xEF*/
4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u /*0xF0to0xFF*/
};

这张表的功能只有一个，就是记录一个字节中哪一bit先置1（从右往左数），比如一个字节是0x21，二进制表示 0010 0001 b，那好，就用这个值作为查表的索引。OSUnMapTbl[0x21]就是0，也就是bit 0位先置1，不信，自己查去。我们不禁会想，需要查表吗，这不是很明显的是吗，直接看二进制就知道了啊，但是机器没我们聪明，他可没有办法进行图像处理，所以只好采用这种办法笨办法找了（在CM3中有一条指令可以实现找前导0的，这样就能最少节省256字节空间了，为啥是256,一个字节8位，每位两种可能，0、1，256字节包含了所有可能）。现在我们看在8*8的就绪表如何进行查找。

INT8U   y;
y = OSUnMapTbl[OSRdyGrp];
OSPrioHighRdy = (INT8U)((y << 3u) + OSUnMapTbl[OSRdyTbl[y]]);

是不是很清爽，执行时间也是确定的，符合要求。
这里有一个局部变量y，还有之前讲的就绪组变量OSRdyGrp。在每一次就绪表操作后，也会同步更新OSRdyGrp。这里记录了一个组中是否有任务处于就绪，只要有就绪任务，相应位置置1。操作后如果发下该组值为0 ，也就是该组没有任务，就会将OSRdyGrp相应bit位清零。

从 OSRdyGrp = 0x69值可以发现组号 0、3、5、6 共四组有任务处于就绪态，但是每一组有多少任务处于就绪态不确定，但是该组最少有一个任务处于就绪态（结合就绪表理解）。现在需要确定这些组的最高优先级组（先确定组号是最小，如果组号是最小，那么这个组计算出的优先级肯定比其他组优先级高），就绪组值为 0110 1001b，十六进制 69H，十进制表示 105,可根据十进制在 OSUnMapTbl 找到索引值 105 的值为 0（从 0 开始计数）， 也就是说最高优先级为 0 组，也可根据十六进制，高 4 位是 6，从 OSUnMapTbl 表找 6 行(0x60 to 0x6F),低 4 位是 9，找 9 列（从 0 开始计数），也可以从表中看出值为 0 ，而事实上由于 bit 0 置 1，所以最高优先级组肯定是 0 组，由此我们可以从表中观察出只要是奇数，最高优先级组肯定是 0 组，因为它的最低位肯定置 1，即奇数，即 0 组有任务处于就绪态。既然 0 组有就绪态，那么不管还有哪些组处于就绪，都不可能比 0 组更高优先（0 组是最高优先组），所以只要是奇数，最高优先级组都是 0 组，即表中的值为 0。 在得到最高优先组的基础上通过 OSUnMapTbl 获得该组的最高优先级任务。同理，也是通过该索引表获得一个字节的最先置 1 的位置，可以获得一个任务优先级的列号，再和之前的组号组合，就可唯一确定一个任务，并且因为组号也是最高优先组，所以该任务的优先级是所有就绪态任务中的最高优先级。

我们再简单看一下16*16位就绪表的情况：

if ((OSRdyGrp & 0xFFu) != 0u) {
   y = OSUnMapTbl[OSRdyGrp & 0xFFu];//组号  0 < y < 7
} else {  
   y = OSUnMapTbl[(OS_PRIO)(OSRdyGrp >> 8u) & 0xFFu] + 8u; //组号  8 < y < 15，
}
ptbl = &OSRdyTbl[y]; //获得该组的所有就绪任务列号
if ((*ptbl & 0xFFu) != 0u) {
OSPrioHighRdy = (INT8U)((y << 4u) + OSUnMapTbl[(*ptbl & 0xFFu)]); //每一组 16 个任务，所以 *16
} else {//列号 8 < y < 15，再和组号进行组合
  OSPrioHighRdy = (INT8U)((y << 4u) + OSUnMapTbl[(OS_PRIO)(*ptbl >> 8u) & 0xFFu]+ 8u);
}

因为变量位数不一样，更重要的是为了节省空间（如果是16 位变量，直接按索引值得话需要 65536 个字节空间大小），所以采用判断方式节省了空间，使 256 个字节就可以获得需要的组号，效率上只比直接索引多了一个判断时间，可以说是非常划算的。可以看到它首先判断低 8 位情况，如果存在就绪组，就从中获得最高优先组，高 8 位就可以不管了，因为运算目标只有一个，就是从所有就绪组中获得一个最高就绪组，既然最低 8 位有就绪组，那最高就绪组肯定就在其中，不可能在高 8 位；如果不在低 8 位，那就继续找高 8 位，因为已经确定了不在低 8 位，即不可能是 0-7 组，所以需要进行偏移，偏移值为 8，所以如果最高 8 位有 bit 置 1，肯定是 8 < y < 15。这样就获得了一个16 位变量的所有可能置 1 的位置。需要说明一点的是因为就绪表一行有 16 个任务，所以组号需要 *16，采用位运算效率更高，这里右移 4 位即 *16。注意位运算不能乱用，否则会导致错误。

总结：该表用于确定一个字节的最先置 1 的位置，如果 OSRdyGrp 所有位都没置 1，说明没有就绪态任务，但是这种情况在 UCOS II 中不会出现，因为必定有系统任务处于就绪态。利用该思想，我们为了节省空间，也可以做成 4*4 的索引表，但这样会影响效率，如果任务数少又想节省空间的话可以修改该表。

关注公众号，方便手机接收最新文章。

今天的文章uCOS II 之查找最高优先级任务分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。