请选择 进入手机版 | 继续访问电脑版

EDABOSS电子论坛

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1015|回复: 0

[转帖] UcosII 就绪表的理解

[复制链接]

18

主题

0

回帖

54

E币

技术员

Rank: 2

积分
36
发表于 2017-4-1 15:32:47 | 显示全部楼层 |阅读模式
为了保证系统的实时性,在就绪表这一块,内核设计者设计了一种算法,这个算法在O(1)的时间里完成查找就绪表中最高优先级的任务(遍历就绪表来查找最高优先级的做法是不能保证实时性要求的)。关于就绪表,这里涉及到四个数据结构,分别是:OSRdyGrp、OSRdyTbl[]、OSMapTbl[]和OSUnMapTbl[]。前两者是全局变量(INT8U),OSRdyTbl[]数组的大小取决于OS_LOWEST_PRIO。后面两个数组是静态成员,其值见下面的表格和代码:

021703rbwqiy5ieeh3q7je.png


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                             


};




先把就绪表的结构图贴出来看看:


021801jn10m36rrr3kr60o.png



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


      这里主要是说明一下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[]数组,原理是一样的。代码如下:



  • if ((OSRdyTbl[prio >> 3] &= ~OSMapTbl[prio & 0x07]) == 0)
  •     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。


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


      结合代码分析一下:



  • y    = OSUnMapTbl[OSRdyGrp];
  • x    = OSUnMapTbl[OSRdyTbl[y]];
  • 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行的移位运算就可以得到最高优先级的任务的优先级了。


积分规则
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|EDABOSS电子论坛

GMT+8, 2024-3-29 19:06 , Processed in 0.043145 second(s), 23 queries .

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表