最短作业优先（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	还剩 6 个中的 5 个	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

步骤 5） 在时间=5 时，进程 P2 到达。比较 P1、P2、P3 和 P5 的突发时间。执行进程 P2，因为它的突发时间最少。进程 P5 被抢占。

进程队列	执行时间	到达时间
P1	还剩 6 个中的 5 个	2
P2	2	5
P3	8	1
P4	3	0
P5	还剩 4 个中的 3 个	4

步骤 6） 在时间=6 时，P2 正在执行。

步骤 7） 在时间=7 时，P2 完成其执行。比较 P1、P3 和 P5 的突发时间。执行进程 P5，因为它的突发时间较短。

进程队列	执行时间	到达时间
P1	还剩 6 个中的 5 个	2
P2	2	5
P3	8	1
P4	3	0
P5	还剩 4 个中的 3 个	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 突发时间的长度。