uC/OS II 中就绪表的理解笔记

只看该作者 · 2015-12-14 18:13

看着OS_EXT INT8U OSMapTbl[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80} 。
突然想到当初学AVR编程的时候，要给某一组引脚设置输入输出模式的时候，用的置位方法。
这个OSMapTbl 的存在原因，不就是为了把OSRdyTbl 的元素在OSRdyGrp 对应的位置位吗？
想到一个改进的方法，其实应该可以去掉这个OSMapTbl 表。
原算法：
优先级的表已经存在了优先级为31的任务，处在OSRdyTbl[]的第3元素，所以应把OSRdyGrp的第三位置1，
此时的OSRdyGrp 的值为 0b0000 1000 = 0x08 这个值刚好是OSMapTbl[3]的值。

   那么优先级为19的任务要加入就绪表，那么19优先级处在OSRdyTbl[] 的第2元素，所以应把OSRdyGrp的第二位置1 ，
   此时的OSRdyGrp 的值为 0b0000 0100 = 0x04  这个值也刚好是OSMapTbl[2]的值。

   两个任务所在的优先级组都要在OSRdyGpr 留下状态位，所以只要把两个值进行或运算就能合并成 0b0000 1100 = 0x0C 。

我想到的改进方法那就是不查表，直接把0x01左移动 OSRdyTbl[]元素即可。
把原算法：

================================== 2014.2.15 ===================================

难得找到高清的视频，看到就绪表算法的时候，思维晃进小胡同了。。。死活理解不过来。

为巩固所得，先记下来。

UCOS-II 的优先级是值越小优先级越高最高支持64级（0-63）0优先级最高，63优先级最低。

只看该作者 · 2015-12-14 18:14

uC/OS II的就绪表结构设计的非常有意思，看看Labrosse（uC/OS II设计者）的就绪表结构设计。

任务就绪表是由一个OSRdyTbl数组表示，数组大小（OS_RDY_TBL_SIZE）由最低优先级(OS_LOWEST_PRIO)确定, 这样可以减少不必要的空间浪费，节约RAM资源。

OSRdyTbl[]是INT8U 类型数组，每一个元素占8位。每一位表示一个优先级状态（1为就绪，0则未就绪）。8个元素则可以表示64个优先级(8*8=64)。为加速就续表的查找，Labrosse把每个OSRdyTbl元素划为每一优先级组，8个元素则有8个优先级组，它定义了一个INT8U类型的8位变量OSRdyGrp ，OSRdyGrp的每一位对应每个优先级组。如下图：

假设优先级31的任务第一个加入了就绪任务表，此时OSRdyGrp和OSRdyTbl的情况：

OSRdyGrp的第3位为1，表示第3优先级组有就绪任务。

OSRdyTbl的第7位为1，表示第31优先级的任务被就绪。

此时OSRdyGrp的其他位为零，OSRdyTbl的其他元素中的位都为零

只看该作者 · 2015-12-14 18:15

现在开始分析一下算法。

定义：

复制

#define  OS_RDY_TBL_SIZE   ((OS_LOWEST_PRIO) / 8 + 1)

OS_EXT  INT8U     OSRdyGrp;                           

OS_EXT  INT8U     OSRdyTbl[OS_RDY_TBL_SIZE];

OS_EXT  INT8U        OSMapTbl[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}

先说说把指定优先级任务加入就绪表的算法。

复制

OSRdyGrp |= OSMapTbl[prio >> 3];                              // prio 表示指定的优先级  

OSRdyTbl[prio >> 3] |= OSMapTbl[prio & 0x07];

上面解释了那么多，就是为了这俩句。

先看看 prio>>3 为什么要右移三位。

UCOS-II最多支持64个优先级，即从0到63。最低的优先级为63 转换成二进制：0x00111111

刚好占6位，那么可以把6为划分为高三位和低三位，就拿上面的优先级为31任务的例子来说：

31取其高三位 31>>3 = 3 ，看，是不是刚好表示OSRdyGrp的第3位？也就是说在OSRdyTbl[3]。

31取其低三位 31&0x07 = 7，看，是不是刚好表示OSRdyTbl的第7位？也就是说在OSRdyTbl[3]的第7位。

两个组合起来：31的优先级在OSRdyTbl的第3个元素中的第7位。

这就是为什么prio >> 3 和 prio & 0x07了。

只看该作者 · 2015-12-14 18:16

