[C++知识库]uCOS-II 优先级判定表的理解

前言

• uCOS-II 中，为了更快的获取最高的优先级，使用了空间换取时间的方法，通过查找【优先级判定表】 PRIORITY RESOLUTION TABLE，很快的获取最高优先级
• uCOS-II 对优先级用 【位】来表示，并分组，每组 8个优先级，最大优先级为 64，优先级 组 有一个8位字节表示，如 64 个优先级， 8个字节表示优先级的每个位，一个优先级组字节，表示分组
• 优先级0 为最高优先级，0 位于 0 组， OSRdyGrp[0]中的 BIT0
• 因为【低位】的优先级高于【高位】的优先级，每个字节的8位中，获取首个1出现的位置即可。

查找算法

• 从优先级分组中，从【低位】开始，找到第一个【分组】，如0x03，第一个分组为：BIT0，0组，可以用 Y （纵坐标）表示
• 通过上面的分组，从【低位】开始，找到第一个【1】，这就是最小的也是最高的优先级，可以用 X 表示
• 通过公式： 最高优先级 = 分组 Y * 8 + X（组员）

计算方法

• 对于一个数，8位或32位，二进制查看，从【低位】 到 【高位】，查找第一个 1 出现的位置
• 如 数字 8， 二进制：00001000 ，返回：3 ，也就是 1<<3，低位开始，第一个1出现在位置3，或者BIT3
• 如数字 0x33，二进制： 00110011，返回 ： 0， 也就是 1 << 0，地位开始，第一个1出现在位置0，或者BIT0

计算代码

• 这里使用RT-Thread 模拟器，visual studio 2022编译，shell命令的方式计算并打印
• get_ffs_value 模拟 ： __builtin_ffs，获取从低位开始，第一个1 出现的位置，

/* 获取从低位开始，第一个1 出现的位置，采用二分法 */
rt_uint32_t get_ffs_value(rt_uint32_t value)
{
    int num = 0;

    if (value == 0x00) /* 数值为0x00，没有1，直接返回 0 */
    {
        return 0;
    }

    if ((value & 0xffff) == 0) /* 低16位是否全为 0 */
    {
        num += 16;
        value >>= 16;
    }
    if ((value & 0xff) == 0) /* 低8位是否全为 0 */
    {
        num += 8;
        value >>= 8;
    }
    if ((value & 0xf) == 0) /* 低4位是否全为 0 */
    {
        num += 4;
        value >>= 4;
    }
    if ((value & 0x3) == 0) /* 低2位是否全为 0 */
    {
        num += 2;
        value >>= 2;
    }
    if ((value & 0x1) == 0) /* 低1位是否为 0 */
    {
        num += 1;
    }

    return num;
}

void ffs_test(void)
{
    rt_kprintf("const rt_uint8_t __lowest_bit_bitmap[] =\r\n");
    rt_kprintf("{\r\n");
    for (int i = 0; i < 256; i++)
    {
        if (i % 16 == 0)
            rt_kprintf("    ");
        rt_kprintf("%d, ", get_ffs_value(i));
        if ((i + 1) % 16 == 0)
            rt_kprintf("\r\n");
    }
    rt_kprintf("};\r\n");
}

MSH_CMD_EXPORT(ffs_test, ffs test);

运行结果

• 生成的优先级判定表数组为：

const rt_uint8_t __lowest_bit_bitmap[] =
{
    0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
};

• 对比 uCOS-II的优先级判定表，发现一致

/*
*********************************************************************************************************
*                                       PRIORITY RESOLUTION TABLE
*
* Note: Index into table is bit pattern to resolve highest priority
*       Indexed value corresponds to highest priority bit position (i.e. 0..7)
*********************************************************************************************************
*/

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

备注

• gcc 下的 __builtin_ffs，可以获取 低位开始，第一个 1 出现的位置

小结

• 了解uCOS-II 优先级判定表的计算方法，查表方法比计算要快一些

《新程序员》：云原生和全面数字化实践

50位技术专家共同创作，文字、视频、音频交互阅读