发信人: vbs (衰衰), 信区: Embedded 标 题: us/os就绪表的维护算法分析 发信站: 武汉白云黄鹤站 (2002年04月16日05:57:40 星期二), 站内信件 刚才看了一下uc/os的就绪表的维护算法，对于像uc/os这种固定优先级 和限制最大任务数的内核，uc/os所采用的算法可以说很经典了。 数据结构： OSMapTbl[8]={1,2,4,8,16,32,64,128} OSUnMapTbl[256] ；这个数组用来确定一个单字节整数中为1的最低位。 OSRdyGrp;组 OSRdyTbl[8] 就绪表 us/os用OSRdyTbl[8]来表示就绪表，其中的每一位都代表一个任务，为 1表示任务就绪，为0表示不就绪，把他理解为一个8×8的位图更容易理解。 为了更好的索引，uc/os给所有任务分组，设置了一个OSRdyGrp; 他的每一位对应于OSTdyTbl中的一个元素。 取值规则是相应元素 不为0就取1，否则取0 使任务就绪： OSRdyGrp |= OSMapTab[prio>>3]; OSRdyTbl[prio>>3] |=OSMapTbl[prio & 0x07]; 这里巧妙的利用OSMaptbl[]使得位检索变成了数组的检索了。 同时由于分组的使用，使得一个64元素表的检索变成了简单的 移位操作，不过所带来的好处并不是使任务就绪变得简单， 而是使寻找优先级最高的任务变得简单，这个在后面可以看到。 毕竟寻优先级最高的任务的操作比使任务就绪要常用得多。 删除任务： if((OSRdyTbl[prio >>3] &= ~OSMapTbl[prio &0x07])==0) OSRdyGrp &= ~OSMapTbl[prio >>3); 这个算法刚好于上面的相反。 寻找优先级最高的算法 y=OSUnMapTbl[OSRdyGrp]; x=OSUnMapTbl[OSRdyTbl[y]]; index=(y << 3) +x 因为OSUnMapTbl的引入，使得寻找OSRdyGrp和OSRdyTbl 中的为1的最低位变得很简单，变成了数组的索引。 这也是这个算法中最大的得利之处。 OSUnMapTbl的值我想不用我给了吧，大伙想想就清楚里面是什么东西了。 这样使得寻找优先级最高的任务变得容易了。 如果用其他方式实现，最差情况下要进行64次比较。 但是这一步又是任务调度中频率最高的算法了。