最短作业优先 (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

在抢占式 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） 在时间 = 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） 在时间 =10 时，P5 将完成其执行。比较 P1 和 P3 的突发时间。进程 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 请求的长度。
• 应该记录经过的时间，这会导致处理器的更多开销。

总结

• SJF 是一种选择执行时间最短的进程进行下一次执行的算法。
• SJF 调度与每项作业相关联，作为完成的时间单位。
• 这种算法方法有助于批处理，因为等待作业完成并不重要。
• SJF 方法基本上有两种类型：1) 非抢占式 SJF 和 2) 抢占式 SJF。
• 在非抢占式调度中，一旦将 CPU 周期分配给进程，该进程就会一直持有该周期，直到达到等待状态或终止。
• 在抢占式 SJF 调度中，作业一到达就被放入就绪队列。
• 尽管开始了一个具有较短突发时间的进程，但当前进程将被移除或被抢占而不执行，并且首先执行较短的作业。
• SJF 经常用于长期调度。
• 它通过 FIFO（先进先出）算法减少了平均等待时间。
• 在SJF调度中，作业的完成时间必须提前知道，但很难预测。
• SJF 无法用于短期 CPU 调度。这是因为没有特定的方法来预测即将到来的 CPU 突发的长度。