多级队列调度 (MLQ)

---

---

在大多数系统中，进程组合多种多样，没有单一的调度算法能够提供最佳解决方案。通常，可以将进程分为不同的类型，以便为每种类型分配优先级值，并为每种类型定义适当的调度策略。

解决方案是引入多个队列而不是单个就绪队列，并在其上执行调度。处理多个队列的调度策略称为多级队列调度。上述的修改版本称为多级反馈队列调度。

多级队列调度 (MLQ)

在多级队列调度中，进程被分为不同的类别，每个类别都有其独特的特性。在大多数系统中，有三种类型的进程：系统进程、前台进程和后台进程。

系统进程具有最高优先级，需要立即处理。前台进程是交互式的用户进程；而后台进程是批处理进程。由于不同的类别需要不同的响应时间和优先级，因此它们需要不同的调度算法。这些进程被分配到不同的队列，如下图所示：

根据系统的性质，可能还有许多其他类别的队列，其优先级介于这些广泛的进程类别之间，例如实时进程队列、交互式编辑队列等。

多级队列

从上图可以看出，就绪队列被划分成几个独立的队列，每个队列都有其自身的特性和调度技术。当进程进入系统时，它将根据其优先级、内存大小或响应时间永久分配到其中一个队列。这个被划分的就绪队列称为多级队列。

多级队列中的每个队列都有不同的调度算法。通常，系统队列使用抢占式优先级调度；前台队列使用轮转调度；后台队列使用先来先服务调度。

多级队列 (MLQ) 调度的运行原理

执行原理如下：

假设有n个队列，编号从1到n，优先级从1到n。每个进程永久分配到这些队列中的一个。一个队列对优先级较低的队列具有绝对优先权。每个队列都有自己的调度策略。首先，检查优先级为1的队列1。如果其中有进程，则根据队列1的调度策略执行它们。

如果队列1中没有进程，则检查队列2。如果队列2有进程，则根据其调度算法进行调度。以此类推，直到队列n。因此，队列x中的进程只有在队列1到队列(x-1)为空时才能访问CPU。如果队列x中的进程P5正在执行，并且一个新的进程P16到达一个具有更高优先级的队列，则P16会立即抢占P5并开始执行。

借助以下示例可以更好地理解其工作原理：

多级队列 (MLQ) 调度的示例

让我们考虑一个具有3个队列的系统，优先级为1到3，进程为P1到P5，如下表所示：

让我们执行MLQ调度并绘制进程的甘特图。

时间 = 0ms

事件：Q3中的P5到达

系统中的进程：Q3中的P5。

由于P5是唯一的进程，因此它立即被调度。

时间 = 2ms

事件：Q3中的P4到达

系统中的进程：Q3中的P4和P5。

由于P4和P5都在Q3中，并且Q3遵循先来先服务调度，因此P5继续执行。

到2ms的甘特图：

时间 = 4ms

事件：进程P2和P3到达。

系统中的进程：Q2中的P2和P3；Q3中的P4和P5。

由于P2和P3都在Q2中，而正在执行的进程P5在Q3中，P5被抢占。在P2和P3中，P3被分配给CPU，因为Q2遵循最短剩余时间优先调度。

到4ms的甘特图：

时间 = 7ms

事件：进程P1到达。

系统中的进程：Q1中的P1；Q2中的P2、P3；Q3中的P4、P5。

由于P1在Q1中，而正在执行的进程P3在Q2中，P3被抢占，P1开始执行。

到7ms的甘特图：

时间 = 9ms

事件：进程P1完成执行。

系统中的进程：Q2中的P2、P3；Q3中的P4、P5。

由于P2和P3在Q2中，其优先级高于P4和P5，因此它们竞争CPU时间。P3被分配给CPU，因为Q2使用SRTN调度，P2和P3的剩余时间分别为6和1。

到9ms的甘特图：

时间 = 10ms

事件：进程P3完成执行。

系统中的进程：Q2中的P2；Q3中的P4、P5。

由于P2在Q2中，其优先级高于P4和P5，因此P2被分配给CPU。

到10ms的甘特图：

时间 = 16ms

事件：进程P2完成执行。

系统中的进程：Q3中的P4、P5。

由于P5先到达，并且Q3遵循FCFS调度，因此P5被分配给CPU。

到16ms的甘特图：

时间 = 24ms

事件：进程P5完成执行。

系统中的进程：Q3中的P4。

由于P4是系统中唯一的进程，因此它被分配给CPU。

到24ms的甘特图：

时间 = 27ms

事件：进程P4完成执行。

系统中的进程：无

到27ms的最终甘特图：

多级队列调度的特点

• 多级队列 - MLQ调度的核心是多个队列，每个队列都有自己的优先级和响应时间。
• 队列间的抢占 - 在MLQ中，当高优先级队列中的进程进入系统时，它可以抢占属于低优先级队列的正在运行的进程。
• 不同队列的不同调度策略 - 不同的队列与不同的调度策略相关联，这取决于其中进程的特性。
• 定制化调度 - 关于要包含的队列数量及其相对优先级的分配没有硬性规定。这为根据系统需求进行定制化调度铺平了道路。
• 新策略的开发 - MLQ基本上是一个概念，可以从中开发新的调度策略。这允许对调度进行研究。随着进程管理不断变化以及新操作系统的开发，调度策略需要更新。此外，没有单一的调度算法能够满足所有进程的需求。MLQ为在新系统中组合不同算法提供了基础。

多级队列调度的优点

• MLQ的主要优点是它允许设置进程间的优先级，这是实际应用中必不可少的。
• MLQ能够有效地分配系统资源到不同的进程之间。
• MLQ大大缩短了高优先级进程的响应时间。这使得整个系统更具响应性。
• MLQ根据系统需求具有高度的可定制性。
• MLQ提高了系统性能并增加了吞吐量。
• 在进程组合多样化的系统中，它具有较低的调度开销。

多级队列调度的局限性

• 如果许多高优先级队列都拥有稳定的进程流，则低优先级队列中的进程可能会面临无限期饥饿。这是MLQ的主要缺点。
• MLQ的实现本身就很复杂。它需要正确的设计和开发，否则整个调度机制可能会崩溃。
• 为进程分配固定的优先级使得MLQ成为一种不灵活的策略。
• 调度过于依赖于固定的优先级，这些优先级是在进程进入系统时立即分配的。进程优先级的错误分配会严重影响性能。

多级反馈队列调度

多级反馈队列调度是对多级队列调度的改进，它成功地克服了饥饿问题。它根据进程的执行行为动态地为进程分配优先级。最初，所有进程都被分配到最高优先级队列。如果进程花费的时间超过所需的时间片，则将其降级到下一个优先级队列。相反，如果进程在低优先级队列中停留时间过长，则将其提升到更高的优先级队列。