程序员经验分享-hwhale

操作系统：进程调度模拟，C语言实现

2023-11-14

作业要求 【题目要求】模拟实现进程调度的经典算法，包括FCFS、SJF（SPF）、HRRN和RR(时间片大小分别为1和4)。输出调度过程，并计算不同调度算法的周转时间、平均周转时间、带权周转时间、平均带权周转时间、等待时间、平均等待时间等信息。
【实习要求】 可选编程语言：C/C++/Java/C#/Python；
实现在同一个程序文件中（C/C++）；
请适当注释；
【实现提示】
可以用链式存储结构实现，推荐实现一个队列数组（queue array），该数组的每个元素都代表一个长度可变的队列，队列中的每个元素则代表一个任务job，任务结构定义（可修改）如下：
typedef struct Job {
int job_pid; //任务号
int arrive_time； //到达时间
int burst; //运行时间
int end_time; //完成时间
int cycle_time; //周转时间
int waited_time; //等待时间
int w_cycle_time; //带权等待时间
struct Job *next;
} Job;
【测试数据】
输入：任务号 到达时间 运行时间
输出：任务号 响应时间 完成时间 周转时间 …
××××算法平均周转时间、平均等待时间、平均带权周转时间…

首先输入例题并测试结果，例题如下：

除例题外，报告上要求写出多批自拟数据测试结果。

代码如下：（运行环境：VS2019）

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>



#define TRUE 1
#define FALSE 0
#define LEN 5
typedef struct job
{
	int PID;//ID
	int arriveTime;//到达时间
	int requireTime;//要求服务时间
	int usedTime;//已使用时间
	int endedTime;//结束时间
	int waitedTime;//等待时间
	int cycleTime;//周转时间
	float weightCycleTime;//带权周转时间
	struct job *next;
	
}Job;

typedef struct linkedqueue
{
	Job* front;
	Job* rear;
	int count;
}LinkedQueue;

Job jobArray[LEN];
//后备队列
LinkedQueue* createdQueue;
//就绪队列
LinkedQueue* readyQueue;
//完成队列
LinkedQueue* endedQueue;

void printMenu();//打印菜单
void initJobs(Job*);//初始化作业
void initQueue();//初始化队列
void fcfsJobs();//先来先服务算法
void enQueueNode(LinkedQueue*, Job*);//入队操作，尾插法
Job* deQueue(LinkedQueue*);//出队头操作
int is_empty(LinkedQueue*);//判空函数
void recordJobTime(Job*);//记录各个时间
void printAvgValue();//打印出平均数值
Job* peekQueue(LinkedQueue*);//返回队列头
void sjfJobs();//最短作业优先发
void rrJobs(int);//时间片轮转法
void hrrnJobs();//高相应比算法
Job* findShortestJob(LinkedQueue*);//找到最短作业
Job* findHighestestJob(LinkedQueue*);//找到最高相应比作业
void CacluateWaitedTime(LinkedQueue*);//计算当前作业等待时间


int main()
{
	char userOpt;
	while (1)
	{
		//初始化作业；
		initJobs(jobArray);
		//初始化队列；
		initQueue();
		//打印菜单
		printMenu();
		scanf_s("%c", &userOpt, sizeof(userOpt));
		getchar();
		switch (userOpt)
		{
		case '1':
			fcfsJobs();
			break;
		case '2':
			sjfJobs();
			break;
		case '3':
			rrJobs(1);
			break;
		case '4':
			rrJobs(4);
			break;
		case '5':
			hrrnJobs();
			break;
		case 'q':
			exit(0);
			break;

		}
	}
	return 66;
	
}