得到之后如何进一步得到OSRdyGrp的值和OSRdyTbl中第3个元素的值呢？
从上图来看，OSRdyGrp的第三位置1 所以OSRdyGrp = 0b0000 1000 = 0x08  而OSRdyTbl[3]的第七位被置1 所以等于 OSRdyTbl[3] = 0b1000 0000 = 0x80 。
那么我们继续分析它的算法，剩下的算法很简单啦，就是将得到的值和OSMapTbl表对应起来。典型的用空间换时间的方法。
OSRdyGrp[31>>3] = 0x08，OSRdyGrp[31&0x07] = 0x80
刚好和我们上图看的结果一样。那既然得到了 OSRdyGrp的值和OSRdyTbl[3]那为什么不直接复制过去呢，而是要与其相| (或)，这是因为OSRdyGrp的每一位记录着每一个优先级组是否有任务就绪的状态，而OSRdyTbl的每一位都记录着每个优先级的就绪状态。如果直接赋值，则会覆盖所有的状态位，所以要用或运算来合并，这样就不会影响其他位的状态了。

举个例子：
例如优先级19的任务此时要进入就绪任务表
就绪表中已经有优先级为31的任务
那么
此时的OSRdyGrp 的值为 0b00001000 = 0x08
此时的OSRdyTbl[3]的值为 0b10000000 = 0x80
现在要将优先级为19的任务加入就绪表中
根据算法：
OSRdyGrp |= OSMapTbl[prio >> 3];
OSRdyTbl[prio >> 3] |= OSMapTbl[prio & 0x07];
一步一步来
// OSRdyGrp |= OSMapTbl[prio >> 3];
19 >> 3 = 0x02;    // 取高三位，确定在第2优先级组即 OSRdyTbl[2]
OSMapTbl[0x02] = 0x04;    // 查表得到 OSRdyGrp 的值应为 0x04 = 0b0000 0100
0x08（OSRdyGrp）| 0x04 = 0x0C; // 0b0000 1000 | 0b0000 0100 = 0b0000 1100 和原OSRdyGrp合并得到新的值 0x0C

只看该作者 · 2015-12-14 18:18

复制

// OSRdyTbl[prio >> 3] |= OSMapTbl[prio & 0x07];

19 & 0x07 = 0x03       // 取低三位，确定在OSRdyTbl[2]的第三位

OSMapTbl[0x03] = 0x08; // 查表得到OSRdyTbl[2]的值为0x08

0x00(OSRdyTbl[0x02]) | 0x08 = 0x08; // 0b0000 0000 | 0b 0000 1000 = 0x08和原OSRdyTbl[0x02]合并得到新的值 0x08

那么此时的就绪表和OSRdyGrp 的每一位状态应为：

OSRdyGrp

0

1

0

而OSRdyTbl的每一位状态应为

OSRdyTbl[0]	0	0
OSRdyTbl[1]	0	0
OSRdyTbl[2]	0	1
OSRdyTbl[3]	1	0
OSRdyTbl[4]	0	0
OSRdyTbl[5]	0	0
OSRdyTbl[6]	0	0
OSRdyTbl[7]	0	0

先写到这，现在只是明白了算法的原理，还不太理解OSRdyGrp存在的意义。

只看该作者 · 2015-12-14 18:18

看着OS_EXT  INT8U       OSMapTbl[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}  。
突然想到当初学AVR编程的时候，要给某一组引脚设置输入输出模式的时候，用的置位方法。
这个OSMapTbl 的存在原因，不就是为了把OSRdyTbl 的元素在OSRdyGrp 对应的位置位吗？
想到一个改进的方法，其实应该可以去掉这个OSMapTbl 表。
原算法：
   优先级的表已经存在了优先级为31的任务，处在OSRdyTbl[]的第3元素，所以应把OSRdyGrp的第三位置1，
此时的OSRdyGrp 的值为 0b0000 1000 = 0x08 这个值刚好是OSMapTbl[3]的值。
   那么优先级为19的任务要加入就绪表，那么19优先级处在OSRdyTbl[] 的第2元素，所以应把OSRdyGrp的第二位置1 ，
   此时的OSRdyGrp 的值为 0b0000 0100 = 0x04  这个值也刚好是OSMapTbl[2]的值。

   两个任务所在的优先级组都要在OSRdyGpr 留下状态位，所以只要把两个值进行或运算就能合并成 0b0000 1100 = 0x0C 。

我想到的改进方法那就是不查表，直接把0x01左移动 OSRdyTbl[]元素即可。
把原算法：

复制

