C++ 实现基于优先级抢占的多级反馈队列调度算法 _ 进程调度模拟【源码】-C++-PHP中文网

MLFQ不能仅用std::priority_queue实现，因其缺乏动态降级、跨队列迁移、抢占检测等能力；需用多个FIFO队列（如std::deque数组）显式管理进程状态与层级切换逻辑。

c++ 实现基于优先级抢占的多级反馈队列调度算法 _ 进程调度模拟【源码】

为什么多级反馈队列（MLFQ）不能只靠 `std::priority_queue` 实现

因为 std::priority_queue 是静态优先级容器，不支持运行中动态降级、时间片耗尽后重新入队、跨队列迁移等关键行为。MLFQ 的核心是「队列层级 + 抢占 + 优先级衰减」，必须自己管理多个就绪队列（如 std::deque 数组），并显式维护每个进程的当前队列索引、剩余时间片、上次 CPU 使用时间等状态。

常见错误是把所有进程塞进一个优先队列，再用 priority 字段模拟级别——这会导致抢占失效：当高优进程到达时，无法中断正在运行的低优进程，除非你手动遍历整个队列找最高优先级，O(n) 开销且逻辑混乱。

每个就绪队列应独立使用 FIFO（std::deque 或 std::list），而非优先队列
调度器每次只从最低编号的非空队列取进程（即最高优先级队列），但需检查是否有新到的更高优先级进程可抢占
进程被抢占或时间片用完后，不是简单放回原队列尾部，而是降级到下一级队列（除非已在最低级）

如何正确建模进程状态和队列切换逻辑

关键不是“怎么排序”，而是“什么时候切队列”。进程结构体至少要包含：pid、arrival_time、burst_time、remaining_time、queue_level、last_run_time（用于判断是否被 I/O 中断后应升回高优队列）。

队列切换规则必须严格按经典 MLFQ 原则编码：

新进程总是进入最高优先级队列（queue_level = 0）
时间片耗尽 → queue_level = min(queue_level + 1, MAX_LEVEL - 1)，然后入对应队列尾部
被更高优先级进程抢占 → 当前进程立即移出运行态，按上述规则降级；抢占者从其所在队列头部取出
I/O 完成唤醒的进程，通常应回到最高优先级队列（避免长等待惩罚），但可加条件：若 last_run_time 距今很近，可保留在原级

示例片段（伪代码逻辑）：

if (current->remaining_time == 0) {
    current->queue_level = std::min(current->queue_level + 1, MAX_LEVEL - 1);
    queues[current->queue_level].push_back(*current);
}

抢占检测和时钟推进怎么写才不崩

模拟器没有真实时钟中断，必须靠事件驱动推进：维护全局 current_time，每次选择下一个要执行的进程时，先将 current_time 推进到该进程的 arrival_time（若尚未到达），再分配时间片。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

抢占只发生在「有新进程到达，且其目标队列优先级高于当前运行进程所在队列」时。注意：不是比较 queue_level 数值大小，而是队列编号越小优先级越高（queue[0] 最高）。

每次新进程到达，插入对应队列后，立即检查：new_process.queue_level → 触发抢占
被抢占的进程要保存 remaining_time 和更新 last_run_time = current_time
时间片长度应随队列层级递增（如 queue[0]: 1ms, queue[1]: 2ms, queue[2]: 4ms），用数组 time_quantum[LEVELS] = {1,2,4,8} 管理

漏掉 current_time 的同步推进，会导致到达时间判断错乱，进程“穿越”到过去执行。

输出调度日志时最容易忽略的三个细节

调试时只打印 “P1 runs at t=5” 没用。真实验证需要能回溯调度决策依据：

必须记录每次上下文切换的触发原因："P2 arrived, preempting P1" 或 "P1 time quantum expired, demoted to level 1"
每个进程的完成时间（finish_time）必须在它 remaining_time == 0 且从 CPU 退出时才赋值，不能在入队时猜
统计周转时间（finish_time - arrival_time）和响应时间（首次获得 CPU 时间 - arrival_time）时，注意响应时间不是“第一次入队时间”，而是 start_time（实际开始执行时刻）

没有这些字段，你无法区分是算法逻辑问题，还是单纯输出逻辑没对齐模拟步进。

队列层级数、时间片倍增系数、I/O 行为建模方式——这些参数微调会极大改变吞吐与响应的权衡，但它们本身不改变核心状态迁移逻辑。真正难的是让所有时间戳、队列指针、抢占标记在每一步都自洽。