void printMenu()
{
	printf("按1FCFS\n");
	printf("按2SJF\n");
	printf("按3时间片轮转 q=1\n");
	printf("按4时间片轮转 q=4\n");
	printf("按5HRRN\n");
	printf("按q退出\n");
	printf("你的选择：\n");
	printf("\n==================\n");

}
void initJobs(Job* jobArray)
{
	jobArray[0].PID = 0;
	jobArray[0].requireTime = 3;
	jobArray[0].arriveTime = 0;
	jobArray[0].endedTime = -1;
	jobArray[0].usedTime = 0;

	jobArray[1].PID = 1;
	jobArray[1].requireTime = 6;
	jobArray[1].arriveTime = 2;
	jobArray[1].endedTime = -1;
	jobArray[1].usedTime = 0;

	jobArray[2].PID = 2;
	jobArray[2].requireTime = 4;
	jobArray[2].arriveTime = 4;
	jobArray[2].endedTime = -1;
	jobArray[2].usedTime = 0;

	jobArray[3].PID = 3;
	jobArray[3].requireTime = 5;
	jobArray[3].arriveTime = 6;
	jobArray[3].endedTime = -1;
	jobArray[3].usedTime = 0;

	jobArray[4].PID = 4;
	jobArray[4].requireTime = 2;
	jobArray[4].arriveTime = 8;
	jobArray[4].endedTime = -1;
	jobArray[4].usedTime = 0;

}

void initQueue()
{
	free(createdQueue);
	free(readyQueue);
	free(endedQueue);
	createdQueue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
	endedQueue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
	readyQueue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
	
	if (createdQueue != NULL && endedQueue != NULL && readyQueue != NULL)
	{//判空,是否创建成功
		createdQueue->front = createdQueue->rear = NULL;
		readyQueue->front = readyQueue->rear = NULL;
		endedQueue->front = endedQueue->rear = NULL;
		printf("\n");
	}
	int i;
	for (i = 0;i < LEN;i++)
	{
		enQueueNode(createdQueue, &jobArray[i]);
	}

}

void fcfsJobs()
{
	int currentTime = 0;
	Job* runningJob = NULL;
	while (!is_empty(createdQueue) || !is_empty(readyQueue) || runningJob != NULL)
	{
		while (!is_empty(createdQueue))
		{//进入就绪队列操作
			//返回队头作业
			Job* frontJob = peekQueue(createdQueue);
			if (frontJob->arriveTime == currentTime)
			{
				//后备出第一个挂入就绪队列
				enQueueNode(readyQueue, deQueue(createdQueue));

			}
			else {
				break;
			}
		}

		if (runningJob == NULL)
		{
			if (!is_empty(readyQueue))
			{
				runningJob = deQueue(readyQueue);
			}
			else
			{
				printf("系统%d时刻就绪队列为空\n", currentTime);
				currentTime++;
				continue;
			}
		}
		else
		{
			if (runningJob->usedTime == runningJob->requireTime)
			{
				runningJob->endedTime = currentTime;
				enQueueNode(endedQueue, runningJob);
				recordJobTime(runningJob);
				printf("作业%d已完成，完成时间：%d 等待时间%d\n", runningJob->PID, runningJob->endedTime,runningJob->waitedTime);

				if (!is_empty(readyQueue)) {
					runningJob = deQueue(readyQueue);
				}

				else {
					runningJob = NULL;
				}
			}
			else
			{

			}

		}
		currentTime++;
		
		//CacluateWaitedTime(readyQueue);
		if (runningJob != NULL)
		{
			runningJob->usedTime++;
		}
	}

	printf("FCFS的调度信息：\n");
	printAvgValue();
}

void enQueueNode(LinkedQueue* queue, Job* job)
{//插入队尾
	if (is_empty(queue))
	{//队列为空时进队
		queue->front = queue->rear = job;
		job->next = NULL;
	}
	else
	{//非空时
		queue->rear->next = job;
		queue->rear = job;
		queue->rear->next = NULL;
	}
}

Job* deQueue(LinkedQueue* queue)
{//出队函数 出队头
	//临时变量存储队头的地址
	Job* returnJob;
	if (is_empty(queue))
	{//若队列为空
		printf("队列为空，无法出列\n");
		return NULL;
	}
	//不为空时
	returnJob = queue->front;
	if (queue->front == queue->rear)
	{//若只有一个节点
		queue->front = queue->rear = NULL;
	}
	else
	{//多于一个节点
		queue->front = queue->front->next;
	}
	returnJob->next = NULL;
	return returnJob;
}

