Python 程序实现最短作业优先 (SJF) CPU 调度

在 CPU 中，调度方法选择进程执行的顺序，从而管理等待时间。其中一种方法称为“最短作业优先”(SJF) 或“最短作业下一个”。此算法首先运行执行时间最短的进程。另一种称为最短作业下一个 (SJN) 的方法，通常用作 SJN，也可以使用。

SJF 调度的特点

最短作业优先可以使用贪心算法实现。

此算法的优点在于，它拥有所有可用 CPU 调度算法中最低的平均等待时间。

然而，如果不断出现执行时间较短的进程，则可能导致饿死。可以通过实现老化概念来解决此特定问题。

由于操作系统无法了解突发时间，因此几乎不可能对其进行分类。尽管无法预测进程的完整执行时间，但可以通过各种技术来确定，例如计算先前执行时段的加权平均值。

在提供准确运行时间估计的专门设置中可以使用 SJF。

算法

• 我们将首先按照到达时间对进程进行排序。
• 然后，我们将选择到达时间最短且突发时间最短的特定进程。
• 然后，我们将创建一个在刚刚完成的进程之后由 CPU 执行的进程集合，并选择该进程之后突发时间最短的进程。
• 完成时间是指进程已到达其执行结束的时间。
• 周转时间定义为进程的完成时间戳与到达时间戳之间的时间差。

周转时间 = 任何特定进程的完成时间 - 任何特定进程的到达时间。

• 等待时间定义为周转时间与特定进程的突发时间之差。

等待时间 = 进程的周转时间 - 进程的突发时间

段树是一种数据结构，可用于构建非抢占式的最短作业优先方法。

在继续之前，需要牢记一个假设。假定到达时间为零，这意味着进程的周转时间和完成时间将相同。

在 Python 中实现 SJF 算法

代码

输出

Enter the number of processes: 10
Enter the Burst Time of the processes:
P1: 4
P2: 3
P3: 7
P4: 9
P5: 1
P6: 10
P7: 14
P8: 11
P9: 5
P10: 16
P	B_T	W_T	TA_T
P5	1	0	1
P2	3	1	4
P1	4	4	8
P9	5	8	13
P3	7	13	20
P4	9	20	29
P6	10	29	39
P8	11	39	50
P7	14	50	64
P10	16	64	80
The average Waiting Time for the whole sequence of processes is = 22.8
The average Turn Around Time of the processes is = 30.8

时间复杂度：此 SJF 算法的时间复杂度为 O(n^2)。时间复杂度是非线性的，因为我们使用嵌套循环来排序突发时间和进程 ID。

辅助空间：此方法需要 O(n) 的额外内存空间。我们正在存储进程的数组。

最短作业优先算法的优点

• 此算法的进程管理方式比先来先服务 (FCFS) 等其他算法具有更短的等待时间。
• 此算法通常用于长期调度。
• 它适用于运行批处理作业且具有已知运行时间的作业。
• 就平均周转时间而言，SJF 可能是最佳选择。

最短作业优先算法的缺点

• SJF 可能导致饿死或周转时间长。
• SJF 需要提前提供作业完成的时间表，尽管这有时可能很困难。
• 通常很难预测即将到来的 CPU 请求将持续多久。
• 它会导致饿死，并且不会缩短典型的周转时间。

最短剩余时间优先 (SRTF)

最短作业优先 (SJF) 算法的抢占版本称为最短剩余时间优先 (SRTF)。此算法将 CPU 分配给即将完成的任务。

此技术不能用于交互式系统，因为它需要对完成任务所需的 CPU 时间有深入的了解。然而，SRT 方法用于批处理系统，在这些系统中，优先处理小作业至关重要。

然而，SRT 比 SJN 具有额外的开销，因为它需要频繁的操作系统上下文切换，并且需要监视队列中进程的 CPU 时间。

对于相同的进程集，SRT 方法比 SJF 算法执行得更快。然而，在这种情况下，忽略了运行成本，即执行上下文切换所需的时间。所有被视为可抢占的任务的处理数据必须存储在其对应的 PCB 中，以便随时可以恢复，而其他进程（即操作系统正在切换到的进程）的数据则被写入通常称为寄存器的位置。这就是上下文切换的过程。

优点

• 如果我们忽略 SRTF 功能中的开销成本，它的处理速度会比 SJF 算法快。
• 此算法有助于更轻松地管理库的修改或替换，而无需重新编译程序。
• 由于多个程序实例可以访问库，因此可以实现经济高效的内存使用。
• 此算法提高了可移植性，因为只要执行期间存在相关库，程序就可以在其他系统上运行。

缺点

• 上下文切换的发生次数与 SJF 相同。这本身就占用了处理任务所需的大量时间。这增加了处理时间，并降低了快速处理的好处。
• 由于额外的链接过程，程序启动会稍慢一些。
• 该算法必须正确处理库依赖关系，以确保适当的执行。
• 由于库是独立的可在运行时获取的实体，因此故障排除会更困难一些。