谷动谷力

标题: 【RT-Thread内核详解系列】基于优先级的全抢占式调度算法... [打印本页]
作者: sunsili    时间: 2022-2-8 23:06
标题: 【RT-Thread内核详解系列】基于优先级的全抢占式调度算法...
本帖最后由 sunsili 于 2022-2-13 21:09 编辑

                                                        【RT-Thread内核详解系列】基于优先级的全抢占式调度算法的实现                                                                            

                                                                                    
The unexamined life is not worth living.
未经审视的人生是不值得过的。
-- 苏格拉底

一、原理概述

RT-Thread 是一款嵌入式实时操作系统（RTOS），同时也是一款优秀的物联网操作系统，相对于裸机的轮询调度算法，它使用的线程（任务）调度算法是基于优先级的全抢占式多线程调度算法，该算法大大增强了系统的实时响应，大大扩展了系统的应用场景。

该调度算法在每次调度任务时，总会选择优先级最高的就绪任务执行，保证优先级高的任务得到最及时的响应。

下面，我们来详细讲解该调度算法的原理和具体实现。

注：本文基于 RT-Thread 的版本为 RT-Thread v4.0.5 released， 其发布于 2021-12-31。

首先，RT-Thread 中定义了一个双向链表数组 rt_thread_priority_table，用来挂载就绪的线程，代码如下所示：
  1. /* Double List structure*/
  2. struct rt_list_node{
  3.     struct rt_list_node *next;                          
  4.   /**< point to next node. */   
  5.    struct rt_list_node *prev;                          
  6. /**< point to prev node. */
  7. };

  9. typedef struct rt_list_node rt_list_t;                  

  11. /**< Type for lists. */
  12. rt_list_t rt_thread_priority_table[RT_THREAD_PRIORITY_MAX]; //线程优先级双向链表数组
复制代码

其实实现的就是如下的结构：


其中 RT_THREAD_PRIORITY_MAX 代表的是该系统配置的优先级数目，RT-Thread 的调度算法只支持 RT_THREAD_PRIORITY_MAX <= 256，这个数目绝对够绝大多数的项目需求了。而 rt_thread_priority_table[RT_THREAD_PRIORITY_MAX] 这个数组从 0 到 RT_THREAD_PRIORITY_MAX-1的数组元素则是分别对应任务的优先级从 0 到 RT_THREAD_PRIORITY_MAX-1。

当有线程就绪时，线程会挂载到其优先级对应的线程优先级表(rt_thread_priority_table)元素的位置，假设现在有两个线程，分别是优先级为 0 的 thread1 和优先级为 1 的 thread2，当它们都进入就绪状态等待调度时，效果如下：


此时问题来了，当任务们都进入就绪状态，挂载在这个线程优先级表(rt_thread_priority_table)上时，我们如何查找到所有就绪任务中拥有最高优先级的那个呢？

首先，我们想到可以从线程优先级表(rt_thread_priority_table)的位置 0 开始查找，一旦发现哪个位置有挂载线程，则说明该优先级下有对应的任务就绪了，执行该线程即可。当下一次调度任务时，又按刚才的步骤从 0 开始查找即可，这不失为一个能解决问题的方法。

但是细细想来，如果就绪任务中的最高优先级比较靠后，这样的查找算法几乎要遍历一遍，明显很耗时间，一点都配不上实时操作系统（RTOS）中 “实时”这两个字。

为了更高效地调度任务，RT-Thread 使用了线程就绪表（rt_thread_ready_table）映射来实现的，简单的说，就是维护一个记录已就绪任务的表，通过查找这个表，我们就能够知道当前就绪任务中最高优先级的任务是哪一个，然后直接执行该优先级下的任务即可。


具体来说，这个线程就绪表（rt_thread_ready_table）的位数和优先级是一一对应的，当这个表的某一位为1时，代表这个优先级下有任务就绪。
RT-Thread 作为多任务调度系统，各个任务由于外部条件的触发，要经常在就绪状态和非就绪状态中切换（对应到数据结构就是：任务的双向指针插入或者脱离 rt_thread_priority_table ），所以作为映射的线程就绪表（rt_thread_ready_table）也要根据任务们的状态随时更新，对应到这个表，无非就是当某个优先级下没有任务时，将这个表对应的位清0，当有任务挂载在该优先级下时，将这个就绪表的位置1。

