[数据结构与算法]常用的调度算法（包含实例）|操作系统

1.先来先服务调度算法（FCFS）

$原理：$

$?$ 先来先服务（First-Come-First-served）调度算法是最简单的非抢占的调度算法。

$?$ 它通过管理一个FIFO就绪队列来实现，从前到后按顺序将CPU分配给进程。

$举例：$

$?$ 现在有如下一组进程：

所以执行顺序为 $<P_1、P_2、P_3>$ ,我们画出它的甘特图来形象的理解：

下面的时刻表示该进程占用CPU的执行时间。（后面的几种调度方法也使用甘特图来帮助理解。）

所以可以计算求得三个进程的平均等待时间为：
$$\frac{0+30+35}{3}\approx 21.7$$

$特点：$

$?$ FCFS调度算法对短进程不利，尤其当一个短进程跟在长进程后面时，它需要等待很长的时间。有时候会导致CPU和设备的利用率很低，在实际情况中，FCFS算法通常与其他算法结合使用。

2.优先级调度算法

$原理：$

$?$ 由用户或者系统按照某种原则给进程一个优先级，系统总是调度优先级最高的那个进程运行。

$?$ 优先级可以分为静态优先级和动态优先级。静态优先级就是指优先级确定以后就不再改变，比如说按照它们的执行时间长短来确定等等；动态优先级会随着进程的不断执行而发生改变，比如说可以按照等待时间的长短划分优先级等等。

$?$ 对优先级动态调整可以改善系统性能，但是动态优先级调度算法会增加系统开销。

$举例：$

$?$ 现在有如下一组进程（采用静态优先级调度算法）：

所以执行顺序为 $<P_2、P_3、P_4、P_1>$，我们画出它的甘特图如下：

所以可以计算求得四个进程的平均等待时间为：
$$\frac{0+4+6+7}{4}=4.25$$

$特点：$

$?$ 可能会出现“饥饿”现象，就是优先级低的进程会一直等待CPU，未来避免这种问题的出现，我们可以采用“老化”的策略，就是按一定时间间隔提高等待进程的的优先级数值。

$?$ 我们假设它们几乎同时到达，但是实际情况中总会有先后顺序，在支持抢占的系统中，当新进程进入就绪队列时，如果它的优先级高于当前运行进程的优先级，那么就会抢占CPU；在非抢占系统中，只是将新进程加入了就绪队列中。

3.最短作业优先调度算法（SJF）

$原理：$

$?$ 最短作业优先（Shortest-Job First）调度算法克服了FCFS的对短进程不利的缺点，它在就绪队列中选择处理时间最短的进程，如果时间相同则可以按照FCFS准则来处理。

$?$ 它提高了系统的吞吐量，但是反过来又对长进程不利。

$?$ 它分为抢占式和非抢占式两种情况

$举例：$

$?$ 现在有如下一组进程，假设它们同时到达（非抢占式）：

所以执行顺序为 $<P_4、P_2、P_1、P_3>$，我们画出它的甘特图如下：

所以可以计算求得三个进程的平均等待时间为：
$$\frac{0+3+7+12}{4}=5.5$$

$?$ 现在有如下一组进程，假设它们不同时到达（抢占式）：

最初只有P₁进程，那么执行P₁进程；当时间1时P₂到达，此时P₁剩余执行时间为7，P₂执行时间为4，那么执行P₂进程；当时间2时，P₃到达，此时最短执行时间仍然为P₂；时间3时，P₄到达，此时P₂执行时间为2，P₄也为2，所以先让P₂执行完在让P₄执行，然后再让P₁执行，最后在让P₃执行。

所以执行顺序为 KaTeX parse error: Expected 'EOF', got '}' at position 31: …{4}、P_{1}、P_{3}}?>，我们画出它的甘特图如下：

所以可以计算求得三个进程的平均等待时间为：
$$\frac{((10?1)+0+(17?2)+(5?3))}{4}=6.5$$

分母上面的式子为每个进程开始执行的时间减去开始等待的时间之和。

$特点：$

$?$ 对于非抢占的SJF调度算法，可以看作是优先级调度算法的一种特例。

4.最高相应比优先调度算法（HRRN）

$原理：$

$?$ 最高响应比（Highest Response Ratio Next）调度算法集合了FCFS算法和非抢占SJF算法的优点，使用响应比R来表征，即：
$$R=\frac{W+S}{S}(W为等待时间、S为预计执行时间)$$

$?$ 在该算法下，等待时间相同的时候短进程响应比高于长进程，短进程优先被调度；而随着等待时间增长，进程的响应比增加，长进程被调度的可能性也会增加。

$举例：$

$?$ 现在有如下一组进程如下：

$?$ 0时刻P₁运行，10时刻P₁运行完毕，此时P₂ ~ P₅的响应比为：

$$P_2:\frac{1+9}{1}=10;P_3:\frac{2+8}{2}=5;$$

$$P_3:\frac{1+7}{1}=8;P_4:\frac{5+6}{2}=5.5;$$

$?$ 所以P₂运行，直到11时刻运行结束，此时P₃ ~ P₅的响应比为：

$$P_3:\frac{2+9}{2}=5.5;P_4:\frac{1+8}{2}=9;P_5:\frac{5+7}{5}=2.4;$$

$?$ 所以P₄运行，直到12时刻运行结束，此时P₃ 和 P₅的响应比为：

$$P_3:\frac{2+10}{2}=6;P_5:\frac{5+8}{5}=2.6;$$

$?$ 所以先执行P₃，后执行P₅。

$?$ 所以执行顺序为 KaTeX parse error: Expected 'EOF', got '}' at position 31: …{4}、P_{3}、P_{5}}?>，我们画出它的甘特图如下：

所以可以计算求得五个进程的平均等待时间为：
$$\frac{(0+(10?1)+(11?2)+(12?3)+(14?4))}{5}=7.4$$

5.轮转调度算法（RR）

$原理：$

$?$ 轮转（Round Robin）调度算法是一种基于抢占的调度策略，在分时系统中，每个进程会被分配一个固定的时间片，就绪队列中的进程按顺序依此调度运行。

$?$ 时间片过短会使进程切换过于频繁，增加系统开销；时间片过长会使进程响应时间增加。

$举例：$

$?$ 现在有如下一组进程如下：

这里时间片我们选择为4，按照原理可得甘特图如下：

所以可以计算求得三个进程的平均等待时间为：
$$\frac{6+4+7}{3}\approx 5.67$$

6.多级反馈轮转调度算法

$原理：$

$?$ 是对简单轮转调度算法的改进，它把新就绪的进程和被抢占后回到就绪队列的进程加以区分，将它们放入不同优先级的就绪队列中；

$?$ 被抢占后放回就绪队列的进程优先级会降低，但是运行的时间片长度会增加。

7.实时系统的调度算法

$原理：$

$?$ 在实时系统中会给出一个最后期限，最后期限指定任务开始或结束的时间，任务必须严格按照最后期限执行。