SJF 进程中的突发时间预测

SJF 算法是最好的调度算法之一，因为它提供了最大的吞吐量和最短的等待时间，但该算法的问题在于，CPU 突发时间无法提前得知。

我们可以估算进程的 CPU 突发时间。有各种技术可以用来假设进程的 CPU 突发时间。为了最优地利用该算法，我们的假设需要准确。

用于假设进程 CPU 突发时间的技巧如下：

1. 静态技术

进程大小

我们可以从进程的大小预测其突发时间。如果我们有两个进程 **T_OLD** 和 **T_New**，旧进程的实际突发时间为 **20 秒**，进程大小为 **20 KB**。我们知道 **P_NEW** 的大小是 **21 KB**。那么 **P_New** 具有与 **20 秒** 相似突发时间的概率最大。

因此，在此技术中，我们实际上是根据新进程的类似大小的旧进程的突发时间来预测新进程的突发时间。

过程类型

我们还可以根据进程的类型来预测其突发时间。进程可以分为以下各种类型：

进程可以是操作系统进程，如调度程序、编译器、程序管理器以及更多系统进程。它们的突发时间通常较低，例如 3 到 5 个时间单位。

用户发起的进程称为用户进程。进程可以有以下三种类型：

交互式进程是会不时与用户交互的进程，或者其执行完全取决于用户输入。例如，各种游戏就是这类进程。它们的突发时间需要较低，因为它们不需要长时间的 CPU，它们主要依赖于用户的交互性，因此它们主要是 I/O 密集型进程。

前台进程是用户用于执行其需求的进程，例如 MS Office、编辑器、实用程序软件等。这类进程的突发时间会稍长一些，因为它们是 CPU 密集型和 I/O 密集型进程的完美结合。

后台进程支持其他进程的执行。它们在后台工作。例如，键盘记录器是记录用户按键和用户在系统上活动的进程。它们主要是 CPU 密集型进程，需要更长的 CPU 时间。

• 操作系统进程
• 用户进程
• 交互式进程
• 前台进程
• 后台进程

2. 动态技术

简单平均

在简单平均中，有 n 个进程 P(i).......P(n) 的列表。令 T(i) 表示进程 P(i) 的突发时间。令 τ(n) 表示 Pth 进程的预测突发时间。然后根据简单平均，进程 n+1 的预测突发时间计算如下：

其中，0<=i<=n 且 ∑ T(i) 是到目前为止所有可用进程的实际突发时间之和。

指数平均或老化

令 Tn 为第 n 个进程的实际突发时间。τ(n) 为第 n 个进程的预测突发时间，则下一个进程 (n+1) 的 CPU 突发时间计算如下：

其中，α 是平滑因子。其值介于 0 和 1 之间。

CPU 突发时间预测的综合方法

尽管上述动态技术比静态方法预测更准确，但其准确性仍不足以满足日益增长的系统需求。先进的方法，如基于机器学习的方法、基于模糊逻辑的方法以及基于统计和模式的方法，可以产生更准确的结果。

使用马尔可夫过程

该统计模型通过分析 CPU 突发时间模式随时间的变化方式，以一定的置信度预测下一个 CPU 时间。马尔可夫模型拟合历史数据并研究局部性原理以产生结果。

使用模糊逻辑过程

这利用模糊逻辑系统来改进指数平均技术。它使用前两个 CPU 突发时间预测作为模糊信息系统 (FIS) 的输入，该系统会产生输出。

使用机器学习过程

CPU 突发时间预测的最佳结果之一由机器学习技术提供。对来自 PCB 的进程数据集进行分析，并通过选择合适的特征数量来设计特征向量。然后使用支持向量机 (SVM)、K-近邻、随机森林、人工神经网络、决策树和 XGBoost 等算法来预测未来值。

SJF 调度算法的其他因素

• 当需要最小化就绪队列中进程的平均等待时间且进程具有不同突发时间时，SJF 算法非常有用。
• SJF 算法的主要缺点是它可能导致突发时间较长的进程发生饿死，因为如果短进程不断到来，它们可能永远没有机会运行。
• 通过允许突发时间较短的进程被突发时间更短的进程中断，可抢占式 SJF 可以缓解饿死问题。
• 准确预测突发时间可能很困难，特别是对于突发时间随时间波动很大的进程。

结论

通过预测突发时间，SJF 可以减少就绪队列中进程的平均等待时间，这是一种有用且有效的 CPU 调度算法。通过利用历史数据来预测进程的突发时间，可以做出更好的调度决策并适应进程行为。但是，要获得最佳结果，必须仔细选择预测的突发时间准确性和 α 的值。