OSRdyGrp |= OSMapTbl[prio >> 3];

OSRdyTbl[prio >> 3] |= OSMapTbl[prio & 0x07];

改成：

复制

 OSRdyGrp |= 0x01<<（prio >> 3）;

  OSRdyTbl[prio >> 3] |=  0x01<<（prio & 0x07 ）;

只看该作者 · 2015-12-14 18:19

把上述例子代入算法：
首先是优先级31 默认就绪表中没有任何任务就绪，所以OSRdyGrp为0
OSRdyGrp |= 0x01<<（31 >> 3）等于 0x00 |= 0x01<<0x03 等于 0x00 |= 0x08 最终OSRdyGrp=0x08 ;
现在看看优先级19
OSRdyGrp |= 0x01<<（19 >> 3）等于 0x08 |= 0x01<<0x02 等于 0x08 |= 0x04 最终OSRdyGrp=0x0C ;
这样就不必要这个OSMapTbl表了，这个就可以节省RAM空间了。
================================== 2014.2.18 更新 ===================

上面说的是添加任务到就绪表，接下来说说把指定任务从就绪表中删除。
下面就是uCOS-II的实现代码：

复制

if ((OSRdyTbl[prio >> 3] &= ~OSMapTbl[prio & 0x07]) == 0)   

     OSRdyGrp &= ~OSMapTbl[prio >> 3];

只看该作者 · 2015-12-14 18:21

把优先级值右移动三位（prio >> 3），就能得到该优先级在OSRdyTbl[]数组中的第几组。
而取优先级值的后三位（prio & 0x07），就能得到该优先级在OSRdyTbl[]数组中某一组的第几位。
OSRdyGrp 中的每一位都代表着OSMapTbl 的每一个元素，例如 OSRdyGrp的第2位被置1，则说明OSMapTbl[2]至少有一位被置1。
要在就绪表删除指定优先级任务，首先
1、在OSRdyTbl数组中把该优先级所在的位清0（把1改为0），
2、然后判断其所在的优先级组是否为0，为0则说明该优先级组中的优先级全都没有被设置就绪。此时就可以把该优先级组与OSRdyGrp 相对应的位清0。否则不需要更改OSrdyGrp。

按照上面的例子，就绪表中只有优先级为31和19的任务就绪。那么OSRdyGrp和OSRdyTbl数组的值如下：

复制

OSRdyGrp = 0x0C ;

OSRdyTbl[0] = 0x00;

OSRdyTbl[1] = 0x00;

OSRdyTbl[2] = 0x08;

OSRdyTbl[3] = 0x80;

OSRdyTbl[4] = 0x00;

...

OSRdyTbl[7] = 0x00;

只看该作者 · 2015-12-14 18:21

我把OSMapTbl表写出来的，计算的时候方便看：OS_EXT  INT8U OSMapTbl[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}
现在我们要把优先级为19的任务从就绪表中删除。步骤应如下：
1、
19 & 0x07 = 3 // 得到19优先级在OSRdyTbl[]数组中某一组的第3位 (此位会为1)
OSMapTbl[3]  = 0x08  // 查表得知 1字节中的第三位为1时值为0x08，OSMapTbl表主要是用来求1字节中某一位为1时，值是多少。
~0x08 = 0xF7 // 0x08 = 0b0000 1000 取反得 0b1111 0111，这步是为了给该位清零准备的。
2、
  19 >> 3= 0x02 // 得到19优先级所在的优先级组，即该优先级在OSRdyTbl[2]
OSRdyTbl[ 0x02 ] = 0x08  // 将整组值取出这一步也是为该优先级清0做准备
3、
  OSRdyTbl[ 0x02 ]  & 0xF7 // 将优先级组与指定优先级取反的值进行与运算达到将指定优先级所在的位清0又不影响其他状态位的目的。
                                             0x08 = 0b00001000 & 0b11110111 = 0x00 最终OSRdyTbl[2]=0x00
4、
   if(OSRdyTbl[2]  == 0 ) // 如果为0则需要将该优先级组与OSRdyGrp对应的状态位清0。方法如下：
   OSRdyGrp & 0xF7// 将OSRdyGrp与指定优先级取反的值进行与运算达到将指定优先级组所在的位清0而又不影响其他状态位的目的。

把上面代码简化就得到uCOSii的算法代码了：
if ((OSRdyTbl[prio >> 3] &= ~OSMapTbl[prio & 0x07]) == 0)    // 将OSRdyTbl[]的指定状态位清0并判断所在的优先级组是否为0
   OSRdyGrp &= ~OSMapTbl[prio >> 3];                // 为0则将该优先级组与OSRdyGrp对应的状态位清0

