rt-thread操作系统的线程调度器获取当前最高优先级线程的算法

上一章大概分析了rt-thread操作系统的线程调度器的源码，此文具体来讲讲rt-thread在调试时，是如何获取获得当前最高优先级线程的算法过程。之前已提到过，rt-thread采用了一个位图来实现此过程，在具体分析此过程之前，我们首先来看看此位图的结构及相关的一些参数变量。1 位图结构及相关参数1.1 位图结构在rt-thread的源码文件scheduler.c中在一位图映射表，如下定义:cpp view plaincopyprint?1. constrt_uint8_trt_lowest_bitmap=2. 3. /*00*/0,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4. /*10*/4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5. /*20*/5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6. /*30*/4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,7. /*40*/6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,8. /*50*/4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,9. /*60*/5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,10. /*70*/4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,11. /*80*/7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,12. /*90*/4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,13. /*A0*/5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,14. /*B0*/4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,15. /*C0*/6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,16. /*D0*/4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,17. /*E0*/5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,18. /*F0*/4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,019. ;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源文件中有一些全局变量，如下定义:cpp view plaincopyprint?1. rt_list_trt_thread_priority_tableRT_THREAD_PRIORITY_MAX;/线程就绪表，上一篇文章已有介绍 2. structrt_thread*rt_current_thread;/当前正在运行的线程 3. 4. rt_uint8_trt_current_priority;/保存当前正在运行的线程的优先级 5. 6. #ifRT_THREAD_PRIORITY_MAX32/最多优先级大于32时 7. /*Maximumprioritylevel,256*/8. rt_uint32_trt_thread_ready_priority_group;/暂且叫做就绪优先级组 9. rt_uint8_trt_thread_ready_table32;/暂且叫做就绪表,实际用做第一级位图 10. #else 11. /*Maximumprioritylevel,32*/12. rt_uint32_trt_thread_ready_priority_group;/就绪优先级组,实际用做第二级位图 13. #endifrt_list_t rt_thread_priority_tableRT_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_table32;/暂且叫做就绪表,实际用做第一级位图#else/* Maximum priority level, 32 */rt_uint32_t rt_thread_ready_priority_group;/就绪优先级组,实际用做第二级位图#endif由上源码可知，不管用户设置定义最大优先级是多少，都存在全局变量就绪优先级组，而只有当最大优先级大于32个优先级时，才会存在另一个全局变量就就绪表，它是一个数组，含义暂先不管，接着看后述内容。 1.3 线程控制块中与位图相关的参数之前已有介绍有关线程控制块包含的成员变量，但对其部分有关位图操作的参数并未做详情介绍，如下：cpp view plaincopyprint?1. /. 2. /*priority*/3. rt_uint8_tcurrent_priority;/*currentpriority*/4. rt_uint8_tinit_priority;/*32 6. rt_uint8_tnumber;7. rt_uint8_thigh_mask;8. #endif 9. rt_uint32_tnumber_mask;10. /./. /* priority */ rt_uint8_t current_priority; /* current priority */ rt_uint8_t init_priority; /* 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函数中:cpp view plaincopyprint?1. /. 2. thread-init_priority=priority;3. thread-current_priority=priority;4. /./.thread-init_priority = priority;thread-current_priority = priority;/.得知在线程初始化时,已经将线程的当前优先级设为初始优先级. 在启动线程函数rt_thread_startup中有如下代码:cpp view plaincopyprint?1. /. 2. /*calculatepriorityattribute*/3. #ifRT_THREAD_PRIORITY_MAX32 4. thread-number=thread-current_priority3;/*5bit*/5. thread-number_mask=1Lnumber;6. thread-high_mask=1Lcurrent_priority&0x07);/*3bit*/7. #else 8. thread-number_mask=1Lcurrent_priority;9. #endif 10. /./. /* calculate priority attribute */#if RT_THREAD_PRIORITY_MAX 32 thread-number = thread-current_priority 3; /* 5bit */ thread-number_mask = 1L number; thread-high_mask = 1L current_priority & 0x07); /* 3bit */#else thread-number_mask = 1L 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,如下代码所示:cpp view plaincopyprint?1. /. 2. #ifRT_THREAD_PRIORITY_MAX32 3. rt_thread_ready_tablethread-number|=thread-high_mask;4. #endif 5. rt_thread_ready_priority_group|=thread-number_mask;6. /./.#if RT_THREAD_PRIORITY_MAX 32 rt_thread_ready_tablethread-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,系统使用如下代码来获取当前最高优先级线程,代码如下:cpp view plaincopyprint?1. /. 2. registerrt_ubase_thighest_ready_priority;3. 4. #ifRT_THREAD_PRIORITY_MAX=8 5. highest_ready_priority=rt_lowest_bitmaprt_thread_ready_priority_group;/如果用户设置优先级总共为8个时最简单 6. #else 7. registerrt_ubase_tnumber;/number为一中间参数 8. /*findoutthehighestprioritytask*/9. if(rt_thread_ready_priority_group&0xff)/以rt_thread_ready_priority_group的取值人条件,然后在位图中找到number这一中间参数的值 10. 11. number=rt_lowest_bitmaprt_thread_ready_priority_group&0xff;12. 13. elseif(rt_thread_ready_priority_group&0xff00)14. 15. number=rt_lowest_bitmap(rt_thread_ready_priority_group8)&0xff+8;16. 17. elseif(rt_thread_ready_priority_group&0xff0000)18. 19. number=rt_lowest_bitmap(rt_thread_ready_priority_group16)&0xff+16;20. 21. else22. 23. number=rt_lowest_bitmap(rt_thread_ready_priority_group24)&0xff+24;24. 25. /接着再以number为因数,在位图和线程就绪表中经过一算法得到最高就绪优先级,这种算法有点怪,不是太明白为什么要这样做 26. /其实这并不妨碍我们理解,只要理解这是一种已经做好的算法即可 27. #ifRT_THREAD_PRIORITY_MAX32 28. highest_ready_priority=(number 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 tlist);同样将当前线程从调度器中移除,然后再执行:rt_list_insert_before(&(rt_thread_priority_tablethread-current_priority),&(thread-tlist);将当前线程加入到调度器中对应队列末尾,紧接着执行rt_schedule();重新调度线程. 由此可见,在被动失去CPU的过程中,程序并未操作与获取线程最高优先级算法相关的几个参数,接上来看看rt_schedule_remove_thread函数:cpp view plaincopyprint?1. /*2. *Thisfunctionwillremoveathreadfromsystemreadyqueue.3. *4. *paramthreadthethreadtoberemoved5. *6. *notePleasedonotinvokethisfunctioninuserapplication.7. */8. voidrt_schedule_remove_thread(structrt_thread*thread)9. 10. registerrt_base_ttemp;11. 12. RT_ASSERT(thread!=RT_NULL);13. 14. /*disableinterrupt*/15. temp=rt_hw_interrupt_disable();16. 17. #ifRT_THREAD_PRIORITY_MAXname,thread-current_priority);20. #else 21. RT_DEBUG_LOG(RT_DEBUG_SCHEDULER,22. (removethread%s,thepriority:%d0x%x%dn,23. thread-name,24. thread-number,25. thread-number_mask,26. thread-high_mask);27. #endif 28. 29. /*removethreadfromreadylist*/30. rt_list_remove(&(thread-tlist);/将当前线程从就绪队列中移除 31. if(rt_list_isempty(&(rt_thread_priority_tablethread-current_priority)32. 33. #ifRT_THREAD_PRIORITY_MAX32/之前参数操作的逆操作 34. rt_thread_ready_tablethread-number&=thread-high_mask;35. if(rt_thread_ready_tablethread-number=0)36. 37. rt_thread_ready_priority_group&=thread-number_mask;38. 39. #else 40. rt_thread_ready_priority_group&=thread-number_mask;41. #endif 42. 43. 44. /*enableinterrupt*/45. rt_hw_interrupt_enable(temp);46. /* * 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_ASSER