操作系统调度算法

---

---

进程调度器根据特定的调度算法，将不同的进程分配给CPU。本章将讨论六种常用的进程调度算法：

• 先来先服务 (FCFS) 调度
• 最短作业优先 (SJN) 调度
• 优先级调度
• 最短剩余时间优先
• 轮询 (RR) 调度
• 多级队列调度

这些算法是非抢占式或抢占式的。非抢占式算法的设计使得一旦一个进程进入运行状态，它就不能被抢占，直到它完成分配的时间，而抢占式调度是基于优先级的，当高优先级的进程进入就绪状态时，调度程序可以随时抢占低优先级的运行进程。

先来先服务 (FCFS)

• 作业按先来先服务的顺序执行。
• 这是一种非抢占式、可抢占的调度算法。
• 易于理解和实现。
• 其实现基于 FIFO 队列。
• 性能较差，因为平均等待时间较长。

每个进程的**等待时间**如下：

平均等待时间：(0+4+6+13) / 4 = 5.75

最短作业优先 (SJN)

• 这也被称为**最短作业优先**，或 SJF。

• 这是一种非抢占式、可抢占的调度算法。

• 最小化等待时间的最佳方法。

• 易于在批处理系统中实现，其中所需的 CPU 时间是预先知道的。

• 无法在交互式系统中实现，因为所需的 CPU 时间是未知的。

• 处理器应该预先知道进程需要多长时间。

已知：进程表及其到达时间、执行时间

每个进程的**等待时间**如下：

平均等待时间：(0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

基于优先级的调度

• 优先级调度是一种非抢占式算法，也是批处理系统中最常见的调度算法之一。

• 每个进程都分配一个优先级。优先级最高的进程首先执行，依此类推。

• 具有相同优先级的进程按先来先服务的顺序执行。

• 优先级可以根据内存需求、时间需求或任何其他资源需求来决定。

已知：进程表及其到达时间、执行时间和优先级。这里我们认为 1 是最低优先级。

每个进程的**等待时间**如下：

平均等待时间：(0 + 10 + 12 + 2)/4 = 24 / 4 = 6

最短剩余时间优先

• 最短剩余时间 (SRT) 是 SJN 算法的抢占式版本。

• 处理器分配给最接近完成的作业，但它可以被一个具有更短完成时间的新就绪作业抢占。

• 无法在交互式系统中实现，因为所需的 CPU 时间是未知的。

• 它通常用于需要优先处理短作业的批处理环境。

轮询调度

• 轮询是一种抢占式进程调度算法。

• 每个进程都被提供一个固定的执行时间，这被称为**时间片**。

• 一旦一个进程执行了一定的时间段，它就会被抢占，然后其他进程执行一定的时间段。

• 上下文切换用于保存被抢占进程的状态。

每个进程的**等待时间**如下：

平均等待时间：(9+2+12+11) / 4 = 8.5

多级队列调度

多级队列不是一个独立的调度算法。它们利用其他现有的算法对具有共同特征的作业进行分组和调度。

• 为具有共同特征的进程维护多个队列。
• 每个队列可以有自己的调度算法。
• 为每个队列分配优先级。

例如，CPU 密集型作业可以安排在一个队列中，所有 I/O 密集型作业安排在另一个队列中。然后，进程调度程序交替地从每个队列中选择作业，并根据分配给该队列的算法将它们分配给 CPU。