欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

操作系统实验六–作业调度算法模拟

程序员文章站 2022-07-05 11:03:00
...

文章目录

基本调度算法

1. 先来先服务（First-Come First-Served，FCFS）调度算法

先来先服务调度算法遵循按照进入后备队列的顺序进行调度的原则。该算法是一种非抢占式的算法，是到目前为止最简单的调度算法，其编码实现非常容易。该算法仅考虑了作业到达的先后顺序，而没有考虑作业的执行时间长短、作业的运行特性和作业对资源的要求。

2. 短作业优先（Shortest-Job-First，SJF）调度算法

短作业优先调度算法根据作业控制块中指出的执行时间，选取执行时间最短的作业优先调度。本实验中规定，该算法是非抢占式的，即不允许立即抢占正在执行中的长进程，而是等当前作业执行完毕再进行调度。

3. 响应比高者优先（HRRF）调度算法

FCFS调度算法只片面地考虑了作业的进入时间，短作业优先调度算法考虑了作业的运行时间而忽略了作业的等待时间。响应比高者优先调度算法为这两种算法的折中。响应比为作业的响应时间与作业需要执行的时间之比。作业的响应时间为作业进入系统后的等待时间与作业要求处理器处理的时间之和。

4. 优先权高者优先（Highest-Priority-First，HPF）调度算法

优先权高者优先调度算法与响应比高者优先调度算法十分相似，根据作业的优先权进行作业调度，每次总是选取优先权高的作业优先调度。作业的优先权通常用一个整数表示，也叫优先数。优先数的大小与优先权的关系由系统或者用户规定。优先权高者优先调度算法综合考虑了作业执行时间和等待时间的长短、作业的缓急度，作业对外部设备的使用情况等因素，根据系统设计目标和运行环境而给定各个作业的优先权，决定作业调度的先后顺序。
本实验所选用的调度算法均默认为非抢占式调度。

实验所用的测试数据如下所示。

作业id 到达时间 执行时间 优先权
1 800 50 0
2 815 30 1
3 830 25 2
4 835 20 2
5 845 15 2
6 700 10 1
7 820 5 0

文件内容如图：
操作系统实验六–作业调度算法模拟

作业的数据结构

typedef struct node
{
	int number; // 作业号
	int reach_time;// 作业抵达时间
	int need_time;// 作业的执行时间
	int privilege;// 作业优先权
	float excellent;// 响应比
	int start_time;// 作业开始时间
	int wait_time;// 等待时间
	int visited;// 作业是否被访问过
	bool isreached;// 作业是否已经抵达
}job;

重要函数说明

void initial_jobs()  // 初始化所有作业信息
void reset_jinfo()  // 重置所有作业信息
int findminjob(job jobs[],int count)  // 找到执行时间最短的作业。输入参数：所有的作业信息及待查找的作业总数，输出为执行时间最短的作业id
int findrearlyjob(job jobs[],int count)  // 找到达到最早的作业 输入参数：所有的作业信息及待查找的作业总数，输出参数为最早达到的作业id
void readJobdata()  // 读取作业的基本信息
void FCFS()  // 先来先服务算法
void SJFschdulejob(job jobs[],int count)  // 短作业优先算法 输入参数：所有的作业信息及待查找的作业总数

