RT-Thread 的线程调度器是如何查找到优先级最高的任务的？

一命二运三风水，四积阴德五读书，六名七相八敬神，九交贵人十养生。
---- 民间出品
冯唐解读成功十要素：一命二运三风水，四积阴德五读书六名七相八敬神

打开 RT-Thread 内核中的 scheduler.c，我们可以看到如下的代码：

rt_list_t rt_thread_priority_table[RT_THREAD_PRIORITY_MAX];
#if RT_THREAD_PRIORITY_MAX > 32
/* Maximum priority level, 256 */
rt_uint32_t rt_thread_ready_priority_group;
rt_uint8_t rt_thread_ready_table[32];
#else
/* Maximum priority level, 32 */
rt_uint32_t rt_thread_ready_priority_group;
#endif

其中 rt_thread_priority_table[RT_THREAD_PRIORITY_MAX] 是根据设置的最大优先级设置大小的数组，对应优先级的线程会挂载到对应的位置。

rt_thread_ready_priority_group 和 rt_thread_ready_table[32] 标识着此时所有就绪线程的优先级情况，线程进入就绪状态和线程脱离就绪状态都会实时更新这两个变量的值。

• 先讨论当最大优先级数量小于等于 32 的情况。

  rt_thread_ready_priority_group 是一个 32 bit的变量，每一个比特对应着一个优先级，比如第 0 位对应着优先级 0，该位为1，说明有优先级0的线程正在就绪，数字越小优先级越高。

  那么问题了，当同时有多个不同线程同时就绪时，如何找到优先级最高的线程？

  先看看，如果是 8bit的变量，如何查找到最低位的 1 RT-Thread 使用的是位图查询的方法，这是一种空间换时间的一种策略，也就是维护如下的查询数组：

  const rt_uint8_t __lowest_bit_bitmap[] =
  {/* 00 */ 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* 10 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* 20 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* 30 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* 40 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* 50 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* 60 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* 70 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* 80 */ 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* 90 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* A0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* B0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* C0 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* D0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* E0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,/* F0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
  };
  

  8bit的变量，意味着有256种情况，所以这是一个256大小的数组，数组的内容是无论你输入0-255之间哪个数，就能返回最低的那一位所处的位置，这样我们就能够在 O(1) 的时间内得到最高优先级的结果。

  那么32位也就简单了，我们要不也搞一个这样的数组？算一下如果要满足要求，需要 2^32 * byte = 4GB 的存储空间，各位单片机的那弱小的身板怎么扛得住？

  RT-Thread 采取是将 32bit 拆成 4 个 8bit，这样就能省不少空间，看一下 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;
  }
  

  其实也就是多加了几个判断，虽不能一步到位，但也算是一种比较好的折中的方法吧。

  查找当前最高优先级的方法如下：

  highest_ready_priority = __rt_ffs(rt_thread_ready_priority_group) - 1;
  

• 当线程的优先级数量大于 32 时（RT-Thread最大支持到 256，这个数量绝对够用了）

  针对这种情况，RT-Thread 采用的是二级位图的算法。

  我们看源码，可以知道，此时多定义了 rt_thread_ready_table[32] 这个数组，用 bit 的视角来看，也就是 32*8 = 256 bit，就是优先级的最大数量。

  其实 rt_thread_ready_table[32] 此时就充当着标识此时哪一个优先级有任务就绪的角色。

  而 rt_thread_ready_priority_group 这个32位的变量就充当一个查找 rt_thread_ready_table[32] 这个32大小的数组哪一个字节有线程处在就绪状态。

  此时查找最高优先级的算法如下：

  register rt_ubase_t number;
  //先找到最高优先级处在rt_thread_ready_table[number]哪个位置
  number = __rt_ffs(rt_thread_ready_priority_group) - 1;
  //再结合 number 和 rt_thread_ready_table 得到最高优先级
  //右移3位相当于乘8
  highest_ready_priority = (number << 3) + __rt_ffs(rt_thread_ready_table[number]) - 1;
  

总结：RT-Thread 的优先级查找算法能够在 O(1) 的时间复杂度内找到最高的优先级线程，保证了线程调度的实时性，同时，采用优先级数量最大为 32 以内是比较好的，不仅省空间，同时只使用到一级位图，也能运行地更快。

网上有一篇文章，写的更详细，可以查看：RT-Thread的位图调度算法分析（最新版）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！