int is_empty(LinkedQueue* queue)
{//判空，1为空，0为非空
	if (queue->front == NULL&& queue->rear==NULL)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}

void recordJobTime(Job* runningJob)
{//计算当前作业的周转时间，等待时间，带权周转时间
	runningJob->cycleTime = runningJob->endedTime - runningJob->arriveTime;
	runningJob->waitedTime = runningJob->cycleTime - runningJob->requireTime;
	runningJob->weightCycleTime = (float)runningJob->cycleTime 
		                                    /
		                         (float)runningJob->requireTime;
}

void printAvgValue()
{//打印每个作业的平均值
	float avgCycleTime = 0;
	float avgWaitedTime = 0;
	float avgWeightCycleTime = 0;
	int i;
	for (i = 0;i < LEN;i++)
	{
		avgCycleTime += (float)jobArray[i].cycleTime;
		avgWaitedTime += (float)jobArray[i].waitedTime;
		avgWeightCycleTime += jobArray[i].weightCycleTime;
	}
	avgCycleTime = avgCycleTime / (float)LEN;
	avgWaitedTime = avgWaitedTime / (float)LEN;
	avgWeightCycleTime = avgWeightCycleTime / (float)LEN;

	printf("平均周转时间%05.2f  平均等待时间：%05.2f 平均带权周转时间：%05.2f\n"
		, avgCycleTime, avgWaitedTime, avgWeightCycleTime);
}

Job* peekQueue(LinkedQueue* queue)
{
	return queue->front;
}

void sjfJobs()
{
	int currentTime = 0;
	Job* runningJob = NULL;
	while (!is_empty(createdQueue) || !is_empty(readyQueue) || runningJob != NULL)
	{
		while (!is_empty(createdQueue))
		{
			Job* frontJob = peekQueue(createdQueue);
			if (frontJob->arriveTime == currentTime)
			{
				enQueueNode(readyQueue, deQueue(createdQueue));
			}
			else
			{
				break;
			}
		}

		if (runningJob == NULL)
		{
			if (!is_empty(readyQueue))
			{
				runningJob = findShortestJob(readyQueue);
			}
			else
			{
				printf("系统%d时刻就绪队列为空\n", currentTime);
				currentTime++;
				continue;
			}
		}
		else
		{
			if (runningJob->usedTime == runningJob->requireTime)
			{
				runningJob->endedTime = currentTime;
				enQueueNode(endedQueue, runningJob);
				recordJobTime(runningJob);
				printf("作业%d已完成，完成时刻%d 等待时间%d\n", runningJob->PID, runningJob->endedTime,runningJob->waitedTime);

				if (!is_empty(readyQueue))
				{
					runningJob = findShortestJob(readyQueue);
					
				}
				else
				{
					runningJob = NULL;
					
				}
			}
			else
			{
				//若当前作业还未完成，则什么都不做，在下面走一步
				
			}
		}
		currentTime++;
		
		
		if (runningJob != NULL)
		{
			runningJob->usedTime++;
		}
	}

	printf("sjfsJob调度信息：\n");
	printAvgValue();
}

Job* findShortestJob(LinkedQueue *readyQueue)
{
	Job* returnJob=NULL,*head;
	head = readyQueue->front;
	if (readyQueue->front != NULL)
	{//就绪对列不为空
		if (head->next == NULL)
		{//若就绪队列只有一个
			returnJob = head;
			returnJob->next = NULL;
			readyQueue->front = readyQueue->rear=NULL;
			return returnJob;
		}
		else
		{//若队列中不止一个
			returnJob = head;
			while (head->next!= NULL)
			{//循环整个就绪队列,记下最短Job
				
				if (returnJob->requireTime > head->next->requireTime)
				{
					returnJob = head->next;
					head = head->next;
					
				}
				else
				{
					head = head->next;
				}
			}
			//循环之后head返回就绪队列队头
			head = readyQueue->front;
			if (head == returnJob)
			{//若返回的JOB是在队头
				head = head->next;
				//不要忘记变更就绪队列的队头！！！
				readyQueue->front = head;
				returnJob->next = NULL;
				return returnJob;
			}
			else
			{//返回的JOB不在队头
				while (head->next != returnJob)
				{
					head = head->next;
				}
				head->next = returnJob->next;
				returnJob->next = NULL;
				return returnJob;
			}
		}
	}
	else
	{
		return returnJob = NULL;
	}
	
}

