rtos学习之支持多优先级

2024-02-02 13:48:40

1、就绪列表

RT-Thread 要支持多优先级，需要靠就绪列表的支持，从代码上看，就绪列表由两个在schedule.c文件定义的全局变量组成，一个是线程就绪优先级组rt_thread_ready_priority_group,另一个是线程优先级表rt_thread_priority_table[RT_THREAD_PRIORITY_MAX].

2、线程就绪优先级组

为了快速找到线程在线程优先级表的插入和移除的位置，RT-Thread专门设置了一个线程就绪优先级组。从代码上看，线程就绪优先级组就是一个32位的整数，每一个位对应一个优先级。一个就绪优先级组最多只能表示32个优先级。如果优先级超过32个怎么办，则可以定义一个线程就绪优先级数组，每一个数组成员都可以表示32个优先级。具体支持到多少由系统的RAM大小决定。线程就绪优先级组在schedule.c中定义

/* 线程就绪优先级组 */
rt_uint32_t rt_thread_ready_priority_group;

那么线程就绪优先级组是如何帮助系统快速地找到线程在线程优先级表的插入和移除的位置？线程就绪优先级组的每一个位对应一个优先级，位 0 对应优先级 0，位 1 对应优先级 1，以此类推。比如，当优先级为 10 的线程已经准备好，那么就将线程就绪优先级组的位 10 置 1，表示线程已经就绪，然后根据 10 这个索引值，在线程优先级表 10（rt_thread_priority_table[10]）的这个位置插入线程。

3、寻找优先级最高的线程

RT-Thread 是一个根据优先级来调度的抢占式实时操作系统，即在每个系统周期到来时，调度器都会扫描就绪列表，选取优先级最高的线程去执行。假设目前系统中，创建了优先级分别为 1、2和 3 的线程 1、线程 2 和线程 3，再加上系统默认创建的空闲线程，那么此时线程就绪优先级组的位设置情况和线程优先级表的链表挂载情况就如图线程就绪优先级组的位设置情况和图线程优先级表的链表挂载情况所示那样。

注意：当线程准备好，先在线程就绪优先级组的相应的位置1，然后再将线程插入线程优先级表。

在系统的下一个系统周期到来时，调度器需要选取优先级最高的线程去执行。从图线程就绪优先级组的位设置情况我们一眼就可以看出线程就绪优先级组从右往左开始数，第一个置 1 的位是位 1，即表示此时就绪的线程当中，优先级最高的是线程 1，然后调度器从线程优先级表的索引 1 下取出线程 1 的线程控制块，从而切换到线程 1。但是，单片机没有眼睛，并不能跟人一样一眼就从线程就绪优先级组中看到那个第一个置 1 的位，怎么办？RT-Thread kservice.c 文件中，有一个专门的函数 __rt_ffffs，用来寻找 32 位整形数第一个（从低位开始）置 1 的位号，具体实现如下：

/**
* 该函数用于从一个 32 位的数中寻找第一个被置 1 的位（从低位开始），
* 然后返回该位的索引（即位号）
* 
* @return 返回第一个置 1 位的索引号。如果全为 0，则返回 0。 
*/
int __rt_ffs(int value)
{ 
　　/* 如果值为 0，则直接返回 0 */
　　if (value == 0) return 0; (1)

　　/* 检查 bits [07:00]
　　这里加 1 的原因是避免当第一个置 1 的位是位 0 时
　　返回的索引号与值都为 0 时返回的索引号重复 */
　　if (value & 0xff) (2)
　　　　return __lowest_bit_bitmap[value & 0xff] + 1;

　　/* 检查 bits [15:08] */
　　if (value & 0xff00) (3)
　　　　return __lowest_bit_bitmap[(value & 0xff00) >> 8] + 9;

　　/* 检查 bits [23:16] */
　　if (value & 0xff0000)
　　　　return __lowest_bit_bitmap[(value & 0xff0000) >> 16] + 17;

　　/* 检查 bits [31:24] */ (5)
　　　　return __lowest_bit_bitmap[(value & 0xff000000) >> 24] + 25;
}

