分类： 嵌入式
2014-02-27 10:09:42
UCOS优先级调度算法
经过一个上午时间，终于明白UCOS系统的按优先级调度就绪任务的算法，以个人见解展示给各位，希望各位提出意见uponzw630@163.com。
首先说明，解释两个表格的含义。
说明
OSMapTbl就是0-7这8个数值用二进制的BIT位来表示。
OSUnMapTbl就是将0x00-0xff每个数据中最低位为1的位号全部列举出来
INT8U const OSMapTbl[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};
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*/
};
优先级变量prio，可以表示为8个比特，如下表：
|
0 |
0 |
Y |
Y |
Y |
X |
X |
X |
Y处于BIT5-BIT3，X处于BIT2-BIT0。
我们知道优先级prio的值越小，prio的优先级越高。
X和Y的范围均为000-111，十进制数里0-7，更8个级别，为了判断X或Y的大小，我们就引入了表格OSMapTbl[]= {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};分别用来表示0-7优先级的值，这是为了方便找到最高优先级。
在使用中，OSRdyGrp表示y，OSRdyTbl[y]表示X。
OSRdyGrp 按BIT位可以表示为第0组-第7组优先级
OSRdyTbl[n] 可以表示为第n组的8个优先级
任务就绪算法：
OSRdyGrp |= OSMapTbl[prio>>3]；
OSRdyTbl[prio>>3] |= OSMapTbl[prio&0x07]；
例如：prio为5，二进制为0b0000 0101，得到Y为0，X为5，再把这两个数据经过查表OSMapTbl[]，最终得到OSRdyGrp为0x01，OSRdyTbl[0] 为0x20；
查询就绪算法：
Y=OSUnMapTbl[OSRdyGrp];
X=OSUnMapTbl[OSRdyTbl[y]];
Prio = (y<<3 )+ x；
验算：如OSRdyGrp为0x01，OSRdyTbl[0] 为0x20，经过查询就绪算法后
Y=0；X=5；
最终prio = (0<<3)+5=5；这样就优先级反向算法就完成了。
各位看官可以自己举例，进行验证。
多个优先级如何查找最高优先级
OSRdyGrp和OSRdyTbl[]中存了许多优先级，但是我们现在要做的是找出其中的最高优先级，我们先找出里面对应存了多少优先级。
如现在就绪的优先级有以下6个，prio = 1，3，4，13，16，20这6个优先级存于OSRdyGrp和OSRdyTbl[]中具体数值分别为多少。
Prio为1，Y=0，x=1经查表OSMapTbl[]，得OSRdyGrp为0x01，OSRdyTbl[0] 为0x02；
Prio为3，Y=0，x=3经查表OSMapTbl[]，得OSRdyGrp为0x01，OSRdyTbl[0] 为0x08；
Prio为4，Y=0，x=4经查表OSMapTbl[]，得OSRdyGrp为0x01，OSRdyTbl[0] 为0x10；
Prio为16，Y=1，x=5经查表OSMapTbl[]，得OSRdyGrp为0x02，OSRdyTbl[2] 为0x20；
Prio为16，Y=2，x=0经查表OSMapTbl[]，得OSRdyGrp为0x04，OSRdyTbl[2] 为0x01；
Prio为20，Y=2，x=4经查表OSMapTbl[]，得OSRdyGrp为0x04，OSRdyTbl[2] 为0x10；
用运算符“或”结果为
OSRdyGrp = 0x07；//0b00000111
OSRdyTbl[0] = 0x1a；//0b00011010
OSRdyTbl[1] = 0x20；//0b00100000
OSRdyTbl[2] = 0x11；//0b00010001
再通过上面任务就绪算法，显然OSRdyGrp为1的最低位为bit0，所以最高优先级在第0组（优先级实际数值0-7），我们就要查OSRdyTbl[0]为1的最低位为bit1，所以就可以得到其中最高优先级为优先级1。
众所周知，时间对于一个系统而言是非常重要的，UCOS为了节约在任务调度时，按优先级算法的时间，只有短短几行指令移位和查表，就可以完成最高级任务的就绪和调度，挺佩服写出这个算法作者。
