操作系统 - 优先级调度算法

---

---

优先级调度是一种 CPU 调度策略，它根据分配给进程的优先级来决定就绪队列中哪个进程应该接下来执行。它通常用于系统中，其中进程的执行是分批进行的。

优先级调度

在实施了优先级调度策略的系统中，每个进程都分配了一个优先级值。一些系统遵循优先级值越低，优先级越高的方案；而其他系统则遵循优先级值越高，优先级越高的方案。优先级值最高的进程被选中执行。

优先级调度有两种变体：

非抢占式优先级调度

在非抢占式版本中，一旦一个进程被分配给 CPU，它就会一直运行到完成。在这里，当一个进程完成执行或当一个新进程到达一个空的准备队列时，调度程序被调用。调度程序选择优先级最高的进程进行执行。

抢占式优先级调度

在抢占式版本中，如果一个高优先级进程在低优先级进程执行期间进入系统，则会发生进程切换，其中正在执行的进程被换出，而新到达的高优先级进程开始执行。因此，调度程序在系统中出现新进程或现有进程完成执行时被调用。

优先级值也可以分为两种形式：

• 静态优先级：在这个系统中，一旦一个优先级值被分配给一个进程，它就会保持不变，直到该进程离开系统。
• 动态优先级：在这里，优先级值根据进程的性质或进程在系统中的等待时间而变化。

优先级调度的特点

• 优先级最高的进程被分配给 CPU。
• 使用静态优先级的非抢占式优先级调度通常用于批处理进程。
• 使用动态优先级的抢占式优先级调度用于大多数操作系统。
• 如果两个进程具有相同的最高优先级，则调度程序会根据先来先服务的原则在它们之间进行仲裁。
• 由于大多数系统都有一些高优先级的系统进程，因此优先级调度得到了广泛的应用，通常与其他调度算法结合使用。

我们可以通过以下示例了解优先级调度算法的工作原理：

非抢占式优先级调度的示例

示例 1

假设我们有一组四个进程，它们以 P1、P2、P3 和 P4 的顺序同时到达。进程的突发时间（以毫秒为单位）和优先级由下表给出：

考虑到优先级值越低，优先级越高，让我们对其执行非抢占式优先级调度。我们将绘制甘特图并找到平均周转时间和平均等待时间。

甘特图

进程 P2 具有最高优先级，因此它首先执行。然后我们发现 P1 和 P4 的优先级值都为 2。由于 P1 先到达，因此 CPU 分配给 P1，然后分配给 P4。最后执行 P3。因此，执行顺序为 P2、P1、P4、P3，如下所示

让我们根据上图计算平均周转时间和平均等待时间。

平均周转时间

= 每个进程周转时间之和 / 进程数

= ( TAT_P1 + TAT_P2 + TAT_P3 + TAT_P4) / 4

= ( 16 + 10 + 26 + 22) / 4 = 18.5 毫秒

平均等待时间

= 每个进程等待时间之和 / 进程数

= ( WT_P1 + WT_P2 + WT_P3 + WT_P4) / 4

= ( 10 + 0 + 22 + 16) / 4 = 10.5 毫秒

示例 2

在这个例子中，我们考虑一个进程到达时间不同的情况。假设我们有一组四个进程，它们的到达时间、CPU 突发时间和优先级如下：

让我们绘制甘特图，并使用非抢占式优先级调度找到平均周转时间和平均等待时间，并将较低的优先级值视为较高的优先级。

甘特图

在 0 毫秒时，只有 P1 存在，因此它被分配给 CPU。P1 在 6 毫秒时完成执行，此时 P2 和 P3 已到达。P2 具有更高的优先级，因此被分配给 CPU。P2 在 10 毫秒时完成执行。到那时，P4 已到达，其优先级值为 1，因此它被分配给 CPU。P4 完成执行后，P3 被分配给 CPU。因此，执行顺序为 P1、P2、P4、P3，如下所示的甘特图：

让我们计算每个进程的周转时间，然后计算平均值。

