最长剩余时间优先 (LRTF) 或抢占式最长作业优先 CPU 调度算法

---

最长剩余时间优先 (LRTF) 调度算法是先来先服务 (LJF) 算法的一种变体，操作系统使用它来调度传入的进程。在 LRTF 中，剩余执行时间最长的进程具有最高优先级，并被首先调度执行。在一定的时间间隔内，例如每单位时间，系统都会检查是否有另一个具有更长突发时间的进程到达。如果存在这样的进程，则会在继续执行当前进程之前将其调度执行。该算法旨在最大限度地提高处理器的利用率并最小化进程的等待时间。

最长剩余时间优先 (LRTF) 调度算法的特性

• 最长剩余时间优先 (LRTF) 是一种常用的 CPU 调度算法，用于以系统的方式确定传入进程的执行顺序。

• LRTF 算法采用抢占式方法，其中 CPU 仅分配给固定的时间片，并选择具有最大突发大小的进程进行执行。

• 具有最大突发大小的进程允许运行一个固定的时间片，之后再次进行选择过程。

• 然而，由于其较高的平均等待时间，LRTF 不是最佳调度算法。

• LRTF 算法优先处理长时间运行的进程，导致较短的进程等待，从而导致平均等待时间增加。

优点

• LRTF 算法易于实现和理解，因此广泛应用于各种操作系统。

• 几乎所有进程的完成时间都在最长作业完成之前。

• LRTF 算法是无饥饿的，这意味着所有进程都能公平地获得 CPU 资源。

缺点

• LRTF 算法的上下文切换会占用本来可以更有效地用于运行进程的 CPU 时间。

• 较低优先级的进程可能必须等待 CPU 完成执行具有更大突发大小的较长进程。

• 尽管每个进程的突发时间较小，但 LRTF 算法具有更高的平均等待时间和平均周转时间。

最长剩余时间优先 (LRTF) CPU 调度算法

• 按进程的到达时间递增顺序排序。

• 选择到达时间最早但突发时间最长的进程。

• 执行所选进程一个单位时间。

• 检查是否有新的进程到达，如果有，则将其剩余的突发时间与当前进程进行比较。如果新进程具有更长的剩余突发时间，则抢占当前进程并开始执行新进程。

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

最长剩余时间优先 (LRTF) 示例

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

进程	到达时间	突发时间
P1	0	3
P2	1	6
P3	3	2
P4	5	3

现在，让我们根据最长剩余时间优先调度创建甘特图：

解释

• 在 t=0 时刻，唯一可用的进程是 P1，其突发时间为 3。因此，P1 开始执行。

• 在 t=1 时刻，P2 到达，其突发时间为 6，但 P1 仍然有 2 个单位的剩余时间。但与 P1 相比，P2 具有更多单位。因此，P2 被添加到就绪队列。

• 因此，这里 P2 重复到 t=5，之后与 P1、P2、P3 和 P4 相比，P4 具有更多单位。因此，P4 被添加到就绪队列。

• 在 t = 6（即 P4 执行之后），我们重复相同的过程，直到所有进程都已执行完毕。

• 在 t=14 时刻，P2 完成执行，所有进程都已完成。

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

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

周转时间 (TAT)

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

此外，等待时间 (WT)

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

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

输出

总周转时间 = 36 毫秒

因此，平均周转时间 = 44/4 = 11 毫秒

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

因此，平均等待时间 = 32/4 = 8 毫秒

结论

最长剩余时间优先 (LRTF) 调度算法通常由操作系统使用，以确保处理器得到有效利用并且进程不必等待太长时间。它的工作原理是优先处理剩余完成时间最长的进程。但是，该算法并不完美，因为较小的进程可能必须等待较大的进程完成更长时间。尽管如此，LRTF 算法易于理解和实现，并且它通常会在最长进程完成之前完成大多数进程。LRTF 算法确保所有进程都有公平的机会使用 CPU。但是，根据系统的需求，其他调度算法可能更适合某些系统。