最短作业优先 (SJF)：抢占式、非抢占式示例
纳撒尼尔·布鲁克斯
什么是最短作业优先调度？
最短作业优先 (SJF) 是一种选择执行时间最短的进程进行下一次执行的算法。这种调度方法可以是抢占式的，也可以是非抢占式的。它显著减少了等待执行的其他进程的平均等待时间。SJF 的全称是“最短作业优先”。
基本上有两种类型的 SJF 方法：
- 非抢占式 SJF
- 先发制人的 SJF
SJF调度的特点
- 它与每项工作相关联，作为完成的时间单位。
- 这种算法方法有助于批处理，因为等待作业完成并不重要。
- 它可以确保先执行较短的作业，从而提高流程吞吐量，并可能缩短周转时间。
- 它通过提供工期更短、周转时间更短的作业来提高工作效率，这些作业应该优先执行。
非抢占式 SJF
在非抢占式调度中，一旦 CPU 周期分配给一个进程，该进程就会一直占用该周期，直到它进入等待状态或被终止。
考虑以下五个进程，每个进程都有其独特的运行时间和到达时间。
| 进程队列 | 爆发时间 | 到达时间 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
步骤0） 在时间 = 0 时，P4 到达并开始执行。
步骤1） 在时间 1 时，进程 P3 到达。但 P4 还需要 2 个执行单元才能完成。它将继续执行。
步骤2） 在时间 = 2 时，进程 P1 到达并被添加到等待队列。P4 将继续执行。
步骤3） 在时间 = 3 时，进程 P4 将完成执行。比较 P3 和 P1 的突发时间。进程 P1 被执行，因为它的突发时间比 P3 短。
步骤4） 在时间 = 4 时，进程 P5 到达并被添加到等待队列。P1 将继续执行。
步骤5） 在时间 = 5 时，进程 P2 到达并被添加到等待队列。P1 将继续执行。
步骤6） 在时间 = 9 时，进程 P1 将完成执行。比较 P3、P5 和 P2 的突发时间。进程 P2 被执行，因为它的突发时间最短。
步骤7） 在时间 = 10 时，P2 正在执行，而 P3 和 P5 在等待队列中。
步骤8） 在时间 = 11 时，进程 P2 将完成执行。比较 P3 和 P5 的突发时间。进程 P5 被执行，因为它的突发时间较短。
步骤9） 在时间 = 15 时，进程 P5 将完成其执行。
步骤10） 在时间 = 23 时，进程 P3 将完成其执行。
步骤11） 让我们来计算一下上述例子的平均等待时间。
Wait time P4 = 0 - 0 = 0 P1 = 3 - 2 = 1 P2 = 9 - 5 = 4 P5 = 11 - 4 = 7 P3 = 15 - 1 = 14
Average Waiting Time = (0 + 1 + 4 + 7 + 14)/5 = 26/5 = 5.2
先发制人的 SJF
在抢占式最短作业优先调度算法中，作业到达后会立即进入就绪队列。执行时间最短的进程开始执行。如果之后有执行时间更短的进程到达，则当前进程会被移除或抢占，并将一个 CPU 周期分配给执行时间更短的进程。
请考虑以下五个过程：
| 进程队列 | 爆发时间 | 到达时间 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
步骤0） 在时间 = 0 时，P4 到达并开始执行。
| 进程队列 | 爆发时间 | 到达时间 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
步骤1） 在时间 1 时，进程 P3 到达。但进程 P4 的执行时间较短，它将继续执行。
步骤2） 在时间 = 2 时，进程 P1 到达，突发时间 = 6。突发时间大于 P4。因此，P4 将继续执行。
步骤3） 在时间 = 3 时，进程 P4 将完成执行。比较 P3 和 P1 的突发时间。进程 P1 被执行，因为它的突发时间较短。
步骤4） 在时间 = 4 时，进程 P5 将到达。比较 P3、P5 和 P1 的突发时间。进程 P5 被执行，因为它的突发时间最短。进程 P1 被抢占。
| 进程队列 | 爆发时间 | 到达时间 |
|---|---|---|
| P1 | 5 人中剩下 6 人 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
步骤5） 在时间 t = 5 时，进程 P2 将到达。比较进程 P1、P2、P3 和 P5 的执行时间。由于进程 P2 的执行时间最短，因此执行该进程。进程 P5 被抢占。
| 进程队列 | 爆发时间 | 到达时间 |
|---|---|---|
| P1 | 5 人中剩下 6 人 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 人中剩下 4 人 | 4 |
步骤6） 在时间 = 6 时，P2 正在执行。
步骤7） 在时间 7 时，进程 P2 执行完毕。比较进程 P1、P3 和 P5 的运行时间。由于进程 P5 的运行时间最短，因此执行该进程。
| 进程队列 | 爆发时间 | 到达时间 |
|---|---|---|
| P1 | 5 人中剩下 6 人 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 人中剩下 4 人 | 4 |
步骤8） 在时间 t = 10 时，进程 P5 将执行完毕。比较进程 P1 和 P3 的运行时间。由于进程 P1 的运行时间更短，因此执行进程 P1。
步骤9） 在时间 15 时，进程 P1 执行完毕。此时只剩下进程 P3，它将开始执行。
步骤10） 在时间 = 23 时，P3 执行完毕。
步骤11） 让我们来计算一下上述例子的平均等待时间。
Wait time P4 = 0 - 0 = 0 P1 = (3 - 2) + 6 = 7 P2 = 5 - 5 = 0 P5 = 4 - 4 + 2 = 2 P3 = 15 - 1 = 14
Average Waiting Time = (0 + 7 + 0 + 2 + 14)/5 = 23/5 = 4.6
SJF 的优势
以下是使用SJF方法的优点/好处：
- SJF 经常用于长期调度。
- 与先进先出 (FIFO) 算法相比，它减少了平均等待时间。
- SJF 方法能够使一组特定进程的平均等待时间最短。
- 它适用于批量运行的作业，其中运行时间是预先知道的。
- 对于长期调度的批处理系统，可以从作业描述中得到突发时间的估计。
- 对于短期调度，我们需要预测下一个突发时间的值。
- 就平均周转时间而言，这可能是最佳方案。
SJF 的缺点
以下是SJF算法的一些缺点：
- 必须提前知道作业的完成时间，但很难预测。
- 它通常用于批处理系统中的长期调度。
- 无法实现SJF CPU调度 短期内。这是因为没有特定的方法来预测即将到来的 CPU 突发的长度。
- 该算法可能会导致非常长的周转时间或饥饿。
- 需要了解流程或作业将运行多长时间。
- 这会导致粮食短缺，但并不会缩短平均周转时间。
- 很难知道即将到来的 CPU 请求的长度。
- 需要记录经过的时间，这会增加处理器的负担。
