最长剩余时间优先 (LRTF) 或抢占式最长作业优先 CPU 调度算法
最长剩余时间优先 (LRTF) 是最长作业优先 (LJF) 调度算法的抢占式版本。在这种调度算法中，我们找到剩余时间最长的进程，然后处理它，即在一段时间后（假设每单位时间检查一次）检查是否有其他具有更长执行时间的进程到达。
最长剩余时间优先 (LRTF) 的特点
- 在所有在等待队列中等待的进程中，CPU 总是分配给具有最长执行时间的进程。
- 如果两个进程具有相同的执行时间，则使用先到先服务 (FCFS) 的方式打破平局，即首先到达的进程先被处理。
- LJF CPU 调度可以是抢占式和非抢占式的。
最长剩余时间优先 (LRTF) 的优点
- 在最长的作业或进程完全执行之前，没有其他进程可以执行。
- 所有作业或进程大约在同一时间完成。
最长剩余时间优先 (LRTF) 的缺点
- 这种算法为给定的一组进程提供了非常高的平均等待时间和平均周转时间。
- 这可能导致护航效应。
- 可能发生的情况是，一个短作业可能永远不会被执行，而系统不断执行更长的进程。
- 它降低了处理速度，从而降低了系统的效率和利用率。
最长剩余时间优先 (LRTF) CPU 调度算法
- 步骤 1： 首先，根据它们的到达时间将进程按升序排序。
- 步骤 2： 选择具有最短到达时间但最多执行时间的进程。
- 步骤 3： 然后处理它 1 单位时间。检查在这个执行时间之前是否有其他进程到达。
- 步骤 4： 重复上述两个步骤，直到执行所有进程。
展示抢占式最长作业优先 CPU 调度算法工作的示例：
示例-1： 考虑以下四个进程 P1、P2、P3 和 P4 的到达时间和执行时间表。
| 进程 | 到达时间 | 执行时间 |
|---|---|---|
| P1 | 1 毫秒 | 2 毫秒 |
| P2 | 2 毫秒 | 4 毫秒 |
| P3 | 3 毫秒 | 6 毫秒 |
| P4 | 4 毫秒 | 8 毫秒 |
最长剩余时间优先 CPU 调度算法将按照下面提到的步骤工作：
在时间 = 1 时，
- 可用进程：P1。因此，选择 P1 并执行 1 毫秒。
| 时间实例 | 进程 | 到达时间 | 等待表 | 执行时间 | 初始执行时间 | 剩余执行时间 |
|---|---|---|---|---|---|---|
| 1-2毫秒 | P1 | 1毫秒 | 1毫秒 | 2毫秒 | 1毫秒 |
在时间 = 2 时，
可用进程：P1, P2。
因此，选择 P2 并执行 1 毫秒（因为 P1 的 B.T = 1 小于 P2 的 B.T = 4）
时间实例 进程 到达时间 等待表 执行时间 初始突发时间 剩余突发时间 2 - 3ms P1 1ms P1 0ms 1ms 1ms P2 2ms 1ms 4ms 3ms
在时间 = 3 时，
可用进程：P1, P2, P3。
因此，选择 P3 并执行 1 毫秒（因为，P1 的 B.T = 1, P2 的 B.T = 3, P3 的 B.T = 6）
时间实例 进程 到达时间 等待表 执行时间 初始突发时间 剩余突发时间 3 - 4ms P1 1ms P1, P2 0ms 1ms 1ms P2 2ms 0ms 3ms 3ms P3 3ms 1ms 6ms 5ms
在时间 = 4 时，
可用进程：P1, P2, P3, P4。
因此，选择 P4（因为 P4 的执行时间最大）并执行 1 毫秒（因为，P1 的 B.T = 1, P2 的 B.T = 3, P3 的 B.T = 5, P4 的 B.T = 8）
时间实例 进程 到达时间 等待表 执行时间 初始突发时间 剩余突发时间 4 - 5ms P1 1ms P1, P2, P3 0ms 1ms 1ms P2 2ms 0ms 3ms 3ms P3 3ms 0ms 5ms 5ms P4 4ms 1ms 8ms 7ms
在时间 = 5 时，
可用进程：P1, P2, P3, P4,
进程 P4 将继续执行，因为没有其他进程的执行时间大于进程 P4
时间实例 进程 到达时间 等待表 执行时间 初始突发时间 剩余突发时间 5 - 7ms P1 1ms P1, P2, P3 0ms 1ms 1ms P2 2ms 0ms 3ms 3ms P3 3ms 0ms 5ms 5ms P4 4ms 2ms 7ms 5ms
在时间 = 7 时，
进程 P3 和 P4 剩余执行时间相同，
因此如果两个进程具有相同的执行时间，则使用先到先服务 (FCFS) 的方式打破平局，即首先到达的进程先被处理。
因此 P3 将被执行 1 毫秒
时间实例 进程 到达时间 等待表 执行时间 初始突发时间 剩余突发时间 7 - 8ms P1 1ms P1, P2, P4 0ms 1ms 1ms P2 2ms 0ms 3ms 3ms P3 3ms 1ms 5ms 4ms P4 4ms 0ms 5ms 5ms
在时间 = 8 时，
可用进程：P1, P2, P3, P4,
进程 P4 将再次继续执行，因为没有其他进程的执行时间大于进程 P4
时间实例 进程 到达时间 等待表 执行时间 初始突发时间 剩余突发时间 8 - 9ms P1 1ms P1, P2, P3 0ms 1ms 1ms P2 2ms 0ms 3ms 3ms P3 3ms 0ms 4ms 4ms P4 4ms 1ms 5ms 4ms
在时间 = 9 时，
可用进程：P1, P2, P3, P4,
进程 P3 将继续执行基于 FCFS 规则。
时间实例 进程 到达时间 等待表 执行时间 初始突发时间 剩余突发时间 9 - 10ms P1 1ms P1, P2, P4 0ms 1ms 1ms P2 2ms 0ms 3ms 3ms P3 3ms 1ms 4ms 3ms P4 4ms 0ms 4ms 4ms
在时间 = 10 时，
- 可用进程：P1, P2, P3, P4,
- 现在 P4 的执行时间最大，因此它将进一步执行。
| 时间实例 | 进程 | 到达时间 | 等待表 | 执行时间 | 初始突发时间 | 剩余突发时间 |
|---|---|---|---|---|---|---|
| 10 - 11ms | P1 | 1ms | P1, P2, P3 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 3ms | 3ms | ||
| P3 | 3ms | 0ms | 3ms | 3ms | ||
| P4 | 4ms | 1ms | 4ms | 3ms |
在时间 = 11 时，
- 可用进程：P1, P2, P3, P4,
- 进程 P2 将继续执行，因为 P2, P3, P4 的执行时间相同
- 因此，在这种情况下，进一步的执行将基于 FCFS 规则决定，即首先到达的进程先被处理。
| 时间实例 | 进程 | 到达时间 | 等待表 | 执行时间 | 初始突发时间 | 剩余突发时间 |
|---|---|---|---|---|---|---|
| 11 - 12ms | P1 | 1ms | P1, P3, P4 | 0ms | 1ms | 1ms |
| P2 | 2ms | 1ms | 3ms | 2ms | ||
| P3 | 3ms | 0ms | 3ms | 3ms | ||
| P4 | 4ms | 0ms | 3ms | 3ms |
在时间 = 12 时，
- 可用进程：P1, P2, P3, P4,
- 进程 P3 将继续执行基于上述解释。
| 时间实例 | 进程 | 到达时间 | 等待表 | 执行时间 | 初始突发时间 | 剩余突发时间 |
|---|---|---|---|---|---|---|
| 12 - 13ms | P1 | 1ms | P1, P2, P4 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 2ms | 2ms | ||
| P3 | 3ms | 1ms | 3ms | 2ms | ||
| P4 | 4ms | 0ms | 3ms | 3ms |
在时间 = 13 时，
- 可用进程：P1, P2, P3, P4,
- 现在 P4 的执行时间最大，因此它将进一步执行。
| 时间实例 | 进程 | 到达时间 | 等待表 | 执行时间 | 初始突发时间 | 剩余突发时间 |
|---|---|---|---|---|---|---|
| 13 - 14ms | P1 | 1ms | P1, P2, P3 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 2ms | 2ms | ||
| P3 | 3ms | 0ms | 2ms | 2ms | ||
| P4 | 4ms | 1ms | 3ms | 2ms |
在时间 = 14 时，
- 可用进程：P1, P2, P3, P4
- 现在，进程 P2 将再次首先开始执行
| 时间实例 | 进程 | 到达时间 | 等待表 | 执行时间 | 初始突发时间 | 剩余突发时间 |
|---|---|---|---|---|---|---|
| 14 - 15ms | P1 | 1ms | P1, P3, P4 | 0ms | 1ms | 1ms |
| P2 | 2ms | 1ms | 2ms | 1ms | ||
| P3 | 3ms | 0ms | 2ms | 2ms | ||
| P4 | 4ms | 0ms | 2ms | 2ms |
在时间 = 15 时，
- 可用进程：P1, P2, P3, P4, 现在 P3 将执行
| 时间实例 | 进程 | 到达时间 | 等待表 | 执行时间 | 初始突发时间 | 剩余突发时间 |
|---|---|---|---|---|---|---|
| 15 - 16ms | P1 | 1ms | P1, P2, P4 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 1ms | 1ms | ||
| P3 | 3ms | 1ms | 2ms | 1ms | ||
| P4 | 4ms | 0ms | 2ms | 2ms |
在时间 = 16 时，
- 可用进程：P1, P2, P3, P4,
- 这里，P4 将执行，因为它在所有进程中具有最长的执行时间
| 时间实例 | 进程 | 到达时间 | 等待表 | 执行时间 | 初始突发时间 | 剩余突发时间 |
|---|---|---|---|---|---|---|
| 16 - 17ms | P1 | 1ms | P1, P2, P3 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 1ms | 1ms | ||
| P3 | 3ms | 0ms | 1ms | 1ms | ||
| P4 | 4ms | 1ms | 2ms | 1ms |
在时间 = 17 时，
- 可用进程：P1, P2, P3, P4,
- 进程 P1 将在这里执行基于上述解释
| 时间实例 | 进程 | 到达时间 | 等待表 | 执行时间 | 初始突发时间 | 剩余突发时间 |
|---|---|---|---|---|---|---|
| 17 - 18ms | P1 | 1ms | P2, P3, P4 | 1ms | 1ms | 0ms |
| P2 | 2ms | 0ms | 1ms | 1ms | ||
| P3 | 3ms | 0ms | 1ms | 1ms | ||
| P4 | 4ms | 0ms | 1ms | 1ms |
在时间 = 18 时，
- 可用进程：P2, P3, P4,
- 进程 P2 将执行。
| 时间实例 | 进程 | 到达时间 | 等待表 | 执行时间 | 初始突发时间 | 剩余突发时间 |
|---|---|---|---|---|---|---|
| 18 - 19ms | P2 | 2ms | P3, P4 | 1ms | 1ms | 0ms |
| P3 | 3ms | 0ms | 1ms | 1ms | ||
| P4 | 4ms | 0ms | 1ms | 1ms |
在时间 = 19 时，
- 可用进程：P3, P4,
- 进程 P3 将执行。
| 时间实例 | 进程 | 到达时间 | 等待表 | 执行时间 | 初始突发时间 | 剩余突发时间 |
|---|---|---|---|---|---|---|
| 19 - 20ms | P3 | 3ms | P4 | 1ms | 1ms | 0ms |
| P4 | 4ms | 0ms | 1ms | 1ms |
在时间 = 20 时，
- 进程 P4 将执行到最后。
| 时间实例 | 进程 | 到达时间 | 等待表 | 执行时间 | 初始突发时间 | 剩余突发时间 |
|---|---|---|---|---|---|---|
| 20 - 21ms | P4 | 4ms | 1ms | 1ms | 0ms |
在时间 = 22 时，
- 进程 P4 将完成其执行。
进程的整体执行如下所示：
| 时间实例 | 进程 | 到达时间 | 等待表 | 执行时间 | 初始突发时间 | 剩余突发时间 |
|---|---|---|---|---|---|---|
| 1 - 2ms | P1 | 1ms | 1ms | 2ms | 1ms | |
| 2 - 3ms | P1 | 1ms | P1 | 0ms | 1ms | 1ms |
| P2 | 2ms | 1ms | 4ms | 3ms | ||
| 3 - 4ms | P1 | 1ms | P1, P2 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 3ms | 3ms | ||
| P3 | 3ms | 1ms | 6ms | 5ms | ||
| 4 - 5ms | P1 | 1ms | P1, P2, P3 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 3ms | 3ms | ||
| P3 | 3ms | 0ms | 5ms | 5ms | ||
| P4 | 4ms | 1ms | 8ms | 7ms | ||
| 5 - 7ms | P1 | 1ms | P1, P2, P3 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 3ms | 3ms | ||
| P3 | 3ms | 0ms | 5ms | 5ms | ||
| P4 | 4ms | 2ms | 7ms | 5ms | ||
| 7 - 8ms | P1 | 1ms | P1, P2, P4 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 3ms | 3ms | ||
| P3 | 3ms | 1ms | 5ms | 4ms | ||
| P4 | 4ms | 0ms | 7ms | 5ms | ||
| 8 - 9ms | P1 | 1ms | P1, P2, P3 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 3ms | 3ms | ||
| P3 | 3ms | 0ms | 4ms | 4ms | ||
| P4 | 4ms | 1ms | 5ms | 4ms | ||
| 9 - 10ms | P1 | 1ms | P1, P2, P4 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 3ms | 3ms | ||
| P3 | 3ms | 1ms | 4ms | 3ms | ||
| P4 | 4ms | 0ms | 4ms | 4ms | ||
| 10 - 11ms | P1 | 1ms | P1, P2, P3 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 3ms | 3ms | ||
| P3 | 3ms | 0ms | 3ms | 3ms | ||
| P4 | 4ms | 1ms | 4ms | 3ms | ||
| 11 - 12ms | P1 | 1ms | P1, P3, P4 | 0ms | 1ms | 1ms |
| P2 | 2ms | 1ms | 3ms | 2ms | ||
| P3 | 3ms | 0ms | 3ms | 3ms | ||
| P4 | 4ms | 0ms | 3ms | 3ms | ||
| 12 - 13ms | P1 | 1ms | P1, P2, P4 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 2ms | 2ms | ||
| P3 | 3ms | 1ms | 3ms | 2ms | ||
| P4 | 4ms | 0ms | 3ms | 3ms | ||
| 13 - 14ms | P1 | 1ms | P1, P2, P3 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 2ms | 2ms | ||
| P3 | 3ms | 0ms | 2ms | 2ms | ||
| P4 | 4ms | 1ms | 3ms | 2ms | ||
| 14 - 15ms | P1 | 1ms | P1, P3, P4 | 0ms | 1ms | 1ms |
| P2 | 2ms | 1ms | 2ms | 1ms | ||
| P3 | 3ms | 0ms | 2ms | 2ms | ||
| P4 | 4ms | 0ms | 2ms | 2ms | ||
| 15 - 16ms | P1 | 1ms | P1, P2, P4 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 1ms | 1ms | ||
| P3 | 3ms | 1ms | 2ms | 1ms | ||
| P4 | 4ms | 0ms | 2ms | 2ms | ||
| 16 - 17ms | P1 | 1ms | P1, P2, P3 | 0ms | 1ms | 1ms |
| P2 | 2ms | 0ms | 1ms | 1ms | ||
| P3 | 3ms | 0ms | 1ms | 1ms | ||
| P4 | 4ms | 1ms | 2ms | 1ms | ||
| 17 - 18ms | P1 | 1ms | P2, P3, P4 | 1ms | 1ms | 0ms |
| P2 | 2ms | 0ms | 1ms | 1ms | ||
| P3 | 3ms | 0ms | 1ms | 1ms | ||
| P4 | 4ms | 0ms | 1ms | 1ms | ||
| 18 - 19ms | P2 | 2ms | P3, P4 | 1ms | 1ms | 0ms |
| P3 | 3ms | 0ms | 1ms | 1ms | ||
| P4 | 4ms | 0ms | 1ms | 1ms | ||
| 19 - 20ms | P3 | 3ms | P4 | 1ms | 1ms | 0ms |
| P4 | 4ms | 0ms | 1ms | 1ms | ||
| 20 - 21ms | P4 | 4ms | 1ms | 1ms | 0ms |
甘特图 如下所示：
由于完成时间 (C.T) 可以通过甘特图直接确定，并且
周转时间 (TAT)
= (完成时间) – (到达时间)
同时，等待时间 (WT)
= (周转时间) – (执行时间)
因此，最终表格如下所示，
总周转时间 = 68 毫秒
所以，平均周转时间 = 68/4 = 17.00 毫秒
以及，总等待时间 = 48 毫秒
所以 平均等待时间 = 48/4 = 12.00 毫秒
示例-2： 考虑以下四个进程 P1, P2, P3, P4 和 P5 的到达时间和执行时间表。
| 进程 | 到达时间 | 执行时间 |
|---|---|---|
| P1 | 0毫秒 | 2毫秒 |
| P2 | 0毫秒 | 3毫秒 |
| P3 | 2毫秒 | 2毫秒 |
| P4 | 3毫秒 | 5毫秒 |
| P5 | 4毫秒 | 4毫秒 |
与示例-1 类似，这个示例的甘特图如下，
由于完成时间 (CT) 可以通过甘特图直接确定，并且
周转时间 (TAT)
= (完成时间) – (到达时间)
同时，等待时间 (WT)
= (周转时间) – (执行时间)
因此，最终表格如下所示，
总周转时间 = 61 毫秒
所以，平均周转时间 = 61/5 = 12.20 毫秒
以及，总等待时间 = 45 毫秒
所以，平均等待时间 = 45/5 = 9.00 毫秒