内核 进程调度

1.操作系统分为两类：一类是实时操作系统，一类是分时操作系统。它们的共同特点是都是多任务的 。多任务操作系统分为两类：非抢占式多任务和抢占式多任务。

非抢占式多任务，就是指进程不断的占用CPU，直到运行完毕或者是自己让出。这样的系统实在不适合多任务操作系统，毕竟，长期占用CPU对任何多任务系统来说，都是很容易让系统崩溃的！这样的操作系统也很少。

抢占式多任务，就是进程占用CPU时间是有限的，到了一定时间，它必须让出来，被后来的进程抢占。进程在被抢占之前的运行时间，我们把它叫做时间片。抢占式多任务调度是很多操作系统最基本的调度方法。

2.那么，我们具体如何调度进程呢？我们发现进程间的不同之处：一些是I/O消耗型，就是说进程频繁的和外界交互，比如要打开、浏览文件，要等待用户命令，要读取光盘上的数据，等等。一些是处理器消耗型，就是说进程多数时间总是不断的在CPU里面运行，很少需要等待。

所以，我们应该区别对待这两种类型的进程。我们利用处理器遵循的原则是：吞吐量大和响应时间快。对于I/O消耗型，由于它需要频繁等待I/O，这样 它需要较高的优先级来抢占当前运行进程，以确保当I/O条件满足后能马上得到CPU响应，并且它的时间片相对其它处理器消耗型进程来说更长。相反，处理器 消耗型进程优先级相对就低了，并且其时间片没有必要太长。

让我们看一个例子，加深理解：假设用户运行两个程序，一个是打字程序，一个是视频程序。很明显，打字程序是I/O消耗型的，而视频程序是处理器消耗 型的。人的打字速度再快也不可能快过计算机计算视频编码并在屏幕上显示出来的速度，可是人希望他每打一个字，就能输入计算机并在屏幕上显示。因此，对于打 字程序，我们让它有较高的优先级，以便让人可以马上输入，并且其时间片也要多些；相比下，视频程序的优先级就低些，以便让位给打字程序，时间片当然也就少 些。

实际上，一般来说，优先级越高，时间片也就越长，反之亦然。

3.那么，具体如何设定优先级和时间片呢？Linux有两种策略：一是设置进程优先级值nice，它的范围从-20到19。nice值越低，优先级别越高，默认下为0。还有一个实时优先级策略，这个待会讨论。

对于时间片，前面说了，优先级越高，时间片也就越长。最小的时间片为10ms，最大为200ms，默认为100ms。

这里要强调的是，进程并不是一直都是一种类型的，而且，有些时候进程是哪种类型本来就不明显。这样linux必须动态的计算优先级和时间片。对于优先级，每次进程让出CPU后都会更新；对于时间片，不是每次都必须耗尽。待会还会具体讲这个问题。

4.先放一放优先级和时间片的问题。让我们先讨论CPU调度进程。其实很简单，每一个CPU（单CPU当然也如此）都有一个可执行队列—— struct runqueue，里面包括很多信息：自旋锁lock、活动优先级数组指针*active、超时优先级数组指针*expired、优先级数组 array[2]……等等。

5.有必要讨论下自旋锁，当进程进入CPU运行时，就会给它的代码上锁，以免别的CPU中的进程修改里面的代码（不排除CPU给别的CPU上锁这 样的情况，以后会讨论到。）。所谓子旋锁就是这样的一把锁：进程A进入CPU，锁上门运行，进程B来到CPU前，发现门被锁上了，于是等待进程A出来交出 开锁钥匙。

正如每次我们谈到“锁”这个概念时，总会谈到“死锁”——是的，我们用锁，就必须防止死锁，死锁是这样产生的：进程A进入CPU运行，上锁，进程B 来到CPU门前等待进程A出来，可是糟糕的情况出现了：进程A要想出来就必须获取进程B的帮助，于是进程A开始等待进程B的帮助，可是进程B却又一直等待 进程A出来！这样的等待无法终止，最终成为死锁。

再比如，进程A要锁上甲代码段，然后想再去锁乙代码段，进程B要锁上乙代码段，然后想再去锁甲代码段。第一步大家都没问题，可是两个进程都要进行下 一步时，发现无法完成任务了：进程A已经锁上甲代码段，进程B没法再去操作它，同理进程B已经锁上乙代码段，进程A也没办法操作它，于是两个进程等待对方 释放锁，当然，这样的等待也是无止无休的。这就好象两辆汽车在一座很榨的桥上相向行驶，两车碰头谁也不让谁，都在等待对方让路。

避免死锁，必须使每次上锁操作都是有顺序的、原子的操作。有顺序的，也就是说每次都按照可执行队列地址从低向高的顺序上锁——我们以后会很好的讨论这个。

原子的，就是说每次上锁必须执行到底，否则不予执行！

关于锁的问题，以后还会进一步讨论。

6.是时候讨论活动优先级数组指针*active、超时优先级数组指针*expired和优先级数组array[2]了。其实还是很简单的。

每一个运行队列都有两个数组：一个当然是活跃的，另一个是过期的；所谓活跃的，就是里面的进程没有使用完时间片，过期的，就是里面的进程时间片已经用完了。active指向活跃的数组，expired则指向过期的数组。数组值最大默认为140。

在活跃数组中，如何确定哪个进程执行呢？首先请看优先级数组的定义：

struct prio_array{

int nr_ative;/*任务数组*/

unsigned bitmap[BITMAP_SIZE];/*优先级位图*/

struct list_head queue[MAX_PRIO];/*优先级队列*/

}；

优先级位图bitmap[BITMAP_SIZE]为每一个优先级准备一位，开始为0，当要求某优先级进程执行时，对应的位置为1。比如要求优先级为7的进程执行，那么bitmap[BITMAP_SIZE]的第7被置为1。

7.重新计算时间片。老版本的linux是这样计算时间片的：当进程的时间片都使用完后，用for语句遍历每一个进程，计算它们的时间片！！

天，这是非常低效率的，而且相当复杂！

新的linux很简单，刚才提到活跃数组和过期数组——它们的用途就在这：活跃数组放着时间片还未用完的进程，过期数组放着时间片已经用完的数组。当进程的时间片使用完后，就被转入过期数组，同时，计算好它的新的时间片。

8.计算优先级和时间片。前面已经说了，优先级和时间片由进程的类型决定，但是我们可不能预知进程到底是什么类型的。linux采用静态优先级和动态优先级的方法，准确的制定了进程的优先级。

首先，进程获得由用户给定的静态优先级nice，这个值在-20到19之间，它不会被改变。接着，进程会运行，然后linux会判断它的休眠时间来 决定动态优先级。休眠时间长，说明是I/O消耗型；短，则是处理器消耗型。linux根据休眠长短，以nice为基数，修正动态优先级，也就是对进程的优 先级进行最大加5的处罚或则最小-5的奖励，例如，一个进程休眠时间长，说明是I/O消耗型，若静态优先级为7，这个时候奖励它-5，使它获得动态优先级 为2；而一个进程休眠时间很短，说明是处理器消耗型，若静态优先级为2，这个时候处罚它+5，使它的动态优先级为7。这样，可以真正的、准确的计算出优先 级。

优先级计算出来，时间片也就不难了