最短作业优先 (SJF) 调度算法

---

---

CPU调度策略是一种选择一个处于等待状态的进程并将其分配给CPU以便执行的过程。存在多种调度算法。在本节中，我们将学习最短作业优先 (SJF) 调度算法。

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

在最短作业优先调度算法中，进程按其CPU突发时间的升序进行调度，即CPU分配给执行时间最短的进程。

SJF 调度算法的变体

SJF 调度算法有两个变体：

非抢占式 SJF 调度

在非抢占式版本中，一旦一个进程被分配给CPU，它就会一直运行到完成。在此，当一个进程完成执行或当一个或多个新进程到达空的准备队列时，就会调用短期调度程序。

抢占式 SJF 调度

这是 SJF 调度的抢占式版本，也称为最短剩余时间优先 (SRTF) 调度算法。在这里，如果在较长进程执行期间，较短进程进入准备队列，则会发生进程切换，即将正在执行的进程交换到准备队列，而新到达的较短进程开始执行。因此，短期调度程序在系统中到达新的进程或现有进程完成执行时被调用。

SJF 算法的特性

• SJF 将 CPU 分配给执行时间最短的进程。
• 如果两个或多个进程具有相同的突发时间，则根据先到先服务原则在这几个进程之间进行仲裁。
• 存在抢占式和非抢占式版本。
• 它最大限度地减少了进程的平均等待时间。
• 如果短进程持续进入系统，则可能会导致长进程饥饿。

我们可以通过以下示例了解这两种调度策略的工作原理。

非抢占式 SJF 算法示例

示例 1

假设我们有一组四个进程同时到达，顺序为 P1、P2、P3 和 P4。每个进程的突发时间（毫秒）如下表所示：

P3

4

P4

8

让我们绘制甘特图，并使用非抢占式 SJF 算法找到平均周转时间和平均等待时间。

使用 SJF 的进程集的甘特图

进程 P3 的突发时间最短，因此它首先执行。然后我们发现 P1 和 P4 的突发时间相同，均为 8ms。由于 P1 先到达，因此 CPU 分配给 P1，然后分配给 P4。最后执行 P2。因此，执行顺序为 P3、P1、P4、P2，如下面的甘特图所示：

让我们根据上图计算平均周转时间和平均等待时间。

平均周转时间

= 各进程周转时间之和 / 进程数

= (TAT_P1 + TAT_P2 + TAT_P3 + TAT_P4) / 4

= (12 + 36 + 4 + 20) / 4 = 18 ms

平均等待时间

= 各进程等待时间之和 / 进程数

P3

示例 2

在前面的示例中，我们假设所有进程同时到达，这在实践中是不可能的。在这里，我们考虑进程在不同时间到达的情况。假设我们有一组四个进程，其到达时间和 CPU 突发时间如下：

到达时间

CPU 突发时间

甘特图

在绘制甘特图时，我们将考虑在调用调度程序时系统中到达了哪些进程。在 0ms 时，只有 P1 存在，因此它被分配给 CPU。P1 在 6ms 完成执行，此时 P2 和 P3 已到达，但 P4 尚未到达。P3 被分配给 CPU，因为在当前进程中它具有最短的突发时间。P3 在 10ms 完成执行。到那时，P4 已到达，因此在进程 P2 和 P4 上运行 SJF 算法。因此，我们发现执行顺序为 P1、P3、P4、P2，如下面的甘特图所示：

让我们计算每个进程的周转时间，并计算平均值。

进程的周转时间 = 完成时间 - 到达时间

让我们绘制甘特图，并使用非抢占式 SJF 算法找到平均周转时间和平均等待时间。

TAT_P1 = CT_P1 - AT_P1 = 6 - 0 = 6 ms

TAT_P2 = CT_P2 - AT_P2 = 23 - 4 = 19 ms

TAT_P3 = CT_P3 - AT_P3 = 10 - 4 = 6 ms

TAT_P4 = CT_P4 - AT_P4 = 13 - 8 = 5 ms

= 各进程周转时间之和 / 进程数

= (6 + 19 + 6 + 5) / 4 = 9 ms

等待时间由每个进程在准备队列中等待的时间给出。对于非抢占式调度算法，每个进程的等待时间可以简单地计算为：

任何进程的等待时间 = CPU 接纳时间 - 到达时间

平均周转时间

WT_P1 = 0 - 0 = 0 ms

= (TAT_P1 + TAT_P2 + TAT_P3 + TAT_P4) / 4

WT_P2 = 13 - 4 = 9 ms

WT_P3 = 6 - 4 = 2 ms

WT_P4 = 10 - 8 = 2 ms

示例 2

= 各进程等待时间之和 / 进程数

= (0 + 9 + 2 + 2) / 4 = 3.25 ms

抢占式 SJF (SRTF) 算法示例

让我们绘制甘特图，并使用非抢占式 SJF 算法找到平均周转时间和平均等待时间。

TAT_P1 = CT_P1 - AT_P1 = 6 - 0 = 6 ms

进程 P3 的突发时间最短，因此它首先执行。然后我们发现 P1 和 P4 的突发时间相同，均为 8ms。由于 P1 先到达，因此 CPU 分配给 P1，然后分配给 P4。最后执行 P2。因此，执行顺序为 P3、P1、P4、P2，如下面的甘特图所示：

现在让我们对以下进程执行抢占式 SJF (SRTN) 调度，绘制甘特图并找到平均周转时间和平均等待时间。

平均周转时间

WT_P1 = 0 - 0 = 0 ms

= (TAT_P1 + TAT_P2 + TAT_P3 + TAT_P4) / 4

由于这是一个抢占式调度算法，因此当进程到达和完成执行时都会调用调度程序。调度程序计算系统中每个进程的剩余完成时间，并选择剩余执行时间最短的进程。

最初，只有 P1 到达，因此它被分配给 CPU。在 4ms 时，P2 和 P3 到达。调度程序计算进程 P1、P2 和 P3 的剩余时间为 4ms、10ms 和 3ms。由于 P3 的时间最短，因此 P1 被 P3 抢占。P3 在 7ms 完成执行，并调用调度程序。在系统中的进程中，P1 的时间最短，因此它继续执行。在 10ms 时，P4 到达，调度程序再次计算每个进程的剩余时间。由于 P1 的剩余时间最短，因此不发生进程切换，P1 继续执行。以类似的方式，其余进程完成执行。

• 根据甘特图，我们计算平均周转时间和平均等待时间。
• = ((11 - 0) + (25 - 4) + (7 - 4) + (15 - 10)) / 4 = 10 ms
• = (3 + 11 + 0 + 1) / 4 = 3.75 ms

SJF 算法的优点

• 与 FCFS 调度相比，在抢占式和非抢占式方法中，SJF 的平均等待时间都大大减少。
• SJF 在相当程度上优化了周转时间。
• 如果精确估计每个进程的执行时间，它可以保证最大吞吐量。

SJF 算法的缺点

如果存在具有较短突发时间的进程流，则系统中的较长进程可能会无限期地等待在准备队列中，从而导致饥饿。