至此，在就绪表中删除指定优先级的任务的实现原理和方法已经完毕。
在就绪表中查找已经就绪的最高优先级任务的实现方法和原理只能晚上再来分析了，那个是重点中的重点啊，直接影响uCOS-ii系统内核的效率。

只看该作者 · 2015-12-14 18:22

就绪表中查找已经就绪的最高优先级任务的实现方法和原理.
实时操作相同的任务切换速度很快，每次做任务切换时，UCOS 都要找到优先级最高的任务来执行，所以从就绪表中寻找最高优先级的任务的效率直接就影响了UCOS内核的效率。

首先我们看看UCOS的算法：

复制

INT8U const OSUnMapTbl[256] = {

    0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,

    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0

};

y = OSUnMapTal[ OSRdyGrp ];                     // 取最高优先级所在的任务组

x = OSUnMapTal[OSRdyTbl[y]]                     // 取该任务组中最高的优先级

prio = (y << 3) + x;                                   // 组合计算

很简单，就三句代码。刚开始我看到这个很诧异，为什么要浪费256个字节的空间来存放这些很奇怪的数值。用个循环不就可以确定优先级了吗？原来，在实时操作系统的任何操作都必须可预知的，而循环则无法确定其执行的时间。
我们看看OSUnMapTbl[256]数组是如何出来的。
由于处于就绪状态的任务可能有多个，也就是说OSRdyGrp和 OSRdyTbl[]中有可能不止一位是被置1的。由于优先级的数字越小，优先级就越高，所以要从这些就绪的任务中找出优先级最高的任务，只需要取OSRdyGrp和OSRdyTbl[]中被置1的最低位。
过程：取OSRdyGrp中被置1的最低位y，得到最高优先级所在的任务组（即在OSRdyTbl[]的y元素），再取这个任务组中被置1的最低位x，得到最高优先级在OSRdyTbl[]所对于的位，再通过y与x的组合就得到了最高优先级。

只看该作者 · 2015-12-14 18:22

那么要解决的问题出现了，怎么去找OSRdyGrp、OSRdyTbl[]被置1的最低位呢？哈，就是上面那个很诡异的OSUnMapTbl[]表啦，不能用循环就只能查表方法了。OSRdyGrp和OSRdyTbl[]元素都占用一个字节，一个字节等于8位，2^8 = 256 种可能性，所以定义了256个字节的OSUnMapTbl[]表。
下面是依次把各种可能性写下来。
0x00 ==00000000b 最低位为1的位数为 bit0==0==OSUnMapTbl[0](其实为空，空的情况默认为0，不影响计算)
0x01 ==00000001b 最低位为1的位数为 bit0==0==OSUnMapTbl[1]
0x02 ==00000010b 最低位为1的位数为 bit1==1==OSUnMapTbl[2]
0x03 ==00000011b 最低位为1的位数为bit0==0==OSUnMapTbl[3] (有两个为1的位，bit0,bit1,取最小的，因为OSRdyGrp或OSOSRdyTbl中最小的位数对应的优先级越大)
0x04 ==00000100b 最低位为1的位数为 bit2==2==OSUnMapTbl[4]
0x05 ==00000101b 最低位为1的位数为 bit0==0==OSUnMapTbl[5]
0x06 ==00000110b 最低位为1的位数为 bit1==1==OSUnMapTbl[6]
0x07 ==00000111b 最低位为1的位数为 bit0==0==OSUnMapTbl[7]
0x08 ==00001000b 最低位为1的位数为 bit3==3==OSUnMapTbl[8]
0x09 ==00001001b 最低位为1的位数为 bit0==0==OSUnMapTbl[9]
0x0A ==00001010b 最低位为1的位数为 bit1==1==OSUnMapTbl[10]
0x0B ==00001011b 最低位为1的位数为 bit0==0==OSUnMapTbl[11]
0x0C ==00001100b 最低位为1的位数为 bit2==2==OSUnMapTbl[12]
0x0D ==00001101b 最低位为1的位数为 bit0==0==OSUnMapTbl[13]
0x0E ==00001110b 最低位为1的位数为 bit1==1==OSUnMapTbl[14]
0x0F ==00001111b 最低位为1的位数为 bit0==0==OSUnMapTbl[15]
…
…
y = OSUnMapTal[ OSRdyGrp ];