精华内容
下载资源
问答
  • 优先级位图算法

    2019-12-26 20:26:46
    文章目录算法的由来优先级位图算法 算法的由来 我是在学习嵌入式操作系统这门课知道优先级位图算法的,可能描述的啰嗦,将就着看吧!这个算法用来对操作系统的任务进行调度。在μC/OS-II中是这样的,每一个任务都有...

    算法的由来

    我是在学习嵌入式操作系统这门课知道优先级位图算法的,可能描述的啰嗦,将就着看吧!这个算法用来对操作系统的任务进行调度。在μC/OS-II中是这样的,每一个任务都有一个优先级,但是每一个优先级只能有一个任务,那么如何让具有最高优先级的任务先执行。系统中每一个任务都有一个任务控制快TCB,可以将就绪的TCB放进就绪队列,然后处理器执行的时候从就绪队列中选择优先级最高的执行,但是这样的话,嵌入式系统的实时性无法保证,因为需要遍历就绪队列找到最高优先级的任务,所以才有了优先级位图算法。

    优先级位图算法

    优先级位图算法有一个数组OSRdyTbl[8],数组中的每一值有八位,这样就构成了一个8*8的格子,如下图所示。
    在这里插入图片描述
    在上面的这个表格中,我们在用一个变量OSRdyGrp(八位)来对应OSRdyTb[8]的每一个元素。这个OSRdyTb中当然不是这些1~63的数字,而都只是1,0的二进制数字。如果某一个优先级有任务,那么对应的位置标志为1,然后让OSRdyGrp对应的bit也标志为1。
    例如(如图A):优先级35,转成二进制00 100 011,然后将二进制分为高三位100 = 4,低三位011 = 3,然后查看一个表如图B,找到4对应的值与OSRdyGrp相或就能将OSRdyGrp对应的行标志为1,然后3对应的值与OSRdyTbl[4]的值相或,就可以确定是哪一列(如图C)。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    当然,有一个问题,比如上面的例子OSRdyGrp初始值为0,优先级35来了过后OSRdyGrp为4,也就是0000 0100,我们就知道是OSRdyTbl索引为4的值。那么,如果是多个优先级的任务且在不同的行?那怎么在多个任务中确认优先级做高的任务所在的行呢?于是就有了一种表记录OSRdyGrp所有的值的二进制中第一个1的位置,这个表如图D所示:
    在这里插入图片描述
    那这个表怎么查呢?比如有优先级6,17,35转化为二进制,6:110,17:10001,35:100011,那么经过计算过后的OSRdyGrp的值为110111,转化为16进制0X37 ,找到这个数字对应的行,然后找到这个数对应的值0,说明最高优先级的在OSRdyTabl的第0行,然后以相同的方式找到所在的列就能确定最高优先级的值了。

    展开全文
  • 分分钟搞定优先级位图算法

    千次阅读 2020-01-03 11:20:18
    在嵌入式操作系统复习中,我们了解了μC/OS-II的相关基础知识,在任务调度这一节,我们提到了优先级位图算法,本文详细介绍该算法的原理和实现。 1、μC/OS-II任务优先级相关简介:μC/OS-II中共有64个优先级(0~...

    嵌入式操作系统复习中,我们了解了μC/OS-II的相关基础知识,在任务调度这一节,我们提到了优先级位图算法,本文详细介绍该算法的原理和实现。
    说明:
    本文参考了这篇文章,加入了一些自己的理解,如有侵权,请联系删除:原文链接

    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、优先级任务调度过程

    1. 创建任务并分配优先级
    2. 通过算法,操作系统对创建完成的任务(即就绪任务)进行标记。并通过标记来查找当中任务中优先级最高的任务
    3. 调用调度函数进行调度,让最高优先级任务运行

    优先级创建
    μC/OS-II中创建任务的函数原型:
    INT8U OSTASKCeate(void (*task)(void *pd),void *pdata,os_stk *ptos,INT8U prio),从这个函数可以看出,最后一个参数就是优先级,所以结论是,在创建任务的同时就要确定任务的优先级,并且是该优先级是8位的(0~2^8-1),这里也可以看出为什么会有64个优先级。

    因为用户可以指定任务的优先级,但实时操作系统最大的好处就是高优先级的任务可以抢占低优先级的任务,那怎么实现的呢?当然是通过优先级实现。
    既然用户在调用系统函数创建任务的同时指定了任务的优先级,一旦创建了任务,该任务就会立即成为就绪状态,操作系统就会将该任务的优先级标志位置位1,相当于做个记号,操作系统心里就会想,哦,这个优先级的任务已经就绪了,同样创建了其他的任务,操作系统都会在某个地方做好标记表明对应优先级的任务已经就绪,然后在调度函数的调度下进行调度,那么在哪个地方做个标记呢?既然是实时操作系统,操作系统用什么算法去查找优先级最高的任务呢?

    任务优先级的标定
    什么是优先级的标定:就是操作系统要知道哪个任务已经就绪了,然后就在这些就绪了的任务里面切换调度。所以第一步就是要知道哪些任务就绪了,然后就可以操作了。
    这里要先介绍两个数据结构,:OSRdyGrp、OSRdyTbl[],这两个变量协同完成优先级的标定。
    OSRdyGrp:优先级就绪组
    这是一个8位的变量。每一个变量对应于OSRdyTbl[]中的一行(实际上是一个元素,但也可以理解为一行)。
    OSRdyTbl[]:优先级就绪表
    这是一个数组,有8个成员,每个成员都是8位的变量,所以就可以构成了8*8的矩阵了。所以64个优先级都是标定在这个数组中的。
    在这里插入图片描述

    从上图可以明显看出,这个图有64个空格(64个位),每个空格对应一个数字,该数字就是优先级的标号,但是这个是人为的标上的,实际上这是64个空格,现在要做的事情就是将就绪任务的优先级相对应的标号置1,表示这个优先级任务就绪了,比如刚创建了一个任务,它的优先级是7,所以往表格中数字为7的空格写入1就表明该优先级的任务就绪了,可以被调度了。另外当所有需要创建任务都创建完毕后,各个就绪任务的相应数字空格都会置1,表明这些任务都就绪了,比如,现在创建了5个任务,优先级分别为4,7,9,10,24.所以在创建完这些任务后,这个优先级就绪表中的相对应的数字空格都会被置1,要特别注意上图的优先级顺序,0的优先级最高,63的优先级最低。

    那到底怎么往空格里置1的呢? 这里就要分析这个优先级就绪表了:

    1.这个表的数据结构是数组,也就是说,这个数组有8个成员,每个成员都是8位的变量。
    2.通过二级查找实现对就绪任务的标定的。这里可以理解为一个矩阵,找某个数,肯定是先找行,再找列。从而找到这个元素位置。思想就是这个。
    怎么找行呢?这里的一个变量OSRdyGrp,是一个8位的变量。每一位对应上图的一行,当某一位置1时,就表明就绪表对应的行有就绪任务,然后再查找列,就可以找到哪个任务就绪了。现在举个列子来说明:

    创建一个任务,它的优先级为 prio=11(这是用户指定的),此优先级用二进制表示(8位):最前面两位无用处,前面已说过 00 001 011。那么怎么在对应的OSRdyTbl[]优先级就绪表中进行标定呢?

    1. 把这个二进制数分为两个部分:高3位 (001)和低3位(011);
    2. 高三位负责找到数组中的行,低三位负责找到数组中的列(其实这里不是列,是一个变量的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[]优先级就绪表:行+列就能标定就绪任务的优先级.
    3. OSMapTbl[]优先级映射表:用来方便生成第几行,第几列的一个转换.

    下面来看ucos中的源码怎么实现的:
    任务就绪源码如下:

    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.解释这个数组中内容,这些数字怎么来的。

    举例:0x53 如上图所示的位置,为什么是0呢?我们把0x53变成二进制来看: 0101 0011,从右往左看,第一个出现1的位,就是0位所以为0. 为什么是从右往左看呢?因为高优先级的数字低,你应该懂的。

    例子 :
    有4个任务 ,优先级分别为6,10,11,17.。把上面就绪任务算法再贴一遍:前面2位不管。

    6对应二进制:000 1103位:000=0 通过OSMapTbl映射后, 
    OSMapTbl[prio>>3]= OSMapTbl[0]=0000 00013位:110=6,通过OSMapTbl映射后 
    OSMapTbl[6]=0100 0000
    OSRdyTbl[prio>>3]= OSRdyTbl[0]=0100 0000  
    
    10对应二进制:001 0103位: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 0113位: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 0013位: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=0x07 
    Y=OSUnMapTbl[0x07]=0
    

    说明是最高优先级在第0组。

    OSRdyTbl[0]=0100 0000=0x40
    X = OSUnMapTbl[0x40]=6
    

    最高优先级为:prio= y*8+x=6

    至此,最高优先级就选出来了。然后调度此任务运行就是了,另外,删除任务就是将对应就绪列表位的置的1清零就是。

    if ((OSRdyTbl[prio >> 3] &= ~OSMapTbl[prio & 0x07]) == 0) 
    	OSRdyGrp &= ~OSMapTbl[prio >> 3];  
    

    看到这里,这行代码理解应该没有问题,就是反操作而已。

    展开全文
  • 在嵌入式操作系统复习中,我们了解了μC/OS-II的相关基础知识,在任务调度这一节,我们提到了优先级位图算法,本文详细介绍该算法的原理和实现。说明:本文参考了这篇文章,加入了一些自己的理解,如有侵权,请联系...

    在嵌入式操作系统复习中,我们了解了μC/OS-II的相关基础知识,在任务调度这一节,我们提到了优先级位图算法,本文详细介绍该算法的原理和实现。说明:本文参考了这篇文章,加入了一些自己的理解,如有侵权,请联系删除:原文链接

    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、优先级任务调度过程

    1. 创建任务并分配优先级
    2. 通过算法,操作系统对创建完成的任务(即就绪任务)进行标记。并通过标记来查找当中任务中优先级最高的任务
    3. 调用调度函数进行调度,让最高优先级任务运行

    优先级创建μC/OS-II中创建任务的函数原型:INT8U OSTASKCeate(void (*task)(void *pd),void *pdata,os_stk *ptos,INT8U prio),从这个函数可以看出,最后一个参数就是优先级,所以结论是,在创建任务的同时就要确定任务的优先级,并且是该优先级是8位的(0~2^8-1),这里也可以看出为什么会有64个优先级。

    因为用户可以指定任务的优先级,但实时操作系统最大的好处就是高优先级的任务可以抢占低优先级的任务,那怎么实现的呢?当然是通过优先级实现。既然用户在调用系统函数创建任务的同时指定了任务的优先级,一旦创建了任务,该任务就会立即成为就绪状态,操作系统就会将该任务的优先级标志位置位为1,相当于做个记号,操作系统心里就会想,哦,这个优先级的任务已经就绪了,同样创建了其他的任务,操作系统都会在某个地方做好标记表明对应优先级的任务已经就绪,然后在调度函数的调度下进行调度,那么在哪个地方做个标记呢?既然是实时操作系统,操作系统用什么算法去查找优先级最高的任务呢?

    任务优先级的标定什么是优先级的标定:就是操作系统要知道哪个任务已经就绪了,然后就在这些就绪了的任务里面切换调度。所以第一步就是要知道哪些任务就绪了,然后就可以操作了。这里要先介绍两个数据结构,:OSRdyGrp、OSRdyTbl[],这两个变量协同完成优先级的标定。OSRdyGrp:优先级就绪组 这是一个8位的变量。每一个变量对应于OSRdyTbl[]中的一行(实际上是一个元素,但也可以理解为一行)。OSRdyTbl[]:优先级就绪表 这是一个数组,有8个成员,每个成员都是8位的变量,所以就可以构成了8*8的矩阵了。所以64个优先级都是标定在这个数组中的。8a502f315dc5d4038deecb86aefc3eb8.png

    从上图可以明显看出,这个图有64个空格(64个位),每个空格对应一个数字,该数字就是优先级的标号,但是这个是人为的标上的,实际上这是64个空格,现在要做的事情就是将就绪任务的优先级相对应的标号置1,表示这个优先级任务就绪了,比如刚创建了一个任务,它的优先级是7,所以往表格中数字为7的空格写入1就表明该优先级的任务就绪了,可以被调度了。另外当所有需要创建任务都创建完毕后,各个就绪任务的相应数字空格都会置1,表明这些任务都就绪了,比如,现在创建了5个任务,优先级分别为4,7,9,10,24.所以在创建完这些任务后,这个优先级就绪表中的相对应的数字空格都会被置1,要特别注意上图的优先级顺序,0的优先级最高,63的优先级最低。

    那到底怎么往空格里置1的呢? 这里就要分析这个优先级就绪表了:

    1.这个表的数据结构是数组,也就是说,这个数组有8个成员,每个成员都是8位的变量。2.通过二级查找实现对就绪任务的标定的。这里可以理解为一个矩阵,找某个数,肯定是先找行,再找列。从而找到这个元素位置。思想就是这个。怎么找行呢?这里的一个变量OSRdyGrp,是一个8位的变量。每一位对应上图的一行,当某一位置1时,就表明就绪表对应的行有就绪任务,然后再查找列,就可以找到哪个任务就绪了。现在举个列子来说明:

    创建一个任务,它的优先级为 prio=11(这是用户指定的),此优先级用二进制表示(8位):最前面两位无用处,前面已说过 00 001 011。那么怎么在对应的OSRdyTbl[]优先级就绪表中进行标定呢?

    1. 把这个二进制数分为两个部分:高3位 (001)和低3位(011);
    2. 高三位负责找到数组中的行,低三位负责找到数组中的列(其实这里不是列,是一个变量的8个位,也可以按列理解),这样配合就可以寻址,往相应数字标号里写1。对上面这个数来说 001 =1说明是第1行(数组从0行开始),011=3说明在第3个位置要写入1,合在一起就是第一行的第三个位置写入1,这样就完成了对应数字优先级标号的标记。

    那从上面的思路来看,我们只要知道数组中的第几行和第几列的值就可以了,所以又引进了一个映射数组OSMapTbl[],其具体内容如下。下标0对应的就是0位为1,下标1对应的就是1位为1,然后把这个数赋值给OSRdyGrp优先级就绪组。则OSRdyGrp哪个位为1则说明就是就绪表哪个行有就绪任务了。这样做的好处就是快。这也就是这个数组就是个映射数组,方便操作而已。

    下标二进制值
    000000001
    100000010
    200000100
    300001000
    400010000
    500100000
    601000000
    710000000

    至此,以上涉及3个数据结构了,现在来总结一下:1.OSRdyGrp优先级就绪组:第几位被置1,就说明就绪表中第几行有就绪任务。比如OSRdyGrp=0000 0001。说明OSRdyTbl[0]行有就绪任务。具体是这行的哪个列还要根据低三位的值来决定. 2.OSRdyTbl[]优先级就绪表:行+列就能标定就绪任务的优先级. 3. OSMapTbl[]优先级映射表:用来方便生成第几行,第几列的一个转换.

    下面来看ucos中的源码怎么实现的:任务就绪源码如下:

    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[],这个表的作用是为了节省时间,这样查表的话,耗的时间是一定的,很好的满足了实时性。下面来分析这个表的作用。959293451a9feed0cd4119806c5ca76a.png1.先看最旁边的注释,说明的是该数组中对应的位置。2.解释这个数组中内容,这些数字怎么来的。

    举例:0x53 如上图所示的位置,为什么是0呢?我们把0x53变成二进制来看:0101 0011,从右往左看,第一个出现1的位,就是0位所以为0. 为什么是从右往左看呢?因为高优先级的数字低,你应该懂的。

    例子 :有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=0x07 
    Y=OSUnMapTbl[0x07]=0

    说明是最高优先级在第0组。

    OSRdyTbl[0]=0100 0000=0x40
    X = OSUnMapTbl[0x40]=6

    最高优先级为:prio= y*8+x=6

    至此,最高优先级就选出来了。然后调度此任务运行就是了,另外,删除任务就是将对应就绪列表位的置的1清零就是。

    if ((OSRdyTbl[prio >> 3] &= ~OSMapTbl[prio & 0x07]) == 0
     OSRdyGrp &= ~OSMapTbl[prio >> 3];  

    看到这里,这行代码理解应该没有问题,就是反操作而已。

    展开全文
  • 在嵌入式操作系统复习中,我们了解了μC/OS-II的相关基础知识,在任务调度这一节,我们提到了优先级位图算法,本文详细介绍该算法的原理和实现。 说明: 本文参考了这篇文章,加入了一些自己的理解,如有侵权,请...

    在嵌入式操作系统复习中,我们了解了μC/OS-II的相关基础知识,在任务调度这一节,我们提到了优先级位图算法,本文详细介绍该算法的原理和实现。 说明: 本文参考了这篇文章,加入了一些自己的理解,如有侵权,请联系删除:原文链接

    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、优先级任务调度过程

    1. 创建任务并分配优先级
    2. 通过算法,操作系统对创建完成的任务(即就绪任务)进行标记。并通过标记来查找当中任务中优先级最高的任务
    3. 调用调度函数进行调度,让最高优先级任务运行

    优先级创建 μC/OS-II中创建任务的函数原型: INT8U OSTASKCeate(void (*task)(void *pd),void *pdata,os_stk *ptos,INT8U prio),从这个函数可以看出,最后一个参数就是优先级,所以结论是,在创建任务的同时就要确定任务的优先级,并且是该优先级是8位的(0~2^8-1),这里也可以看出为什么会有64个优先级。

    因为用户可以指定任务的优先级,但实时操作系统最大的好处就是高优先级的任务可以抢占低优先级的任务,那怎么实现的呢?当然是通过优先级实现。 既然用户在调用系统函数创建任务的同时指定了任务的优先级,一旦创建了任务,该任务就会立即成为就绪状态,操作系统就会将该任务的优先级标志位置位1,相当于做个记号,操作系统心里就会想,哦,这个优先级的任务已经就绪了,同样创建了其他的任务,操作系统都会在某个地方做好标记表明对应优先级的任务已经就绪,然后在调度函数的调度下进行调度,那么在哪个地方做个标记呢?既然是实时操作系统,操作系统用什么算法去查找优先级最高的任务呢?

    任务优先级的标定 什么是优先级的标定:就是操作系统要知道哪个任务已经就绪了,然后就在这些就绪了的任务里面切换调度。所以第一步就是要知道哪些任务就绪了,然后就可以操作了。 这里要先介绍两个数据结构,:OSRdyGrp、OSRdyTbl[],这两个变量协同完成优先级的标定。 OSRdyGrp:优先级就绪组 这是一个8位的变量。每一个变量对应于OSRdyTbl[]中的一行(实际上是一个元素,但也可以理解为一行)。 OSRdyTbl[]:优先级就绪表 这是一个数组,有8个成员,每个成员都是8位的变量,所以就可以构成了8*8的矩阵了。所以64个优先级都是标定在这个数组中的。

    c50bece5d659a89b5eef22a545a025e5.png

    从上图可以明显看出,这个图有64个空格(64个位),每个空格对应一个数字,该数字就是优先级的标号,但是这个是人为的标上的,实际上这是64个空格,现在要做的事情就是将就绪任务的优先级相对应的标号置1,表示这个优先级任务就绪了,比如刚创建了一个任务,它的优先级是7,所以往表格中数字为7的空格写入1就表明该优先级的任务就绪了,可以被调度了。另外当所有需要创建任务都创建完毕后,各个就绪任务的相应数字空格都会置1,表明这些任务都就绪了,比如,现在创建了5个任务,优先级分别为4,7,9,10,24.所以在创建完这些任务后,这个优先级就绪表中的相对应的数字空格都会被置1,要特别注意上图的优先级顺序,0的优先级最高,63的优先级最低。

    那到底怎么往空格里置1的呢? 这里就要分析这个优先级就绪表了:

    1.这个表的数据结构是数组,也就是说,这个数组有8个成员,每个成员都是8位的变量。 2.通过二级查找实现对就绪任务的标定的。这里可以理解为一个矩阵,找某个数,肯定是先找行,再找列。从而找到这个元素位置。思想就是这个。 怎么找行呢?这里的一个变量OSRdyGrp,是一个8位的变量。每一位对应上图的一行,当某一位置1时,就表明就绪表对应的行有就绪任务,然后再查找列,就可以找到哪个任务就绪了。现在举个列子来说明:

    创建一个任务,它的优先级为 prio=11(这是用户指定的),此优先级用二进制表示(8位):最前面两位无用处,前面已说过 00 001 011。那么怎么在对应的OSRdyTbl[]优先级就绪表中进行标定呢?

    1. 把这个二进制数分为两个部分:高3位 (001)和低3位(011);
    2. 高三位负责找到数组中的行,低三位负责找到数组中的列(其实这里不是列,是一个变量的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[]优先级就绪表:行+列就能标定就绪任务的优先级. 3. OSMapTbl[]优先级映射表:用来方便生成第几行,第几列的一个转换.

    下面来看ucos中的源码怎么实现的: 任务就绪源码如下:

    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[],这个表的作用是为了节省时间,这样查表的话,耗的时间是一定的,很好的满足了实时性。下面来分析这个表的作用。

    e1c241a09e8986b77005c6ef4e9e3e6d.png 1.先看最旁边的注释,说明的是该数组中对应的位置。 2.解释这个数组中内容,这些数字怎么来的。

    举例:0x53 如上图所示的位置,为什么是0呢?我们把0x53变成二进制来看: 0101 0011,从右往左看,第一个出现1的位,就是0位所以为0. 为什么是从右往左看呢?因为高优先级的数字低,你应该懂的。

    例子 : 有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=0x07 
    Y=OSUnMapTbl[0x07]=0
    

    说明是最高优先级在第0组。

    OSRdyTbl[0]=0100 0000=0x40
    X = OSUnMapTbl[0x40]=6
    

    最高优先级为:prio= y*8+x=6

    至此,最高优先级就选出来了。然后调度此任务运行就是了,另外,删除任务就是将对应就绪列表位的置的1清零就是。

    if ((OSRdyTbl[prio >> 3] &= ~OSMapTbl[prio & 0x07]) == 0) 
     OSRdyGrp &= ~OSMapTbl[prio >> 3];  
    

    看到这里,这行代码理解应该没有问题,就是反操作而已。

    展开全文
  • 优先级位图算法详解

    千次阅读 2019-11-18 19:45:11
    这两个变量协同完成优先级的标定。 OSRdyGrp:优先级就绪组 这是一个8位的变量。每一个变量对应于OSRdyTbl[]中的一行(实际上是一个元素,但也可以理解为一行)。 OSRdyTbl[]:优先级就绪表 这是一个数组,有8个...
  • [嵌入式操作系统] 优先级位图算法

    千次阅读 2019-12-31 15:20:12
    在ucos系统中,任务调度按照优先级调度算法,从就绪队列中选取优先级最高的任务进行调度。那么首先我们就要解决如何找到最高优先级的任务。 一种方法,我们可以从头到尾遍历就绪队列,找到优先级最高的任务。 另一种...

空空如也

空空如也

1 2 3 4 5
收藏数 87
精华内容 34
关键字:

优先级位图算法