RT-thread内核之线程调度算法

⼀个操作系统如果只是具备了⾼优先级任务能够“⽴即”获得处理器并得到执⾏的特点，那么它仍然不算是实时操作系统。因为这个查找最⾼优先级线程的过程决定了调度时间是否具有确定性，例如⼀个包含n个就绪任务的系统中，如果仅仅从头找到尾，那么这个时间将直接和n相关，⽽下⼀个就绪线程抉择时间的长短将会极⼤的影响系统的实时性。当所有就绪线程都链接在它们对应的优先级队列中时，抉择过程就将演变为在优先级数组中寻找具有最⾼优先级线程的⾮空链表。

RT-Thread内核中采⽤了基于位图(bitmap)的优先级算法（时间复杂度O(1)，即与就绪线程的多少⽆关），通过位图的定位快速的获得优先级最⾼的线程。⼤致来说，就是每次调度的时间是恒定的：⽆论当前的系统中存在多少个线程，多少个优先级，rt-thread的调度函数总是可以在⼀个恒定的时间内选择出最⾼优先级的那个线程来执⾏。对不同优先级的线程，RT-Thread采⽤可抢占的⽅式：即⾼优先级的线程会“⽴刻”抢占低优先级的线程。

RT-Thread内核中也允许创建相同优先级的线程。相同优先级的线程采⽤时间⽚轮转⽅式进⾏调度（也就是通常说的分时调度器），时间⽚轮转调度仅在当前系统中⽆更⾼优先级就绪线程存在的情况下才有效。每个线程的时间⽚⼤⼩都可以在初始化或创建这个线程时指定。在src/scheduler.c中：

rt_list_t rt_thread_priority_table[RT_THREAD_PRIORITY_MAX];//就绪线程优先级链表数组（在rt_schedule_insert_thread函数中将线程设置为就绪状态后，将当前线程链表节点插⼊对应优先级线程链表中）

struct rt_thread *rt_current_thread; //保存当前运⾏的线程（在线程跳转时设置为⽬标线程to_thread）

rt_uint8_t rt_current_priority; //保存当前运⾏线程优先级（在线程跳转时设置为⽬标线程to_thread的优先级）

#if RT_THREAD_PRIORITY_MAX > 32 /* Maximum priority level, 256 */

rt_uint32_t rt_thread_ready_priority_group;//32位⼆级位图，⽤于查找⼀级位图中32个字节的最低⾮0字节（即当前所有就绪线程中最⾼优先级对应的字节）

rt_uint8_t rt_thread_ready_table[32]; //256位⼀级位图，代表32个字节，分别对应256个线程优先级。⽐如第⼀个字节的bit0表⽰优先级0，bit7表⽰优先级7。第⼆个字节bit0表⽰优先级8，bit7表⽰优先级15#else

/* Maximum priority level, 32 */

rt_uint32_t rt_thread_ready_priority_group;/32位位图变量，当Maximum priority level==32时，可看成⼀级位图，该变量32bit分别对应32个线程优先级（0-31）#endif

1、当最⼤优先级为8时：

若最⼤优先级取8，则位图变量可⽤⼀个字节表⽰，且取值范围为0-255，字节的每⼀位分别对应优先级0-7。当位图变量取0-255之间的任意⼀个数字时，它的最低为1的BIT位置都是预知的。我们可以预先将这位图变量的所有取值对应的最低为1的BIT位置（最⾼优先级）计算出来，并存成⼀张表格，⽽只需要查表即可，这个执⾏时间⾃然是恒定的。实际上，查表法就是⼀种常⽤的⽤空间换取时间的⽅法。在src/kservice.c中：

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};

上表可由下⾯的python简单程序⽣成：

#coding=gbk

#打印⼀个字节的最低bit位，可能的值为0,1,2,3,4,5,6,7 samples = 256

def getlowbit(byte): c = 0

for i in range(0,8): if(byte & 0x01): return c c = c+1

byte = byte >> 1 return 0

line =\"\"

for i in range(0,samples): print \"%d,\" %getlowbit(i), if((i+1)%16 == 0): print \"\\n\"

