C++实现改进的轮转调度算法（附代码及缺陷分析）

轮转调度算法（Round Robin Scheduling）是一种常用的操作系统进程调度算法，它为每个进程分配一个固定的时间片，按照先来先服务的原则循环调度进程。本文将使用 C++ 实现经典的轮转调度算法，并分析其存在的缺陷，最后给出改进的算法和代码。

1. 经典轮转调度算法及代码实现

1.1 算法描述

经典的轮转调度算法将所有就绪进程放入一个队列中，每次选择队首进程执行一个时间片。如果进程在时间片内完成，则将其从队列中移除；否则，将其剩余服务时间减去一个时间片，并将其重新放入队列末尾。

1.2 C++代码实现cpp#include #include #include

using namespace std;

// 进程控制块struct ProcessControlBlock { int process_id; int service_time; int remaining_time;};

// 轮转调度算法函数void roundRobinScheduling(vector& processes, int time_quantum) { queue ready_queue;

int current_time = 0;    while (!processes.empty()) {        ProcessControlBlock current_process = processes.front();        processes.erase(processes.begin());//移除就绪队列里的第一个进程

    if (current_process.remaining_time <= time_quantum) {            current_time += current_process.remaining_time;            cout << 'Process ' << current_process.process_id << ' is scheduled and completed at time ' << current_time << endl;        }        else {            current_time += time_quantum;            current_process.remaining_time -= time_quantum;            ready_queue.push(current_process);        }

    while (!ready_queue.empty()) {            ProcessControlBlock next_process = ready_queue.front();            ready_queue.pop();            processes.push_back(next_process);        }    }}

int main() { vector processes = { {1, 10, 10}, {2, 4, 4}, {3, 6, 6}, {4, 2, 2} };

int time_quantum = 3;//时间片大小    roundRobinScheduling(processes, time_quantum);

return 0;}

2. 算法缺陷分析

经典轮转调度算法存在一个缺陷：当一个进程的剩余服务时间大于时间片大小时，它会被反复放回就绪队列，并且其他进程无法被调度到CPU上执行，造成了不必要的延迟。

3. 改进方案：优先级队列

为了解决上述缺陷，可以对就绪队列进行优先级排序，以确保每次都选择剩余服务时间最短的进程执行。可以使用优先级队列（priority_queue）来实现这个功能。

3.1 改进后的代码实现cpp#include #include #include

using namespace std;

struct ProcessControlBlock { int process_id; int service_time; int remaining_time;};

struct CompareRemainingTime { bool operator()(const ProcessControlBlock& p1, const ProcessControlBlock& p2) { return p1.remaining_time > p2.remaining_time; }};

void roundRobinScheduling(vector& processes, int time_quantum) { priority_queue<ProcessControlBlock, vector, CompareRemainingTime> ready_queue;

int current_time = 0;    while (!processes.empty() || !ready_queue.empty()) {        if (!ready_queue.empty()) {            ProcessControlBlock current_process = ready_queue.top();            ready_queue.pop();

        if (current_process.remaining_time <= time_quantum) {                current_time += current_process.remaining_time;                cout << 'Process ' << current_process.process_id << ' is scheduled and completed at time ' << current_time << endl;            }            else {                current_time += time_quantum;                current_process.remaining_time -= time_quantum;                ready_queue.push(current_process);            }        }

    while (!processes.empty() && processes.front().service_time <= current_time) {            ready_queue.push(processes.front());            processes.erase(processes.begin());        }    }}

int main() { vector processes = { {1, 10, 10}, {2, 4, 4}, {3, 6, 6}, {4, 2, 2} };

int time_quantum = 3;    roundRobinScheduling(processes, time_quantum);

return 0;}

3.2 代码解读

自定义比较函数 CompareRemainingTime: 用于优先级队列的排序，确保剩余服务时间短的进程排在队列前面。2. 使用优先级队列 ready_queue: 将就绪进程按照剩余服务时间排序。3. 改进调度逻辑: 每次从优先级队列中取出剩余服务时间最短的进程执行。

4. 总结

改进后的轮转调度算法通过优先级队列，优先调度剩余服务时间短的进程，从而减少了不必要的延迟，提高了调度效率。