关于java:优先级位图算法详解

在嵌入式操作系统温习中，咱们理解了 μ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=3×8+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 则阐明就是就绪表哪个行有就绪工作了。这样做的益处就是快。这也就是这个数组就是个映射数组，不便操作而已。

至此，以上波及 3 个数据结构了，当初来总结一下：
1.OSRdyGrp优先级就绪组：第几位被置 1，就阐明就绪表中第几行有就绪工作。比方 OSRdyGrp=0000 0001。阐明OSRdyTbl[0] 行有就绪工作。具体是这行的哪个列还要依据 低三位 的值来决定.
2.OSRdyTbl[]优先级就绪表：行 + 列就能标定就绪工作的优先级.

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

举例：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];  

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