(1)：如果值为 0，则直接返回 0。 (2)：检查 bits [07:00]，然后通过 __lowest_bit_bitmap[value & 0xffff]+1返回第一个置 1 的位号，这里加 1 的原因是避免当第一个置 1 的位是位 0 时返回的索引号与值都为 0 时返回的索引号重复，返回 1 表示优先级为 0 就绪，使用这个索引号的时候再减 1 即可。现在我们在具体分析下 __lowest_bit_bitmap[] 这个数组，该数组在 kservice.c 中定义，具体见

/*
* __lowest_bit_bitmap[] 数组的解析
* 将一个 8 位整形数的取值范围 0~255 作为数组的索引，索引值第一个出现 1(从最低位开始) 的位号作为该数组索引下的成员值。
 * 举例：十进制数 10 的二进制为：0000 1010, 从最低位开始，第一个出现 1 的位号为 bit1，则有__lowest_bit_bitmap[10]=1
* 注意：只需要找到第一个出现 1 的位号即可
 */
 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
 };

要从一个 8 位整形数中从低位开始找出第一个置 1 的位，常规的方法是从低位开始一位一位的判断，优点是逻辑简单好理解，缺点是耗时，这里采取一种空间换时间的方法，即：将 8 位整形数的取值范围 0~255 作为数组 __lowest_bit_bitmap[] 的索引，索引值第一个出现 1(从最低位开始) 的位号作为该数组索引下的成员值。举例：十进制数 10 的二进制为：00001010，从最低位开始，第一个出现 1 的位号为 bit1，则有 __lowest_bit_bitmap[10]=1。注意：只需要找到第一个出现 1 的位号即可。

4、线程优先级表

线程优先级表是一个在 scheduler.c 中定义的全局数组

/* 线程优先级表 */
rt_list_t rt_thread_priority_table[RT_THREAD_PRIORITY_MAX];

线程优先级表的数据类型为 rt_list，每个索引号对应线程的优先级，该索引下维护着一条双向链表，当线程就绪时，线程就会根据优先级插入到对应索引的链表，同一个优先级的线程都会被插入到同一条链表中（当同一个优先级下有多个线程时，需要时间片的支持）。一个空的就绪列表和一个有 4 个线程就绪的就绪列表示意图具体见图空的就绪列表和有 5 个线程就绪的就绪列表。

将线程插入到线程优先级表和移除分别由 scheduler.c 的 rt_schedule_insert_thread() 和rt_schedule_remove_thread() 这两个函数实现。

调度器插入线程

void rt_schedule_insert_thread(struct rt_thread *thread) 
{ 
　　register rt_base_t temp;
　　/* 关中断 */
　　temp = rt_hw_interrupt_disable();
　　/* 改变线程状态 */
　　thread->stat = RT_THREAD_READY;

　　/* 将线程插入就绪列表 */
　　rt_list_insert_before(&(rt_thread_priority_table[thread->current_priority]),&(thread->tlist));

　　/* 设置线程就绪优先级组中对应的位 */
　　rt_thread_ready_priority_group |= thread->number_mask;

　　/* 开中断 */
　　rt_hw_interrupt_enable(temp);
}

调度器删除线程

void rt_schedule_remove_thread(struct rt_thread *thread) 
{ 
　　register rt_base_t temp;
　　/* 关中断 */
 　temp = rt_hw_interrupt_disable();
   /* 将线程从就绪列表删除 */
   rt_list_remove(&(thread->tlist));

　　if (rt_list_isempty(&(rt_thread_priority_table[thread->current_priority])))
　　{
　　　　rt_thread_ready_priority_group &= ~thread->number_mask;
　　}

　　/* 开中断 */
　　rt_hw_interrupt_enable(temp);
}

码农公寓