最短剩余时间优先 (SRTF) 调度算法

此算法是 SJF 调度的抢占版本。在 SRTF 中，进程的执行可以在特定时间后停止。在每个进程到达时，短程调度程序会在可用进程列表和正在运行的进程中选择剩余执行时间最短的进程进行调度。

一旦所有进程都进入 就绪队列，将不再进行抢占，算法将按照 SJF 调度工作。当进程从执行中移除并调度下一个进程时，其上下文信息会保存在 进程控制块 (PCB) 中。在进程的 下次执行时会访问此 PCB。

SRTF 算法实现

步骤：

实现 SRTF 算法的步骤如下：

1. 输入进程的详细信息： 输入每个进程的到达时间和执行时间，在计算完进程数量之后。

2. 跟踪剩余时间： 初始化为执行时间后，创建一个用于存储剩余时间的数组。

3. 初始化变量

• 将当前时间设置为零。
• 监控周转时间、等待时间和已完成的进程。

4. 检查到达的进程： 在每个时间单位，将到达时间小于当前时间的进程添加到就绪队列。

5. 选择最短剩余时间选项

• 从就绪队列中选择剩余时间最短的进程。
• 预期会有新进程到达，且剩余时间更短。

6. 执行进程

• 缩短所选进程的剩余持续时间。
• 增加当前时间。

7. 进程完成

• 当剩余时间为零时。
• 表明进程已完成。
• 周转时间计算为完成时间减去到达时间。
• 计算等待时间为周转时间减去执行时间。

8. 重复直到所有进程完成： 持续选择、验证和执行进程，直到所有进程都完成为止。

9. 计算平均值： 计算平均周转时间和等待时间。

• 输出结果
• 记录每个进程的周转时间、等待时间和完成时间。
• 显示平均周转时间和等待时间。

示例

在此示例中，有六个作业 P1、P2、P3、P4、P5 和 P6。它们的到达时间和执行时间如下表所示。

平均等待时间 = 24/6

根据表中给出的到达时间和执行时间，准备甘特图。

1. 由于在时间 0，唯一可用的进程是 P1，其 CPU 执行时间为 8。这是列表中唯一可用的进程，因此对其进行调度。
2. 下一个进程在时间单位 1 到达。由于我们使用的算法是 SRTF，这是一个抢占式算法，因此会停止当前执行，调度程序会查找剩余执行时间最短的进程。
   到目前为止，就绪队列中有两个可用进程。操作系统已经执行了 P1 一单位时间，P1 的剩余执行时间为 7 单位。进程 P2 的执行时间为 4 单位。因此，根据算法，在 CPU 上调度进程 P2。
3. 下一个进程 P3 在时间单位 2 到达。此时，将停止 P3 进程的执行，并搜索剩余执行时间最短的进程。由于进程 P3 的执行时间为 2 单位，因此它将获得优先权。
4. 下一个进程 P4 在时间单位 3 到达。在此到达时，调度程序将停止 P4 的执行，并检查可用进程（P1、P2、P3 和 P4）中哪个进程的剩余执行时间最短。P1 和 P2 的剩余执行时间分别为 7 单位和 3 单位。
5. P3 和 P4 的剩余执行时间均为 1 单位。由于两者相等，因此将根据其到达时间进行调度。P3 比 P4 早到达，因此将再次调度它。
6. 下一个进程 P5 在时间单位 4 到达。此时，进程 P3 已完成其执行，不再在列表中。调度程序将比较所有可用进程的剩余执行时间。由于进程 P4 的执行时间为 1，是所有进程中最短的，因此将调度 P4。
7. 下一个进程 P6 在时间单位 5 到达，此时，进程 P4 已完成其执行。到现在为止，我们有 4 个可用进程，即 P1 (7)、P2 (3)、P5 (3) 和 P6 (2)。P6 的执行时间是所有进程中最短的，因此调度 P6。由于现在所有进程都已到达，该算法将像 SJF 一样工作。P6 将执行直到完成，然后将调度剩余时间最短的进程。

所有进程到达后，不再进行抢占，算法将像 SJF 一样工作。

SRTF 调度的代码实现

以下是使用 Python 语言实现最短剩余时间优先调度的程序。

代码

输出

SRTF 调度的优点

1. 减少平均等待时间： 通过优先处理剩余执行时间最短的进程，SRTF 降低了平均等待时间。
2. 对短进程有效： 短进程更快完成，从而提高了系统的整体响应能力。
3. 适用于时间关键型系统： 它确保时间敏感的过程能够及时完成。

SRTF 调度的缺点

1. 长进程可能发生饥饿： 如果短进程持续到达，长进程可能会被持续延迟。
2. 难以预测执行时间： 准确预测进程的执行时间可能很困难，这会影响调度决策。
3. 开销高： 频繁的上下文切换会增加开销并降低系统性能。
4. 对实时系统效率低下： 由于频繁的抢占，实时任务可能会出现延迟。

常见问题

1. 什么是操作系统 SRTF 算法？

称为最短剩余时间或最短剩余时间优先 (SRTF) 的调度技术是最短作业优先调度的一种抢占式变体。使用此调度算法选择剩余完成时间最短的进程来运行。

2. SJF 和 SRTF 之间有什么区别？

在处理非抢占式内核时，通常使用 SJF 算法。选择并处理最短的作业。然而，在抢占式内核的情况下，应用 SRTF 算法。当出现一个更短的作业时，我们选择最短的、可以被抢占的作业。

3. 哪种调度算法最有效？

系统的特征决定了调度算法的有效性。通过最短作业优先 (SJN) 或最短作业优先 (SJF) 可以实现等待时间的减少和周转时间的增加。

4. 哪种调度速度最快？

由于它通过选择执行时间最短的进程来最小化执行时间，因此最短作业优先 (SJN) 或 最短作业优先 (SJF) 是最快的调度算法。

结论

本教程介绍了最短剩余时间优先调度算法。它详细介绍了该算法在减少等待时间和最大化 CPU 利用率方面的有效性。这种 CPU 调度算法存在于操作系统中，也称为抢占式最短作业优先 (PSJF) 或最短作业优先 (SJN)。最短作业优先 (SJF) 是该算法的抢占版本。