sparrow系列十六
skaiuijing
前言
在前面我们完成了Sparrow的临界区的代码，使用临界区，能够解决常见的并发问题，现在该完善我们的调度算法了。
调度算法在操作系统领域常常是热门的话题。不同的用途将会使用不同的调度策略。在本节，笔者将为大家介绍一些操作系统中的调度算法的知识，加深读者对操作系统的理解。
linux内核中的调度策略
调度策略负责进行任务选择和任务切换，linux内核中的调度基于分时技术：多个进程以“时间多路复用”的方式运行，将时间进行分割，不同段时间运行不同的任务，这段时间被称之为时间片。
进程的分类
linux内核中通常有三类进程：
交互式进程：用于和用户发生交互，对时间不是很敏感，时不时卡一卡也是在用户容许范围内。
批处理进程：在后台运行的进程，不与用户直接接触，例如编译程序和科学计算程序等等。
实时进程：对时间要求非常严格的程序，例如自动控制程序。
进程的抢占
linux内核是抢占式的，也就是说，不同的进程有不同的优先级，如果响应的进程的优先级比当前运行的进程的优先级要高，那么当前的进程就会被响应的进程所抢占。
调度算法
早期linux版本的内核的调度算法比较简单：扫描并且计算所有就绪进程的优先级，然后选择最佳的进程来运行，参考的标准是时间片，时间片大的进程往往优先运行。这一算法的缺点非常明显，就是时间不固定。
当然，到了2.6版本之后，linux内核的调度算法已经复杂到不可想象的程度了，这跟多处理器的出现也有很大的关系，此时，调度选择算法会在固定的时间选出任务执行，以确保CPU的运行速度。
Linux0.11版本调度算法
让我们先看看linux内核0.11版本的调度算法。
首先是前几行：
c其实代表的是保存进程时间片的值
next表示下一个进程的序列
i,p都与挂载进程的任务队列有关，i代表数组下标，p是指向队列本身的指针。
其实这就是一个很常见的比较大小的算法，首先检查这个进程的状态是不是运行状态，然后进行比较，如果在运行队列里遇到比当前进程时间片大的进程，那么就替换成它，c更改为这个大的进程的时间片，next更改为这个进程的下标。
通过这个比较算法，我们筛选出了队列里时间片最大的任务。接下来就是切换了，如果要切换的进程的时间片没有用完，也就是c>0时，这个while循环会直接结束，程序会跳转到switch这里，这就是进程切换的函数。
如果这个优先级高的进程的时间片已经用完了，也就是c==0时，会进入for循环，这是对时间片的重新分配。因为我们从前面的排序已经知道，c就是被筛选出来的最大的时间片，如果c==0，意味着所有的进程都没有了时间片。
上面的for循环，其实就是根据优先级的大小来调整时间片的大小，最后每一个进程counter的值=原先值/2 +优先级。
可能读者还会疑惑，为什么要加上*p->counter>>1呢？位于运行状态的进程的时间片不是都为0了吗？
进程不止一种状态，显然，还在被阻塞的任务时间片肯定不为0啊，虽然运行状态的进程最终时间片都等于自身优先级的大小，但是阻塞任务就要考虑原先的时间片了，对原先时间片除以2，这是对平均时间片的综合考虑的结果，时间片过短，切换的开销会变大，时间片过长，进程看起来就不会是并行的。
现在让我们来到switch_to函数：
在前文笔者简单讨论过进程的上下文切换，因为进程之间隔绝了资源，这往往意味着切换的步骤会变得简单一些，从代码中可以看出，主要是TSS（一个保存进程状态信息的结构体）的切换，但是在FreeRTOS中，则主要是对arm寄存器的操作，因为进程切换是所有的资源都进行了改变，而线程的切换则是在原有的资源上修修改改，本质是任务栈的切换。
通过schedule和switch_to两个函数，我们知道了linux0.11版本是如何进行调度的，schedule负责时间片的分配和进程的选择，switch_to负责进程的切换。
操作系统的调度器本质就是在进行选择和切换。
现在该来到常见的RTOS内核了
FreeRTOS的调度算法
让我们看看tasks.c文件中的这几行代码：
prvAddTaskToReadyList函数在每个任务在添加到就绪列表时都会执行，它会与uxTopReadyPriority进行比较，然后uxTopReadyPriority记录两者中的较大者，不断的对每一个新添加进来的任务优先级进行比较，这其实就是在找出最大的优先级。
这样做，遍历时就能直接找到优先级最高的线程。
顺便一提，FreeRTOS中的任务优先级跟我们在mcu中学习到的中断优先级判断是不一样的，也跟RTT和uc/os不一样，mcu中的中断优先级是数字越小，优先级越大，RTT和uc/os的任务优先级也是这样，但FreeRTOS中是任务优先级的数字越大，优先级越大。
taskSELECT_HIGHEST_PRIORITY_TASK就是通用的选择算法的具体函数了，先对uxTopReadyPriority的值进行保存。
configASSERT笔者之前提过，是断言，用来debug，如果uxTopPriority小于0，会触发它。
每一个优先级都有一个特定的链表，while判断就绪链表的这个优先级是否有任务挂载在上面，如果没有，就继续找下一个优先级的链表，也就是–uxTopPriority。
uxTopPriority被设定为是代表最大优先级的数字，自减操作代表从就绪列表最后一个链表（优先级最高的链表）开始查找，直到找到任务链表不为空的优先级任务，那么这个任务肯定也是所有任务中优先级最大的任务。
然后获取这个任务的TCB并更新pxCurrentTCB（切换的具体函数），最后更新uxTopReadyPriority的值。
rt-thread内核的调度算法
rt-thread是一个国产RTOS，和sylixOS这些OS一样，也是头部RTOS了，不过在国内的开源领域确实是当之无愧的第一RTOS。
它是一个偏linux的RTOS，而且用面向对象的思想开发的，非常有特色。
笔者决定再讲一讲rtt的选择算法，因为这种算法很常见，用途也非常广泛。
RTT使用的是查表法，让笔者简单介绍一下这种策略的思想。
我们要查找一个链表中优先级最高的任务，最简便的做法就是for循环，一个个遍历比较，找到优先级最高的任务，这种做法很简便，缺点是复杂度过高,达到了o(n)，查询的时间很长。那么有没有使复杂度为1的方法呢？
于是RTT使用了空间换时间的策略。
假设我们有八个优先级，用八个位来表示它们。任务优先级为多少，那么就在哪个位置1。
例如，task1优先级为5，那么优先级的数字就是00010000。
在实时操作系统中，优先级数字越小，优先级越高，那么这个任务代表的1更靠近右侧。
既然知道了这些，那么，把所有8个位的组合都列出来，判断每一个不同的数字最低位的1在哪个位，然后直接查询，不就可以知道任务的优先级最高是多少吗？然后顺着优先级，去执行对应的任务。
通过这个函数，可以将prioritynum最低位的1的位置打印出来。这个函数比较简单，就是循环遍历0到255，也就是00000000到11111111，让每一个数依次右移最多八位，找到最低位的1。prioritynum右移后，会与1进行与运算，也就是说，除非右移后的数最低位是1，否则都会进行下一轮循环，直到找到最低位的1并且打印；随后程序又会跳出内层循环进行下一个prioritynum的运算。
运行结果：
通过这个数组，我们可以可以将prioritynum作为数组下标查询最高优先级。这其实就是一种哈希算法的思想，用特定的数字映射特定的优先级。
这种算法缺点也十分明显，就是数组占用空间太大了，一个int就要4个字节，上面的例子是优先级为8位，如果优先级有32位呢？那么占用空间将会达到：4*2的32次方个字节。
为了解决这个问题，RTT内核使用了四个表，每个表对应8个位，算法也很简洁，先读最低八位的值，判断是否为0，不为0说明优先级肯定在最低八位中，然后直接查表即可。可能有读者好奇为什么要加上1，其实观察就会发现，这个表的第一个0，是在循环之前手动打印的，否则没有256个数，为了避免与32位全为0冲突，所以加上了1。
简单来说，笔者手动让数组里的所有数向后移动了一位，那么相应的，把prioritynum作为下标读取表里的数，也要往后面移动一位。
如果最低八位没有，那就到次八位找，同样先判断是否在次八位中，如果在，那么右移八位然后查表，因为进行了右移操作，所以返回值要在最低八位的返回值的基础加上8。
剩下两个同理，留给读者自己分析了。
总的来说，这种基于哈希思想的查表法应用十分广泛，采用空间换时间的策略，具有一定的学习价值，如果某些程序对查询的时间要求比较高，可以尝试用查表策略代替之前的遍历策略。
总结
笔者介绍了linux内核、FreeRTOS、RT-Thread的调度策略和算法，旨在加深读者对操作系统的理解。当然，本来这些内容应该分成几篇不同的文章细细讲解的，不过笔者还是决定全部放在一篇。
一方面是考虑到放在同一篇文章里更加全面系统，另一方面是考虑到Sparrow的文章数量如果过多了，比如更成了四五十篇。
那么笔者相信屏幕前的读者一定没什么兴趣看下去了。所以笔者还是决定追求简洁明了，不更那么多废话。
Sparrow的教程更到这里，其实已经快接近尾声了。更完调度算法，再更完定时器阻塞延时后，就结束了。
一步步跟着教程实现Sparrow RTOS的小伙伴们，一路看到这里，不知道是否有所收获?