void rrJobs(int timeSlice)
{//时间片轮转
	int currentTime = 0,timeControl=0;
	Job* runningJob = NULL;
	while (!is_empty(createdQueue) || !is_empty(readyQueue) || runningJob != NULL)
	{
		while (!is_empty(createdQueue))
		{
			
			Job* frontJob = peekQueue(createdQueue);
			if (frontJob->arriveTime == currentTime)
			{
				//后备出第一个挂入就绪队列
				enQueueNode(readyQueue, deQueue(createdQueue));

			}
			else {
				break;
			}
		}
		if (runningJob == NULL)
		{
			if (!is_empty(readyQueue))
			{
				runningJob = deQueue(readyQueue);
			}
			else
			{
				printf("系统%d时刻就绪队列为空\n", currentTime);
				currentTime++;
				continue;
			}
		}
		else
		{
			if (runningJob->usedTime == runningJob->requireTime)
			{
				runningJob->endedTime = currentTime;
				enQueueNode(endedQueue, runningJob);
				recordJobTime(runningJob);
				printf("作业%d已完成，完成时间：%d 等待时间%d\n", runningJob->PID, runningJob->endedTime,runningJob->waitedTime);

				if (!is_empty(readyQueue)) {
					runningJob = deQueue(readyQueue);
				}

				else {
					runningJob = NULL;
				}
			}
			
			else
			{

			}
		}
		currentTime++;
		
		
		if (runningJob != NULL)
		{
			
			runningJob->usedTime++;
			timeControl++;
			CacluateWaitedTime(readyQueue);
			if (timeControl == timeSlice)
			{//时间片到
				timeControl=0;

				while (!is_empty(createdQueue))
				{//先让后备队列进入就绪队列一个
					//返回队头作业
					Job* frontJob = peekQueue(createdQueue);
					if (frontJob->arriveTime == currentTime)
					{
						//后备出第一个挂入就绪队列
						enQueueNode(readyQueue, deQueue(createdQueue));

					}
					else {
						break;
					}
				}

				if (runningJob->usedTime != runningJob->requireTime)
				{//若当前作业还未完成
					printf("作业%d在%d时刻阻塞，剩余服务时间%d，等待时间%d\n", runningJob->PID
						, currentTime, runningJob->requireTime - runningJob->usedTime,runningJob->waitedTime);
					enQueueNode(readyQueue, runningJob);
					runningJob = NULL;
				}
				else {

				}
			}
		}
	}
	printf("rrJobs %d时间片 的调度信息：\n",timeSlice);
	printAvgValue();
}

void hrrnJobs()
{
	int currentTime = 0;
	Job* runningJob = NULL;
	
	
	while (!is_empty(createdQueue) || !is_empty(readyQueue) || runningJob != NULL)
	{
		while (!is_empty(createdQueue))
		{
			Job* frontJob = peekQueue(createdQueue);
			if (frontJob->arriveTime == currentTime)
			{
				enQueueNode(readyQueue, deQueue(createdQueue));
			}
			else
			{
				break;
			}
		}
		if (runningJob == NULL)
		{
			if (!is_empty(readyQueue))
			{
				runningJob = findHighestestJob(readyQueue);
			}
			else
			{
				printf("系统%d时刻就绪队列为空\n", currentTime);
				currentTime++;
				continue;
			}
		}
		else
		{
			if (runningJob->usedTime == runningJob->requireTime)
			{
				runningJob->endedTime = currentTime;
				enQueueNode(endedQueue, runningJob);
				recordJobTime(runningJob);
				printf("作业%d已完成， 完成时刻%d 等待时间%d\n", runningJob->PID, runningJob->endedTime
				                                               ,runningJob->waitedTime);

				if (!is_empty(readyQueue))
				{
					runningJob = findHighestestJob(readyQueue);

				}
				else
				{
					runningJob = NULL;

				}
			}
			else
			{
				//若当前作业还未完成，则什么都不做，在下面走一步

			}
		}
		currentTime++;
		
		if (runningJob != NULL)
		{
			CacluateWaitedTime(readyQueue);
			runningJob->usedTime++;
		}
	}
	printf("HRRNJobS调度信息：\n");
	printAvgValue();
}

