多级反馈队列进程调度算法通过设置多个优先级不同的就绪队列，为每个队列分配不同的时间片，进程在运行时会根据执行情况动态调整优先级和所属队列，兼顾短进程响应速度和长进程运行公平性，是操作系统中非常经典的调度策略。
核心设计思路
实现该算法需要先明确几个核心规则：第一，新进程进入时默认放入最高优先级队列，该队列时间片最短；第二，进程在当前队列时间片内运行完成则直接退出，未用完时间片主动让出CPU则保持原优先级；第三，进程时间片用完仍未完成则降低优先级，放入下一级队列，最低优先级队列采用时间片轮转调度；第四，系统可以周期性提升所有队列中等待进程的优先级，避免长进程饥饿。
关键数据结构定义
首先定义进程结构体和队列相关结构，进程需要记录进程ID、剩余运行时间、已用时间片、当前优先级、状态等属性：
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
// 进程状态枚举
enum ProcessState {
READY, // 就绪
RUNNING, // 运行
FINISHED // 完成
};
// 进程结构体
struct Process {
int pid; // 进程ID
int total_time; // 总运行时间
int remain_time; // 剩余运行时间
int used_time; // 当前时间片已用时间
int priority; // 当前优先级，数值越大优先级越高
ProcessState state; // 进程状态
Process(int id, int time, int pri = 3) : pid(id), total_time(time), remain_time(time),
used_time(0), priority(pri), state(READY) {}
};
然后定义多级队列管理结构，假设设置3个优先级队列，不同队列的时间片长度不同：
// 多级反馈队列管理类
class MFQScheduler {
private:
vector<queue<Process*>> ready_queues; // 就绪队列数组，下标越小优先级越高
vector<int> time_slices; // 每个队列对应的时间片长度
int current_queue_idx; // 当前调度的队列下标
int time; // 系统运行时间
vector<Process*> all_processes; // 所有进程记录，用于最后统计
public:
// 初始化，设置3个队列，时间片分别为2、4、8
MFQScheduler() : current_queue_idx(0), time(0) {
time_slices.push_back(2);
time_slices.push_back(4);
time_slices.push_back(8);
for (int i = 0; i < 3; i++) {
ready_queues.push_back(queue<Process*>());
}
}
};
核心调度逻辑实现
进程入队与优先级调整
新进程加入时默认放入最高优先级队列，时间片用完的进程降低优先级进入下一级队列，同时实现周期提升优先级的逻辑：
// 添加新进程到最高优先级队列
void add_process(Process* proc) {
proc->priority = ready_queues.size() - 1; // 最高优先级对应最大下标值
ready_queues[ready_queues.size() - 1].push(proc);
all_processes.push_back(proc);
cout << "进程" << proc->pid << "加入最高优先级队列，剩余运行时间：" << proc->remain_time << endl;
}
// 降低进程优先级，放入下一级队列
void lower_priority(Process* proc) {
if (proc->priority > 0) {
proc->priority--;
ready_queues[proc->priority].push(proc);
cout << "进程" << proc->pid << "时间片用完，降低优先级到" << proc->priority << "级队列" << endl;
} else {
// 已经是最高优先级队列，重新放入队尾，时间片轮转
ready_queues[0].push(proc);
cout << "进程" << proc->pid << "在最高优先级队列时间片用完，重新入队" << endl;
}
}
// 周期性提升所有等待进程的优先级，避免饥饿
void boost_priority() {
// 每20个时间单位提升一次优先级
if (time > 0 && time % 20 == 0) {
// 清空所有就绪队列，将进程重新放入最高优先级队列
for (int i = 0; i < ready_queues.size(); i++) {
while (!ready_queues[i].empty()) {
Process* proc = ready_queues[i].front();
ready_queues[i].pop();
proc->priority = ready_queues.size() - 1;
ready_queues[ready_queues.size() - 1].push(proc);
}
}
cout << "时间" << time << "：执行优先级提升，所有就绪进程回到最高优先级队列" << endl;
}
}
调度执行主逻辑
调度主逻辑按照优先级从高到低遍历队列，找到第一个有就绪进程的队列，取出队首进程执行一个时间单位，根据执行情况处理后续逻辑：
// 执行一次调度
void schedule() {
boost_priority();
// 从高优先级队列到低优先级队列查找就绪进程
for (int i = ready_queues.size() - 1; i >= 0; i--) {
if (!ready_queues[i].empty()) {
Process* current_proc = ready_queues[i].front();
ready_queues[i].pop();
current_proc->state = RUNNING;
current_proc->used_time++;
current_proc->remain_time--;
time++;
cout << "时间" << time << "：调度进程" << current_proc->pid
<< "运行，当前队列优先级" << i << "，时间片长度" << time_slices[i]
<< "，剩余运行时间" << current_proc->remain_time << endl;
// 判断进程是否运行完成
if (current_proc->remain_time == 0) {
current_proc->state = FINISHED;
cout << "进程" << current_proc->pid << "运行完成" << endl;
} else {
// 判断当前时间片是否用完
if (current_proc->used_time >= time_slices[i]) {
current_proc->used_time = 0;
lower_priority(current_proc);
} else {
// 时间片未用完，进程主动让出CPU，保持原优先级入队
ready_queues[i].push(current_proc);
cout << "进程" << current_proc->pid << "时间片未用完，保持优先级入队" << endl;
}
}
return;
}
}
// 没有就绪进程，时间推进
time++;
cout << "时间" << time << "：无就绪进程，空闲" << endl;
}
// 判断所有进程是否都完成
bool all_finished() {
for (Process* proc : all_processes) {
if (proc->state != FINISHED) {
return false;
}
}
return true;
}
完整测试示例
编写测试代码验证调度逻辑的正确性，创建3个不同运行时间的进程，启动调度直到所有进程完成：
int main() {
MFQScheduler scheduler;
// 创建3个测试进程，运行时间分别为5、10、15
Process* p1 = new Process(1, 5);
Process* p2 = new Process(2, 10);
Process* p3 = new Process(3, 15);
scheduler.add_process(p1);
scheduler.add_process(p2);
scheduler.add_process(p3);
// 执行调度直到所有进程完成
while (!scheduler.all_finished()) {
scheduler.schedule();
}
// 释放内存
delete p1;
delete p2;
delete p3;
return 0;
}
算法特性分析
该实现的多级反馈队列调度算法具备以下特性：第一，短进程可以在高优先级短队列中快速完成，响应速度快；第二，长进程会逐渐降低优先级到时间片更长的队列，不会因为频繁切换浪费CPU资源；第三，优先级提升机制避免了长进程长期饥饿的问题；第四，优先级和时间片调整逻辑完全可配置，可根据实际需求修改队列数量、时间片长度和优先级提升周期。