实验代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
//最大作业数量
#define MAXJOB 50
//作业的数据结构
typedef struct node
{
	int number;//作业号        
	int reach_time;//作业抵达时间
	int need_time;//作业的执行时间
	int privilege;//作业优先权
	float excellent;//响应比
	int start_time;//作业开始时间
	int wait_time;//等待时间
	int visited;//作业是否被访问过
	bool isreached;//作业是否抵达
}job;
job jobs[MAXJOB];//作业序列
int quantity;//作业数量
//初始化作业序列
void initial_jobs()
{
	int i;
	for(i=0;i<MAXJOB;i++)
	{
		jobs[i].number=0;
		jobs[i].reach_time=0;
		jobs[i].privilege=0;
		jobs[i].excellent=0;
		jobs[i].start_time=0;
		jobs[i].wait_time=0;
		jobs[i].visited=0;
		jobs[i].isreached=false;
	}
	quantity=0;
}
//重置全部作业信息
void reset_jinfo() 
{ 
	int i; 
	for(i=0;i<MAXJOB;i++)
	{ 
		jobs[i].start_time=0; 
		jobs[i].wait_time=0; 
		jobs[i].visited=0; 
		jobs[i].isreached = false;
	}
}
//查找当前current_time已到达未执行的最短作业,若无返回-1
int findminjob(job jobs[],int count)
{
	int minjob=-1;//=jobs[0].need_time;
	int minloc=-1;
	for(int i=0;i<count;i++)
	{
		if(minloc==-1){
			if(	 jobs[i].isreached==true && jobs[i].visited==0){
			minjob=jobs[i].need_time;
			minloc=i;
			}
		}
		else if(minjob>jobs[i].need_time&&jobs[i].visited==0&&jobs[i].isreached==true)
		{
			minjob=jobs[i].need_time;
			minloc=i;
		}
	}
	return minloc;
}
//查找最早到达作业，若全部到达返回-1.
int findrearlyjob(job jobs[],int count)
{
	int rearlyloc=-1;
	int rearlyjob=-1;
	for(int i=0;i<count;i++)
	{
		if(rearlyloc==-1){
			if(jobs[i].visited==0){
			rearlyloc=i;
			rearlyjob=jobs[i].reach_time;
			}
		}
		else if(rearlyjob>jobs[i].reach_time&&jobs[i].visited==0)
		{
			rearlyjob=jobs[i].reach_time;
			rearlyloc=i;
		}
	}
	return rearlyloc;
}
//读取作业数据
void readJobdata()
{
	FILE *fp;
	char fname[20];
	int i;
    //输入测试文件文件名
	printf("please input job data file name\n");
	scanf("%s",fname);
	if((fp=fopen(fname,"r"))==NULL)
	{
		printf("error, open file failed, please check filename:\n");
	}
	else
	{
		//依次读取作业信息
		while(!feof(fp))
		{
	if(fscanf(fp,"%d %d %d %d",&jobs[quantity].number,&jobs[quantity].reach_time,&jobs[quantity].need_time,&jobs[quantity].privilege)==4)
			quantity++;
		}
		//打印作业信息
		printf("output the origin job data\n");
		printf("---------------------------------------------------------------------\n");
		printf("\tjobID\treachtime\tneedtime\tprivilege\n");
		for(i=0;i<quantity;i++)
		{
	printf("\t%-8d\t%-8d\t%-8d\t%-8d\n",jobs[i].number,jobs[i].reach_time,jobs[i].need_time,jobs[i].privilege);
		}
	}
}
//FCFS
void FCFS() 
{ 
	int i; 
	int current_time=0;
	int loc;
	int total_waitime=0;
	int total_roundtime=0;
	//获取最近到达的作业
	loc=findrearlyjob(jobs,quantity);
	//输出作业流
	printf("\n\nFCFS算法作业流\n");
	printf("------------------------------------------------------------------------\n"); 
	printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
	current_time=jobs[loc].reach_time; 
	//每次循环找出最先到达的作业并打印相关信息
	for(i=0;i<quantity;i++)
	{ 
		if(jobs[loc].reach_time>current_time)
		{
			jobs[loc].start_time=jobs[loc].reach_time;
			current_time=jobs[loc].reach_time;
		}
		else
		{
			jobs[loc].start_time=current_time;
		}
		jobs[loc].wait_time=current_time-jobs[loc].reach_time; 
	printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n",loc+1,jobs[loc].reach_time,jobs[loc].start_time,jobs[loc].wait_time,
			jobs[loc].wait_time+jobs[loc].need_time);
		jobs[loc].visited=1;
		current_time+=jobs[loc].need_time;
		total_waitime+=jobs[loc].wait_time;
		total_roundtime=total_roundtime+jobs[loc].wait_time+jobs[loc].need_time;
		//获取剩余作业中最近到达作业
		loc=findrearlyjob(jobs,quantity);
	} 
	printf("总等待时间:%-8d 总周转时间:%-8d\n",total_waitime,total_roundtime); 
	printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n",(float)total_waitime/(quantity),(float)total_roundtime/(quantity)); 
}
//短作业优先作业调度
void SJFschdulejob(job jobs[],int count)
{
	int i; 
	int current_time=0;
	int loc;
	int total_waitime=0;
	int total_roundtime=0;
	//获取最近到达的作业
	loc=findrearlyjob(jobs,quantity);
	//输出作业流
	printf("\n\nSJFschdulejob算法作业流\n");
	printf("------------------------------------------------------------------------\n"); 
	printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
	current_time = jobs[loc].reach_time;
	jobs[loc].isreached = true;
	for (i = 0; i < quantity; i++)
	{

		loc = findminjob(jobs, quantity);
		jobs[loc].start_time = current_time;
		jobs[loc].wait_time = jobs[loc].start_time - jobs[loc].reach_time;
		current_time += jobs[loc].need_time;
		printf("\t%-8d\t%-8d\%-8d\t%-8d\t%-8d\n",loc+1,jobs[loc].reach_time,jobs[loc].start_time,jobs[loc].wait_time,
			jobs[loc].wait_time+jobs[loc].need_time);
		jobs[loc].visited = 1;
		total_waitime += jobs[loc].wait_time;
		total_roundtime=total_roundtime+jobs[loc].wait_time+jobs[loc].need_time;

		// 标记已到达的作业
		for (int j = 0; j < quantity; j++)
		{
			if (jobs[j].reach_time <= current_time)
			{
				jobs[j].isreached = true;
			}
		}
		// 寻找离当前时间最近的未到达的作业
		int minloc = -1;
		int minjob = 9999999;
		for (int j = 0; j < quantity; j++)
		{
			if (jobs[j].isreached == false)
			{
				if (minjob > jobs[j].reach_time)
				{
					minjob = jobs[j].reach_time;
					minloc = j;
				}
			}
		}
		if (jobs[minloc].reach_time >= current_time)
		{
			current_time = jobs[minloc].reach_time;
			jobs[minloc].isreached = true;
		}


	}
	printf("总等待时间:%-8d 总周转时间:%-8d\n",total_waitime,total_roundtime); 
	printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n",(float)total_waitime/(quantity),(float)total_roundtime/(quantity)); 
}
//高响应比调度算法
void HRRFschdulejob(job jobs[],int count) 
{
	int i; 
	int current_time=0;
	int loc;
	int total_waitime=0;
	int total_roundtime=0;
	//获取最近到达的作业
	loc=findrearlyjob(jobs,quantity);
	//输出作业流
	printf("\n\nHRRF算法作业流\n");
	printf("------------------------------------------------------------------------\n"); 
	printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
	current_time = jobs[loc].reach_time;
	jobs[loc].isreached = true;
	jobs[loc].wait_time = 0;
	jobs[loc].excellent = (jobs[loc].wait_time + jobs[loc].need_time) / jobs[loc].need_time;
	for (int i = 0; i < quantity; i++)
	{
		// 查找最高响应比
		float maxexcellent = 0;
		int jobnum = -1;
		for (int j = 0; j < quantity; j++)
		{
			if (jobs[j].isreached == true && jobs[j].visited == 0)
			{
				jobs[j].wait_time = current_time - jobs[j].reach_time;
				jobs[j].excellent = (float)((jobs[j].wait_time + jobs[j].need_time)) / jobs[j].need_time;
				if (maxexcellent < jobs[j].excellent)
				{
					maxexcellent = jobs[j].excellent;
					jobnum = j;
				}
			}
		}
		jobs[jobnum].start_time = current_time;
		jobs[jobnum].wait_time = jobs[jobnum].start_time - jobs[jobnum].reach_time;
		current_time += jobs[jobnum].need_time;
		printf("\t%-8d\t%-8d\%-8d\t%-8d\t%-8d\n",jobnum+1,jobs[jobnum].reach_time,jobs[jobnum].start_time,
				jobs[jobnum].wait_time,jobs[jobnum].wait_time+jobs[jobnum].need_time);
		jobs[jobnum].visited = 1;
		total_roundtime += jobs[jobnum].wait_time + jobs[jobnum].need_time;
		total_waitime += jobs[jobnum].wait_time;
		// jobs[jobnum].isreached = true;


		for (int j = 0; j < quantity; j++)
		{
			if (jobs[j].reach_time <= current_time)
			{
				jobs[j].isreached = true;
			}
		}
		int minloc = -1;
		int minjob = 9999999;
		for (int j = 0; j < quantity; j++)
		{
			if (jobs[j].isreached == false)
			{
				if (minjob > jobs[j].reach_time)
				{
					minjob = jobs[j].reach_time;
					minloc = j;
				}
			}
		}
		if (jobs[minloc].reach_time >= current_time)
		{
			current_time = jobs[minloc].reach_time;
			jobs[minloc].isreached = true;
		}

	}
	printf("总等待时间:%-8d 总周转时间:%-8d\n",total_waitime,total_roundtime); 
	printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n",(float)total_waitime/(quantity),(float)total_roundtime/(quantity)); 
}
//优先权高者优先调度算法
void HPF(job jobs[], int quantity)
{
	int i; 
	int current_time=0;
	int loc;
	int total_waitime=0;
	int total_roundtime=0;
	//获取最近到达的作业
	loc=findrearlyjob(jobs,quantity);
	//输出作业流
	printf("\n\nHPF算法作业流\n");
	printf("------------------------------------------------------------------------\n"); 
	printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
	current_time = jobs[loc].reach_time;
	jobs[loc].isreached = true;
	for (int i = 0; i < quantity; i++)
	{
		// 查找最大优先权
		int maxprivilege = -1;
		int jobnum = -1;
		for (int j = 0; j < quantity; j++)
		{
			if (jobs[j].isreached == true && jobs[j].visited == 0)
			{
				if (maxprivilege < jobs[j].privilege)
				{
					maxprivilege = jobs[j].privilege;
					jobnum = j;
				}
			}
		}
		jobs[jobnum].start_time = current_time;
		jobs[jobnum].wait_time = jobs[jobnum].start_time - jobs[jobnum].reach_time;
		current_time += jobs[jobnum].need_time;
		printf("\t%-8d\t%-8d\%-8d\t%-8d\t%-8d\n",jobnum+1,jobs[jobnum].reach_time,jobs[jobnum].start_time,
				jobs[jobnum].wait_time,jobs[jobnum].wait_time+jobs[jobnum].need_time);
		jobs[jobnum].visited = 1;
		total_roundtime += jobs[jobnum].wait_time + jobs[jobnum].need_time;
		total_waitime += jobs[jobnum].wait_time;

		for (int j = 0; j < quantity; j++)
		{
			if (jobs[j].reach_time <= current_time)
			{
				jobs[j].isreached = true;
			}
		}
		int minloc = -1;
		int minjob = 9999999;
		for (int j = 0; j < quantity; j++)
		{
			if (jobs[j].isreached == false)
			{
				if (minjob > jobs[j].reach_time)
				{
					minjob = jobs[j].reach_time;
					minloc = j;
				}
			}
		}
		if (jobs[minloc].reach_time >= current_time)
		{
			current_time = jobs[minloc].reach_time;
			jobs[minloc].isreached = true;
		}
	}
	printf("总等待时间:%-8d 总周转时间:%-8d\n",total_waitime,total_roundtime); 
	printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n",(float)total_waitime/(quantity),(float)total_roundtime/(quantity)); 
}

int main() 
{  
	initial_jobs(); 
	readJobdata(); 
	FCFS();
	reset_jinfo();
	SJFschdulejob(jobs,quantity);
	reset_jinfo();
	HRRFschdulejob(jobs, quantity);
	reset_jinfo();
	HPF(jobs, quantity);
	system("pause");
	return 0;
}

短作业优先、高响应比优先、优先权高者优先均为自己手码，若有错误，感谢指正。

本人较菜，大佬轻喷。

相关标签： 笔记 操作系统

上一篇： 操作系统，作业调度算法参考

下一篇： 操作系统作业调度-操作系统

推荐阅读