进程的周转时间 = 完成时间 - 到达时间

TAT_P1 = CT_P1 - AT_P1 = 6 - 0 = 6 毫秒

TAT_P2 = CT_P2 - AT_P2 = 16 - 4 = 12 毫秒

TAT_P3 = CT_P3 - AT_P3 = 23 - 4 = 19 毫秒

TAT_P4 = CT_P4 - AT_P4 = 19 - 8 = 11 毫秒

平均周转时间

= 每个进程周转时间之和 / 进程数

= ( 6 + 12+ 19 + 11) / 4 = 12 毫秒

等待时间由每个进程在就绪队列中等待的时间给出。对于非抢占式调度算法，每个进程的等待时间可以简单地计算如下：

任何进程的等待时间 = CPU 接纳时间 - 到达时间

WT_P1 = 0 - 0 = 0 毫秒

WT_P2 = 6 - 4 = 2 毫秒

WT_P3 = 19 - 4 = 15 毫秒

WT_P4 = 16 - 8 = 8 毫秒

平均等待时间

= 每个进程等待时间之和 / 进程数

= (WT_P1 + WT_P2 + WT_P3 + WT_P4) / 4

= ( 0 + 2 +15 + 8) / 4 = 6.25 毫秒

抢占式优先级调度的示例

在抢占式优先级调度中，如果到达的进程优先级高于正在执行的进程，则高优先级进程会抢占低优先级进程。让我们考虑以下一组进程，其到达时间、突发时间和优先级在下表中给出：

甘特图

在 0 毫秒时，P1 是唯一的进程，因此它开始执行。在 4 毫秒时，P2 和 P3 到达。由于 P2 的优先级高于 P1，因此 P2 抢占 P1。在 10 毫秒时，P4 到达，其优先级高于 P2，因此抢占 P2。P4 在 14 毫秒时完成执行并离开。系统中的进程为 P1、P2 和 P3，其中 P2 具有最高优先级，因此被分配给 CPU。在 18 毫秒时，P2 完成执行，因此系统中的进程为 P1 和 P3。由于这两个进程的优先级相同，因此调度程序使用先来先服务的机制选择 P1。当 P1 完成执行时，最后执行 P3。以下甘特图显示了执行顺序：

从甘特图中，我们计算平均周转时间和平均等待时间。

平均周转时间

= 每个进程周转时间之和 / 进程数

= (TAT_P1 + TAT_P2 + TAT_P3 + TAT_P4) / 4

= ((22-0) + (18-4) + (25-4) + (14-10)) / 4 = 15.25 毫秒

平均等待时间

= 每个进程等待时间之和 / 进程数

= (WT_P1 + WT_P2 + WT_P3 + WT_P4) / 4

= (14 + 4 + 18 +0) / 4 = 7 毫秒

优先级调度的优点

• 实现简单，因为调度程序不需要进行任何预先计算。
• 一旦 CPU 定义了进程的相对相关性（优先级），执行顺序就很容易预测。
• 高优先级进程几乎立即得到服务。
• 优先级调度在具有各种进程（每个进程都有自己的需求）的系统中特别有用。

优先级调度的缺点

• 在静态优先级系统中，低优先级进程可能需要无限期地等待，因为系统忙于执行高优先级进程。这会导致停滞。
• 动态优先级解决了停滞问题。但是，根据系统动态更新优先级值的附加逻辑需要额外的 CPU 周期，从而增加了系统负载。
• 在非抢占式优先级调度中，一个大型进程通常会让较短的进程等待很长时间。
• 在抢占式优先级调度中，低优先级进程可能会被间歇性出现的高优先级进程反复抢占，从而导致频繁的上下文切换。

结论

优先级调度算法为更复杂的调度方法（如多级队列调度）铺平了道路。为进程分配优先级可以帮助 CPU 首先完成其重要工作，并将剩余时间留给后台进程。可以根据进程的突发时间、进程类型、等待时间等为进程分配优先级，从而融合其他基本调度算法的优点。