【Java】优先级位图算法详解
优先级位图算法详解
码之泪殇发布于 今天 07:04
1、μC/OS-II任务优先级相关简介:μC/OS-II中共有64个优先级(0~63级,数字越小优先级越高)。因为是实时系统,所以对应每个任务就分配一个优先级。
2、2进制和10进制转换基础
这里先介绍一个数学知识,二进制如何变为十进制,比如十进制26,其8位二进制表示为:00 011 010
。当十进制为0~63时,前两位无作用,所以只看后6位——011 010
.怎么计算成十进制呢?很简单:把这个十进制数,分为两个部分,高三位和低三位,这个十进制数的大小就等于高三位的十进制8+低三位的十进制数(其实就是二进制转八进制再转十进制)。高三位的011=3
,低三位的010=2
,所以26=3x8+2=(011)<<3+(010).即将高三位左移三位
就是8再加上低三位。下面要介绍的算法也是这个数学方法。
3、优先级任务调度过程
- 创建任务并分配优先级
- 通过算法,操作系统对创建完成的任务(即
就绪任务
)进行标记。并通过标记来查找当中任务中优先级最高的任务 - 调用调度函数进行调度,让最高优先级任务运行
优先级创建
μC/OS-II中创建任务的函数原型: INT8U OSTASKCeate(void (*task)(void *pd),void *pdata,os_stk *ptos,INT8U prio)
,从这个函数可以看出,最后一个参数就是优先级,所以结论是,在创建任务的同时就要确定任务的优先级,并且是该优先级是8位的(0~2^8-1),这里也可以看出为什么会有64个优先级。
任务优先级的标定
什么是优先级的标定:就是操作系统要知道哪个任务已经就绪了,然后就在这些就绪了的任务里面切换调度。所以第一步就是要知道哪些任务就绪了,然后就可以操作了。
这里要先介绍两个数据结构,:OSRdyGrp、OSRdyTbl[]
,这两个变量协同完成优先级的标定。OSRdyGrp
:优先级就绪组
这是一个8位的变量。每一个变量对应于OSRdyTbl[]中的一行(实际上是一个元素,但也可以理解为一行)。OSRdyTbl[]
:优先级就绪表
这是一个数组,有8个成员,每个成员都是8位的变量,所以就可以构成了8*8的矩阵了。所以64个优先级都是标定在这个数组中的。
那到底怎么往空格里置1的呢? 这里就要分析这个优先级就绪表了
:
1.这个表的数据结构是数组,也就是说,这个数组有8个成员,每个成员都是8位的变量。
2.通过二级查找实现对就绪任务的标定的。这里可以理解为一个矩阵,找某个数,肯定是先找行,再找列。从而找到这个元素位置。思想就是这个。
怎么找行呢?这里的一个变量OSRdyGrp,是一个8位的变量。每一位对应上图的一行,当某一位置1时,就表明就绪表对应的行有就绪任务,然后再查找列,就可以找到哪个任务就绪了。现在举个列子来说明:
创建一个任务,它的优先级为 prio=11(这是用户指定的),此优先级用二进制表示(8位):最前面两位无用处,前面已说过 00 001 011
。那么怎么在对应的OSRdyTbl[]优先级就绪表中进行标定呢?
- 把这个二进制数分为两个部分:高3位 (001)和低3位(011);
- 高三位负责找到数组中的行,低三位负责找到数组中的列(其实这里不是列,是一个变量的8个位,也可以按列理解),这样配合就可以寻址,往相应数字标号里写1。
对上面这个数来说 001 =1说明是第1行(数组从0行开始),011=3说明在第3个位置要写入1,合在一起就是第一行的第三个位置写入1
,这样就完成了对应数字优先级标号的标记。
那从上面的思路来看,我们只要知道数组中的第几行和第几列的值就可以了,所以又引进了一个映射数组
: OSMapTbl[]
,其具体内容如下。下标0对应的就是0位为1,下标1对应的就是1位为1,然后把这个数赋值给OSRdyGrp优先级就绪组。则OSRdyGrp哪个位为1则说明就是就绪表哪个行有就绪任务了。这样做的好处就是快。这也就是这个数组就是个映射数组,方便操作而已。
下标 | 二进制值 |
---|---|
0 | 00000001 |
1 | 00000010 |
2 | 00000100 |
3 | 00001000 |
4 | 00010000 |
5 | 00100000 |
6 | 01000000 |
7 | 10000000 |
至此,以上涉及3个数据结构了,现在来总结一下:
1.OSRdyGrp
优先级就绪组:第几位被置1,就说明就绪表中第几行有就绪任务。比如OSRdyGrp=0000 0001
。说明OSRdyTbl[0]
行有就绪任务。具体是这行的哪个列还要根据低三位
的值来决定.
2.OSRdyTbl[]
优先级就绪表:行+列就能标定就绪任务的优先级.
OSMapTbl[]
优先级映射表:用来方便生成第几行,第几列的一个转换.
<font color='red'>下面来看ucos中的源码怎么实现的:</font>
任务就绪源码如下:
OSRdyGrp |= OSMapTbl[prio>>3];OSRdyTbl[prio>>3] |= OSMapTbl[prio&0x07];
代码解释:prio>>3是获取优先级的高3位
,prio&0x07是获取优先级的低3位
。然后在通过OSMapTbl的映射分别获得了就绪表中的行和就绪表中的列, 然后查询就绪算法:
y = OSUnMapTbl[OSRdyGrp];x = OSUnMapTbl[OSRdyTbl[y]];
prio = (y << 3) + x;
举个例子:
创建一个任务,且prio=11=001 011
的情况分析:高3位
:001=1
通过OSMapTbl
映射后,OSRdyGrp=0000 0010,即是就绪表中第1行有任务就绪。低3位
:011=3,通过OSMapTbl
映射后
//低三位的映射OSMapTbl[prio&0x07] = OSMapTbl[3] = 0000 1000;
OSRdyTbl[prio>>3] = OSRdyTbl[1] = 0000 1000;
通过这句代码就往就绪表第一行(从OSRdyTbl[1]看到)第3个位置(从右往左看0000 1000,第一个为1的位,0开始)写入1,表明该任务就绪了。
这样就完成了单个任务优先级的标定。
多任务优先级设定
这里引入一个表格:优先级判定表OSUnMapTbl[]
,这个表的作用是为了节省时间,这样查表的话,耗的时间是一定的,很好的满足了实时性。下面来分析这个表的作用。
1.先看最旁边的注释,说明的是该数组中对应的位置。
2.解释这个数组中内容,这些数字怎么来的。
例子 :
有4个任务 ,优先级分别为6,10,11,17.。把上面就绪任务算法再贴一遍:前面2位不管。
6对应二进制:000 110高3位:000=0 通过OSMapTbl映射后,
OSMapTbl[prio>>3]= OSMapTbl[0]=0000 0001
低3位:110=6,通过OSMapTbl映射后
OSMapTbl[6]=0100 0000
OSRdyTbl[prio>>3]= OSRdyTbl[0]=0100 0000
10对应二进制:001 010高3位:001=1 通过OSMapTbl映射后,
OSMapTbl[prio>>3]= OSMapTbl[1]=0000 0010.
低3位:010=2,通过OSMapTbl映射后
OSMapTbl[2]=0000 0100
OSRdyTbl[prio>>3]= OSRdyTbl[1]=0000 0100
11对应二进制:001 011高3位:001=1 通过OSMapTbl映射后,
OSMapTbl[prio>>3]= OSMapTbl[1]=0000 0010.
低3位:011=3,通过OSMapTbl映射后
OSMapTbl[3]=0000 1000
OSRdyTbl[prio>>3]= OSRdyTbl[1]=0000 1000
17对应二进制:010 001高3位:010=2 通过OSMapTbl映射后,
OSMapTbl[prio>>3]= OSMapTbl[2]=0000 0100.
低3位:001=1,通过OSMapTbl映射后
OSMapTbl[1]=0000 0010
OSRdyTbl[prio>>3]= OSRdyTbl[2]=0000 0010
通过就绪任务算法:
OSRdyGrp |= OSMapTbl[prio>>3];OSRdyTbl[prio>>3] |= OSMapTbl[prio&0x07];
最终OSRdyGrp的值就是将所有的OSMapTbl[prio>>3]进行位或运算:
OSRdyGrp=000 00001
|0000 0010
|0000 0010
|0000 0100
=0000 0111 = 0x07
OSRdyTbl[0]=0100 0000
OSRdyTbl[1]=
0000 0100
|0000 1000
=0000 1100(相同的列进行位或运算)
OSRdyTbl[2]=0000 0010
然后查找优先级判定表OSUnMapTbl[]
OSRdyGrp=0x07Y=OSUnMapTbl[0x07]=0
说明是最高优先级在第0组。
OSRdyTbl[0]=0100 0000=0x40X = OSUnMapTbl[0x40]=6
最高优先级为:prio= y*8+x=6
至此,最高优先级就选出来了。然后调度此任务运行就是了,另外,删除任务就是将对应就绪列表位的置的1清零就是。
if ((OSRdyTbl[prio >> 3] &= ~OSMapTbl[prio & 0x07]) == 0)OSRdyGrp &= ~OSMapTbl[prio >> 3];
看到这里,这行代码理解应该没有问题,就是反操作而已。
阅读 44更新于 今天 07:07
本作品系原创,采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议
码之泪殇
这是一行不知道写点什么的Slogan
0 声望
0 粉丝
码之泪殇
这是一行不知道写点什么的Slogan
0 声望
0 粉丝
宣传栏
1、μC/OS-II任务优先级相关简介:μC/OS-II中共有64个优先级(0~63级,数字越小优先级越高)。因为是实时系统,所以对应每个任务就分配一个优先级。
2、2进制和10进制转换基础
这里先介绍一个数学知识,二进制如何变为十进制,比如十进制26,其8位二进制表示为:00 011 010
。当十进制为0~63时,前两位无作用,所以只看后6位——011 010
.怎么计算成十进制呢?很简单:把这个十进制数,分为两个部分,高三位和低三位,这个十进制数的大小就等于高三位的十进制8+低三位的十进制数(其实就是二进制转八进制再转十进制)。高三位的011=3
,低三位的010=2
,所以26=3x8+2=(011)<<3+(010).即将高三位左移三位
就是8再加上低三位。下面要介绍的算法也是这个数学方法。
3、优先级任务调度过程
- 创建任务并分配优先级
- 通过算法,操作系统对创建完成的任务(即
就绪任务
)进行标记。并通过标记来查找当中任务中优先级最高的任务 - 调用调度函数进行调度,让最高优先级任务运行
优先级创建
μC/OS-II中创建任务的函数原型: INT8U OSTASKCeate(void (*task)(void *pd),void *pdata,os_stk *ptos,INT8U prio)
,从这个函数可以看出,最后一个参数就是优先级,所以结论是,在创建任务的同时就要确定任务的优先级,并且是该优先级是8位的(0~2^8-1),这里也可以看出为什么会有64个优先级。
任务优先级的标定
什么是优先级的标定:就是操作系统要知道哪个任务已经就绪了,然后就在这些就绪了的任务里面切换调度。所以第一步就是要知道哪些任务就绪了,然后就可以操作了。
这里要先介绍两个数据结构,:OSRdyGrp、OSRdyTbl[]
,这两个变量协同完成优先级的标定。OSRdyGrp
:优先级就绪组
这是一个8位的变量。每一个变量对应于OSRdyTbl[]中的一行(实际上是一个元素,但也可以理解为一行)。OSRdyTbl[]
:优先级就绪表
这是一个数组,有8个成员,每个成员都是8位的变量,所以就可以构成了8*8的矩阵了。所以64个优先级都是标定在这个数组中的。
那到底怎么往空格里置1的呢? 这里就要分析这个优先级就绪表了
:
1.这个表的数据结构是数组,也就是说,这个数组有8个成员,每个成员都是8位的变量。
2.通过二级查找实现对就绪任务的标定的。这里可以理解为一个矩阵,找某个数,肯定是先找行,再找列。从而找到这个元素位置。思想就是这个。
怎么找行呢?这里的一个变量OSRdyGrp,是一个8位的变量。每一位对应上图的一行,当某一位置1时,就表明就绪表对应的行有就绪任务,然后再查找列,就可以找到哪个任务就绪了。现在举个列子来说明:
创建一个任务,它的优先级为 prio=11(这是用户指定的),此优先级用二进制表示(8位):最前面两位无用处,前面已说过 00 001 011
。那么怎么在对应的OSRdyTbl[]优先级就绪表中进行标定呢?
- 把这个二进制数分为两个部分:高3位 (001)和低3位(011);
- 高三位负责找到数组中的行,低三位负责找到数组中的列(其实这里不是列,是一个变量的8个位,也可以按列理解),这样配合就可以寻址,往相应数字标号里写1。
对上面这个数来说 001 =1说明是第1行(数组从0行开始),011=3说明在第3个位置要写入1,合在一起就是第一行的第三个位置写入1
,这样就完成了对应数字优先级标号的标记。
那从上面的思路来看,我们只要知道数组中的第几行和第几列的值就可以了,所以又引进了一个映射数组
: OSMapTbl[]
,其具体内容如下。下标0对应的就是0位为1,下标1对应的就是1位为1,然后把这个数赋值给OSRdyGrp优先级就绪组。则OSRdyGrp哪个位为1则说明就是就绪表哪个行有就绪任务了。这样做的好处就是快。这也就是这个数组就是个映射数组,方便操作而已。
下标 | 二进制值 |
---|---|
0 | 00000001 |
1 | 00000010 |
2 | 00000100 |
3 | 00001000 |
4 | 00010000 |
5 | 00100000 |
6 | 01000000 |
7 | 10000000 |
至此,以上涉及3个数据结构了,现在来总结一下:
1.OSRdyGrp
优先级就绪组:第几位被置1,就说明就绪表中第几行有就绪任务。比如OSRdyGrp=0000 0001
。说明OSRdyTbl[0]
行有就绪任务。具体是这行的哪个列还要根据低三位
的值来决定.
2.OSRdyTbl[]
优先级就绪表:行+列就能标定就绪任务的优先级.
OSMapTbl[]
优先级映射表:用来方便生成第几行,第几列的一个转换.
<font color='red'>下面来看ucos中的源码怎么实现的:</font>
任务就绪源码如下:
OSRdyGrp |= OSMapTbl[prio>>3];OSRdyTbl[prio>>3] |= OSMapTbl[prio&0x07];
代码解释:prio>>3是获取优先级的高3位
,prio&0x07是获取优先级的低3位
。然后在通过OSMapTbl的映射分别获得了就绪表中的行和就绪表中的列, 然后查询就绪算法:
y = OSUnMapTbl[OSRdyGrp];x = OSUnMapTbl[OSRdyTbl[y]];
prio = (y << 3) + x;
举个例子:
创建一个任务,且prio=11=001 011
的情况分析:高3位
:001=1
通过OSMapTbl
映射后,OSRdyGrp=0000 0010,即是就绪表中第1行有任务就绪。低3位
:011=3,通过OSMapTbl
映射后
//低三位的映射OSMapTbl[prio&0x07] = OSMapTbl[3] = 0000 1000;
OSRdyTbl[prio>>3] = OSRdyTbl[1] = 0000 1000;
通过这句代码就往就绪表第一行(从OSRdyTbl[1]看到)第3个位置(从右往左看0000 1000,第一个为1的位,0开始)写入1,表明该任务就绪了。
这样就完成了单个任务优先级的标定。
多任务优先级设定
这里引入一个表格:优先级判定表OSUnMapTbl[]
,这个表的作用是为了节省时间,这样查表的话,耗的时间是一定的,很好的满足了实时性。下面来分析这个表的作用。
1.先看最旁边的注释,说明的是该数组中对应的位置。
2.解释这个数组中内容,这些数字怎么来的。
例子 :
有4个任务 ,优先级分别为6,10,11,17.。把上面就绪任务算法再贴一遍:前面2位不管。
6对应二进制:000 110高3位:000=0 通过OSMapTbl映射后,
OSMapTbl[prio>>3]= OSMapTbl[0]=0000 0001
低3位:110=6,通过OSMapTbl映射后
OSMapTbl[6]=0100 0000
OSRdyTbl[prio>>3]= OSRdyTbl[0]=0100 0000
10对应二进制:001 010高3位:001=1 通过OSMapTbl映射后,
OSMapTbl[prio>>3]= OSMapTbl[1]=0000 0010.
低3位:010=2,通过OSMapTbl映射后
OSMapTbl[2]=0000 0100
OSRdyTbl[prio>>3]= OSRdyTbl[1]=0000 0100
11对应二进制:001 011高3位:001=1 通过OSMapTbl映射后,
OSMapTbl[prio>>3]= OSMapTbl[1]=0000 0010.
低3位:011=3,通过OSMapTbl映射后
OSMapTbl[3]=0000 1000
OSRdyTbl[prio>>3]= OSRdyTbl[1]=0000 1000
17对应二进制:010 001高3位:010=2 通过OSMapTbl映射后,
OSMapTbl[prio>>3]= OSMapTbl[2]=0000 0100.
低3位:001=1,通过OSMapTbl映射后
OSMapTbl[1]=0000 0010
OSRdyTbl[prio>>3]= OSRdyTbl[2]=0000 0010
通过就绪任务算法:
OSRdyGrp |= OSMapTbl[prio>>3];OSRdyTbl[prio>>3] |= OSMapTbl[prio&0x07];
最终OSRdyGrp的值就是将所有的OSMapTbl[prio>>3]进行位或运算:
OSRdyGrp=000 00001
|0000 0010
|0000 0010
|0000 0100
=0000 0111 = 0x07
OSRdyTbl[0]=0100 0000
OSRdyTbl[1]=
0000 0100
|0000 1000
=0000 1100(相同的列进行位或运算)
OSRdyTbl[2]=0000 0010
然后查找优先级判定表OSUnMapTbl[]
OSRdyGrp=0x07Y=OSUnMapTbl[0x07]=0
说明是最高优先级在第0组。
OSRdyTbl[0]=0100 0000=0x40X = OSUnMapTbl[0x40]=6
最高优先级为:prio= y*8+x=6
至此,最高优先级就选出来了。然后调度此任务运行就是了,另外,删除任务就是将对应就绪列表位的置的1清零就是。
if ((OSRdyTbl[prio >> 3] &= ~OSMapTbl[prio & 0x07]) == 0)OSRdyGrp &= ~OSMapTbl[prio >> 3];
看到这里,这行代码理解应该没有问题,就是反操作而已。
以上是 【Java】优先级位图算法详解 的全部内容, 来源链接: utcz.com/a/106518.html
得票时间