Job* findHighestestJob(LinkedQueue* readyQueue)
{
	Job* returnJob = NULL, * head;
	head = readyQueue->front;
	if (readyQueue->front != NULL)
	{//就绪对列不为空
		if (head->next == NULL)
		{//若就绪队列只有一个
			returnJob = head;
			returnJob->next = NULL;
			readyQueue->front = readyQueue->rear = NULL;
			return returnJob;
		}
		else
		{//若队列中不止一个
			returnJob = head;
			while (head->next != NULL)
			{//循环整个就绪队列,记下最高相应比
				//计算相应比并且比较大小
				if ((float)(returnJob->waitedTime/returnJob->requireTime) <(float)(head->next->waitedTime/ head->next->requireTime))
				{
					returnJob = head->next;
					head = head->next;

				}
				else
				{
					head = head->next;
				}
			}
			head = readyQueue->front;

			if (head == returnJob)
			{//若返回的JOB是在队头
				head = head->next;
				//不要忘记变更就绪队列的队头！！！
				readyQueue->front = head;
				returnJob->next = NULL;
				return returnJob;


			}
			else
			{//返回的JOB不在队头
				while (head->next != returnJob)
				{
					head = head->next;
				}
				head->next = returnJob->next;
				returnJob->next = NULL;
				return returnJob;
			}
		}
	}
	else
	{
		return returnJob = NULL;
	}
}

