ucOSII操作系统就绪表分析

ucos-II 实时操作系统练习题

手写最简单的单片机操作系统

UC/OS-II 操作系统最高优先级任务的任务ID 计算

第一次接触ucos实时操作系统，对就绪列表的优先级的查找，一头雾水，感觉完全没必要写的如此复杂，但经过一天的查找资料与思考，哈哈，原来还是我太年轻了，原来通过查表确保了查找最高优先级的实时性(优先级的高低并不影响查表花费的时间，因为查表过程都一样，能够准确知道查表的时间)，为了方便以后回顾知识，便整理如理知识框架。

如果我们直接去查找就绪任务的最高优先级任务，那我们需要遍历这八个变量，去判断最高位是1，很显然在最坏情况下需要遍历64次，那有没有更好的方法呢，仔细观察发现一个规律，当任务优先级是8的时候，其就绪标志位在OSRdyTbl[1]中的第0位，8对应的二进制是00001000，这样00001正好是1，000正好是0，我们在看看其他是不是这样，例如7的二进制00000111，00000对应的是0，也就是OSRdy[0]，111对应7，也就是第7位，继续验证发现确实所有的优先级都满足这个规律，因此我们可以利用这一点来加快查找速度。这样我们就有如下结构：

多任务操作系统的主要工作是为系统中处于就绪状态的任务分配CPU资源，其中涉及的两个关键是：判断哪些任务处于就绪状态、确定哪个任务应该马上得到执行，即任务调度。

1. 任务就绪表
     任务就绪表记录了系统中所有处于就绪状态的任务，从代码上来看它就是一个类型为INT8U的数组OSRdyTbl[]。。系统中的任务为32个时，OSRdyTbl[]就有4个成员。每个成员占据8位，所以OSRdyTbl[]的每一个数据元素对应8个任务，这8个任务称为一个任务组。在就绪表中，以任务优先二进制位，当该位为1时表示对应的任务处于就绪状态，反之为非就绪状态。

考虑到查找效率，uCOS-II定义了一个INT8U的变量OSRdyGrp，该变量的每一位都对应OSRdyTbl[]的一个任务组(即数据的一个成员)。若某任务任务所对应的位置置为1，否则为0。

举例：OSRdyGrp=00001011，那么就意味着OSRdyTbl[0]、OSRdyTbl[1]、OSRdyTbl[3]中有就绪的任务。由图可知，uCOS-II最多可以管理8 * 8 = 64个任务。

任务就绪表是以任务的优先级从低到高排序的，那么想要根据任务的优先级来找到该任务所处于就绪表中位置就轻而易举了：

由于系统至多支持64个任务，所以优先级至多也就到63，即二进制的00111111，只占据低6位，每一个OSRdyTbl[]元素只是占据8，所以只需要用3个二进制位即可表示这8位中的哪一位为1，同理，高3位用于表示至多8个OSRdyTbl[]元素的哪一个元素。即：优先级的高3位二进制位(D5、D4、D3)指明O即：优先级的高3位二进制位(D5、D4、D3)指明OSRdyTbl[]的数组下标n，低3位(D2、D1、D0)指明OSRdyTbl[n]的哪一位数据位。另外，确定OSRdyTbl[]的下标n，也就意味着OSRdyGrp的具体数据位了。

举例：某任务的优先级prio=24，问该任务落在就绪表中的哪一位？
24的二进制位为00011000，D5、D4、D3位011，即OSRdyTbl[]的下标为3，D2、D1、D0为0，即优先级prio=24的任务在OSRdyTbl[3]的第0位。

2. 操作任务就绪表
     uCOS-II系统对任务就绪表的操作无非：登记就绪，注销就绪和从就绪表中的所有就绪任务取出最高优先级的任务的任务控制块(TCB)。

2.1 登记就绪
  当系统中的某个任务处于就绪状态时，系统会将该任务登记在任务就绪表中，即在该任务的优先级的在就绪表的对应位置1，uCOS-II的实现代码为：

OSRdyGrp    |=  ptcb->OSTCBBitY;
OSRdyTbl[y] |=  ptcb->OSTCBBitX;

ptcb->OSTCBY的值为：

#if OS_LOWEST_PRIO <= 63
ptcb->OSTCBY    = (INT8U)(prio >> 3); 
ptcb->OSTCBX    = (INT8U)(prio & 0x07);
ptcb->OSTCBBitY = (INT8U)(1 << ptcb->OSTCBY);
ptcb->OSTCBBitX = (INT8U)(1 << ptcb->OSTCBX);
//...

