[OS] 基于RR（Round Robin）算法的CPU调度

1. 代码

2. 代码详细解析

2.1 结构体 processing

2.2 进程信息的输入

2.3 进程数据预处理

2.4 进程执行计算

2.5 计算平均时间

2.6 结果输出

3. 测试

4. 总结

1. 代码

实现时间片轮转调度（Round Robin, RR）算法，适用于分时系统，其主要特点是：

进程按照到达时间排序，进入就绪队列（queue）。
进程依次执行 一个时间片（Time Quantum），若在时间片内未完成，则重新进入队列。
计算并输出：

- 完成时间（Completion Time, CT）
- 周转时间（Turnaround Time, TAT）
- 带权周转时间（Weighted Turnaround Time, WTAT）
- 平均周转时间（Avg TAT）
- 平均带权周转时间（Avg WTAT）

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXSIZE 5
int ID[MAXSIZE], COME_TIME[MAXSIZE], RUN_TIME[MAXSIZE];
struct processing
{int pid;		//作业号int sequence;	//顺序号double come_time;	//到达时double run_time;	//运行时double last_run_time;	//剩余运行时间double over_time;	//完成时double round_time;	//周转时double avg_time;	//带权周转时
}pc[MAXSIZE];		//作业数
queue<processing > q;
bool CmpByComeTime(processing p1, processing p2) {return p1.come_time<p2.come_time;
}
void push_in_queue() {		//进程入队列for (int i = 0; i < MAXSIZE; ++i){q.push(pc[i]);}
}
void info_to_process() {for (int i = 0; i<MAXSIZE; ++i) {pc[i].sequence = i;pc[i].pid = ID[i];pc[i].come_time = COME_TIME[i];pc[i].run_time = RUN_TIME[i];pc[i].last_run_time = pc[i].run_time;}sort(pc, pc + MAXSIZE, CmpByComeTime);push_in_queue();
}
void get_info() {		//输入进程信息for (int i = 0; i<MAXSIZE; i++) {cin >> ID[i] >> COME_TIME[i] >> RUN_TIME[i];}info_to_process();}
void print(double avg_sum_round_time, double avg_sum_avg_time) {cout << "执行顺序：" << endl;for (int i = 0; i < MAXSIZE; ++i){/* code */cout << pc[i].pid << " ";}cout << endl;cout << "作业号" << '\t' << "到达时" << '\t' << "运行时" << '\t' << "完成时" << '\t' << "周转时" << '\t' << "带权周转时" << '\t' << endl;for (int i = 0; i < MAXSIZE; ++i){cout << pc[i].pid << '\t' << pc[i].come_time << '\t'<< pc[i].run_time << '\t' << pc[i].over_time << '\t'<< pc[i].round_time << '\t'<< pc[i].avg_time << endl;}cout << "平均周转时: " << avg_sum_round_time << endl<< "平均带权周转时: " << avg_sum_avg_time << endl << endl;
}
void get_RoundAndAvgTime() {double sum_round_time = 0;double avg_sum_round_time = 0.0;double sum_avg_time = 0.0;double avg_sum_avg_time = 0.0;for (int i = 0; i<MAXSIZE; i++) {sum_round_time += pc[i].round_time;sum_avg_time += pc[i].avg_time;}avg_sum_round_time = sum_round_time * 1.0 / MAXSIZE;avg_sum_avg_time = sum_avg_time * 1.0 / MAXSIZE;print(avg_sum_round_time, avg_sum_avg_time);
}
void calculate(int TimePeace) {int NowTime = 0;while (!q.empty()) {int NowPcNum = q.front().sequence;if (TimePeace >= pc[NowPcNum].last_run_time) {pc[NowPcNum].over_time = NowTime + pc[NowPcNum].last_run_time;		//完成时间pc[NowPcNum].round_time = pc[NowPcNum].over_time - pc[NowPcNum].come_time;		//周转时 = 完成时 - 到达时pc[NowPcNum].avg_time = pc[NowPcNum].round_time / pc[NowPcNum].run_time;			//带权周转时 = 周转时 / 运行时NowTime += pc[NowPcNum].last_run_time;q.pop();}else {pc[NowPcNum].last_run_time -= TimePeace;		//该进程剩余需要运行的时间NowTime += TimePeace;q.push(pc[NowPcNum]);q.pop();}}get_RoundAndAvgTime();
}int main(int argc, char const *argv[])
{get_info();int TimePeace;char ch;while (true) {cout << "时间片大小" << endl;cin >> TimePeace;calculate(TimePeace);cout << "continue? [y/n]" << endl;cin >> ch;if (ch == 'y') {info_to_process();continue;}else {break;}}system("pause");return 0;}

2. 代码详细解析

2.1 结构体 `processing`

struct processing {int pid;               // 进程IDint sequence;          // 进程顺序号double come_time;      // 到达时间double run_time;       // 运行时间double last_run_time;  // 剩余运行时间double over_time;      // 完成时间double round_time;     // 周转时间double avg_time;       // 带权周转时间
};

pid：进程ID
come_time：进程的到达时间
run_time：进程需要的CPU运行时间
last_run_time：进程尚未执行完的时间
over_time：进程最终完成的时间
round_time：周转时间 = 完成时间 - 到达时间
avg_time：带权周转时间 = 周转时间 / 运行时间

2.2 进程信息的输入

void get_info() {  for (int i = 0; i < MAXSIZE; i++) {cin >> ID[i] >> COME_TIME[i] >> RUN_TIME[i];  // 读入进程数据}info_to_process();
}

功能：获取用户输入的进程ID、到达时间、运行时间，然后存入全局数组 ID、COME_TIME、RUN_TIME。
调用：info_to_process() 处理输入数据。

2.3 进程数据预处理

void info_to_process() {for (int i = 0; i < MAXSIZE; ++i) {pc[i].sequence = i;  // 进程顺序号pc[i].pid = ID[i];   // 进程IDpc[i].come_time = COME_TIME[i]; // 进程到达时间pc[i].run_time = RUN_TIME[i];   // 运行时间pc[i].last_run_time = pc[i].run_time; // 剩余时间初始化为运行时间}sort(pc, pc + MAXSIZE, CmpByComeTime); // 按到达时间排序push_in_queue();  // 进程入队
}

数据存储：

- 读取用户输入的 ID、COME_TIME、RUN_TIME
- 按到达时间 (come_time) 升序排序
- 将进程推入队列（queue）

2.4 进程执行计算

void calculate(int TimePeace) { int NowTime = 0;  // 记录当前时间while (!q.empty()) {  // 队列不为空int NowPcNum = q.front().sequence;  // 获取当前队列头的进程if (TimePeace >= pc[NowPcNum].last_run_time) { pc[NowPcNum].over_time = NowTime + pc[NowPcNum].last_run_time; // 计算完成时间pc[NowPcNum].round_time = pc[NowPcNum].over_time - pc[NowPcNum].come_time; // 计算周转时间pc[NowPcNum].avg_time = pc[NowPcNum].round_time / pc[NowPcNum].run_time; // 计算带权周转时间NowTime += pc[NowPcNum].last_run_time; // 更新时间q.pop();  // 进程完成，出队} else {pc[NowPcNum].last_run_time -= TimePeace; // 进程未执行完，减少运行时间NowTime += TimePeace;q.push(pc[NowPcNum]);  // 进程重新入队q.pop();}}get_RoundAndAvgTime(); // 计算平均时间
}

执行逻辑：

1. 从队列头部取出进程
2. 若剩余执行时间 ≤ 时间片：进程执行完毕，计算完成时间、周转时间、带权周转时间，并出队。
3. 若剩余执行时间 > 时间片：执行时间片后，减少last_run_time，进程重新入队。

2.5 计算平均时间

void get_RoundAndAvgTime() {double sum_round_time = 0, sum_avg_time = 0;for (int i = 0; i < MAXSIZE; i++) {sum_round_time += pc[i].round_time;sum_avg_time += pc[i].avg_time;}double avg_sum_round_time = sum_round_time / MAXSIZE;double avg_sum_avg_time = sum_avg_time / MAXSIZE;print(avg_sum_round_time, avg_sum_avg_time);  // 输出结果
}

计算公式：

- 平均周转时间 = 总周转时间 / 进程数
- 平均带权周转时间 = 总带权周转时间 / 进程数

2.6 结果输出

void print(double avg_sum_round_time, double avg_sum_avg_time) {cout << "执行顺序：" << endl;for (int i = 0; i < MAXSIZE; ++i) {cout << pc[i].pid << " ";}cout << endl;cout << "作业号" << '\t' << "到达时" << '\t' << "运行时" << '\t' << "完成时" << '\t' << "周转时" << '\t' << "带权周转时" << endl;for (int i = 0; i < MAXSIZE; ++i) {cout << pc[i].pid << '\t' << pc[i].come_time << '\t'<< pc[i].run_time << '\t' << pc[i].over_time << '\t'<< pc[i].round_time << '\t' << pc[i].avg_time << endl;}cout << "平均周转时: " << avg_sum_round_time << endl<< "平均带权周转时: " << avg_sum_avg_time << endl << endl;
}