RT-Thread基于优先级的全抢占式调度算法的实现
RT-Thread基于优先级的全抢占式调度算法的实现
RT-Thread的调度算法采用基于优先级的全抢占式调度策略，通过位图调度算法实现O(1)时间复杂度的调度。本文将详细介绍RT-Thread的调度算法实现原理，包括线程控制块的存储方式、位图的定义和使用，以及如何通过查表法实现高效的调度算法。
线程结构存储
在RT-Thread中，每个线程的信息用线程控制块（Thread Control-Block，缩写为TCB）表示，它是定义在rtdef.h中的struct结构体，用来描述一个线程所有必要信息。线程的优先级别用非负整数（即无符号整数）表示，数值越小，优先级越高。系统的线程优先级的数目固定，最多支持256级；系统中的线程数目不做任何限制，线程的数目仅受限于系统RAM的大小。
为了满足上述设计要求，RT-Thread采用数组和链表结合的方式存储TCB。数组的长度即为线程优先级的数目，数组的每个元素为一个指向TCB数据结构的指针。当某个线程优先级上存在多个线程时，这些TCB通过链表依次连接。具体来说，不同线程优先级的线程的TCB分别存在线程TCB数组对应优先级的位置上。对于相同优先级别的多个线程，我们只需要将该优先级的第一个就绪线程的TCB存储在线程TCB数组中相关位置，后续同级线程通过链表依次连接。
位图调度算法
调度算法首先要找出所有线程优先级中优先级最高的那个线程优先级。系统中某些线程优先级上可能不存在线程，也就说，rt_thread_priority_table数组中某些元素为空，因此要找出该数组中第一个非空的元素。
调度算法1
上面策略可以工作，但是它的问题是运行时间并不固定，如果当前系统中具有最高优先级的线程对应的优先级的数字为0级，循环一次就可以找出，如果很不幸，从0级到254级上都没有就绪的线程，仅在255级上有就绪的线程，这个调度函数不得不在检查了数组这256个元素之后，才能找出可以运行的线程。这个算法虽然直接简单，但是太低效，而且运行时间也不稳定，作为嵌入式实时操作系统这是不可接受的。我们需要寻找一种具有恒定执行时间的调度算法。
调度算法2
该调度算法双层for循环可能只循环一次，也可能会循环256次，这取决于位图中位图中为1的最低BIT的位置。如果BIT0为1，则执行一次即跳出循环，如果BIT0-BIT254都是0，仅BIT255为1，则循环256次。 平均来说， 双层for循环的次数大约是 255/2 次。即与优先级数目N成正比。每次调度函数执行的时间不恒定，取决于当前线程的优先级分布状况。这种调度策略从整体上说执行的时间是O(n)的，即调度算法的平均执行时间跟优先级数目成正比。这种方式本质上跟调度算法1一样，依然不能实现在恒定时间完成调度的目标。
RT-Thread的调度算法
将位图看作一个变量，并假定当前优先级别为8，则位图变量可以用一个字节表示。考虑位图变量的取值范围，当位图所有BIT0全为0时，位图变量的值就是0，当位图所有BIT位都是1时（表示所有线程优先级上都存在就绪的线程，此时最高优先级为0级），则位图变量的值是255。反过来，如果当位图变量为1时，此时位图的BIT0为1，即最高优先级为优先级0，同样，位图变量为255时，最高优先级依然是0。 当位图变量为6时，BIT2=1，BIT1=1，即最高优先级为1。因此当位图变量取0-255之间的任意一个数字时，它的最低为1的BIT位置都是预知的。可以预先将这位图变量的所有取值所对应的最高优先级计算出来，并存成一张表格，然后就可以避免算法2中的for循环，而只需要查表即可，执行时间自然是恒定的。查表法就是一种常用的用空间换取时间的方法。
位图取值 最低为1的bit位
注意0x0比较特殊，全部bit位都是0，返回0但不表示其第0位为1。只是为了数组整齐所以填充0。
可以写个简单的程序来生成位图首BIT表，我写了个python程序，
# gettab.py
# 生成位图首BIT表的Python程序
就可以得到如下的表了：
当进程优先级为8时，直接查表就得到最高优先级了。
当系统存在32个优先级时，如果采用类似方案直接制作表格的话，表格的元素个数将是2**32=4G字节，显然这是不可接受的。32个优先级，即4个字节，正好可以用一个uint32_t变量存储。查找首个非0位，可以将其分拆为4个字节，以此查询上表。
假定u32 rt_thread_priority_bitmap维护着当前系统优先级位图。
调度算法3-32级优先级查找最高优先级算法
这就解决了32个系统优先级时的调度问题，现在来考虑线程优先级为256的情况。读者可能觉得这没什么不同，256个bit=32个字节，依然采用算法3的思路，对着32个字节依次查表。问题是，当位图变量有32个字节时，依次查表耗费的时间就不可以忽略了，为了提升系统实时调度的性能，需要对算法3进行改进。
为了解决这个问题，RT-Thread引入了二级位图。即256个bit由32个字节存储，每一个字节的8个bit代表着位图变量中的8个优先级，如果某个字节非0，则表示其中必有非0的bit位。
rtt中对应的数组为rt_uint8_t rt_thread_ready_table[32]
所谓二级位图，即先确定32个字节中最低的非0的字节。为了实现这个效果，现对这32个字节引入一个32个bit的位图变量，每一个bit位表示对应的字节是否为0。例如，这个32bit的位图变量的BIT5为0，表示系统线程优先级256bit所分成的32个字节中的第五个字节非0。为了区分，称这个32个bit的位图变量为字节位图变量，这就是rt-thread中使用的是rt_thread_ready_priority_group.
这样查找系统系统最高优先级时，先确定非0的最低字节，这实际上依然是算法3，然后再对该字节进行查表，即得到该字节内最低为1的bit位，然后两者叠加（注意不是简单的加）即可。
根据上面的分析，要想使用这个二级位图算法，rt-thread在跟踪线程的状态转换时，不仅需要维护256bit的位图变量数组rt_thread_ready_table[thread->number] |= thread->high_mask，还需要维护32bit的字节位图变量 rt_thread_ready_priority_group.参看如下代码。
初始化线程时，指定了线程的优先级别thread->init_priority，由于线程优先级为0到255，一个字节就可以表示。但是bitmap是32个字节。为了调高效率，最好能快速向位图的对应的bit写1。
语句(1)thread->current_priority >> 3，等价于除以8，移位效率效率更高。
上面除法的余数，就表示这个优先级在上面字节中的第几个bit。这个余数可以使用 (thread->current_priority & 0x07)来表示。
语句(3)是得到该bit对应的权值。例如一个字节的bit7对应的权值即 (1<<7)，这样做是为了使用“位与，或，非”等位运算，可以提高运行速度，即语句(4)。
语句(4)表示了这几个变量作用。可见，根据某个表示优先级的数字向位图中相应的bit位写入了1。
那么语句(2)和(5)是做什么用的呢？ 这个number_mask实际上是为了加快查找位图的速度而创建的。它将在rt_schedule函数中发挥作用。
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位置。
概括起来就是，rt-thread首先确定32个字节的位图中，非0的最低的那个字节，然后再查表得到这个字节非0的最低那个bit。这两步骤正好可以利用两次上面的表格rt_lowest_bitmap。
下面是rt_schedule的核心逻辑，非必要的代码被我隐去。读者可以对比下面的代码理解思路
可以看出位图调度算法的核心就是查找字节最低非0 bit位的查表法软件实现，是整个位图调度算法的核心。ARM公司提供专门的指令获取寄存器最低位，只要几条汇编语句就可以完成同样的功能，而且性能更好。
rt-thread作为一款成熟商用的RTOS内核，也支持使用CPU指令实现查找字节最低非0位，这部分代码在libcpu/arm//cpuport.c中，以cortex-m3的为例，代码如下
通过编译器提供的内联汇编功能，在C语言程序中直接使用汇编指令实现原本软件查表实现的功能，代码更少，性能更好。