进程调度算法：短作业优先，时间片，优先级

浅浅的花香味﹌ 2021-09-26 01:56 379阅读 0赞

实验环境：VS2010 VC++ 实验题目： 模拟短作业优先算法、时间片轮转算法（RR）和优先数算法的执行情况，并 动态画出其进程执行的 Gantt 图，计算以上算法的每个进程的响应时间和周转时间。

/*
    模拟短作业优先算法、时间片轮转算法（RR）和优先数算法的执行情况，并动态画出其进程执行的Gantt图，计算以上算法的每个进程的响应时间和周转时间。
    */
    
    
    #include<iostream>
    
    using namespace std;
    
    const int MAX = 100;
    
    //定义进程结构体
    struct process{
    	char p_name[10];	//进程名
    	int reach_time;		//到达时间
    	int run_time;		//剩余运行时间
    	int priority;		//优先级
    	int response_time;	//响应时间
    	int turnaround_time;//周转时间
    };
    struct gantt{
    	char p_name[10];	//进程名
    	int run_time;		//运行时间
    };
    
    process p[MAX];			//进程数组
    gantt g[MAX];			//Gantt图数组
    int p_Num;				//实际进程数
    char FileName[20];		//进程序列文件名
    int MaxReachTime;		//最大到达时间
    int BeReached[MAX];		//到达进程数组
    int reach_Num;			//到达进程数
    
    //读文件
    int ReadFile()
    {
    	FILE *fp; 
    	int i; 
    	char c;
    	
    	cout << "请输入要打开的文本文件名(注意：包括路径名和后缀名)： "; 
    	cin >> FileName; 
    
    	if((fp = fopen(FileName,"r")) == NULL)
    	{ 
    		cout << "错误：文件 " << FileName << " 打不开,请检查文件名和路径!!" << endl; 
    		exit(0);
    	} 
    	else
    	{
    		c = fgetc(fp);
    		while(c == ' ' || c == 10 || c == 9)	//过滤空格、换行和TAB字符
    		{
    			c = fgetc(fp);
    		}
    		if(c == EOF)
    		{
    			printf("错误：文件：%s 为空!!\n", FileName);
    			exit(0);
    		}
    		else
    		{
    			fseek(fp, -1, SEEK_CUR); 
    			while(!feof(fp))
    			{ 
    				fscanf(fp, "%s %d %d %d", p[p_Num].p_name, &p[p_Num].reach_time, &p[p_Num].run_time, &p[p_Num].priority); 
    				p_Num++; 
    			}
    			
    			//输出所读入的进程数据
    			cout << endl << "从文件 " << FileName << " 读入的进程数据：" << endl << endl; 
    			cout << "进程名  到达时间  运行时间  优先数" << endl; 
    			for(i = 0; i < p_Num; i++)
    			{ 
    				cout << "  " << p[i].p_name << "       " << p[i].reach_time << "	      " << p[i].run_time << "	      " << p[i].priority << endl; 
    			} 
    			cout << endl << "进程总数：" << p_Num << endl << endl; 
    
    			return 0;
    		}		
    	}	
    }
    
    //找到所有进程中的最大到达时间
    void GetMaxReachTime()
    {
    	for(int i = 0; i < p_Num; i++)
    	{
    		if(p[i].reach_time > MaxReachTime) MaxReachTime = p[i].reach_time;
    	}
    }
    
    //全部初始化
    void Init()
    {
    	for(int i = 0; i < MAX; i++)
    	{
    		strcpy(p[i].p_name, "");
    		p[i].reach_time = -1;
    		p[i].run_time = -1;
    		p[i].priority = -1;
    		p[i].response_time = -1;
    		p[i].turnaround_time = -1;
    
    		strcpy(g[i].p_name, "");
    		g[i].run_time = 0;
    
    		BeReached[i] = -1;
    	}
    	p_Num = 0;
    	MaxReachTime = 0;
    	reach_Num = 0;
    
    	ReadFile();
    
    	GetMaxReachTime();
    }
    
    //检查是否所有进程都运行结束
    bool CheckFinish()
    {
    	for(int i = 0; i < p_Num; i++)
    	{
    		if(p[i].run_time > 0) return false;
    	}
    	return true;
    }
    
    //显示Gantt图
    void ShowGantt()
    {
    	int i = 0;
    
    	cout << "Gantt图如下所示：" << endl << endl;
    	cout << "进程名	运行时间" << endl;
    
    	while(true)
    	{
    		if(g[i].run_time == 0) break;
    		cout << "  " << g[i].p_name << "	   " << g[i].run_time << endl;
    		i++;
    	}
    	cout << endl;
    }
    
    //显示每个进程的响应时间和周转时间
    void ShowTime()
    {
    	int i = 0;
    
    	cout << "进程名 响应时间 周转时间" << endl;
    
    	while(i < p_Num)
    	{
    		cout << "  " << p[i].p_name << "	  " << p[i].response_time << "	   " << p[i].turnaround_time << endl;
    		i++;
    	}
    	cout << endl;
    }
    
    //更新到达进程数组和到达进程数
    void UpdateReachArray(int t)
    {
    	if(t <= MaxReachTime)
    	{
    		for(int i = 0; i < p_Num; i++)
    		{
    			if(p[i].reach_time - t == 0)
    			{
    				BeReached[reach_Num++] = i;
    			}
    		}
    	}
    }
    
    //短作业优先算法，抢占调度
    void SPN()
    {
    	int t = 0, i, j = -1;
    	int ilMin;				//上次最短进程下标
    	int iMin = -1;			//当前最短进程下标
    	int iMinRuntime;		//当前最短运行时间
    	
    	while(true)
    	{
    		UpdateReachArray(t);	//更新到达进程数组
    		
    		ilMin = iMin;
    		iMinRuntime = 100000;
    		for(i=0; i<reach_Num; i++)	//找到剩余运行时间最短的进程
    		{ 
    			if(p[BeReached[i]].run_time > 0 && p[BeReached[i]].run_time < iMinRuntime)
    			{ 
    				iMin = BeReached[i]; 
    				iMinRuntime = p[BeReached[i]].run_time; 
    			} 
    		}
    		if(ilMin != iMin)	//若当前运行进程和上个运行进程不是同一个，则j++
    		{	
    			j++;
    			strcpy(g[j].p_name, p[iMin].p_name);
    		}
    
    		g[j].run_time += 1;
    		p[iMin].run_time -= 1;
    
    		if(p[iMin].response_time == -1) p[iMin].response_time = t - p[iMin].reach_time;	//记录该进程响应时间
    		if(p[iMin].run_time == 0) p[iMin].turnaround_time = t + 1 - p[iMin].reach_time;	//记录该进程周转时间
    
    		if(CheckFinish()) break;
    
    		t++;	//时间加1
    	}
    	ShowGantt();
    	ShowTime();
    }
    
    //时间片轮转法算法，抢占调度，BTime为时间片大小的参数
    void RR(int BTime)
    {
    	int t = 0, j = 0, k = 0;
    	int FBTime = 0;			//已用时间片长度
    
    	while(true)
    	{
    		UpdateReachArray(t);
    
    		if(FBTime == BTime || p[BeReached[k]].run_time == 0) //时间片用完或当前运行进程已结束
    		{
    			j++;
    			k++;
    			FBTime = 0;	//已用时间片清零
    		}
    
    		if(k == reach_Num) k = 0;	//已运行到队列最后进程之后，从队列最前重新运行
    		while(p[BeReached[k]].run_time == 0)	//如果该进程已运行结束，跳到下一个进程
    		{
    			k++;
    			if(k == reach_Num) k = 0;
    		}
    
    		strcpy(g[j].p_name, p[BeReached[k]].p_name);
    		g[j].run_time += 1;
    		p[BeReached[k]].run_time -= 1;
    
    		if(p[BeReached[k]].response_time == -1) p[BeReached[k]].response_time = t - p[BeReached[k]].reach_time;	//记录该进程响应时间
    		if(p[BeReached[k]].run_time == 0) p[BeReached[k]].turnaround_time = t + 1 - p[BeReached[k]].reach_time;	//记录该进程周转时间
    
    		if(CheckFinish()) break;
    
    		t++;	//时间加1
    		FBTime++;	//已用时间片加1
    	}
    	ShowGantt();
    	ShowTime();
    }
    
    //优先数算法
    void Priority()
    {
    	int t = 0, i, j = -1;
    	int ilMin;			//上次最高优先级进程下标
    	int iMin = -1;		//当前最高优先级进程下标
    	int iMinPriority;	//当前最高优先级（数值小的优先级高）
    
    	while(true)
    	{
    		UpdateReachArray(t);	//更新到达进程数组
    		
    		ilMin = iMin;
    		iMinPriority = 100;
    		for(i = 0; i < reach_Num; i++)	//找到优先级最高的进程
    		{ 
    			if(p[BeReached[i]].run_time > 0 && p[BeReached[i]].priority < iMinPriority)
    			{ 
    				iMin = BeReached[i]; 
    				iMinPriority = p[BeReached[i]].priority; 
    			} 
    		}
    
    		if(ilMin != iMin)	//若当前运行进程和上个运行进程不是同一个，则j++
    		{
    			j++;
    			strcpy(g[j].p_name, p[iMin].p_name);
    		}
    		
    		g[j].run_time += 1;
    		p[iMin].run_time -= 1;
    
    		if(p[iMin].response_time == -1) p[iMin].response_time = t - p[iMin].reach_time;	//记录该进程响应时间
    		if(p[iMin].run_time == 0) p[iMin].turnaround_time = t + 1 - p[iMin].reach_time;	//记录该进程周转时间
    
    		if(CheckFinish()) break;
    
    		t++;	//时间加1
    	}
    	ShowGantt();
    	ShowTime();
    }
    
    void Information()
    {
    	cout << "***********************************提示信息***********************************" << endl;
    	cout << "文本文件格式为：" << endl;
    	cout << "进程名 到达时间 运行时间 优先级" << endl << endl;
    }
    
    void main()
    {
    	Information();
    
    	cout << "********************************短作业优先算法********************************" << endl << endl;
    	Init();
    	SPN();
    
    	cout << "****************************时间片轮转法(时间片为1)***************************" << endl << endl;
    	Init();
    	RR(1);
    
    	cout << "****************************时间片轮转法(时间片为2)***************************" << endl << endl;
    	Init();
    	RR(2);
    
    	cout << "****************************时间片轮转法(时间片为3)***************************" << endl << endl;
    	Init();
    	RR(3);
    
    	cout << "**********************************优先数算法**********************************" << endl << endl;
    	Init();
    	Priority();
    }

实验结果如下图：

![Center][] ![Center 1][] ![Center 2][]

[Center]: https://img-blog.csdn.net/20161121095943169?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: https://img-blog.csdn.net/20161121095947520?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: /images/20210923/b900e951f7cd466686e8c848c3344a58.png