操作系统课程实验1-进程调度模拟实验

news/2024/9/25 7:46:42/

操作系统课程实验1-进程调度模拟实验

一、实验介绍

1.1 实验目的

本实验模拟在单处理机环境下的处理机调度,帮助理解进程调度的概念,深入了解进程控制块的功能,以及进程的创建、撤销和进程各个状态间的转换过程。

1.2 实验内容
  1. 进程调度算法:采用最高优先数优先的调度算法、先来先服务算法、SJF和多级反馈调度算法
  2. 每个进程有一个进程控制块(PCB)表示。进程控制块可以包含如下信息:进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。进程的优先数及需要的运行时间可以事先人为输入(也可以由随机数产生)。进程的到达时间为进程输入的时间。 进程的运行时间以时间片为单位进行计算。
1.3 实验要求
  1. 每进行一次调度程序都显示输出一次运行进程、就绪队列、以及各个进程的PCB,以便进行检查。
  2. 对同一组进程的各种调度算法分别计算平均周转时间和平均带权周转时间。
1.4 参考测试数据

系统有5个进程,其就绪时刻、服务时间和优先级(优先级数值越大优先级越高)如下图所示:
在这里插入图片描述

多级反馈队列调度算法:设3个就绪队列,时间片分别为1、2、3。

