多层位图查表法

在嵌入式操作系统中，特别是实时操作系统中经常采用位图法解决任务的就绪以及查找最高优先级的快速方法，即通过对所有的可能性采用查表的形式即可实现对于uC/OS-II这种64（ 2^8）个优先级任务的小系统，可以通过求取x,y,得到对应的最高优先级值，而且在查表的过程中，只有256种可能性，通过简单的查表就能快速的实现，但是当任务的优先级数大于64个时，那又该如何让实现呢？因为此时的查表不在那么容易，比存在16个bit时，2^16=65536，也就是存在65536种可能性，这个数据表格太大因此不是我们考虑的形式，那么如何确定呢，此时采用分层的形式就能比较快速的实现，在64个任务时首先可以采用一个就绪表每一个bit代表一个任务优先级，另外准备一个标志变量，每一个bit表示具体的某一个组，每一组八个数据，通过这种x,y的形式能够快速的实现查找。当任务对于64个时，我们可以尝试多增加一维z的形式表示不同的任务，也就是实现分层，一共分成了三层，这样就能通过这种多层的形式，通过同一个查询表（256种可能性）的使用而快速的确定x,y,z,进而得到最高的优先级号。这种三层的形式最多能够支持512个优先级号的操作系统。当多于这种情况时，就需要再次增加层数。

具体的实现如下：

z的每一个bit对应着1个y。也就是一共对应8个y。

y的每一个bit对应着一个x，也就是一共对应着8*8个x。

每一个x刚好也就对应着8个任务优先级号。这样就能够通过x,y,z设置优先级。

因此可以采用下面的形式定义一个结构体：

#ifndef __HIGH_BITMAP_H_H__
#define __HIGH_BITMAP_H_H__

#define LENGTH_HIGHLAYER    8
#define LENGTH_BYTE            8
typedef unsigned char Byte;


typedef struct
{
    Byte high_Layer;
    Byte mid_Layer[LENGTH_HIGHLAYER];
    Byte low_Layer[LENGTH_HIGHLAYER*LENGTH_BYTE];
}BitMaps;

#ifdef __cplusplus
extern "C"
{
#endif

void inital_bitmap(BitMaps *bitmap);
void set_bitmap(BitMaps *bitmap,int prio);
int calculate_high_prio(BitMaps *bitmap);

#ifdef __cplusplus
}
#endif

#endif

基本的操作函数如下：

 

#include"high_bitmap.h"
#include<stdio.h>

int const OSUnMapTbl[256] = {
     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 */
};


void inital_bitmap(BitMaps *bitmap)
{
    int i = 0;
    if(NULL == bitmap)
    {
        return ;
    }

    bitmap->high_Layer = 0x00;
    for(; i < sizeof(bitmap->mid_Layer); ++ i)
    {
        bitmap->mid_Layer[i] = 0x00;
    }

    for (i = 0; i < sizeof(bitmap->low_Layer); ++ i)
    {
        bitmap->low_Layer[i] = 0x00;
    }
}

void set_bitmap(BitMaps *bitmap,int prio)
{
    int x,y,z;
    if(NULL == bitmap || prio >= 512)
    {
        return ;
    }

    z = (prio >> 6)& 0x7;
    bitmap->high_Layer |= 1<<z;

    y = (prio >> 3) & 0x7;
    bitmap->mid_Layer[z] |= 1<<y;

    x = prio & 0x7;
    bitmap->low_Layer[z*8+y] |= 1<<x;
}

int calculate_high_prio(BitMaps *bitmap)
{
    int x,y,z;

    if(NULL == bitmap)
    {
        return -1;
    }

    z = OSUnMapTbl[bitmap->high_Layer];
    y = OSUnMapTbl[bitmap->mid_Layer[z]];
    x = OSUnMapTbl[bitmap->low_Layer[(z << 3)+y]];

    z = (z << 6) + (y << 3) + x;

    return z;
}

这种分层的实现方式能够方便的解决位图中多种可能性问题，通过分层可以使得各个变量x,y,z都能过使用查询表（256种可能），解决了超大可能性的问题。当然这种方式也不是唯一的，但是确实是一种可行的方案，共享查询表的。

 

文章查询的思路uC/OS-II中查询的形式相同，也就是当对应的任务需要就绪时，可以通过设置对应的x,y,z对应的bit为1即可。