2、当最⼤优先级为32时：

当进程优先级为8时，我们可以通过查表直接解决，但是当系统存在32个优先级时，如果直接制作表格的话，这个表格的元素个数将是 2^32 = 4294967296L= 4G字节，显然这是不可接受的。若当前最⼤优先级为32，即优先级位图变量可以使⽤u32型，也就是等价于4个字节，我们可以对这4个字节从字节0开始依次查表，如果字节0中⾮0，则最⾼优先级⼀定存在于字节0中，我们对字节0查表rt_lowest_bitmap，即可以得到最⾼优先级。 如果字节0为0，字节1⾮0，我们对字节1查表得到的是字节1中为1的最低bit位，然后加上8，就是系统的最⾼优先级。对字节2，字节3同样处理。当Maximum priority level==32时，则位图变量为：

/* Maximum priority level, 32 */

rt_uint32_t rt_thread_ready_priority_group; //32位位图变量，当Maximum priority level==32时，该变量32bit分别对应32个线程优先级

/*

* rt_thread_ready_priority_group ⽤来表⽰当前系统优先级位图。 * highest_ready_priority表⽰当前系统中最⾼优先级 */

这⾥仅仅说明如何获取最⾼优先级，在实际源码中可能有⼀些⼩改动。

if (rt_thread_ready_priority_group & 0xff) {

highest_ready_priority = __lowest_bit_bitmap[rt_thread_ready_priority_group & 0xff]; }

else if (rt_thread_ready_priority_group & 0xff00) {

highest_ready_priority = __lowest_bit_bitmap[(rt_thread_ready_priority_group >> 8) & 0xff] + 8; }

else if (rt_thread_ready_priority_group & 0xff0000) {

highest_ready_priority = __lowest_bit_bitmap[(rt_thread_ready_priority_group >> 16) & 0xff] + 16; } else {

highest_ready_priority = __lowest_bit_bitmap[(rt_thread_ready_priority_group >> 24) & 0xff] + 24; }

3、当最⼤优先级为256时：

现在我们解决了32个系统优先级时的调度问题，现在来考虑线程优先级为256的情况。读者可能会想了，这没什么不同，256个bit=32个字节，依然采⽤算法3的思路，对着32个字节依次查表。问题是，当位图变量有32个字节时，对这32个字节依次

查表耗费的时间就不可以忽略了，为了提升系统实时调度的性能，我们需要对算法3进⾏改进。为了解决这个问题，我们使⽤⼆级位图。即，256个bit由32个字节存储，每⼀个字节的8个bit代表着位图变量中的8个优先级，如果某个字节⾮0，则表⽰其中必有⾮0的bit位。rtt中对应的数组为:

rt_uint8_t rt_thread_ready_table[32]; //256位⼀级位图，代表32个字节，分别对应256个线程优先级。⽐如第⼀个字节的bit0表⽰优先级0，bit7表⽰优先级7。第⼆个字节bit0表⽰优先级8，bit7表⽰优先级15。

所谓⼆级位图，即我们⾸先确定32个字节中最低的⾮0的字节。为了实现这个效果，我们需要对这32个字节引⼊⼀个32个bit的位图变量，每⼀个bit位表⽰对应的字节是否为0。例如，这个32bit的位图变量的bit5为0，表⽰系统线程优先级256bit所分成的32个字节中的byte5为⾮0。为了区分，称这个32个bit的位图变量-字节位图变量 ，rt-thread中使⽤的是：

/* Maximum priority level, 256 */

rt_uint32_t rt_thread_ready_priority_group;//32位⼆级位图，⽤于查找⼀级位图就绪表中32个字节的最低⾮0字节（即当前所有就绪线程中最⾼优先级对应的字节）

显然我们查找系统系统最⾼优先级时，先确定⾮0的最低字节，这实际上依然是算法3，然后再对该字节进⾏查表，即得到该字节内最低为1的bit位，然后两者叠加（注意不是简单的加）即可。根据上⾯的分析，要想使⽤这个⼆级位图算法，rtt在跟踪线程的状态转换时，不仅需要维护256bit的位图变量数组rt_thread_ready_table[thread->number] |= thread->high_mask，还需要维护32bit的字节位图变量 rt_thread_ready_priority_group。参看如下代码

