四轴飞行器DIY活动征集报名中!更有现金奉送哦~→ 立即报名 ←
电子产品世界 » 论坛首页 » 嵌入式开发 » MCU » [转帖]us/os就绪表的维护算法分析

共1条 1/1 1 跳转至

[转帖]us/os就绪表的维护算法分析

菜鸟
2002-05-17 21:27:00    评分
发信人: 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次比较。 但是这一步又是任务调度中频率最高的算法了。



关键词: 转帖     就绪     维护     算法     分析     任务    

共1条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]