void CacluateWaitedTime(LinkedQueue* queue)
{
	//iJob是用来循环就绪队列使等待时间++的控制变量赋予就绪队列的队头
	Job* iJob = queue->front;

	if (iJob != NULL)
	{//若就绪队列不为空
		while (iJob != NULL)
		{//循环队列增加作业的等待时间
			iJob->waitedTime++;

			iJob = iJob->next;
		}
		iJob = peekQueue(queue);
	}
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

作业

操作系统

算法

c语言

编程语言

操作系统：进程调度模拟，C语言实现 的相关文章

随机推荐

  • 杨桃的Python进阶讲座17——数组array（七）三维数组和n维数组的索引和取值（配详细图解）

    本人CSDN博客专栏 https blog csdn net yty 7 Github地址 https github com yot777 三维数组的索引和取值 创建一个numpy三维数组z 如下所示 gt gt gt import num

  • Nginx官方文档(三十四)【ngx_http_ssl_module】

    ngx http ssi module 示例配置 指令 ssl ssl buffer size ssl certificate ssl certificate key ssl ciphers ssl client certificate s

  • 电脑报错vcomp100.dll丢失怎样修复？这三个方法可以解决

    vcomp100 dll是微软Visual C 2005 Redistributable Package的一部分 它包含了运行某些程序所需的C 运行时库 当电脑中的vcomp100 dll文件丢失或损坏时 可能会导致一些程序无法正常运行 甚

  • [springboot 项目启动类Application.java运行没有任何反应]

    1 问题 最近从网上找了一个springboot项目学习 发现项目启动类无法运行 运行没有任何反应 maven依赖检查没有任何问题 2 解决方案 Files Setting Plugins Groovy勾选 再次运行 成功 3

  • Python: 装饰器和语法糖

    一 Python 装饰器 Python 装饰器本身就是一个函数 它的作用是装饰一个其他的函数 但是不改变原有的程序功能 还要增添新的功能 调用函数时的接口没有变化 比如 装修一个房子 如果不隔音 我在墙上加一层隔音板 却不能把墙拆了 换成隔

  • C# 关于浏览器——WebBrowser篇

    最近要写一个浏览器包裹一个网站 试了各种浏览器插件 记录一下 第一个就是微软的WebBrowser 这个很容易 直接拖过来 然后写一下注册表调用IE11的内核显示 这个代码是抄的

  • python金融数据分析马伟明_Python金融数据分析

    前言 第1章Python在金融中的应用 1 1Python适合我吗 1 1 1免费 开源 1 1 2高级 强大 灵活的编程语言 1 1 3丰富的标准库 1 2面向对象编程与函数式编程 1 2 1面向对象式方法 1 2 2函数式方法 1 2

  • docker day04

    Dockerfile FORM 1 指定基础镜像 可以起别名 也可以指定多个FROM指令 用于多阶段构建 2 加载触发器 加载ONBUILD指令 3 不指定基础镜像 声明当前镜像不依赖任何镜像 官方保留字 scratch RUN 1 在容器

  • 循序渐进，学会用pyecharts绘制瀑布图

    循序渐进 学会用pyecharts绘制瀑布图 瀑布图简介 瀑布图 Waterfall Plot 是由麦肯锡顾问公司所独创的图表类型 因为形似瀑布流水而称之为瀑布图 瀑布图采用绝对值与相对值结合的方式 适用于表达多个特定数值之间的数量变化关系

  • 串口调试助手与CH340驱动分享

    串口调试助手与CH340驱动分享 分享以下资源给大家 包括CH340与CH341驱动 野火以及正点原子的串口调试助手 网盘链接 链接 https pan baidu com s 1cARKBdzJhDcrQrBSfs2Nlw 提取码 fxv

  • python: PyCharm 2023.1打包项目成执行程序

    IDE 最底部 pyinstaller i heart ico D main py 生成成功

  • d指针在Qt上的应用及实现

    Qt为了使其动态库最大程度上实现二进制兼容 引入了d指针的概念 那么为什么d指针能实现二进制兼容呢 为了回答这个问题 首先弄清楚什么是二进制兼容 所谓二进制兼容动态库 指的是一个在老版本库下运行的程序 在不经过编译的情况下 仍然能够在新的版

  • Unity TimeLine循环播放某个时间段

    1 设置Playable Director的Update Method为GameTime模式 2 API using UnityEngine Playables 我们需要用到PlayableDirector的time属性 3 设置开始和结束

  • USB CDC 4G Module 调试问题总结

    USB CDC 4G Module ESP32S2 自定义开发板 SIM7600C1 其他按照github USB CDC 4G Module 使用说明 确保硬件正确SIM卡正常 编译注意做好在4 4版本下 配置过程注意运营商APN 编译没

  • python的编译器与解释器

    作者介绍 作者 小刘在C站 每天分享课堂笔记 一起努力 共赴美好人生 夕阳下 是最美的绽放 目录 一 为什么会有编译器和解释器 二 编译器和解释器的区别 三 python解释器种类 四 python的运行机制 一 为什么会有编译器和解释器

  • Java集合——Set详解

    前几天简单介绍了一下单列集合中的List 今天就给大家讲一下它的同胞兄弟Set的简介与使用情况 Set存取无序 元素唯一 代码演示 public static void demo1 HashSet

  • 各种排序算法详解集合（时间复杂度、空间复杂度、稳定性分析）

    动图来源 https blog csdn net weixin 41190227 article details 86600821 目录 一 冒泡排序 二 选择排序 三 插入排序 四 希尔排序 五 归并排序 六 快速排序 七 堆排序 八 计

  • Supermarket 【POJ - 1456】【并查集+哈希表思想+贪心】

    题目链接 原来 并查集还有这样的作用 题记 我想用个哈希表的思维来解这道题 但是 显然O N 2 的哈希表去查询并插入显然是不行的 那么既然挂在图论专题 我就得用相应的方式解答咯 要是不挂在图论专题 我可能会自闭了 我们对于每个物品按照价值

  • vue3实现前端导出Excel

    1 安装依赖 npm install xlsx 2 使用

  • 操作系统：进程调度模拟，C语言实现

    作业要求 题目要求 模拟实现进程调度的经典算法 包括FCFS SJF SPF HRRN和RR 时间片大小分别为1和4 输出调度过程 并计算不同调度算法的周转时间 平均周转时间 带权周转时间 平均带权周转时间 等待时间 平均等待时间等信息 实

热门标签