Linux中的进程调度策略总结(加入O(1)以后，CFS之前）
Linux中的进程调度策略
１.早期版本的进程调度
首先，在linux2.6以前的版本中，调度策略都是非抢占式的，无论是用户进程还是内核线程，都是不可被抢占的。
最原始的linux0.11版本中，有"进程槽“的概念，是一个长度为64的数组，也就是说，系统中同时最多可以存在64个进程。调度时，遍历进程槽，选取剩余时间片最多的进程来执行。当所有进程时间片都用光时，根据优先级给所有进程重新分配时间片，然后再选择具有最大时间片的进程进行执行。没有实时进程的概念。所有进程都采用相同的调度策略。
linux２.4版本中，已经抛开了“进程槽”的概念，描述进程的结构体task_struct(也就是理论课上所讲的PCB）通过链表链接到一起。所以从这点看，系统中可以存在无数多进程（其实不然，因为每个进程要在GDT表中占两项，而GDT表的大小有限，并且，描述进程id的pid变量是int整数）
linux2.4版本中，虽然有实时进程的概念，但是，对于进程切换时到底切换到哪个进程，还是需要遍历链表，寻找最优的那个进程（所谓对实时进程的处理只不过是要遍历时给它较大的权值）
２.存在的问题
对于下一个被调入的进程的选择算法时间复杂度为O(n)，在进程较多时会消耗太多时间。
旧的调度算法中，一旦优先级确定，时间片就随之确定。但是，对于普通进程来讲，有的进程属于计算密集型，有的进程属于IO密集型，而为了获得较好的用户体验，需给予IO密集型的进程较多时间片。
旧内核中，调度是非抢占式的，也就是说，即使提交了一个新的实时进程，也必需等到当前进程（很可能是一个普通进程)执行结束后，才有可能被调入CPU，这样就损失了一定的实时性，就像“急惊风遇上了慢郎中"。
３.新版本内核中的调度策略(未引入CFS,2.6.23以前)
１).进程分类
根据是否为实时进程，以及实时程度的不同，将进程所属的调度策略分为三类：
SCHED_FIFO 。
SCHED_RR
SCHED_NORMAL
以上三种进程中，前两种都属于实时进程，最后一种是最普遍的普通进程。
2）.SCHED_FIFO类进程的调度策略
SCHED_FIFO进程属于实时进程，使用这种策略进行调度的进程，基本上不存在时间片的概念，从它的名字就可以看出，FIFO,也就是说，大部分情况下当当前进程执行完毕后才能调入下一个进程。不过，由于linux2.6采用抢占式调度，所以，也有可能出现当前进程并没有完而调入另一个进程的情况，这种情况会出现在：
一个优先级更高的SCHED_FIFO进程被提交
当前进程由于等待IO被阻塞
被发送的kill信号杀死
通过系统调用，主动放弃CPU
３）.SCHED_RR类进程的调度策略
SCHED_RR进程同样属于实时进程，不过这类进程的"实时性“没有刚才的那种高，它存在时间片的概念，不过它所占有的时间片要比一般普通进程大很多(数量级上的差异)，在时间片用完时，它会重新得到时间片，并被放到可执行队列的末尾，然后调度器从具有相同优先级的SCHED_RR进程队列中选取第一个进程来执行，如此循环。RR也因此得名(round robin)。
4).SCHED_NORMAL类进程的调度策略
SCHED_NORMAL进程最为常见，我们平时自己fork出来的进程基本上都属于这类进程。如前面所讲，为了获得好的反应时间，这种进程还可以根据其性质分为计算密集型和IO密集型，对于IO密集型应该适当给予更多的时间片。下面具体介绍这类策略。
首先，在进程刚产生，没有被执行之前，内核也无法预测它是计算密集还是IO密集。于是便有了静态优先级的概念，内核先赋予进程一个静态优先级，以后会在此静态优先级基础上，加以参数进行修正，生成动态优先级，来决定进程最终的优先级。
动态优先级的数值范围是[100,139]，数值越小表示优先级越高。(刚才那两种实时进程的优先级范围是[0,100)，可见，实时进程总会在普通进程之前得以调度)。对于不同的动态优先级，进程会被初始的赋予不同的时间片，初始时间片按如下公式进行计算：
基本时间片＝(140-静态优先级)*20 (静态优先级(140-静态优先级)*5 (静态优先级>=120)
将这两个函数的图像绘制出来以后，可以发现，对于不同静态优先级，时间片的差异还是很大的，也就是说有很好的区分度。
在进程运行过一些时间后，根据其在运行期间的表现，来确定其动态优先级。具体方法是：在task_struct结构体设置定时器，分别对占用CPU进行计算以及等待IO而睡眠的时间进行计数。根据其睡眠时间的多少，综合其静态优先级，来得到其动态优先级。动态优先级的数值也为[100,139]，其计算方法如下：
动态优先级＝max(100 , min(静态优先级-bonus+5 , 139))
其中，bonus是根据进程的睡眠时间得出的一个数据，范围为[0,10)，睡眠时间越少，bonus数值越小，其对应函数是一个简单的分段线性函数，具体映射表在代码中很明确。
观察上式可以得出，对于相同静态优先级的进程来讲，如果其睡眠时间越多，bonus值就越大，最后得出的动态优先级就越小，也就是被分配到时间片就会越多，这正是我们所希望的。
对于IO密集型进程，只是通过调整其动态优先级还不够，还通过经验公式对其性质做“最终判断”，判断其是否具有”interactive”性质，如果动态优先级与静态优先级符合以下关系，便判定其为"interactive”:
动态优先级
将刚才的动态优先级计算公式代入上式，便可以得出如下另一个不等式：
bonus - 5 >= 静态优先级 / 4 - 28
由上式可以看出，对于一个确定的bonus，它所对应的静态优先级数值越小，该等式越容易成立，也就是说，对于静态优先级高的进程（优先级数值小），被判定成为"interactive”所需的睡眠也越小。这也是我们所希望的，因为我们当然希望优先级高的进程有较快的响应时间。
当一个SCHED_NORMAL进程被判定具有"interactive”性质后，时间片用完后就不一定被调度出去了。调度器首先会检查当前可执行队列中的最后一个进程是否已处于饥饿状态（其判定方法了与该进程的入队时间和队列的长度有关)，如果没有进程饥饿，那么便重新加满当前进程的时间片，并将其放入可执行队列的末尾，等待被调和，如果有进程饥饿，那么加满当前进程的时间片，但是并不将其放入可执行队列，具体的放入位置下面会介绍。
４.具体的数据结构及调度算法
1）可执行队列及优先级队列
每个CPU都有一个单独的可执行队列（其实不是单独的一个队列，而是多个队列的数组）这个可执行队列又分成140个独立的分队列（每个分队列又用１个比特位来表示队列是否为空)，来代表优先级为0-139的可运行进程（即优先级为0的可执行进程就会被挂入到编号为0的分队列中去，优先级为1的可执行进程就会被拷入到编号为1的分队列中去，依此类推)，而对于一个特定的优先级队列，又有两个分队列，一个记为active，一个记为expired。
２）调度方法
当需要换入一个进程时，先扫描分优先级队列位图（０表示对应优先级队列为空，１表示为非空)，由于大多数CPU都提供了功能与之相关的汇编指令，所以这个扫描相当迅速，而且与可执行进程的数量无关。当扫描到第一个不为0的比特位时停止，此时所对应的优先级队列便是需要进行操作的队列（因为其不为空，而且优先级数值最小，优先级最高)，然后，从它的队列头取出一个进程，（取队列的头元素，此操作耗时也与可执行进程数量无关)，将其调入CPU执行。
回想以前的调度算法，如果队列中所有进程的时间片均用光，便会遍历所有进程，重新分配时间片，再选择最佳进程加以执行，这样就不可避免的将时间复杂度提升到了O(n)。在新版本中，由于对于一个特定的优先级队列，有两个分队列(active,expired），所以，当时间片全部耗光时，只需要常数时间即可“为所有进程重新分配时间片，并选择最佳进程执行”，具体做法如下：
当一个进程时间片用光时，先为它重新计算时间片（因为由于不同的IO表现，进程每次得到的时间片可能会不同)，然后，将其链入相应的优先级中的expired队列中。再从active队列中取头元素进行执行。当active队列为空时，说明此时可执行进程已经全部转入了expired中去，而且相应的时间片已经计算好，所以，只需要交换active队列和expired队列的指针，也就把active变成了expired，把expired变成了active，然后继续扫描优先级位图，挑选队列头元素执行就可以了。
从上面可以看出，调度时所需的时间与可执行进程的数量无关，基本上均在常数时间即可完成，这便是著名的O(1)调度算法。