在rtdef.h中定义的线程控制发块 /* 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个优先级以内都会存在。

在thread.c中_rt_thread_init函数：thread->init_priority = priority; thread->current_priority = priority;

在thread.c中rt_thread_startup函数：/* set current priority to init priority */

thread->current_priority = thread->init_priority;//将当前优先级设置为初始值/* calculate priority attribute */

#if RT_THREAD_PRIORITY_MAX > 32

thread->number = thread->current_priority >> 3; /* high-5bit *///右移3位就是除以8，因为⼀个字节表⽰8个优先级。这样就可以得到当前这个优先级对应⼀级位图（32个字节）中的第⼏个字节

thread->number_mask = 1L << thread->number; //thread->number范围是0到31，将当前线程优先级所对应的⼀级位图字节在⼆级(32bit)位图变量中对应的bit置1，表⽰该字节代表的8个优先级⾄少存在⼀个就绪线程

thread->high_mask = 1L << (thread->current_priority & 0x07); /* low-3bit */ //current_priority的低3位表⽰这个优先级在上⾯字节中的第⼏个bit

#else

thread->number_mask = 1L << thread->current_priority; //将当前线程的优先级在位图变量rt_thread_ready_priority_group中对应的bit置1，表⽰该优先级存在就绪线程#endif

在scheduler.c中rt_schedule_insert_thread函数：

在rt_thread_startup函数⾸先调⽤rt_thread_resume函数，在resume函数中调⽤rt_schedule_insert_thread函数，然后在insert函数中将线程状态设置为就绪状态，即所有在调度器中的线程均为就绪状态。#if RT_THREAD_PRIORITY_MAX > 32

rt_thread_ready_table[thread->number] |= thread->high_mask;//将当前线程优先级所处⼀级位图(32个字节)中对应字节(由thread->number确定)的对应位(由thread->high_mask确定)置1，表⽰该优先级存在就绪线程#endif

rt_thread_ready_priority_group |= thread->number_mask; //若最⼤优先级为32，则将当前线程优先级在位图变量rt_thread_ready_priority_group中对应的bit置1，表⽰该优先级存在就绪线程 //若最⼤优先级为256，则将当前线程优先级所对应的⼀级位图字节在

⼆级(32bit)位图变量中对应的bit置1，表⽰该字节代表的8个优先级⾄少存在⼀个冰绪线程

上⽂已说明，thread->number就表⽰当前线程优先级在32个字节的位图数组中的字节位置。为了提⾼效率，rt-thread另外使⽤了⼀个u32类型的变量rt_thread_ready_priority_group 来加快速度。如果这32个bit中某⼀个bit为1，就表⽰对应的某个字节⾮0（想想看，这意味着该字节所表⽰的8个优先级中存在就绪线程）。rt_thread_ready_priority_group变量为32位宽度，长度上等于4个字节，因此可以对每⼀个字节查表（上⾯⽣成的表格）就可以得到为1的最低的bit位置。概括起来就是，rtt⾸先确定32个字节的位图中，⾮0的最低的那个字节，然后再查表得到这个字节⾮0的最低那个bit。这两步骤正好可以利⽤两次上⾯的表格__lowest_bit_bitmap。

4、在线程调度时获取所有就绪线程优先级的最⾼优先级：

在ksevicer.c中：

int __rt_ffs(int value)//该函数⽤于获取32位value第⼀个bit位为1的bit值加1。以低8位为例,0x00--0(特殊情况),0x01--0+1,0x02--1+1,0x03--0+1,0x04--2+1{

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;}

在scheduler.c中rt_system_scheduler_start函数：#if RT_THREAD_PRIORITY_MAX > 32 register rt_ubase_t number;

number = __rt_ffs(rt_thread_ready_priority_group) - 1;//number为⼀中间参数，表⽰根据⼆级位图rt_thread_ready_priority_group查表得到⼀级位图32个字节中最低⾮0字节，取值范围为0-31

