标签： OS

UcosII 就绪表的理解

为了保证系统的实时性，在就绪表这一块，内核设计者设计了一种算法，这个算法在O(1)的时间里完成查找就绪表中最高优先级的任务（遍历就绪表来查找最高优先级的做法是不能保证实时性要求的）。关于就绪表，这里涉及到四个数据结构，分别是：OSRdyGrp、OSRdyTbl[]、OSMapTbl[]和OSUnMapTbl[]。前两者是全局变量（INT8U），OSRdyTbl[]数组的大小取决于OS_LOWEST_PRIO。后面两个数组是静态成员，其值见下面的表格和代码：


 


OSMapTbl[]的下标

 


OSMapTbl[]（即位掩码）

 


0

 


00000001

 


1

 


00000010

 


2

 


00000100

 


3

 


00001000

 


4

 


00010000

 


5

 


00100000

 


6

 


01000000

 


7

 


10000000

 

 

 

  

 

INT8U  const  OSUnMapTbl[] = {

 

    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就绪表 - 灰太狼 - 嵌入式開發學習

 

至于这个就绪表是怎么构成的，为什么是8×8表格，这里就不浪费宝贵的网络资源了，任何一本书上都说得我比清楚。

 

      这里主要是说明一下OSMapTbl[]和OSUnMapTbl[]这两个数组的值是怎么得来的，以及对进入、脱离就绪态代码和找出最高优先级任务代码的理解。

 

      一、OSMapTbl[]数组。

 

      这个数组出现的目的是为了更方便的置位。说白点，使用OSMapTbl[index]的作用是更方便的把某个数值的第index位置1。比如：使任务进入就绪态的代码是：

 

OSRdyGrp  |= OSMapTbl[prio>>3];                   （1）

 

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

 

先取prio（任务优先级）的“高三位”（这里的高三位是指不考虑prio的最高两位，剩下的六位中的高三位），“高三位”是OSRdyGrp的索引，就是说：“高三位”的值（0到7）指定OSRdyGrp（8位）中某一位置位，比如，“高三位”是111，即7，这样就把OSRdyGrp的第7位置1。再看代码（1），先通过prio>>3确定OSRdyGrp的哪一位应该置1（比如第7位），然后通过OSMapTbl[]表把这一位置1，其他位为0（比如OSMapTbl[7]=10000000），再通过位或操作就可以把OSRdyGrp的相应位（第7位）置1了。代码（2）是同样的道理。这里就说明了OSMapTbl[]数组的用处了。

 

      使任务脱离就绪态要对某些位进行清0操作，这里也要用到OSMapTbl[]数组，原理是一样的。代码如下：



  1. if ((OSRdyTbl[prio >> 3] &= ~OSMapTbl[prio & 0x07]) == 0)    
  2.     OSRdyGrp &= ~OSMapTbl[prio >> 3];   

 

 

 

第一行先对OSRdyTbl[]中某数据的某一位清0，然后进行判断，如果OSRdyTbl[]中这个数据为0（也主相当于这个数据的所有8位都已经清0了），再对OSRdyGrp的某位清0。

 

      二、OSUnMapTbl[]数组

 

       OSUnMapTbl[]数组主要是用于找出进入就绪态的优先级最高的任务。而这个地方也是我一开始没搞明白的，不明白OSUnMapTbl[]中的数值是怎么来的。

 

      先脱离所有上下文关系来说说OSUnMapTbl[]的一般意义。这里用二进制比较方便说明问题。OSUnMapTbl[]共0xFF个元素，0x00~0xFF为索引，而OSUnMapTbl[]里的值就是通过分析索引得到的。比如说，索引0x50, 二进制表示为0101 0000,然后从右边数，看第几位首先为1，则OSUnMapTbl[0x50]的值就为几。易知，0101 0000从右起，第4位首先为1，所以有OSUnMapTbl[0x50]=4。再比如0x51，二进制为0101 0001，右起第0位为1，所以OSUnMapTbl[0x51]=0。

 

      那为什么要从右数起呢？这个和优先级表有关系，优先级的值越小，优先级就越高。再看上面那幅优先级的结构图，可见，优先级是从右至左，从上至下越来越低的，最低优先级给了空闲任务。

 

      结合代码分析一下：



  1. y    = OSUnMapTbl[OSRdyGrp];    
  2. x    = OSUnMapTbl[OSRdyTbl[y]];    
  3. prio = (y << 3) + x;   

 

 

 

      x、y的含义看上面的图就知道了：y是“高三位”，x是“低三位”。

 

      找最高优先级任务的过程是这样的：首先，查OSRdyGrp，看OSRdyGrp中右起的第几位首先为1，比如OSRdyGrp=0x56，0x56的二进制为0101 0110,可见右起第1位首先为1，所以y=OSUnMapTbl[0x56]=1，然后再去OSRdyTbl[y]即OSRdyTbl[1]中查找（为什么是OSRdyTbl[y]，这个书上说得很明确，这个得清楚得了解OSRdyGrp和OSRdyTbl[]之间的关系），这里假设OSRdyTbl[1]=0xD4，即1101 0100，同样找到OSRdyTbl[1]中右起的第2位首先为1，这样得到x=2，再通过第3行的移位运算就可以得到最高优先级的任务的优先级了。
转自：http://blog.sina.com.cn/s/blog_9f14969901011t53.html

关于《orange‘s一个操作系统的实现》中调用门部分的补充和纠正

在《orange‘s一个操作系统的实现》中书对调用门中参数复制一点一略而过，并没有对参数大小等做出解释！上网找了很久发现并没有太多这方面的描述于是自已动手实验了一下并查了80386指令手册得出如下结论：

经过实验发现：如果调用门是向32位代码段跳转时，那么调用门在用param count复制时以一个参数为双字大小进得复制，也是就要复制的参数大小为（param count)*4字节，如果调用门是向16位代码段跳转时，那么调用门在用param count复制时以一个参数为单字大小进得复制，也是就要复制的参数大小为（param count)*2字节。那么什么时候向32位代码段中跳转，什么时候向16位代码段中跳呢？这关系到门描述符中TYPE字段中的内容，如果TYPE字段的值为4则为16位门描述符用来向16位代码跳转，如果TYPE字段的值为c时则为32位门描述符，用来向32位代码段跳转！

