RTT 的内核调度器寻找优先级算法的一点疑问

发布于 2021-06-12 14:52:50 浏览：1589 订阅该版

RT-Thread 的内核调度算法中使用的查找当前最高优先级的线程的代码实现是这样的：

int __rt_ffs(int value)
{
    if (value == 0) return 0;
    if (value & 0xff)
        return __lowest_bit_bitmap[value & 0xff] + 1;
    if (value & 0xff00)
        return __lowest_bit_bitmap[(value & 0xff00) >> 8] + 9;
    if (value & 0xff0000)
        return __lowest_bit_bitmap[(value & 0xff0000) >> 16] + 17;
    return __lowest_bit_bitmap[(value & 0xff000000) >> 24] + 25;
}

这里有一个判断 value 的值是否为0的操作，为了应对这个判断，所有的优先级都多加了1。
然后在调用的时候，把这个1减掉了。

highest_ready_priority = __rt_ffs(rt_thread_ready_priority_group) - 1;

我的疑问来了，value值不可能为 0，为什么要判断这个值是否为0，不判断的话还省去了减一再加一的过程。

如果说是为了保持函数的健壮性，把 0 也检查了。
那么为什么不检查

highest_ready_priority = __rt_ffs(rt_thread_ready_priority_group) - 1;

这句代码中的 highest_ready_priority是否合理，因为如果__rt_ffs(rt_thread_ready_priority_group)的结果是0，减一后，就是一个很大的整数(无符号整型)，后面调用就会造成数组溢出。

我觉得 __rt_ffs(int value) 不应该检查value是否等于0,这样代码还能更简单一点。

可能是我还没考虑到更多的情况，希望知道的大佬，解决一下我心中的疑惑，谢谢。

aozima 2021-06-13

调网络不抓包，调I2C等时序不上逻辑分析仪，就像电工不用万用表！多用整理的好的文字，比截图更省流量，还能在整理过程中思考。

ffs这个函数是有标准的，外面检查了，里面还是要按要求返回0的。

/**
 * This function finds the first bit set (beginning with the least significant bit)
 * in value and return the index of that bit.
 *
 * Bits are numbered starting at 1 (the least significant bit).  A return value of
 * zero from any of these functions means that the argument was zero.
 *
 * @return return the index of the first bit set. If value is 0, then this function
 * shall return 0.
 */

不光是调试这边用，别的代码会有引用。
目前在 mmcsd_select_voltage 中也有引用这个函数。

/*
 * Mask off any voltages we don't support and select
 * the lowest voltage
 */
rt_uint32_t mmcsd_select_voltage(struct rt_mmcsd_host *host, rt_uint32_t ocr)
{
    int bit;
    extern int __rt_ffs(int value);
    ocr &= host->valid_ocr;
    bit = __rt_ffs(ocr);

Eureka1024 2021-06-13

嵌入式软件开发工程师一枚

明白了，谢谢解惑

请登录后再发布评论，点击登录

追加回复

3 个回答

issac_wan 2022-03-26

这家伙很懒，什么也没写！

以支持最大的优先级为32为例

线程启动时调用rt_thread_startup：

rt_err_t rt_thread_startup(rt_thread_t thread)
{
     [...]
     thread->current_priority = thread->init_priority;
     thread->number_mask = 1 << thread->current_priority;
     rt_thread_resume(thread);
     [...]
}

当优先级为0时，优先级掩码是为1的，调用rt_thread_resume将线程插入到就绪优先级链表中：

void rt_schedule_insert_thread(struct rt_thread *thread) 
{
    [...]
    rt_thread_ready_priority_group |= thread->number_mask;
    [...]
}

将位图变量rt_thread_ready_priority_group相应位置位

调用rt_schedule发起线程调度：

void rt_schedule(void)
{
    [...]
    highest_ready_priority = __rt_ffs(rt_thread_ready_priority_group) - 1;
    [...]
}

当最高优先级为0时，rt_thread_ready_priority_group最低非0 bit位是第一位，调用位图查表算法__rt_ffs

int __rt_ffs(int value)
{
    if (value == 0) return 0;
    if (value & 0xff)
        return __lowest_bit_bitmap[value & 0xff] + 1;
    if (value & 0xff00)
        return __lowest_bit_bitmap[(value & 0xff00) >> 8] + 9;
    if (value & 0xff0000)
        return __lowest_bit_bitmap[(value & 0xff0000) >> 16] + 17;
    return __lowest_bit_bitmap[(value & 0xff000000) >> 24] + 25;
}

最后返回return lowest_bit_bitmap[value & 0xff] + 1 = 1; 这里+1是因为lowest_bit_bitmap中最低有效位是从0开始的，即bit0~bit255，而rtt中认为位图变量rt_thread_ready_priority_group的最低有效位是从1开始的，即bit1~bit32，但最高优先级又是从0开始的，因此highest_ready_priority = __rt_ffs(rt_thread_ready_priority_group) - 1 = 0;因此不存在你所认为最高优先级为0时，无符号整数溢出的情况。

以上，__rt_ffs返回结果必须要+1，而if (value == 0) return 0表示不存在最低非0 bit位的情况，但在实际线程调度中是不会出现的，这样做是因为建立位图需要，方便查表，同时也是为了提高算法鲁棒性。

zhkag 2021-06-12

这家伙很懒，什么也没写！

if (value == 0) return 0;

复位的优先级是0，这一行可能是由于这个？
具体的也不太了解

Eureka1024 2021-06-12

嵌入式软件开发工程师一枚

感觉不对，调度器启动前，已经有了空闲线程，不可能有0的情况

flashman2002 2021-06-12

这家伙很懒，什么也没写！

RTT系统优先级最高为0，而不是相反。内核调度器的算法不能轻易修改，请仔细论证后再提交PR。

Eureka1024 2021-06-12

嵌入式软件开发工程师一枚

“而不是相反” 指的是？

zhkag 2021-06-12

这家伙很懒，什么也没写！

@Glen_Young 我也没看懂……..

请登录后再发布评论，点击登录

追加回复

RTT 的内核调度器寻找优先级算法的一点疑问

撰写答案

关于作者

Eureka1024

相关问题

热门标签

本月文章贡献

RTT 的内核调度器寻找优先级算法的一点疑问

撰写答案

关于作者

Eureka1024

相关问题

推荐文章

最新文章

热门标签

本月问答贡献

本月文章贡献