最长作业优先 (LJF) CPU调度算法

---

最长作业优先 (LJF) 是一种 CPU 调度算法，它根据进程的爆发时间 (burst time) 来优先安排进程。在 LJF 中，爆发时间最长的进程优先于爆发时间较短的进程。此算法基于非抢占式，这意味着一旦进程启动，它将一直运行直到完成，任何其他进程都不能抢占它。

要实现 LJF 算法，进程根据其爆发时间以降序排列在就绪队列中。选择并处理在到达该时间点之前所有进程中爆发时间最长的进程。此过程持续到所有进程都执行完毕。

LJF 的抢占式版本，称为最长剩余时间优先 (LRTF)，类似但允许在新的进程到达且具有更长爆发时间时抢占正在运行的进程。

最长作业优先的特性

以下是最长作业优先 (LJF) CPU 调度算法的特性，特别是对于其非抢占式版本：

• 进程根据其爆发时间优先级排序，最长进程具有最高优先级。

• 正在运行的进程不能被其他进程抢占，这意味着它将一直运行直到完成其整个爆发时间。

• 如果两个进程具有相同的爆发时间，则应用先到先服务 (FCFS) 规则，这意味着先到达的进程将先被处理。

• LJF 可以实现为抢占式和非抢占式调度算法，但非抢占式版本确保在最长作业或进程完全完成之前，任何其他进程都不能执行。

优点

• 爆发时间最长的进程具有最高优先级，确保在最长作业或进程完全完成之前，任何其他进程都不能执行。

• 所有进程大约在同一时间完成，这在特定场景中可能是有益的。

缺点

• 对于给定的进程集，LJF 算法可能导致较高的平均等待时间和平均周转时间，这可能会对系统性能产生负面影响。

• 可能会出现车队效应，这意味着短进程必须等待长进程完成，从而导致不必要的延迟。

• 短进程可能永远无法执行，系统不断执行较长进程，这会降低系统效率。

• LJF降低了处理速度，导致系统效率和利用率降低。

最长作业优先 CPU 调度算法

• 按进程到达时间的升序排列进程。

• 在到达该时间点之前所有进程中，选择具有最长爆发时间的进程。

• 执行选定的进程，直到完成其整个爆发时间。

• 检查当前进程执行期间是否有其他进程到达。

• 如果新的进程到达，则将其爆发时间与当前进程的剩余时间进行比较。如果新进程的爆发时间更长，则停止当前进程并执行新进程。如果新进程的爆发时间较短，则将其放入就绪队列，并继续执行当前进程直到完成。

• 重复步骤 2-5，直到所有进程都执行完毕。

示例

首先，让我们根据它们的到达时间对进程进行排序：

进程	到达时间	爆发时间
P1	1	2
P2	2	5
P3	3	3
P4	4	8

现在，让我们根据最长作业优先调度创建甘特图：

进程	P1	P2	P4	P3
时间	3	8	16	19

注意 - 由于在给定时间间隔内没有可用进程，因此 CPU 将在 0 到 1 个时间单位内处于空闲状态。

解释

• 在 t=1 时，唯一可用的进程是 P1，其爆发时间为 2。因此，首先执行 P1 2ms。

• 在 t = 3 时，即 P1 执行后，可用的进程为 P2 和 P3。正如你所看到的，P2 的爆发时间比 P3 更长。因此，选择 P2 并执行 5ms。

• 在 t = 8 时，即 P2 执行后，可用的进程为 P3 和 P4。正如你所看到的，P4 的爆发时间比 P3 更长。因此，选择 P4 并执行 8ms。

• 在 t=16 时，只有 P3 可用，它被执行 3ms。

• 最后，P4 再次执行剩余的 4ms。

现在，让我们计算每个进程的等待时间和周转时间：

由于完成时间 (C.T) 可以直接从甘特图中确定，并且

周转时间 (TAT)

= (完成时间) – (到达时间)

还有等待时间 (WT)

= (周转时间) – (爆发时间)

进程	到达时间	爆发时间	完成时间	周转时间 周转时间 = 完成时间 – 到达时间	等待时间 等待时间 = 周转时间 – 爆发时间
P1	1	2	3	3-1=2	2-2=0
P2	2	5	8	8-2=6	6-5=1
P3	3	3	19	19-3=16	16-3=13
P4	4	8	16	16-4=12	12-8=4

输出

总周转时间 = 36 毫秒

因此，平均周转时间 = 36/4 = 9.00 毫秒

而且，总等待时间 = 18 毫秒

因此，平均等待时间 = 18/4 = 4.5 毫秒

结论

最长作业优先 (LJF) CPU 调度算法通过赋予爆发时间最长的进程最高优先级来工作。但是，LJF 有一些缺点，包括潜在的高平均等待时间、车队效应的可能性以及降低的系统效率。虽然 LJF 可以实现为抢占式或非抢占式，但非抢占式版本确保在最长作业完成之前任何其他进程都不能执行。需要注意的是，LJF 可能不是最有效的调度算法，并且可能不适用于所有情况。