highest_ready_priority = (number << 3) + __rt_ffs(rt_thread_ready_table[number]) - 1;//查表得到最低⾮0字节所代表的8位中最低为1的位(取值范围为0-7)，再与最低⾮0字节乘以8相加得到最⾼优先级（0-255）#else

highest_ready_priority = __rt_ffs(rt_thread_ready_priority_group) - 1;//若最⼤优先级为32，则直接根据32位位图变量查表得到32位中最低为1的位(取值范围为0-31)，即最⾼优先级#endif

在scheduler.c中rt_schedule函数：#if RT_THREAD_PRIORITY_MAX <= 32

highest_ready_priority = __rt_ffs(rt_thread_ready_priority_group) - 1;//若最⼤优先级为32，则直接根据32位位图变量查表得到32位中最低为1的位(取值范围为0-31)，即最⾼优先级#else

register rt_ubase_t number;

number = __rt_ffs(rt_thread_ready_priority_group) - 1;//number为⼀中间参数，表⽰根据⼆级位图rt_thread_ready_priority_group查表得到⼀级位图32个字节中最低⾮0字节，取值范围为0-31

highest_ready_priority = (number << 3) + __rt_ffs(rt_thread_ready_table[number]) - 1;//查表得到最低⾮0字节所代表的8位中最低为1的位(取值范围为0-7)，再与最低⾮0字节乘以8相加得到最⾼优先级（0-255）#endif

5、线程失去占⽤cpu时参数变化：

主动失去cpu：(1)调⽤sleep,delay函数使⽤线程放弃CPU；(2)等待信号量，互斥锁，事件，邮箱或消息队列过程中调⽤suspend使线程挂起。

在线程主动失去CPU时,程序都会在rt_thread_suspend函数中执⾏rt_schedule_remove_thread函数，将当前线程

从调度器中移除。

在rt_schedule_remove_thread函数中执⾏rt_list_remove(&(thread->tlist));将当前线程从调度器中移除，同时将该线程优先级对应的位图变量所在位清0。

被动失去cpu：(1)线程的时间⽚耗尽,被迫放弃CPU；(2)系统产⽣中断,线程暂时失去CPU,⼀旦中断例程执⾏完,还是会还原,这些是由硬件⾃动完成的。

被动失去CPU时调⽤线程让出rt_thread_yield函数(这⾥指(1)，(2)完全由硬件来完成,不需要软件⼲预)，此函数中程序会执⾏rt_list_remove(&(thread->tlist));即将当前线程从调度器中移除，

然后再执⾏rt_list_insert_before((rt_thread_priority_table[thread->current_priority]),&(thread->tlist));将当前线程加⼊到调度器中对应优先级的就绪线程链表末尾

紧接着执⾏rt_schedule();重新调度线程。在被动失去CPU的过程中,程序并未操作与获取线程最⾼优先级算法相关的⼏个参数。

在scheduler.c中rt_schedule_remove_thread函数：

该函数在rt_thread_suspend函数中调⽤，调⽤之前在suspend函数中会将线程状态设置为挂起状态，即所有从调度器中移除的线程（不包括detach和delete函数中的移除）均为挂起状态。

/* remove thread from ready list */

rt_list_remove(&(thread->tlist));//重置线程链表节点为初始值，即节点next与prev均指向⾃⾝节点，即将当前线程从调度器中移除 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;//将该线程优先级在⼀级位图中对应字节的对应位清0

if (rt_thread_ready_table[thread->number] == 0) //若该线程优先级在⼀级位图中对应字节的对应位清0后，该对应字节仍然为0，则说明该对应字节所代表的8个优先级均不存在就绪线程 {

rt_thread_ready_priority_group &= ~thread->number_mask; //若该线程优先级在⼀级位图中对应字节所代表的8个优先级均不存在就绪线程，则将⼆级位图中对应位清0 }

#else

rt_thread_ready_priority_group &= ~thread->number_mask; //若最⼤优先级为32，则将32位图变量中当前线程优先级的对应位清0，表⽰当前优先级不存在就绪线程#endif }