最短作业优先（SJF）调度

引言

到目前为止，我们一直根据进程的到达时间进行调度（FCFS 调度）。然而，SJF 调度算法根据进程的突发时间进行调度。

在 SJF 调度中，就绪队列中可用进程列表中突发时间最短的进程将被安排在下一个执行。

然而，预测进程所需的突发时间非常困难，因此该算法在系统中很难实现。

最短作业优先（SJF）或最短作业下一个（SJN）调度方法选择具有最短执行时间的等待进程运行。这种调度技术可能抢占，也可能不抢占。它显著减少了其他进程完成的平均等待时间。

SJF 调度的特点

• 在所有操作系统调度算法中，最短作业优先的优点是它具有最低的平均等待时间。
• 每个任务都与特定的完成时间相关联。
• 如果较短的进程持续出现，可能会导致饥饿。老化是一种可以用来解决这个问题的概念。

SJF 调度的类型

SJF 调度有两种类型。它们是：

1. SJF 非抢占式调度

在非抢占式版本中，进程一旦分配给 CPU，就会一直执行直到完成。当进程运行结束或新进程或多个进程进入空的就绪队列时，短期调度程序会被触发。

2. SJF 抢占式调度

它也被称为最短剩余时间优先 (SRTF) 调度算法，这是 SJF 调度的抢占式变体。当一个较短的进程在较长的进程正在运行时加入就绪队列时，正在执行的进程会被切换到就绪队列，新到达的较短进程开始运行。这称为进程切换。因此，当新进程进入系统或现有进程运行结束时，短期调度程序会被触发。

SJF 调度的实现

• 根据到达时间对所有进程进行排序。
• 接下来选择到达时间和突发时间最短的进程。
• 进程完成后，创建一个就绪队列或进程池，其中包含在前一个进程完成后到达的进程，并从该队列中选择突发时间最短的进程。

SJF 调度估计公式概念

最短作业优先（SJF）调度算法选择突发时间最短的进程来运行。然而，进程的精确突发时间可能并非总能提前知道。在这些情况下，使用考虑过去突发时间的估计公式来预测下一个突发时间。

估计公式

其中

• T_n+1：后续操作的估计突发时间。
• T_n：之前估计的突发时间。
• t_n：前一个进程的实际突发时间。
• α：平滑因子 0 ≤ α ≤ 1。

示例

在以下示例中，有五个作业，命名为 P1、P2、P3、P4 和 P5。它们的到达时间和突发时间如下表所示。

由于在时间 0 没有进程到达，因此在甘特图中，从时间 0 到 1（第一个进程到达的时间）将有一个空槽。

根据算法，操作系统会调度就绪队列中可用进程中突发时间最短的进程。

到目前为止，就绪队列中只有一个进程，因此调度程序将调度它到处理器，无论其突发时间是多少。

这将执行 8 个时间单位。在此之前，就绪队列中又到达了三个进程，因此调度程序将选择突发时间最短的进程。

在表中给出的进程中，P3 将在下一个执行，因为它在所有可用进程中具有最短的突发时间。

因此，最短作业优先（SJF）调度算法中的过程就是这样进行的。

平均等待时间 = 27/5

SJF 的优点

1. 最大化吞吐量
2. 平均等待时间和周转时间最短

SJF 的缺点

1. 可能出现饥饿问题
2. 无法实现，因为无法提前知道进程的准确突发时间。

结论

由于它在理论上能产生最佳结果，最短作业优先调度可以被称为最优调度算法。但与先来先服务或循环调度相比，其实现要复杂得多，执行也更不确定。