二、实现代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>using namespace std;typedef struct ProcessControlBlock { // 定义进程控制块结构体int name;                   // 进程名称unsigned int Arrive_Time;   // 到达时间unsigned int Wait_Time;     // 等待时间unsigned int Start_Time;    // 开始时间unsigned int Serve_Time;    // 服务时间unsigned int Finish_Time;   // 完成时间int Priority;               // 优先级unsigned int cycle_time;    // 周转时间double Weighted_cycle_time; // 带权周转时间unsigned int Original_Serve_Time;bool FinishFlag;            // 完成标志
} PCB;                          // 进程控制块的别名typedef struct Multilevel_Feedback_Queue { // 定义多级反馈队列int L1_Length, L1[5];       // 第一级别反馈队列int L2_Length, L2[5];       // 第二级别反馈队列int L3_Length, L3[5];       // 第三级别反馈队列unsigned int Time_Slice[3]; // 三级反馈队列分配的时间片
} MFQ;void PCB_Info_Input(PCB Process_HPF[5], PCB Process_FCFS[5], PCB Process_SJF[5], PCB Process_MFQ[5]); 					 	// 函数声明:输入进程控制块信息void Highest_Prioriy_First(PCB  Process[5]); 	// 函数声明:最高优先级优先算法
void First_Come_First_Serve(PCB Process[5]); 	// 函数声明:先来先服务算法
void Shortest_Job_First(PCB Process[5]);	 	// 函数声明:短作业优先算法
void Multilevel_Feedback_Queue_Algorithm(PCB Process[5]);	// 函数声明:多级反馈队列算法
void Multilevel_Feedback_Queue_Algorithm_Input(MFQ * mfq);	// 函数声明:多级反馈队列的输入bool SortBy_Priority(PCB* a, PCB* b);		 	// 函数声明:按优先级排序
bool SortBy_ServeTime(PCB* a, PCB* b);		 	// 函数声明:按服务时间排序
bool SortBy_ArriveTime(PCB a, PCB b);		 	// 函数声明:按到达时间排序int main(void) {PCB Process_HPF[5]; 								// 定义5个进程控制块数组PCB Process_FCFS[5]; 								// 定义5个进程控制块数组PCB Process_SJF[5]; 								// 定义5个进程控制块数组PCB Process_MFQ[5]; 								// 定义5个进程控制块数组PCB_Info_Input(Process_HPF, Process_FCFS, Process_SJF, Process_MFQ); 								// 调用输入进程控制块信息函数Highest_Prioriy_First(Process_HPF); 				// 调用优先级最高优先算法函数First_Come_First_Serve(Process_FCFS); 				// 调用先来先服务算法函数Shortest_Job_First(Process_SJF);	 				// 调用短作业优先算法函数Multilevel_Feedback_Queue_Algorithm(Process_MFQ); 	// 调用多级反馈队列调度算法return 0;
}//	3比较函数,用于sort函数的参数
bool SortBy_ArriveTime(PCB a, PCB b) {return a.Arrive_Time < b.Arrive_Time;
}
bool SortBy_Priority(PCB* a, PCB* b) {return a->Priority < b->Priority;
}
bool SortBy_ServeTime(PCB* a, PCB* b) {return a->Serve_Time < b->Serve_Time;
}void PCB_Info_Input(PCB Process_HPF[5], PCB Process_FCFS[5], PCB Process_SJF[5], PCB Process_MFQ[5]) {cout << "\nPlease input the Process Control Block information\n" << endl;for (int i = 0; i < 5; i++) {printf("PCB%d:", i);scanf("%u%u%d", &Process_HPF[i].Arrive_Time, &Process_HPF[i].Serve_Time, &Process_HPF[i].Priority);// 完成输入的深拷贝Process_FCFS[i].Arrive_Time = Process_SJF[i].Arrive_Time = Process_MFQ[i].Arrive_Time = Process_HPF[i].Arrive_Time;Process_FCFS[i].Serve_Time = Process_SJF[i].Serve_Time = Process_MFQ[i].Serve_Time = Process_HPF[i].Serve_Time;Process_FCFS[i].Priority = Process_SJF[i].Priority = Process_MFQ[i].Priority = Process_HPF[i].Priority;Process_HPF[i].name = Process_FCFS[i].name = Process_SJF[i].name = Process_MFQ[i].name = i + 1; 							// 设置进程名称Process_HPF[i].FinishFlag = Process_FCFS[i].FinishFlag = Process_SJF[i].FinishFlag = Process_MFQ[i].FinishFlag = false; 	// 初始化完成标志为false}
}// 优先级最高优先调度算法函数
void Highest_Prioriy_First(PCB Process[5]) {cout << "\n优先级最高优先调度算法:" << endl;PCB* Available_Processes[5]; 	// 定义指向进程控制块的指针数组int FinishCout = 0; 			// 完成进程计数器初始化为0unsigned Time = 0; 				// 时间初始化为0cout << endl;sort(Process, Process + 5, SortBy_ArriveTime);  // 按到达时间对进程数组进行排序while (FinishCout < 5) { 						// 当完成进程数量小于5时循环执行调度算法,因为进程还有进程未得到处理机时间int j = 0; 									// 已到达且未完成进程计数器初始化为0for (int i = 0; i < 5; i++) { 				// 循环遍历所有进程if (Process[i].Arrive_Time <= Time and Process[i].FinishFlag == false) { // 如果进程已到达且未完成Available_Processes[j++] = Process + i; 							 // 将该进程加入到可用进程数组中}}// 如果j为0,表示当前时间没有到达的进程,此时应该让时间继续推进if (j == 0) {Time += 1; 	// 时间加1continue; 	// 继续下一次循环}// 将当前时间已经到达的所有进程按优先级进行排序sort(Available_Processes, Available_Processes + j, SortBy_Priority);// 选取优先级最大的进程执行任务Available_Processes[0]->Start_Time = Time; 	// 设置进程开始时间Available_Processes[0]->Wait_Time = Available_Processes[0]->Arrive_Time; // 设置进程等待时间Time += Available_Processes[0]->Serve_Time; // 更新时间Available_Processes[0]->Finish_Time = Time; // 设置进程完成时间Available_Processes[0]->cycle_time = Available_Processes[0]->Finish_Time - Available_Processes[0]->Arrive_Time; 	// 计算进程周转时间Available_Processes[0]->Weighted_cycle_time = Available_Processes[0]->cycle_time * 1.0 / Available_Processes[0]->Serve_Time;Available_Processes[0]->FinishFlag = true; 	// 设置进程完成标志为truecout << "PCB:" << Available_Processes[0]->name << "\tArriveTime:" << Available_Processes[0]->Arrive_Time<< "\tPriority:" << Available_Processes[0]->Priority<< "\tWaitTime:" << Available_Processes[0]->Wait_Time<< "\tStartTime:" << Available_Processes[0]->Start_Time<< "\tServeTime:" << Available_Processes[0]->Serve_Time<< "\tFinishTime:" << Available_Processes[0]->Finish_Time<< "\tCircleTime:" << Available_Processes[0]->cycle_time<< endl; // 输出进程完成信息FinishCout += 1; 							// 完成进程计数器加1}double avg = 0, weighted_avg = 0;for (int i = 0; i < 5; i++) {      // 遍历进程数组avg += Process[i].cycle_time;     // 计算总周转时间weighted_avg += Process[i].Weighted_cycle_time; // 计算总带权周转时间}avg /= 5; // 计算平均周转时间weighted_avg /= 5; // 计算带权平均周转时间cout << "\n平均周转时间:" << avg << endl;          // 输出平均周转时间cout << "带权平均周转时间:" << weighted_avg << endl; // 输出带权平均周转时间
}// 先来先服务调度算法(FCFS)
void First_Come_First_Serve(PCB  Process[5]) {cout << "\n先来先服务调度算法:" << endl;int FinishCout = 0; 	// 完成进程计数器初始化为0unsigned Time = 0; 		// 时间初始化为0cout << endl;sort(Process, Process + 5, SortBy_ArriveTime); // 按到达时间对进程数组进行排序while (FinishCout < 5) { // 当完成进程数量小于5时循环执行调度算法,因为进程还有进程未得到处理机时间int j = -1; 		 // 已到达且未完成进程计数器初始化为0for (int i = 0; i < 5; i++) { // 循环遍历所有进程if (Process[i].Arrive_Time <= Time and Process[i].FinishFlag == false) {j = i;break;}}// 如果j为-1,表示当前时间没有到达的进程,此时应该让时间继续推进if (j == -1) {Time += 1; 	// 时间加1continue; 	// 继续下一次循环}// 选取当前满足条件且到达时间最早的进程进行执行Process[j].Start_Time = Time; 	// 设置进程开始时间Process[j].Wait_Time = Process[j].Start_Time - Process[j].Arrive_Time; // 设置进程等待时间Time += Process[j].Serve_Time; 	// 更新时间Process[j].Finish_Time = Time; 	// 设置进程完成时间Process[j].cycle_time = Process[j].Finish_Time - Process[j].Arrive_Time; 				// 计算进程周转时间Process[j].Weighted_cycle_time = Process[j].cycle_time * 1.0 / Process[j].Serve_Time;Process[j].FinishFlag = true; 	// 设置进程完成标志为truecout << "PCB:" << Process[j].name << "\tArriveTime:" << Process[j].Arrive_Time<< "\tWaitTime:" << Process[j].Wait_Time<< "\tStartTime:" << Process[j].Start_Time<< "\tServeTime:" << Process[j].Serve_Time<< "\tFinishTime:" << Process[j].Finish_Time<< "\tCircleTime:" << Process[j].cycle_time<< endl; // 输出进程完成信息FinishCout += 1; // 完成进程计数器加1}double avg = 0, weighted_avg = 0;for (int i = 0; i < 5; i++) {      // 遍历进程数组avg += Process[i].cycle_time;     // 计算总周转时间weighted_avg += Process[i].Weighted_cycle_time; // 计算总带权周转时间}avg /= 5; // 计算平均周转时间weighted_avg /= 5; // 计算带权平均周转时间cout << "\n平均周转时间:" << avg << endl;          // 输出平均周转时间cout << "带权平均周转时间:" << weighted_avg << endl; // 输出带权平均周转时间
}// 短作业优先算法 (SJF)
void Shortest_Job_First(PCB Process[5]) {cout << "\n短作业优先算法:" << endl;PCB* Available_Processes[5]; 	// 定义指向进程控制块的指针数组int FinishCout = 0; 			// 完成进程计数器初始化为0unsigned Time = 0; 				// 时间初始化为0cout << endl;sort(Process, Process + 5, SortBy_ArriveTime); // 按到达时间对进程数组进行排序while (FinishCout < 5) { 	// 当完成进程数量小于5时循环执行调度算法,因为进程还有进程未得到处理机时间int j = 0; 				// 已到达且未完成进程计数器初始化为0for (int i = 0; i < 5; i++) { // 循环遍历所有进程if (Process[i].Arrive_Time <= Time and Process[i].FinishFlag == false) { 	// 如果进程已到达且未完成Available_Processes[j++] = Process + i; 								// 将该进程加入到可用进程数组中}}// 如果j为0,表示当前时间没有到达的进程,此时应该让时间继续推进if (j == 0) {Time += 1; 	// 时间加1continue; 	// 继续下一次循环}// 将当前时间已经到达的所有进程按服务时间进行排序sort(Available_Processes, Available_Processes + j, SortBy_ServeTime);// 选取当前满足条件且服务时间最短的进程执行任务Available_Processes[0]->Start_Time = Time; 	// 设置进程开始时间Available_Processes[0]->Wait_Time = Available_Processes[0]->Arrive_Time; // 设置进程等待时间Time += Available_Processes[0]->Serve_Time; // 更新时间Available_Processes[0]->Finish_Time = Time; // 设置进程完成时间Available_Processes[0]->cycle_time = Available_Processes[0]->Finish_Time - Available_Processes[0]->Arrive_Time; 	// 计算进程周转时间Available_Processes[0]->Weighted_cycle_time = Available_Processes[0]->cycle_time * 1.0 / Available_Processes[0]->Serve_Time;Available_Processes[0]->FinishFlag = true; 	// 设置进程完成标志为truecout << "PCB:" << Available_Processes[0]->name << "\tArriveTime:" << Available_Processes[0]->Arrive_Time<< "\tWaitTime:" << Available_Processes[0]->Wait_Time<< "\tStartTime:" << Available_Processes[0]->Start_Time<< "\tServeTime:" << Available_Processes[0]->Serve_Time<< "\tFinishTime:" << Available_Processes[0]->Finish_Time<< "\tCircleTime:" << Available_Processes[0]->cycle_time<< endl; // 输出进程完成信息FinishCout += 1; 							// 完成进程计数器加1}double avg = 0, weighted_avg = 0;for (int i = 0; i < 5; i++) {      // 遍历进程数组avg += Process[i].cycle_time;     // 计算总周转时间weighted_avg += Process[i].Weighted_cycle_time; // 计算总带权周转时间}avg /= 5; // 计算平均周转时间weighted_avg /= 5; // 计算带权平均周转时间cout << "\n平均周转时间:" << avg << endl;          // 输出平均周转时间cout << "带权平均周转时间:" << weighted_avg << endl; // 输出带权平均周转时间}void Multilevel_Feedback_Queue_Algorithm(PCB Process[5]) {cout << "\n多级反馈队列调度算法:" << endl;MFQ MFQSet;Multilevel_Feedback_Queue_Algorithm_Input(&MFQSet); // 调用输入多级反馈队列的函数queue<PCB> L1, L2, L3; // 定义三个队列sort(Process, Process + 5, SortBy_ArriveTime); // 按到达时间对进程数组进行排序unsigned int Time = 0; // 时间初始化为0double avg = 0, weighted_avg = 0; // 初始化平均周转时间和带权平均周转时间for (int i = 0; i < 5; i++) { // 将进程按照到达时间加入到第一级别队列Process[i].Original_Serve_Time = Process[i].Serve_Time;L1.push(Process[i]);}while (!L1.empty() || !L2.empty() || !L3.empty()) { // 当三个队列有不为空的时循环cout << "Time:" << Time << " \t\t"; // 输出当前时间if (!L1.empty()) { // 如果第一级别队列不为空PCB temp = L1.front(); // 获取队首进程L1.pop();              // 弹出队首进程cout << "P" << temp.name << " is processing:"; // 输出当前处理的进程名称Time += min(temp.Serve_Time, MFQSet.Time_Slice[0]); // 时间增加当前进程的服务时间或者时间片长度中较小的那个temp.Serve_Time = max(0, (int)(temp.Serve_Time - MFQSet.Time_Slice[0])); // 更新当前进程的服务时间if (temp.Serve_Time == 0) { // 如果当前进程的服务时间为0temp.Finish_Time = Time; // 设置当前进程的完成时间temp.cycle_time = temp.Finish_Time - temp.Arrive_Time;   // 计算当前进程的周转时间temp.Weighted_cycle_time = (double)temp.cycle_time / temp.Original_Serve_Time; // 计算当前进程的带权周转时间avg += temp.cycle_time;     // 计算总周转时间weighted_avg += temp.Weighted_cycle_time; // 计算总带权周转时间cout << "Finish Time:" << Time << endl; // 输出当前进程的完成时间} else {cout << 'P' << temp.name << "转移到队列2的末尾\n";L2.push(temp); // 否则将当前进程加入到第二级别队列}} else if (!L2.empty()) { // 如果第一级别队列为空但第二级别队列不为空PCB temp = L2.front(); // 获取队首进程L2.pop();              // 弹出队首进程cout << "P" << temp.name << " is processing:"; // 输出当前处理的进程名称Time += min(temp.Serve_Time, MFQSet.Time_Slice[1]); // 时间增加当前进程的服务时间或者时间片长度中较小的那个temp.Serve_Time = max(0, (int)(temp.Serve_Time - MFQSet.Time_Slice[1])); // 更新当前进程的服务时间if (temp.Serve_Time == 0) { // 如果当前进程的服务时间为0temp.Finish_Time = Time; // 设置当前进程的完成时间temp.cycle_time = temp.Finish_Time - temp.Arrive_Time;   // 计算当前进程的周转时间temp.Weighted_cycle_time = (double)temp.cycle_time / temp.Original_Serve_Time; // 计算当前进程的带权周转时间avg += temp.cycle_time;     // 计算总周转时间weighted_avg += temp.Weighted_cycle_time; // 计算总带权周转时间cout << "Finish Time:" << Time << endl; // 输出当前进程的完成时间} else {cout << 'P' << temp.name << "转移到队列3的末尾\n";L3.push(temp); // 否则将当前进程加入到第三级别队列}} else { // 如果第一级别和第二级别队列均为空while (!L3.empty()) {PCB temp = L3.front(); // 获取队首进程L3.pop();              // 弹出队首进程cout << "P" << temp.name << " is processing:"; // 输出当前处理的进程名称Time += min(temp.Serve_Time, MFQSet.Time_Slice[2]); // 时间增加当前进程的服务时间或者时间片长度中较小的那个temp.Serve_Time = max(0, (int)(temp.Serve_Time - MFQSet.Time_Slice[2])); // 更新当前进程的服务时间if (temp.Serve_Time == 0) { // 如果当前进程的服务时间为0temp.Finish_Time = Time; // 设置当前进程的完成时间temp.cycle_time = temp.Finish_Time - temp.Arrive_Time;   // 计算当前进程的周转时间temp.Weighted_cycle_time = (double)temp.cycle_time / temp.Original_Serve_Time; // 计算当前进程的带权周转时间avg += temp.cycle_time;     // 计算总周转时间weighted_avg += temp.Weighted_cycle_time; // 计算总带权周转时间cout << "Finish Time:" << Time << endl; // 输出当前进程的完成时间} else {cout << 'P' << temp.name << "继续执行\n";L3.push(temp); // 将当前进程加入到第三级别队列末尾}}}}avg /= 5; // 计算平均周转时间weighted_avg /= 5; // 计算带权平均周转时间cout << "\n平均周转时间:" << avg << endl;          // 输出平均周转时间cout << "带权平均周转时间:" << weighted_avg << endl; // 输出带权平均周转
}// 输入多级反馈队列的函数
void Multilevel_Feedback_Queue_Algorithm_Input(MFQ *mfq) {cout << "Please input the Time Slice(Three Numbers) for Multilevel Feedback Queue" << endl;cin >> mfq->Time_Slice[0] >> mfq->Time_Slice[1] >> mfq->Time_Slice[2];
}

三、心灵的救赎

  1. “爱”就是科学与逻辑永远无法解释的程序
    在这里插入图片描述

http://www.ppmy.cn/news/1463123.html

相关文章

Redis常见数据类型(4) - hash, List

hash 命令小结 命令执行效果时间复杂度hset key field value设置值O(1)hget key field获取值O(1)hdel key field [field...]删除值O(k), k是field个数hlen key计算field个数O(1)hgetall key获取所有的field-valueO(k), k是field的个数hmget field [field...]批量获取field-va…

基于springboot的大创管理系统

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了大创管理系统的开发全过程。通过分析大创管理系统管理的不足&#xff0c;创建了一个计算机管理大创管理系统的方案。文章介绍了大创管理系统的系统分析部分&…

网络编程-TCP

一、TCP的相关IP 1.1 SeverSocket 这是Socket类,对应到网卡,但是这个类只能给服务器使用. 1.2 Socket 对应到网卡,既可以给服务器使用,又可以给客户端使用. TCP是面向字节流的,传输的基本单位是字节. TCP是有连接的,和打电话一样,需要客户端拨号,服务器来听. 服务器的内核…

国产数据库TiDB简介

TiDB是一款由PingCAP公司自主设计、研发的开源分布式关系型数据库。以下是对TiDB的详细介绍&#xff1a; 一、基本特性 开源与兼容性&#xff1a;TiDB是开源的&#xff0c;并且高度兼容MySQL 5.7协议和MySQL生态&#xff0c;这意味着用户可以无缝地将现有MySQL应用迁移到TiDB…

集中抄表电表是什么?

1.集中抄表电表&#xff1a;简述 集中抄表电表&#xff0c;又称为远程抄表系统&#xff0c;是一种现代化电力计量技术&#xff0c;为提升电力行业的经营效率和客户服务质量。它通过自动化的形式&#xff0c;取代了传统人工抄水表&#xff0c;完成了数据信息实时、精确、高效率…

力扣:92. 反转链表 II(Java)

目录 题目描述&#xff1a;示例 1&#xff1a;示例 2&#xff1a;代码实现&#xff1a; 题目描述&#xff1a; 给你单链表的头指针 head 和两个整数 left 和 right &#xff0c;其中 left < right 。请你反转从位置 left 到位置 right 的链表节点&#xff0c;返回 反转后的…

Java开发大厂面试第17讲:MySQL 的优化方案有哪些?数据库设计、查询优化、索引优化、硬件和配置优化等

性能优化&#xff08;Optimize&#xff09;指的是在保证系统正确性的前提下&#xff0c;能够更快速响应请求的一种手段。而且有些性能问题&#xff0c;比如慢查询等&#xff0c;如果积累到一定的程度或者是遇到急速上升的并发请求之后&#xff0c;会导致严重的后果&#xff0c;…

【机器学习数据可视化-07】波士顿房价预测数据分析

波士顿房价预测&#xff1a;基于数据可视化的深入探索 一、引言   在当今社会&#xff0c;房地产市场作为经济的重要支柱之一&#xff0c;其走势与波动直接影响着国家经济的稳定和人民生活的品质。波士顿&#xff0c;这座历史悠久且充满活力的城市&#xff0c;其房地产市场一…