1.实时系统调度说明

  RTOS实时系统，实时的体现在于，每条命令执行完全可控可预期，市场上较为广泛的有rtthread，threadX等，
其中各类实时系统，任务优先级查找调度，是系统实现实时的一个核心。只有在固定周期内找到最高优先级，才能符合实时要求。

2.实时系统的具体体现

  rtthread内核调度采用位图算法，好处是实现O(1)调度，就是每次调度的时间都是固定的，
无论线程中存在多少个线程，多少优先级，系统可以在一个恒定的时间内选择出最高优先级的线程。要解决固定时间内寻找最高优先级，先解决线程数据结构的存储。

a、每个线程的信息使用线程控制块，TCB，thread Control Block,
b、线程优先级非负整数，优先级数目固定，最多256级
c、线程数目仅受ram大小，多个TCB，如何排列存储，才能实现O(1)

探索O(1)复杂度找到最高优先级任务

方法1：（理论上可以找到最高优先级，但是时间复杂度不保）

for(i=0;i<256;i++}
    {
        if(rt_thread_priority_table[i] != NULL)
        break;
    }
    highest_ready_priority = i;//

假设255级有就绪任务，可以时间复杂度最大是O(n); 对于实时系统来说查找最高优先级任务，时间复杂度不是固定的，肯定不行

方法2：(记住一点优先级数字小，优先级高，目标是找到最小)

使用一个变量32个字节的数组，使用位表示256级。 相当于第一字节BIT0, 表示优先级0 相当于第二字节BIT0, 表示优先级8 ...... 这时，引入变量 rt_uint8_t rt_thread_ready_table[32]; 举个例子：当创建线程，并指定优先级125，然后设置为ready。 这就相当于rtt将256bit中的第125bit位置1， 这里需要将125bit对应到具体字节位。 125/8 =15,125%8 =5，也就是第15字节，第BIT5位。 当rtt执行好后，优先级125不在就绪，就将15字节BIT5清零。 当然这个调度思路就是将遍历数组rt_thread_prioriy_table, 找到第一个非0的bit位，也就是最高优先级，根据指针取出当前线程 TCB，进而调度执行。

该算法代码：
for(i=0;i<32;i++)
{
    for(j=0;j<8;j++)
    {
        if(rt_thread_priority_table[i] &(1<<j))
        break;//这个就是找到的最低为的那个为1的bit位。
    }
//下面就是我们需要的最高优先级
highest_ready_priority = i *8 +j;
}

上面代码其实还是没有控制时间复杂度为O(1);
最大周期是O(32*8);!!
为什么这个是耗时就，主要是需要对位图每个bit位做检查。

方法3：位图算法

  现在先从一个简单的模型入手，将位图看做一个变量（一个char型的），假定优先级为8，那么位图变量
使用一个字节表示，当BIT全为0，则位图变量为0，当所有BIT全为1，则为255，此时最高优先级为0（所有位都有），
当位图变量为6时，bit2=1，bit1=1，最高优先级为1。上面说明了位图变量取0-255之间任意数字，
最低位为1的bit位置都是预知的，所以可以将这个位图变量所有取值所对应的最高优先级计算出来，
并存为表格，这样避免方法2中的for循环。

总结：也就是这个字节等于0~255值，我们都可以直到哪个bit为是最高优先级。使用查表方式，替换掉for循环，
时间复杂度也就从O(n)变成了O(1)。

  只要查表就可以得到最高优先级。（备注：0x00是特殊，虽然全部为为0，但是不是说第0位为1，这里为方便写0）。 当然实际上上面是一级位图，256级优先级实际上是二级位图，rtt首先确定32个字节的位图中，非0的最低的那个字节 ，然后查表得到这个字节非0的最低那个bit。（一个字节可以直接通过位图值得到优先级位置）。   实际上优先级在较多超多8级时,例如假定为32级优先级，当有4字节，这个时候存位图，就不合适了，
如果做表格，表格元素2^32=4G字节。如果使用u32型，也等价于4字节。如果字节0中非0，则优先级一定 在字节0中，我们对字节0查表rt_lowet_bitmap，即可以得到最高优先级。如果字节0为0，字节1非0，则对字节1查表，
假定得到的字节1中为1的最低bit位，然后加上8，就是最高优先级，同理。

假定u32 rt_thread_priority_bitmap维护当前优先级位图。
    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  
};  

if(rt_thread_priority_bitmap & 0xff)//非0，说明了最高优先级在里面。
    highest_ready_priority = rt_lowest_bitmap[rt_thread_priority_bitmap & 0xff];
if(rt_thread_priority_bitmap & 0xff00)
    highest_ready_priority = rt_lowest_bitmap[(rt_thread_priority_bitmap>>8)&0xff] + 8;

  如上先确定最高优先级在哪一个字节端包含范围内（此时共4个字节）。如果我们将系统优先级调整到256级，此时
如果我们仍然使用这种位图，那时间复杂度变得有开始大起来，这时我们需要引入二级位图算法。
二级位图
  首先要确定32个字节中最低的非0的字节，这时需要一个32bit的位图变量，每个bit位标识对应字节是否为0，例如：
这个32bit的位图变量bit5为0，表示系统优先级256bit所分的32个字节中的字节5非0，为了区分，这个32bit的位图
称为，字节位图变量【作用就是找到256bit中对应的32bit一组中，哪一组存在就绪位（置1表示就绪）】，rt系统
中使用：rt_thread_read_priority_group，再查找到非0的最低字节，然后再对该字节查表，即得到该字节内最低
为1的bit位，此时就可以确定下，具体是256bit中哪个bit位就绪。
  使用二级位图，不仅需要维护256bit的位图变量数组rt_thread_ready_table[ thread->number] |=thread->high_mask;,还需要维护32bit的 字节位图变量rt_thread_ready_priority_group. RTT源码中：

//256级优先级
number = __rt_ffs(rt_thread_ready_priority_group) -1;
highest_ready_priority = (number<<3)+__rt_ffs(rt_thread_ready_table[number]);

3. 总结

  主要需要理解就是两点，
第一：调度中如何保证可以实现O(1)复杂度查找到最高优先级
第二：位图算法是如何使用空间换取时间策略保证，固定的复杂度