C++实现多级反馈队列调度算法 _ 进程优先级动态调整【源码】

C++实现多级反馈队列调度算法：进程优先级动态调整【源码】

多级反馈队列中，为什么不能直接用 std::priority_queue 管理每个队列？

直接使用 std::priority_queue 来管理多级反馈队列（MFQ）中的单个队列，是一个看似合理实则行不通的陷阱。原因在于，std::priority_queue 本质上是一个基于堆的容器适配器，它只关心“堆顶”那个优先级最高的元素。而MFQ的精髓恰恰相反：在同一级队列内部，必须严格按照先来先服务（FIFO）的顺序进行调度。想象一下，当一个进程的时间片用尽但尚未完成时，你需要将它精准地“挪”到下一级队列的队尾，而不是根据某个新的优先级值重新插入堆中——后者是 std::priority_queue 的工作方式，它不支持这种确定性的尾部插入操作。

更关键的是，MFQ的“优先级”概念体现在队列层级之间，而非队列内部。高级别队列（如第0级）比低级别队列拥有更高的调度优先权，但每个队列自己就是个简单的FIFO队列。因此，正确的容器选择应该是：

• 使用 std::deque 或 std::list：它们能保证在队头取出和队尾插入都是O(1)时间复杂度，并且迭代器稳定，非常适合模拟FIFO行为。
• 将优先级逻辑上移：不要给单个队列内部添加比较逻辑。优先级差异完全由调度器决定——它总是优先检查高优先级队列是否为空，再从其中取任务。
• 一个效率细节：判断队列是否为空时，直接使用 queue.empty() 方法，而不是 queue.size() > 0。因为在某些标准库实现中，size() 可能不是常数时间复杂度。

不能直接用 std::priority_queue 管理多级反馈队列的每个队列，因其仅支持堆顶操作、不支持FIFO调度和随机插入；应改用 std::deque 或 std::list，并通过队列层级而非内部优先级体现优先级差异。

Process 结构体里哪些字段是 MFQ 必须维护的？

设计进程结构体时，字段并非越多越好。针对MFQ算法，以下几个字段具有明确的、不可替代的语义，是必须维护的核心状态：

• pid：进程的唯一标识。这是调试、日志追踪和区分不同进程的基础。
• arrival_time：到达时间。它决定了进程初始进入哪一级队列（通常是最高优先级队列），也是后续计算响应时间等指标的关键依据。
• burst_time 与 remaining_time：前者是进程所需的总CPU时间（只读），后者是剩余执行时间（动态更新）。这里有个常见错误：切勿在单个时间片未用完时就提前将 remaining_time 清零，必须等到它真正减为0才算执行完毕。
• queue_level：当前进程所在的队列编号（通常0代表最高优先级）。每次被降级时，这个值需要递增。不能简单地用进程所在容器的索引来反推，因为进程对象需要在不同队列间移动。
• time_in_current_queue：这个字段可选，但强烈建议添加。它记录了进程在当前级别队列中已累积等待或被调度的时间，是实现“防饥饿”或“优先级提升”机制的重要依据。

需要特别注意的是，MFQ算法本身并不维护一个抽象的“优先级数值”。它只关心两个核心状态：「进程当前所处的层级」和「在当前时间片内已执行的情况」。因此，不必引入类似 static_priority 和 dynamic_priority 的复杂计算，那反而会混淆MFQ的简洁逻辑。

立即学习“C++免费学习笔记（深入）”；

时间片怎么设才不会让低级队列永远没机会执行？

为不同级别队列设置时间片，是MFQ调度的艺术所在。一个典型的错误策略是采用固定倍增模式：比如第0级队列4ms，第1级8ms，第2级16ms……这种设置可能导致短作业迅速在第0级完成，而长作业一旦掉入低级队列，就会面临极其漫长的等待，造成严重的响应延迟。这违背了MFQ“优待短作业、公平调度长作业”的初衷。

更合理的实操建议如下：

• 前两级队列采用相同的小时间片（例如都是4ms）。这能确保新到达的交互型短作业得到快速响应，是提升系统感知流畅度的关键。
• 从第三级开始，采用线性增长而非指数增长。例如每级增加2ms（4ms, 4ms, 6ms, 8ms, 10ms…）。这样既能给予长作业更长的连续执行时间，又避免了等待时间失控。
• 设置最大队列级数（比如5级）。这是防止进程无限降级的“安全网”。当进程降至最后一级时，就不再降级，并在该级内采用标准的轮转（RR）调度，保证所有长作业都能获得基本的执行机会。
• 在调度器的主循环逻辑中，记得加入边界检查：if (current_level > MAX_LEVEL) current_level = MAX_LEVEL;。

降级逻辑写在 run_one_quantum() 还是 scheduler_tick()？

这是一个关于逻辑位置的关键抉择。答案是：必须写在 run_one_quantum() 函数的末尾。这个函数模拟了进程执行一个完整时间片的过程。只有当进程用完一个时间片后，检查其 remaining_time 仍大于0，才触发降级操作。

如果错误地将降级判断放在全局的 scheduler_tick() 中，会导致一个刚进入队列、还没来得及执行的进程，仅仅因为时间戳的推进就被误判为“超时”而降级，这显然是不合理的。

实现降级时，有几个细节至关重要：

• 先更新状态，再移动容器：首先递增 process.queue_level，然后将进程对象插入到对应的 queues[process.queue_level] 队尾。
• 保留时间累积信息：降级时，不要重置 process.time_in_current_queue。这个累积值是用来判断进程是否在某一级等待过久、从而需要被“提级”以预防饥饿的重要依据。
• 考虑主动提级机制：为了防止CPU密集型的长进程在低级队列中“饿死”，可以设计一个策略：如果进程在某一级队列中被连续调度了N次（例如3次）仍未完成，则将其提升回较高级别（如第0级），给予它再次被快速响应的机会。

最后，理解降级的本质很重要：它并非一种“惩罚”，而是一种“资源让渡”策略。目的是让更可能快速结束的短作业优先获得服务，从而提升系统整体的吞吐量和平均响应时间。一个进程降级后，它下次获得CPU的时间，取决于它新加入的那个队列的繁忙程度，而不再与它最初的高优先级直接绑定。