在指令返回时本书中那副堆栈示意图旁边那段代码疑似有错误，因为RET 中的参数应与调用门中的（param count）就该是对应关系，也就是说如果是16位调用门跳转时返回时应用retf／ret  (param count)*2来返回，如果是32位调用门跳转时返回时就用retf／ret  (param count)*4，这样堆栈才能平衡！但那一小段代码竟用ret 3！

以下为参考资料和实验代码：


Changing Size of Call
When adding 32-bit gates to 16-bit procedures, it is important to consider
the number of parameters. The count field of the gate descriptor specifies
the size of the parameter string to copy from the current stack to the stack
of the more privileged procedure. The count field of a 16-bit gate specifies
the number of words to be copied, whereas the count field of a 32-bit gate
specifies the number of doublewords to be copied; therefore, the 16-bit
procedure must use an even number of words as parameters.

There are three ways to cause a 16-bit procedure to execute a 32-bit call:
1. Use a 16-bit call to a 32-bit interface procedure that then uses a
  32-bit call to invoke the intended target.
2. Bind the 16-bit call to a 32-bit call gate.
3. Modify the 16-bit procedure, inserting an operand-size prefix before
  the call, thereby changing it to a 32-bit call.
Likewise, there are three ways to cause a 32-bit procedure to execute a
16-bit call:
1.
Use a 32-bit call to a 32-bit interface procedure that then uses a
16-bit call to invoke the intended target.

 

2. Bind the 32-bit call to a 16-bit call gate.
3. Modify the 32-bit procedure, inserting an operand-size prefix before
  the call, thereby changing it to a 16-bit call. (Be certain that the
 return offset does not exceed 64K.)
Programmers can utilize any of the preceding methods to make a CALL in a
USE16 segment match the corresponding RET in a USE32 segment, or to make a
CALL in a USE32 segment match the corresponding RET in a USE16 segment.


以下为代码：

代码：