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

操作系统课程实验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. “爱”就是科学与逻辑永远无法解释的程序