我们通过这个表，能够在 O(1) 的时间复杂度上找到最高优先级的任务，实现了快速地调度最高优先级任务。在切换任务的状态时，实时更新这张表的内容，确保线程就绪表（rt_thread_ready_table）和线程优先级表(rt_thread_priority_table)相互对应的结果是正确的。

接下来到了 show the code 时间了，可能会耗点脑细胞了。

二、实现细节


先来看看线程就绪表（rt_thread_ready_table）的代码实现形式：
  1. /* 线程优先级就绪组，当RT_THREAD_PRIORITY_MAX<=32时，每一位直接对应32个优先级，否则分别映射到rt_thread_ready_table）*/

  3. rt_uint32_t rt_thread_ready_priority_group;
  4. #if RT_THREAD_PRIORITY_MAX > 32
  5. /* Maximum priority level, 256 */
  6. rt_uint8_t rt_thread_ready_table[32];
  7. //对应 32*8(位) = 256个优先级
  8. #endif
复制代码

根据 RT_THREAD_PRIORITY_MAX  这个宏定义的不同，线程就绪表（rt_thread_ready_table）的实现方式有两种：

在谈到具体如何使用、更新线程就绪表（rt_thread_ready_table）之前，看看具体某个优先级任务的结构体有哪些是和调度算法相关的。如下是任务线程的结构体的定义，我将无关的变量删除，只留下所有相关的变量：
  1. /** * Thread structure */
  2. struct rt_thread{
  3.     .......
  4.     rt_list_t   tlist;
  5.      /**< the thread list 用于挂载在线程优先级表中*/
  6.     /* priority */
  7.     rt_uint8_t  current_priority;

  9.       /**< current priority 当前优先级*/
  10.    rt_uint8_t  init_priority;
  11.      /**< initialized priority 初始优先级*/
  12. #if  RT_THREAD_PRIORITY_MAX > 32
  13.     rt_uint8_t  number;
  14.     //标记为是rt_thread_ready_table[32]中的哪个元素
  15.     rt_uint8_t  high_mask;  //具体元素对应的掩码,用于加快操作速度
  16. #endif

  18.     rt_uint32_t number_mask; //rt_thread_ready_priority_group对应的掩码，用于加快操作速度
  19.     .......
  20. };

  22. typedef struct rt_thread *rt_thread_t;
复制代码

简单提及一个这里的掩码的作用，目的是为了方便后面对线程优先级就绪表进行操作。举个例子，假设有一个优先级(priority)为 20 的任务，那么其对应的线程结构的掩码情况如下：
对于 RT_THREAD_PRIORITY_MAX <= 32：
number_mask = 1<<20(priority);  即number_mask：000100000000000000000000，就是让 number_mask 的第 19 位为1。

话说回来，为什么要设置 number_mask 这个变量呢？遇到要使用这个变量的时候直接使用 1<<priority 代替 number_mask 不就可以了吗？其实也不是不可以，只是这样使用的话，需要多进行一次位移操作，这其实也是一种用空间换时间的策略，付出一个变量的代价获取更快的运算速度，增加了实时系统的调度任务的速度，也算是有利于系统的实时性。

对于 RT_THREAD_PRIORITY_MAX > 32，原理是一样的，就不赘述了。

RT-Thread是如何初始化上述的变量的呢？

在线程的初始化函数中（无论是动态创建线程还是静态初始化线程），根据传入的优先级参数进行操作，主要是用作初始化：
  1. rt_err_t _thread_init(...,priority)
  2. {
  3.     ......
  4.     /* priority init */
  5.     RT_ASSERT(priority < RT_THREAD_PRIORITY_MAX);
  6.     thread->init_priority    = priority;
  7.     thread->current_priority = priority;
  8.     thread->number_mask = 0;
  9. #if    RT_THREAD_PRIORITY_MAX > 32
  10.     thread->number = 0;
  11.     thread->high_mask = 0;
  12. #endif
  13.        ......
  14. }
复制代码