如上4个变量是任务与就绪表关联的关键，它们被保存在任务的控制块中(TCB)，其中ptcb->OSTCBY等于任务优先级的高3位(D5、D4、D3)，即为OSRdyGrp、OSRdyTbl[]的数组下标。ptcb->OSTCBX等于任务优先级的低3位(D2、D1、D0)。(ptcb->OSTCBBitY和ptcb->OSTCBBitX也是为查询就绪表高效而设置的)

所以”OSRdyGrp |= ptcb->OSTCBBitY”是置一OSRdyGrp对应OSRdyTbl[]下标值的位，”OSRdyTbl[ptcb->OSTCBY] |= ptcb->OSTCBBitX”是置一OSRdyTbl[]对应成员的位。

2.2 注销就绪
  注销就绪即在该任务的优先级的在就绪表的对应位清零，uCOS-II的实现代码为：

INT8U   y;
y            =  OSTCBCur->OSTCBY;
OSRdyTbl[y] &= ~OSTCBCur->OSTCBBitX;   //清零OSRdyTbl[y]对应的位
if (OSRdyTbl[y] == 0x00)                //若此时OSRdyTbl[y]已经为0，即所在就绪组已经没有任务就绪
{
    OSRdyGrp &= ~OSTCBCur->OSTCBBitY;  //将OSRdyGrp对应的位清零
}

2.3 从就绪表中查找优先级最高的任务
  找出优先级最高的任务，要实现不是很简单？只要一个循环遍历接可以了。但是uCOS-II是一个RTOS，对于RTOS来说，系统上的每一个操作所耗费的时间必须是一个常量，如果是去遍历就绪表找出目标任务，也是意味着整个操作所耗时间不一。

uCOS-II系统对目标的查找操作，基本都是采用哈希算法实现的(前面写了一篇哈希表的示例http://blog.csdn.net/qq_29344757/article/details/69855658，感兴趣者可以阅读，粗略了解哈希思想)。

INT8U   y;
y             = OSUnMapTbl[OSRdyGrp]; //最高优先级所在的任务组     
OSPrioHighRdy = (INT8U)((y << 3) + OSUnMapTbl[OSRdyTbl[y]]); //最高优先级任务所在的任务组的位

INT8U  const  OSUnMapTbl[256] = {
    0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x00 to 0x0F  */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x10 to 0x1F */
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x20 to 0x2F */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x30 to 0x3F */
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x40 to 0x4F */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x50 to 0x5F */
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x60 to 0x6F */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x70 to 0x7F */
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x80 to 0x8F */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x90 to 0x9F */
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xA0 to 0xAF */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xB0 to 0xBF */
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xC0 to 0xCF */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xD0 to 0xDF */
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xE0 to 0xEF */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0        /* 0xF0 to 0xFF */
};

找出目标任务，即找出目标任务的优先级(uCOS-II中每一个优先级对应一个任务)。

任务的优先级prio = (任务组Y) << 3 | 任务组的上哪一位X

所以要找出优先级最高的任务，分两步：
  (1) 确定任务组(OSRdyTbl[]的下标)Y：找出OSRedyGrp中为1的最低位Y
  (2) 确定任务组中的位X：找出任务组中OSRdyTbl[x]中为1的最低位X

综上，找出目标任务的核心算法在于确定某数值为1的最低位，uCOS-II的具体实现是，借助OSUnMapTbl[]数组：
  例如0x06(00000110)，为1的最低位是Bit[1]，那么OSUnMapTbl[0x06]=1；0x20(00100000)，为1的最低位是Bit[5],即OSUnMapTbl[0x20]=5。

直接通过数组的下标取值就可以取得目标值，这就是哈希算法。哈希算法虽然消耗多了点空间，但是效率大大提高，在uCOS-II中多处使用这种思想。
————————————————
ucOSII操作系统就绪表分析
uCOS-II系统中的任务就绪表
————————————————
在uCOS-ii中，经典的查找算法会转换成【针对某个8bit的字节，快速找到其为1的位】。作者的方法是非常简单粗暴的，把1个字节出现所有bit为1的值，全部遍历写一遍，了不起最多也就255个字节，但是这带来的好处是，当我们只需要使用某个byte值，直接查表，就能获取该值的第一个为1的bit，这样查找复杂度就是O(1).
————————————————