上一章大概分析了rt-thread操作系统的线程调试器的源码，此文具体来讲讲rt-thread在调试时，是如何获取获得当前最高优先级线程的算法过程。
之前已提到过，rt-thread采用了一个位图来实现此过程，在具体分析此过程之前，我们首先来看看此位图的结构及相关的一些参数变量。
1 位图结构及相关参数
1.1 位图结构
在rt-thread的源码文件scheduler.c中在一位图，如下定义:
const rt_uint8_t rt_lowest_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};从这里暂时我们看不出什么名堂出来，暂且跳过，且再看些与此位图相关的一些参数.
1.2 与位图相关的参数
还是在scheduler.c源文件中有一些全局变量，如下定义:
rt_list_t rt_thread_priority_table[RT_THREAD_PRIORITY_MAX];//线程就绪表，上一篇文章已有介绍struct rt_thread *rt_current_thread;//当前正在运行的线程rt_uint8_t rt_current_priority;//保存当前正在运行的线程的优先级#if RT_THREAD_PRIORITY_MAX > 32//最多优先级大于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
由上源码可知，不管用户设置定义最大优先级是多少，都存在全局变量就绪优先级组，而只有当最大优先级大于32个优先级时，才会存在另一个全局变量就就绪表，它是一个数组，含义暂先不管，接着看后述内容。
1.3 线程控制块中与位图相关的参数
之前已有介绍有关线程控制块包含的成员变量，但对其部分有关位图操作的参数并未做详情介绍，如下：
//... /* priority */ rt_uint8_t current_priority; /**< current priority */ rt_uint8_t init_priority; /**< initialized priority */#if RT_THREAD_PRIORITY_MAX > 32 rt_uint8_t number; rt_uint8_t high_mask;#endif rt_uint32_t number_mask;//...
从上述源码可知，线程控制块中，只有当用户定义的最大优先级大于32个时，才会存在number和high_mask两个成员变量，这两个成员变量及另一个成员变量number_mask都是用来作位图运算用的，只不过后面那个成员变量number_mask不管用户定义的优先级个数大于32还是在32个优先级以内都会存在。它们的含义暂且看后述内容解说.
2 参数在初始化时的变化
在thread.c源文件中的_rt_thread_init函数中:
//...thread->init_priority = priority;thread->current_priority = priority;//...得知在线程初始化时,已经将线程的当前优先级设为初始优先级.
在启动线程函数rt_thread_startup中有如下代码:
//... /* calculate priority attribute */#if RT_THREAD_PRIORITY_MAX > 32 thread->number = thread->current_priority >> 3; /* 5bit */ thread->number_mask = 1L << thread->number; thread->high_mask = 1L << (thread->current_priority & 0x07); /* 3bit */#else thread->number_mask = 1L << thread->current_priority;#endif//...
从上述代码可知,初次启动后的线程的成员number取当前优先级右移三位所得的值,即取高5位的值.
而将1左移number次所得的值做为number_mask的值,而high_mask的值取将1左移thread->current_priority &0x07后的值,即左称当前优先级低三位所代表的值.
由此可见,当用户定义的优先级等级多于32个时,优先级的高5位和低3位是表示不同含义的,看来优先级只是与位图掩码相关而已.
3 参数在线程调试过程中的变化
在线程rt_thread_startup后,系统会调用rt_thread_resume函数将线程立即运行,而在rt_thread_resume函数中,系统会调用rt_schedule_insert_thread函数将线程加入到调试器中,接着在rt_schedule_insert_thread函数中,系统会操作线程就绪表rt_thread_ready_table和线程就绪优先级组rt_thread_ready_priority_group,如下代码所示:
//...#if RT_THREAD_PRIORITY_MAX > 32 rt_thread_ready_table[thread->number] |= thread->high_mask;#endif rt_thread_ready_priority_group |= thread->number_mask;//...由上可见,系统以thread->number值作为下标,在线程就绪表rt_thread_ready_table中对应的值或上thread->high_mask,而线程就绪优先级组th_thread_ready_priority_group的值或上thread->number_mask.
4 调试中获取当前最高优先级线程过程
接下来当然是最重要的,也就是本文的核心内容啦,之前那么多内容其实都是讲相关参数是如何变化的,因为这些参数在获取最高优先级的过程中将会使用到,因此有必要对其变化过程作个说明.
在线程调试函数rt_schedule,系统使用如下代码来获取当前最高优先级线程,代码如下:
//... register rt_ubase_t highest_ready_priority;#if RT_THREAD_PRIORITY_MAX == 8 highest_ready_priority = rt_lowest_bitmap[rt_thread_ready_priority_group];//如果用户设置优先级总共为8个时最简单#else register rt_ubase_t number;//number为一中间参数 /* find out the highest priority task */ if (rt_thread_ready_priority_group & 0xff)//以rt_thread_ready_priority_group的取值人条件,然后在位图中找到number这一中间参数的值 { number = rt_lowest_bitmap[rt_thread_ready_priority_group & 0xff]; } else if (rt_thread_ready_priority_group & 0xff00) { number = rt_lowest_bitmap[(rt_thread_ready_priority_group >> 8) & 0xff] + 8; } else if (rt_thread_ready_priority_group & 0xff0000) { number = rt_lowest_bitmap[(rt_thread_ready_priority_group >> 16) & 0xff] + 16; } else { number = rt_lowest_bitmap[(rt_thread_ready_priority_group >> 24) & 0xff] + 24; }//接着再以number为因数,在位图和线程就绪表中经过一算法得到最高就绪优先级,这种算法有点怪,不是太明白为什么要这样做//其实这并不妨碍我们理解,只要理解这是一种已经做好的算法即可#if RT_THREAD_PRIORITY_MAX > 32 highest_ready_priority = (number << 3) + rt_lowest_bitmap[rt_thread_ready_table[number]];#else highest_ready_priority = number;#endif#endif /* get switch to thread */ to_thread = rt_list_entry(rt_thread_priority_table[highest_ready_priority].next,//最终从优先级算法系统中对应的就绪队列中得到相应的线程 struct rt_thread, tlist);//...5 线程失去占用CPU时的参数变化
有以下几种方式线程将失去CPU:
主动失去CPU:
1:源码中调用sleep,delay函数使用线程放弃CPU.
2:源码中调用suspend使线程挂起.
被动失去CPU:
1:线程的时间片耗尽,被迫放弃CPU.
2:系统产生中断,线程暂时失去CPU,一旦中断例程执行完,还是会还原,这些是由硬件自动完成的.
在线程主动失去CPU时,程序最终会执行rt_schedule_remove_thread函数,将当前线程从调试器中移除.而在被动失去CPU中(这里指第一种,第二种完全由硬件来完成,不需要软件干预),程序会执行rt_list_remove(&(thread->tlist));同样将当前线程从调度器中移除,然后再执行: rt_list_insert_before(&(rt_thread_priority_table[thread->current_priority]),&(thread->tlist));将当前线程加入到调试器中对应队列末尾,紧接着执行rt_schedule();重新调试线程.
由此可见,在被动失去CPU的过程中,程序并未操作与获取线程最高优先级算法相关的几个参数,接上来看看rt_schedule_remove_thread函数:
/* * This function will remove a thread from system ready queue. * * @param thread the thread to be removed * * @note Please do not invoke this function in user application. */void rt_schedule_remove_thread(struct rt_thread *thread){ register rt_base_t temp; RT_ASSERT(thread != RT_NULL); /* disable interrupt */ temp = rt_hw_interrupt_disable();#if RT_THREAD_PRIORITY_MAX <= 32 RT_DEBUG_LOG(RT_DEBUG_SCHEDULER, ("remove thread[%s], the priority: %d\n", thread->name, thread->current_priority));#else RT_DEBUG_LOG(RT_DEBUG_SCHEDULER, ("remove thread[%s], the priority: %d 0x%x %d\n", thread->name, thread->number, thread->number_mask, thread->high_mask));#endif /* remove thread from ready list */ rt_list_remove(&(thread->tlist));//将当前线程从就绪队列中移除 if (rt_list_isempty(&(rt_thread_priority_table[thread->current_priority]))) {#if RT_THREAD_PRIORITY_MAX > 32//之前参数操作的逆操作 rt_thread_ready_table[thread->number] &= ~thread->high_mask; if (rt_thread_ready_table[thread->number] == 0) { rt_thread_ready_priority_group &= ~thread->number_mask; }#else rt_thread_ready_priority_group &= ~thread->number_mask;#endif } /* enable interrupt */ rt_hw_interrupt_enable(temp);}由上述源码可见,在rt_schedule_remove_thread函数中,程序对与线程调试器获取最高优先级相关的几个参数做了逆操作.
6 后记
整个算法过程分析完毕,其实在目前为止,这里并没有对这个位图原理做出解释,个人认为,这并没多大关系,我们只需要知道,正是这么一个操作流程,结合这个位图,才得到一个与时间无关的算法.这个就是rt-thread操作系统线程调试的核心.