进程调度算法有哪些

《进程调度是什么》一节讲到在多任务操作系统中，整个进程调度机制可能包含 3 种进程调度程序，分别是长期调度程序、短期调度程序和中期调度程序。

根据指定的调度策略（算法），长期调度程序可以从用户发布的诸多任务中挑选出一个任务，并将其移入内存；中期调度程序可以从外存中处于就绪或者等待状态的诸多进程中挑选出一个进程，并将其移入内存；短期调度程序可以从内存中处于就绪状态的诸多进程中挑选出一个进程，并将 CPU 资源分配给它。

不同种类的操作系统，其采用的任务（进程）调度算法也不相同。本节，我们将带您了解一些常见的调度算法。

1、先来先服务调度算法

先来先服务调度算法简称 FCFS 调度算法，既适用于任务调度，也适用于进程调度，是最简单的一种调度算法，广泛应用于批处理操作系统中。

顾名思义，FCFS 算法的核心调度思想是：最早发布的任务最先得到调度，最早请求 CPU 资源的进程最先获得 CPU 资源。FCFS 算法属于非抢占式调度算法，即只有获得 CPU 资源的进程执行完毕后，其它进程才能执行。

FCFS 算法看似很公平，但对于一些在长任务（进程）之后进入内存的短任务（进程）来说，它们需要等待足够长的时间，直到长任务执行完毕后才能获得 CPU 资源。因此在单位时间内，FCFS 算法调度的进程数量较少（吞吐量较低）。

FCFS 算法很少单独使用，而是和其它一些算法搭配使用。例如在基于优先级的调度算法中，对于具有同样优先级的多个任务或者进程，需要进一步采用 FCFS 算法确定它们的执行顺序。

2、最短作业优先调度算法

最短作业优先调度算法（简称 SJF 算法）既适用于进程调度，也适用于任务调用，属于非抢占式调度算法。

SJF 算法的核心调度思想是：执行时间最短的任务或者进程最先得到调度。也就是说，用户发布的所有任务中执行时间最短的任务会优先得到调度，就绪队列中执行时间最短的进程会优先获得 CPU 资源。

使用最短作业优先调度算法，可以保证操作系统在同一时间内处理的任务或进程数最多，即吞吐量大于其它的调度算法。但是，如果系统中不断有执行时间短的新任务进入，那么执行时间长的任务将永远得不到执行的机会。

3、最高响应比优先调度算法

FCFS 算法只考虑了每个任务（进程）的等待时间，而未考虑不同任务（进程）的执行时间；SJF 算法正好相反，只考虑了每个任务（进程）的执行时间，而未考虑等待时间。

最高响应比优先调度算法（简称 HRN 算法）对 FCFS 和 SJF 这两种极端的算法做了平衡，它基于每个任务（进程）的等待时间和执行时间，通过比较每个任务（进程）的响应比，谁的响应比最大，就优先得到调度。

任务（进程）响应比的求值公式为：(W+T)/T，其中 W 表示任务（进程）的等待时间，T 表示任务（进程）的执行时间。

HRN 算法的不足之处在于，每次进行任务调度或者进程调度，都要提前计算出每个任务（进程）的响应比，才能挑选出响应比最大的任务或进程，无疑会影响整体的系统效率。

4、轮转法

轮转法是一种抢占式调度算法，只适用于进程调度，无法进行任务调度。

轮转法的调度思想是：将 CPU 资源轮流分配给各个进程使用，每个进程使用固定大小的时间（又称时间片）。对于在时间片内未执行完的进程，调度算法会将它中断并将 CPU 资源分配给下一个进程，直到该进程再次分配到 CPU 资源，它才可以继续执行。

轮转法常用于分时操作系统中。

5、优先级调度法

优先级调度算法是批处理操作系统中最常见的调度算法之一，既适用于进程调度，也适用于任务调度。

所谓优先级调度算法，指的是由用户或者操作系统为每个任务（进程）设定一个优先级，优先级最高的任务（进程）最先得到调度，优先级相同的任务或进程，通常借助 FCFS 算法进一步判断出它们的执行顺序。

任务（进程）的优先级，通常用固定区间内的数字表示，如 0~7 或 0~4095。有的操作系统中，数字越小优先级越低；有的则正好相反，数字越小优先级越高。

使用此方法调度 CPU 时，它可能是抢占式调度算法，也可能是非抢占调度算法。假设新进程的优先级高于当前正在执行的进程，如果调度算法立即将 CPU 资源分配给新进程，则它属于抢占式调度算法；反之，如果调度算法将新进程作为下一个要执行的进程，则它属于非抢占式调度算法。

6、多级队列调度算法

我们知道，进入内存后的进程，其 PCB 会进入就绪队列，等待分配 CPU 资源。

多级队列调度算法的核心思想是，根据各个进程的某些属性（例如所占内存大小、进程优先级、进程类型等），将就绪队列分割成很多队列，同一属性的进程位于同一队列，如下图所示：
通常情况下，不同的队列设定有不同的优先级，优先级越高的队列，其内部的进程会优先执行。至于同一队列中进程的执行顺序，各个队列可以使用不同的调度算法，例如 FCFS 算法，轮转法等。