当启动线程时，更新线程对应的数据：
  1. rt_err_t rt_thread_startup(rt_thread_t thread)
  2. {
  3.     ......
  4.      /* calculate priority attribute */
  5. #if     RT_THREAD_PRIORITY_MAX > 32
  6.     thread->number      = thread->current_priority >> 3;      /* 相当于除以8，得到对应所处的是哪个数组 */
  7.     thread->number_mask = 1L << thread->number;             /* 得到对应所处的数组位置的掩码 */
  8.     thread->high_mask   = 1L << (thread->current_priority & 0x07);  /* 具体到对应的数组元素的掩码 */
  9. #else
  10.     thread->number_mask = 1L << thread->current_priority;
  11.    /* 掩码 *
  12. #endif
  13.      ......
  14. }
复制代码

一切准备就绪，接下来看看当调度器调度任务时是怎么操作优先级就绪表的。

2.1、如何查找当前就绪任务中的最高优先级


其实就是查找优先级就绪表最靠近前面的1所处的位置，每次进行任务调度的时候会用到这个表去获得最高优先级，然后根据最高优先级得到此时就绪的最高优先级线程。
  1. //该函数用于获取当前已就绪的最高优先级任务
  2. static struct rt_thread* _scheduler_get_highest_priority_thread(rt_ubase_t *highest_prio)
  3. {
  4.    ......        
  5. #if     RT_THREAD_PRIORITY_MAX > 32
  6.     register rt_ubase_t number;    //得到是数组rt_thread_ready_table的哪个元素
  7.     number = __rt_ffs(rt_thread_ready_priority_group) - 1;    //右移3位则是*8的意思，得到该数组的基地址，最后加上在该组的位置，就可以得到真正的优先级
  8.     highest_ready_priority = (number << 3) + __rt_ffs(rt_thread_ready_table[number]) - 1;
  9. #else
  10.     //直接得到具体的优先级
  11.     highest_ready_priority = __rt_ffs(rt_thread_ready_priority_group) - 1;
  12. #endif
  13. /* RT_THREAD_PRIORITY_MAX > 32 */
  14.         ......
  15. }
复制代码

重点说一下这里的 __rt_ffs()  函数，该函数实现的功能：得到传入的 32 位变量中 1 所在的最低位位置，也就是所谓的实现查找字节最低非0位。该函数能够在 O(1)的时间复杂度下实现查找到最低优先级，其使用的是位图查找算法，还是挺精妙的，由于篇幅有限，请移步到这篇文章：《RT-Thread的位图调度算法分析（最新版）》。

2.2、当任务就绪时，如何更新线程就绪列表？


如果某个任务就绪，根据该任务的优先级更新线程就绪表rt_thread_ready_table对应位置。
  1. //该函数用于将新的任务加入就绪状态
  2. void rt_schedule_insert_thread(struct rt_thread *thread)
  3. {
  4.     ......
  5. #if
  6.     RT_THREAD_PRIORITY_MAX > 32    rt_thread_ready_table[thread->number] |= thread->high_mask; //让对应的优先级所在分组的具体位置1，表明就绪
  7. #endif
  8.     rt_thread_ready_priority_group |= thread->number_mask; //让对应的优先级所在分组位置置1
  9.        ......
  10. }
复制代码



2.3、当任务脱离就绪状态时，如何更新线程就绪列表？

当某个任务脱离就绪状态时（被删除、挂起等），我们也需要更新更新线程就绪表rt_thread_ready_table，由于RT-Thread支持多个任务可以拥有相同的优先级，所以我们在更新线程就绪表rt_thread_ready_table需要考虑该优先级下是否有别的任务还处于就绪状态。
  1. //该函数用于将某个任务从就绪状态中移除
  2. void rt_schedule_remove_thread(struct rt_thread *thread)
  3. {
  4.     ......
  5.    if (rt_list_isempty(&(rt_thread_priority_table[thread->current_priority])))//说明该优先级下没有别的就绪任务了
  6.    {
  7. #if         RT_THREAD_PRIORITY_MAX > 32
  8.         rt_thread_ready_table[thread->number] &= ~thread->high_mask;  //让对应的优先级所在分组的具体位 置0，表明脱离就绪状态               if (rt_thread_ready_table[thread->number] == 0) //当这个数组元素的每个bit都是0，才能够置0，因为可能所处的组还有别的任务就绪      
  9.       {
  10.                  rt_thread_ready_priority_group &= ~thread->number_mask;//将该表的对应位置清0
  11.        }
  12. #else
  13.        rt_thread_ready_priority_group &= ~thread->number_mask; //将该表的对应位置清0

  15. #endif /* RT_THREAD_PRIORITY_MAX > 32 */
  16.    }
  17.        .....
  18. }
复制代码

三、一些有用的建议


四、参考资料






欢迎光临 谷动谷力 (http://bbs.sunsili.com/) Powered by Discuz! X3.2