SJF 调度中突发时间的预测

---

---

在许多调度策略中，调度程序的效率取决于对 CPU 进程突发时间的准确预测。

让我们考虑最短作业优先 (SJF) 算法的例子，这是吞吐量最高、等待时间最短的最优策略。SJF 按照进程突发大小的递增顺序分配 CPU。我们观察到，它假设在执行之前可以获得进程的突发大小。

然而，没有任何进程能够预先声明其 CPU 突发时间，因为它是一个动态变化的参数，在很大程度上取决于计算机的硬件。如果无法获得正确的突发时间，则调度策略将失败。这种情况也发生在最高响应比优先 (HRRN) 和最短剩余时间优先 (SRTN) 算法中。

为了使这些调度策略能够用于 CPU 进程调度，一个解决方案是预测 CPU 进程的突发时间。在本主题中，我们将讨论各种预测突发时间的技术。

预测进程突发时间的技术

可以使用传统技术或机器学习方法找到进程的突发时间。在传统技术中，预测是基于已经完成的进程的突发时间进行的，可以使用静态或动态算法。下图描述了不同的方法：

静态技术

这些技术基于已完成进程的一些启发式策略进行计算。然而，这些策略并不十分准确，因此可靠性较低。

预测 CPU 突发时间的两种传统的静态技术启发式方法基于进程大小和进程类型，如下所述：

基于进程大小

在这种情况下考虑的启发式参数是进程大小。启发式方法是：“大小相似的进程的突发时间相似”。因此，当进程进入系统时，会考虑分配给该进程的总内存空间。考虑过去大小相似的进程的突发时间。由此预测新进程的突发时间。

例如，假设一个大小为 250KB 的进程已到达系统。历史数据中有五个进程 P1 到 P5，参数如下：

• P1 大小为 100 KB，执行时间为 4 毫秒
• P2 大小为 375 KB，执行时间为 10 毫秒
• P3 大小为 170 KB，执行时间为 5 毫秒
• P4 大小为 245 KB，执行时间为 7 毫秒
• P5 大小为 500 KB，执行时间为 15 毫秒

可以看出，新进程的大小最接近 P4。因此，根据这种进程大小启发式方法，预测的突发时间为 7 毫秒。

基于进程类型

在这里，启发式方法是：“类型相似的进程的突发时间相似”。进程可以是系统进程、用户进程、实时进程、交互式进程等等。当一个新进程进入系统时，确定进程的类型并据此预测其突发时间。

例如，假设一个系统根据进程类型具有以下近似的突发时间：

• 内核进程的突发时间：4 毫秒
• 前台进程的突发时间：14 毫秒
• 交互式进程的突发时间：8 毫秒
• 后台进程的突发时间：20 毫秒

如果内核进程到达此系统，则根据进程类型启发式方法，其突发时间将预测为 4 毫秒。

动态技术

动态技术将进程的历史视为时间序列，并将下一个进程的突发时间预测为过去进程的函数。两种传统的动态方法使用简单平均和指数平均，解释如下：

简单平均

在这种方法中，下一个进程的突发时间是系统中所有进程的突发时间的简单平均值。

数学上，假设系统中有 n 个进程 P₁, P₂, P₃,…… P_n，其突发时间为 t₁, t₂, t₃,…… t_n，则队列中下一个进程的突发时间由下式给出：

$$\mathrm{t_{n+1} \: = \: \frac{1}{n}\displaystyle\sum\limits_{i=1}^n t_{i}}$$

例如，假设系统中之前有 5 个进程，其突发时间分别为 4、6、7、5 和 3 毫秒。下一个进程的突发时间将是 (4 + 6 + 7 + 5 + 3) / 5 = 5ms。

指数平均

这是对简单平均的改进，因为它对近期历史和过去历史赋予优先权重。这里，定义一个平滑因子 α (0 ≤ α ≤ 1) 来给出相对权重。预测的突发时间 τ_(n+1) 定义为：

$$\mathrm{\tau_{n+1} \: = \: \alpha t_{n} \: + \: (1 - \alpha)\tau_{n}}$$

其中，t_n 是 P_n 的实际突发时间，τ_n 是之前的预测突发时间。我们可以通过代入 τ_n 的后续值来展开此公式，得到：

$$\mathrm{\tau_{n+1} \: = \: \alpha t_{n} \: + \: (1 - \alpha) \alpha t_{n-1} \: + \: (1-\alpha)^{2} \alpha t_{n-2} \: + \: \cdots \: + \: (1-\alpha)^{j} \alpha t_{n-j} \: + \: (1- \alpha)^{n}T_{0}}$$

需要注意的是，如果 α 的值为 0，则近期历史对预测没有影响，如果 α 为 1，则预测的突发时间等于最近的突发时间。

预测 CPU 突发时间的先进技术

尽管所述动态技术比静态方法预测得更好，但准确性仍然实用，可以满足不断增长的系统需求。可以使用更先进的技术来获得更准确的结果，例如基于统计和模式的方法、基于模糊逻辑的方法和基于机器学习的方法。

基于马尔可夫过程的方法

这是一个统计模型，它分析 CPU 突发时间随时间的变化模式，并以一定的置信度预测下一个 CPU 时间。马尔可夫模型探索局部性原理，并拟合历史数据以获得结果。

基于模糊逻辑的方法

这是使用模糊逻辑系统改进指数平均技术的一种方法。它将之前的两次 CPU 突发时间预测作为输入提供给模糊信息系统 (FIS)，然后 FIS 给出输出。

基于机器学习的方法

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