当前位置： 首页 > article >正文

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

article 2025/2/26 17:50:53

目录

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;               // 进程ID
    int 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];   // 进程ID
        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();  // 进程入队
}
  • 数据存储：
    • 读取用户输入的 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;
}
  • 输出格式：
    • 进程执行顺序
    • 各进程的完成时间、周转时间、带权周转时间
    • 平均值

3. 测试

4. 总结

  • 时间片大小影响：
    • 过小：频繁切换，开销大。
    • 过大：趋近于 FCFS（先来先服务）。
  • 适用场景：
    • 适用于交互式系统，保证每个进程公平地获得 CPU 资源。

http://www.kler.cn/a/562041.html

相关文章：

  • Windows golang安装和环境配置
  • QT各种版本下载安装
  • IP-------GRE和MGRE
  • ERROR 1524 (HY000) Plugin ‘mysql_native_password‘ is not loaded
  • 项目一 - 任务3：搭建Java集成开发环境IntelliJ IDEA
  • 布署elfk-准备工作
  • 什么是DrawCall？DrawCall为什么会影响游戏运行效率？如何减少DrawCall？
  • TCP网络编程库——Muduo库
  • sql server笔记
  • AI 自动化编程盛行，程序员失业是个xx命题
  • jdk21下载、安装（Windows、Linux、macOS）
  • Qt：布局管理器
  • AI将会取代生活的方方面面吗？
  • 记录此刻：历时两月，初步实现基于FPGA的NVMe SSD固态硬盘存储控制器设计！
  • SUSE15SP4 网络配置连外网
  • 货车一键启动无钥匙进入手机远程启动的正确使用方法
  • OkHttp、Retrofit、RxJava：一文讲清楚
  • 前端如何转战鸿蒙
  • ubuntu离线安装Ollama并部署Llama3.1 70B INT4
  • 超越云计算：计算连续体中的无服务器函数