进程的调度算法

什么时候调度进程

在进程的生命周期中，当进程从一个运行状态到另外一状态变化的时候，其实会触发一次调度。比如，以下状态的变化都会触发操作系统的调度：

从就绪态->运行态：当进程被创建时，会进入到就绪队列，操作系统会从就绪队列选择一个进程运行；
从运行态->阻塞态：当进程发生I/O事件而阻塞时，操作系统必须选择另外一个进程运行；
从运行态->结束态：当进程退出结束后，操作系统得从就绪队列选择另外一个进程运行；

进程的状态

五状态模型

如图，进入就绪队列，其状态就会变为就绪态。各个状态之间的关系描述如下：

就绪->运行：当操作系统内存在着调度程序，当需要运行一个新进程时，调度程序选择一个就绪态的进程，让其进入运行态。
运行 ->就绪：运行态的进程，会占有CPU (参照一开始的饼状图)。每个进程会被分配一定的执行时间，当时间结束后，重新回到就绪态。
运行->阻塞：进程请求调用系统的某些服务，但是操作系统没法立即给它(比如这种服务可能要耗时初始化，比如1/0资源需要等待)，那么它就会进入阻塞态。
阻塞->就绪：当等待结束了，就由阻塞态进入就绪态。
运行 ->终止：当进程表示自己已经完成了，它会被操作系统终止。这便是对于单个进程，经典的五状态模型。当存在多个进程时，由于同一时间只能有一个进程在执行，那么如何去管理这一系列的处于阻塞态和就绪态的进程呢？一般来说，会使用就绪队列，和阻塞队列，让处于阻塞态和就绪态的进程进入队列，排队执行。

这便是对于单个进程，经典的五状态模型。当存在多个进程时，由于同一时间只能有一个进程在执行，那么如何去管理这一系列的处于阻塞态和就绪态的进程呢？一般来说，会使用就绪队列，和阻塞队列，让处于阻塞态和就绪态的进程进入队列，排队执行。

七状态模型

一旦排队的进程多了，对于有限的内存空间将会是极大的考验。为了解决内存占用问题，可以将一部分内存中的进程交换到磁盘中，这些被交换到磁盘的进程，会进入挂起状态

挂起状态可以分为两种：

阻塞挂起状态：进程在外存(硬盘)并等待某个事件的出现；

就绪挂起状态：进程在外存(硬盘)，但只要进入内存，即刻立刻运行这两种挂起状态加上前面的五种状态，就变成了七种状态变迁，见如下图：

因为，这些状态变化的时候，操作系统需要考虑是否要让新的进程给CPU运行，或者是否让当前进程从CPU上退出来而换另一个进程运行。另外，如果硬件时钟提供某个频率的周期性中断，那么可以根据如何处理时钟中断，把调度算法分为两类：

非抢占式调度算法挑选一个进程，然后让该进程运行直到被阻塞，或者直到该进程退出，才会调用另外一个进程，也就是说不会理时钟中断这个事情（轮流执行，直到该进程执行结束才执行下一个）。
抢占式调度算法挑选一个进程，然后让该进程只运行某段时间，如果在该时段结束时，该进程仍然在运行时，则会把它挂起，接着调度程序从就绪队列挑选另外一个进程。这种抢占式调度处理，需要在时间间隔的末端发生时钟中断，以便把 CPU控制返回给调度程序进行调度，也就是常说的时间片机制（通过算法在多个进程见来回切换，CPU通常使用抢占式调度）。

以什么原则来进行调度

五种调度原则：

CPU利用率：调度程序应确保CPU是始终匆忙的状态，这可提高CPU的利用率；
系统吞吐量：吞吐量表示的是单位时间内CPU完成进程的数量，长作业的进程会占用较长的CPU资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；
周转时间：周转时间是进程运行和阻塞时间总和，一个进程的周转时间越小越好；
等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；
响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。说白了，这么多调度原则，目的就是要使得进程要「快」

进程调度算法

常见的进程调度算法有：

先来先服务
时间片轮转
最短作业优先
最短剩余时间优先
优先级调度
多级反馈队列调度

先来先服务

*先来先服务(First Come First Serverd， FCFS)。先进就绪队列，则先被调度，先来先服务是最简单的调度算法。

先来先服务存在上面谈论过的问题：当前面任务耗费很长时间执行，那么后面的任务即使只需要执行很短的时间，也必须一直等待，属于非抢占式。

时间片轮转调度

每一个进程会被分配一个时间片，表示允许该进程在这个时间段运行，如果时间结束了，进程还没运行完毕，那么会通过抢占式调度，将CPU分配给其他进程，该进程回到就绪队列。

这是一种最简单最公平的调度算法，但是有可能会存在问题。由于进程的切换，需要耗费时间，如果时间片太短，频繁进行切换，会影响效率。如果进程时间片太长，有可能导致排后面的进程等待太长时间。因此时间片的长度，需要有大致合理的数值。(《现代操作系统》的观点是建议时间片长度在 20ms~50ms)。

最短作业优先

最短作业优先( (Shortest Job First， SJF)，顾名思义即进程按照作业时间长短排队，作业时间段的排前面先执行，如下图

这显然对长作业不利，很容易造成一种极端现象。比如，一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行。

最短剩余时间优先

最短剩余时间优先 (Shortest Remaining Time Next)，从就绪队列中选择剩余时间最短的进程进行调度。该算法可以理解最短作业优先和时间片轮转的结合。如果没有时间片，那么最短剩余时间其实就是最短作业时间，因为每个进程都是从头执行到尾。

优先级调度

假设就绪队列中有如下进程：

进程	执行时间	优先级
p1	5	1
p2	3	2
p3	1	3

按照优先级调度，执行顺序为p1->p3->p2。如果多个进程优先级相同，则按照先来先服务的方式依次执行。

优先级调度可以进一步细分为抢占式和非抢占式。

非抢占式：和上面提及的非抢占式类似，一旦该进程占有CPU就将一直执行到拮束或者阻塞。

抢占式：进程执行期间，一旦有更高优先级的进程进入就绪队列，那么该进程就会被暂停，重回就绪队列，让更高优先级的进程执行。但是为了防止最高优先级进程一直执行，每个进程依然有自己的时间片，每次时间片结束后，会根据一定规则降低该进程优先级，避免某些最高优先级长作业进程一直占用CPU。但是依然有缺点，可能会导致低优先级的进程永远不会运行。

多级反馈队列调度

多级反馈队列调度基于时间片轮转和优先级调度，设置多个就绪队列，赋予每个就绪队列优先级，优先级越高的队列进程的时间片越短。如下图，第1级就绪队列优先级最高，进程的时间片长度最短，第2级就绪队列次之，以此类推。

当有新的进程创建时，先进入第1级就绪队列，时间片结束之前就运行完毕，则终止，否则进入第2级队列等待下一次调度。在n级队列之前，进程按照先到先服务规则依次调度，到了第n级队列(最后一级)采用时间片轮转调度。仅当第1级队列为空时，才调度第2级队列的进程，如果第级队列的进程正在运行，此时有一个更高优先级的进程进入，则会停下第级的进程，让它回到第级队列尾部，转而执行更高优先级的进程，即满足优先级调度算法的原则。