CS101

主题

最短作业优先CPU调度与预测的执行时间 ​

最短作业优先（SJF） 是一种最优的调度算法，因为它提供了最大的吞吐量和最小的平均等待时间（WT）和周转时间（TAT），但由于无法提前预测进程的执行时间，因此实际上无法实现。我们可能不知道下一个CPU突发的长度，但我们可以预测它的值。我们期望下一个CPU突发的长度与之前的相似。通过计算下一个CPU突发长度的近似值，我们可以选择预测的CPU突发最短的进程。

预测执行时间的方法 ​

我们可以通过以下两种方法预测进程的执行时间：

静态方法 ​

我们可以通过以下两个因素使用静态方法预测执行时间：

1. 执行时间与进程大小： 假设我们有一个旧进程Pold，大小为200 KB，已经执行，其执行时间为20个时间单位，现在我们有一个新进程Pnew，大小为201 KB，尚未执行。我们将已执行的旧进程Pold的执行时间（与新进程大小几乎相同）作为新进程Pnew的执行时间。

2. 进程类型： 我们可以根据进程的类型预测执行时间。操作系统进程（如调度器、调度程序、分段和碎片整理）比用户进程（如游戏、应用软件）更快。任何新操作系统进程的执行时间都可以从类似类型的旧操作系统进程中预测，用户进程也是如此。

  • 操作系统进程： 调度器、编译器、程序管理器等操作系统进程是进程的例子。通常，它们的执行时间更短——在三到五个时间单位之间。
  • 用户进程： 用户进程是由用户启动的。可能的三种进程类别如下。
    • 交互式进程： 交互式进程是与用户交互或其执行完全依赖于用户输入的进程。这些类型的进程的一些例子是游戏。由于它们主要依赖于人类交互，并且不需要长时间占用CPU，因此它们的执行时间需要减少。因此，它们主要是IO密集型进程。
    • 前台进程： 这些是用户用来完成任务的进程，如使用Microsoft Office、编辑器、实用程序软件等。由于这些进程是CPU和IO绑定的理想组合，它们的执行时间稍长一些。
    • 后台进程： 这有助于其他进程的执行方式。它们在隐蔽模式下运行。例如，键盘记录器是一个记录用户在系统上活动和按键的程序。它们主要需要CPU，并且运行时间更长。

动态技术 ​

1. 简单平均值： 给定n个进程（P1、P2… Pn）

Τn+1 = 1/n(Σi=1 to n ti)

2. 指数平均值（老化）：

Τn+1 = αtn + (1 - α)Τn
  • 其中α = 平滑因子，0 <= α <= 1，tn = 第n个进程的实际执行时间，Τn = 第n个进程的预测执行时间。通用术语，
αtn + (1 - α)αtn-1 + (1 - α)2αtn-2...+ (1 - α)jαtn-j...+ (1 - α)n+1Τ0
  • Τ 0 是一个常数或整个系统的平均值。
  • 如果α = 0，Τn+1 = Τn，即初始预测执行时间的值没有变化。
  • 如果α = 1，Τn+1 = tn，即新进程的预测执行时间将始终根据第n个进程的实际执行时间变化。
  • 如果α = 1/2，最近和过去的历史被平等加权。

SJF调度算法的额外考虑因素 ​

  • SJF算法适用于进程具有不同执行时间并且需要最小化就绪队列中进程平均等待时间的场景。
  • SJF算法的一个主要缺点是，它可能导致执行时间较长的进程饥饿，因为如果不断有执行时间较短的进程到达，它们可能永远不会有机会执行。
  • 抢占式SJF可以通过允许执行时间更短的进程中断执行时间更短的进程来解决饥饿问题。
  • 准确预测执行时间可能具有挑战性，特别是对于执行时间随时间变化很大的进程。

结论 ​

带有预测执行时间的SJF是一种实用且高效的CPU调度算法，可以减少就绪队列中进程的平均等待时间。通过使用历史数据预测进程的执行时间，它可以做出更好的调度决策并适应进程行为的变化。然而，预测执行时间的准确性和α值的选择需要仔细考虑以实现最佳结果。