Ucos优先级位图算法详解 优先级, 二进制, 十进制, 操作系统, 如何

yuyang911220

1. ucos任务相关简介
在实时操作系统中，由于系统不可能太庞大，因此任务数量也不会太大，ucos中共有64个优先级（0~63级，数字越小优先级越高）。因为是实时系统，所以对应每个任务就分配一个优先级。
2.二进制和十进制的转换数学基础

这里先介绍一个数学知识，二进制如何变为十进制，比如 十进制26，其8位二进制表示为：00011010。当十进制为0~63时，前两位无作用，所以只看后6位，011 010.怎么计算成十进制呢？很简答：如下所示
这个过程就是，把这个十进制数，分为两个部分，高三位和低三位，这个十进制数的大小就等于高三位的十进制*8+第三位的十进制数。高三位的011=3 ，低三位的010=2.所以26=3*8+2.=（011）<<3+(010).即将高三位左移三位就是*8再加上低三位。所以下面要介绍的算法也是这个数学方法。
3..整个过程的流程
       1.创建任务并分配优先级
       2.通过算法，操作系统对创建了的任务即就绪任务进行标记。并通过标记来查找当中任务中优先级最高的任务
       3.调用调度函数进行调度，让最高优先级任务运行。
3..1任务的优先级怎么创建的。

我们先来看一下，ucos中创建任务的函数原型：
       INT8UOSTASKCeate(void (*task)(void *pd),void *pdata,os_stk *ptos,INT8U prio)，从这个函数可以看出，最后一个参数就是优先级，所以结论是，在创建任务的同时就要确定任务的优先级，并且是该优先级是8位的（0~2^8-1），这里也可以看出为什么会有64个优先级。
       因为用户可以指定任务的优先级，但实时操作系统最大的好处就是高优先级的任务可以抢占低优先级的任务，那怎么实现的呢？通过优先级实现
         既然用户在调用系统函数创建任务的同时指定了任务的优先级，一旦创建了任务，该任务就会立即成为就绪状态，操作系统就会将该任务的优先级标志位置位，相当于做个记号，操作系统心里就会想，哦，这个优先级的任务已经就绪了，同样创建了其他的任务，操作系统都会在某个地方做好标记表明对应优先级的任务已经就绪，然后在调度函数的调度下进行调度，那么在哪个地方做个标记呢？既然是实时操作系统，操作系统考什么算法去查找优先级最高的任务呢？
3.2 ucos怎么实现就绪状态任务优先级的标定

什么是优先级的标定：就是操作系统要知道哪个任务已经就绪了，然后就在这些就绪了的任务里面切换调度。所以第一步就是要知道哪些任务就绪了，然后就可以操作了。
这里要先介绍两个数据结构，：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）。
高三位负责找到数组中的行，低三位负责找到数组中的列（其实这里不是列，是一个变量的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[]：优先级就绪表：行+列就能标定就绪任务的优先级
3. OSMapTbl[] 优先级映射表：用来方便生成第几行，第几列的一个转换而已。
下面来看ucos中的源码怎么实现的：任务就绪源码如下;
OSRdyGrp |= OSMapTbl[prio>>3];          （1）
OSRdyTbl[prio>>3] |=OSMapTbl[prio&0x07];   （2）
代码解释：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=00000010.即是就绪表中第一行有任务就绪。
低3位：011=3，通过OSMapTbl映射后
OSRdyTbl[prio>>3]= OSRdyTbl[1]=00001000  ，通过这句代码就往就绪表第一行（从OSRdyTbl[1]看到）第3个位置（从右往左看00001000，第一个为1的位，0开始。）写入1，表明该任务就绪了。
这样就完成了 优先级的标定

4 多个任务参与下怎么选定最高的优先级任务
       此时又要加入一个表格：优先级判定表OSUnMapTbl[]，这个表的作用是为了节省时间，这样查表的话，耗的时间是一定的，很好的满足了实时性。下面来分析这个表的作用。
1.先看最旁边的注释，说明的是该数组中对应的位置。
2.解释 这个数组中内容，这些数字怎么来的。
举例：0x53 如上图所示的位置，为什么是0呢？我们把0x53变成二进制来看：
01010011，从右往左看，第一个出现1的位 就是0位所以为0.
为什么是从右往左看呢？因为高优先级的数字低，你应该懂的。