常用的进程调度算法

进程调度是由操作系统的进程调度程序按照某种策略和算法从就绪态进程中为当前空闲的CPU选择要运⾏的新进程，常用的进程调度算法有以下几种：

1. 先来先服务调度算法

从就绪队列的队⾸选择最先到达的进程，为该进程分配CPU。下面通过一个例子来说明先来先服务算法。

已知：就续队列中有3个进程， 分别为 P1、P2、P3，进入系统的时间分别为 0、1、2，服务时间分别为 24、3、3，求3个进程的系统 平均周转时间 和 带权平均周转时间 ？如下表所示：

我们知道：

1. 开始运行时间等于上个进程的结束时间。

2. 结束时间等于开始运行时间加上服务时间。

3. 周转时间等于结束时间减去进入时间。

4. 系统平均周转时间等于n个进程的周转时间之和除以n。

5. 带权平均周转时间等于n个进程中每个进程的周转时间除以服务时间的结果之和除以n。

根据以上基本知识计算结果如下：

先来先服务调度算法属于非抢占式调度算法。从表面上看，它对所有作业都是公平的，但若一个长进程先到达系统，就会使后面许多短进程等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度策略中使用，例如，在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按先来先服务原则处理。

​总结一下，先来先服务调度算法有以下特点：

1.算法简单，但效率低；

2.对长进程比较有利，但对短进程不利（相对短进程优先和高响应比)；

3.有利于CPU繁忙型作业，而不利于I/O繁忙型作业。

2. 短进程优先调度算法SPF

从就绪队列中选择估计运⾏时间最短的进程，为该进程分配CPU。下面通过一个例子来说明先来先服务算法。

已知：就续队列中有3个进程， 分别为 P1、P2、P3，进入系统的时间分别为 2、1、0，服务时间分别为 24、3、3，求3个进程的系统 平均周转时间 和 带权平均周转时间 ？如下表所示：

基本常识再说一遍：

1. 开始运行时间等于上个进程的结束时间。

2. 结束时间等于开始运行时间加上服务时间。

3. 周转时间等于结束时间减去进入时间。

4. 系统平均周转时间等于n个进程的周转时间之和除以n。

5. 带权平均周转时间等于n个进程中每个进程的周转时间除以服务时间的结果之和除以n。

根据以上基本知识计算结果如下：

通过短进程优先算法的运算特点，我们发现，如果有一长进程进入系统的后备队列，由于调度程序总是优先调度那些 (即使是后进来的）短进程，将导致长进程长期不被调度，就会出现所谓的“饥饿”现象。请注意"饥饿"现象与“死锁”现象的区别，"死锁"现象是系统环形等待，而"饥饿"现象属于调度策略问题。

​总结一下，短时程优先调度算法有以下特点：

1. 短进程优先算法与先来先服务算法相⽐，能有效降低进程的平均等待时间与周转时间，提高系统吞吐量。

2. 短进程优先算法对长进程不利，长进程的周转时间会增加。

3. 短进程优先算法完全未考虑作业的紧迫程度，不能保证紧迫性作业会被及时处理。

4. 短进程优先算中进程长短由用户估计，不⼀定准确，使该算法不一定能真正做到短进程优先调度。

3. 优先权调度算法

该算法中，系统将CPU分配给就绪队列中优先权最高的进程。

根据新进程能否抢占正在执行的进程，可将该调度算法分为：

1. 非抢占式优先权调度算法。运行期间，有更⾼的优先权的进程到来，也不能剥夺CPU。

2. 抢占式优先权调度算法。运行期间，有更⾼优先权的进程到来，可以抢占CPU。

根据进程优先级是否可以改变，可将该调度算法分为：

1. 静态优先权调度算法。优先级是在创建进程时确定的，且在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求。

2. 动态优先权调度算法。在进程运行过程中，根据进程情况的变化动态调整优先级。动态调整优先级的主要依据为进程占有CPU时间的长短、就绪进程等待CPU时间的长短。

在优先权调度算法中，如果一直有更高级别的进程进来，将会导致低优先权的进程一直等待，也就是所谓的"饥饿"现象，解决办法是采用"老化"技术，即增加等待时间很长进程的优先权。

4. 时间片轮转调度算法

系统将所有就绪进程按先来先服务的原则，排成一个队列，每次调度时 把CPU分给队首进程，并令其执行一个时间片。当时间片用完时，调度 程序终止当前进程的执行，并将它送到就绪队列的队尾，等待下次CPU执行。

在时间片轮转调度算法中，时间片的大小对系统性能的影响很大。如果时间片足够大，以至于所有进程都能在一个时间片内执行完毕，则时间片轮转调度算法就退化为先来先服务调度算法。如果时间片很小，那么处理机将在进程间过于频繁切换，使处理机的开销增大，而真正用于运行用户进程的时间将减少。所以时间片的大小应该遵守以下规则：

5. 多级队列调度算法

多级队列调度算法建⽴多个优先权不同的就绪队列，所有队列的优先权从大到到小依次排列，每个队列有自己的调度算法。

例如，有两个队列分别用于前台进程和后台进程，前台队列可以采用时间片轮转调度算法，而后台队列可以采用先来先服务调度算法。

现在，我们看一个多级队列调度算法的实例，这里有五个队列，它们的优先级由高到低：

队列之间的调度通常采用固定优先级抢占调度，因此，高优先级队列比低优先极队列相比具有绝对的优先。

例如，只有系统进程、交互进程和交互编辑进程队列都为空，批处理队列内的进程才可运行，如果在一个批处理进程运行时有一个交互进程进入就绪队列，那么该批处理进程会被抢占。

6. 多级队列反馈调度算法

多级反馈队列调度算法建⽴多个优先权不同的就绪队列，所有队列的优先权从大到到小依次排列，每个队列有自己的调度算法，并且每个队列的时间⽚也不同，优先权越高的队列中，进程时间片就越小；优先权越低的队列中，进程时间片就越大。

当一个新进程进入内存后，首先将它放入第一队列的末尾，按先来先服务原则排队等待调度。当轮到该进程执行时，如果它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按先来先服务原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，依次类推，当一个长作业(进程)从第一队列依次降到第n队列后，在第n 队列便采取按时间片轮转的方式运行。