精华内容
下载资源
问答
  • 先来先服务和高响应比优先调度算法C语言实现

    万次阅读 多人点赞 2016-10-29 00:58:34
    1、进程调度与作业调度的区别: 2、单道批处理系统与多道批处理系统的区别: 3、程序设计用到的公式: 4、高响应比优先算法特点: 5、源代码示例: 6、测试用例: 7、运行结果:
    先来先服务和高响应比优先调度算法C语言实现

    目录:

    1、进程调度与作业调度的区别:

    2、单道批处理系统与多道批处理系统的区别:

    3、程序设计用到的公式:

    4、高响应比优先算法特点:

    5、源代码示例:

    6、测试用例:

    7、运行结果:


    1、进程调度与作业调度的区别:

    答:(1)作业调度:根据作业控制块(JCB)中的信息,检查系统中的资源是否满足作业对资源的需求,以及按照一定的调度算法,从外存的后备队列中选取某些作业调入内存,并为它们创建进程,分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度。

    (2)进程调度:保存当前进程的处理机的现场信息,如程序计数器、多个通用寄存器中的内容等,然后按某种算法从就绪队列中选取一个进程,将其状态转换为运行状态,再把进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中,把处理器的控制权交予该进程,让它从上次的断点处恢复运行。

    (3)进程调度时让某个就绪状态的进程到处理机上运行,而作业调度只是使作业具有了竞争处理机的机会。


    2、单道批处理系统与多道批处理系统的区别:

    答:(1)单道批处理系统(Simple Batch Processing System):系统对作业的处理是成批进行的,但在内存中始终只保持一道作业。

    特点:自动性、顺序性、单道性

    主要问题:CPUI/O设备忙闲不均,对计算为主的作业,外设空闲;对I/O为主的作业,CPU空闲。

    (2)多道批处理系统(Multiprogrammed Batch Processing System):在内存中同时存放几个作业,宏观上并行运行——都处于运行状态,但都没运行完;微观上串行运行——各作业交替使用CPU

    特点:调度性、无序性、多道性

    主要问题:①作业平均周转时间长:短作业的周转时间显著增长;

    ②无交互能力:整个作业完成后或者中间出错时,才与用户交互,不利于调试和修改。


    3、程序设计用到的公式:

    答:完成时间 = 开始时间 +  需要运行时间

    周转时间 = 完成时间 -  到达时间

    带权周转时间 = 周转时间 / 需要运行时间

    等待时间 = 当前时间 -  到达时间

    优先权 = (等待时间 + 需要运行时间) / 需要运行时间

     

    4、高响应比优先算法特点:

    答:①当等待时间相同时,短进程的优先权高;

    ②当需要运行时间相同时,作业的优先权又取决于等待时间,相当于先到先服务;

    ③长作业的优先级可以随着等待时间的增加而提高,因此长作业等待一段时间后仍能得到调度。


    5、源代码示例:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define WAIT "Wait"//就绪状态 
    #define RUN "Run"//运行状态 
    #define FINISH "Finish"//完成状态 
    #define JOBNUMBER 5 //设置进程测试数为5   
    typedef struct JCB{	
    	char jobName[10];//作业名 
    	int arriveTime;//到达时间 
    	int runTime;//需要运行时间 
    	int startTime;//开始时间 
    	int endTime;//完成时间 
    	int turnoverTime;//周转时间 
    	float useWeightTurnoverTime;//带权周转时间
    	char processStatus[10];//进程状态 	
    };
    static int currentTime = 0;//当前时间 
    static int finishNumber = 0;//进程完成数量 
    char JobArray[JOBNUMBER][10];//存放数组名信息的二元数组 
    float priority[JOBNUMBER];//存放进程优先级的一元数组 
    
    //创建JCB
    void createJCB(struct JCB* jcb){
     	freopen("input.txt","r",stdin);
     	printf("从文件中读入三个参数的数据:\n");
     	printf("作业号 到达时间 需要运行时间\n"); 
     	for(int i = 0; i < 5; i++){
    	 	scanf("%s", &jcb[i].jobName);//作业号 
    	 	scanf("%d", &jcb[i].arriveTime);//到达时间 
    	 	scanf("%d", &jcb[i].runTime);//需要运行时间 
    	 	jcb[i].startTime = 0;
    	 	jcb[i].endTime = 0;
    	 	jcb[i].turnoverTime = 0;
    	 	jcb[i].useWeightTurnoverTime = 0.0;
    	 	strcpy(jcb[i].processStatus, WAIT);
    	 	printf("%s\t%d\t%d\n",jcb[i].jobName, jcb[i].arriveTime,jcb[i].runTime);
    	}
    	printf("---------------------------------------------\n");
    	freopen("CON", "r", stdin);
     }
     
    //打印用途
    void printJob(struct JCB* jcb){
    	printf("当前时间为%d\n", currentTime);
    	printf("作业号 到达时间 需要运行时间 开始时间 完成时间 周转时间 带权周转时间 进程状态\n");
    	for(int i = 0; i < JOBNUMBER; i++){	
    		if(strcmp(jcb[i].processStatus, FINISH) == 0)//如果进程为finish状态,这样输出 
    			printf("%s\t%d\t%4d\t\t%d\t%d\t  %d\t  %.2f\t  %s\n", jcb[i].jobName, jcb[i].arriveTime, jcb[i].runTime, jcb[i].startTime, jcb[i].endTime, jcb[i].turnoverTime, jcb[i].useWeightTurnoverTime, jcb[i].processStatus);	
    		else if(strcmp(jcb[i].processStatus, RUN) == 0)//如果进程为run状态,这样输出 
    			printf("%s\t%d\t%4d\t\t%d\t运行中\t  none\t  none    %s\n", jcb[i].jobName, jcb[i].arriveTime, jcb[i].runTime, jcb[i].startTime, jcb[i].processStatus);	
    		else //如果进程为wait状态,这样输出
    			printf("%s\t%d\t%4d\t\t未运行\tnone\t  none\t  none    %s\n", jcb[i].jobName, jcb[i].arriveTime, jcb[i].runTime, jcb[i].processStatus);
    	}
    	printf("---------------------------------------------\n");
    }
    
    //计算平均带权周转时间 
    float weightTurnoverTimeCount(struct JCB* jcb){
    	float sum = 0.0;
    	for(int i = 0; i < JOBNUMBER; i++)
    		sum += jcb[i].useWeightTurnoverTime;
    	return sum / JOBNUMBER;
    }
    
    //计算平均周转时间 
    float turnOverTimeCount(struct JCB* jcb){
    	float sum = 0.0;
    	for(int i = 0; i < JOBNUMBER; i++)
    		sum += jcb[i].turnoverTime;
    	return sum / JOBNUMBER;
    }
    
    //比较各个进程之间的到达时间,按升序排列 
    void compare(struct JCB* jcb){
    	for(int i = 0; i < JOBNUMBER; i++){
    		int min = jcb[i].arriveTime, minIndex = i;
    		for(int j = i + 1; j < JOBNUMBER; j++){
    			if(jcb[j].arriveTime < min){
    				min = jcb[j].arriveTime;
    				minIndex = j;		
    			}	
    		}
    		struct JCB temp = jcb[i];
    		jcb[i] = jcb[minIndex];
    		jcb[minIndex] = temp;
    	}	
    }
    
    //打印进程调度顺序,平均周转时间及平均带权周转时间 
    void printInfo(struct JCB* jcb){
    	printf("1、进程调度顺序为:%s -> %s -> %s -> %s -> %s\n", JobArray[0], JobArray[1], JobArray[2], JobArray[3], JobArray[4]);
    	printf("2、平均周转时间为:%.2f\n",turnOverTimeCount(jcb));
    	printf("3、平均带权周转时间为:%.2f\n", weightTurnoverTimeCount(jcb));
    	printf("------------------测试完毕 版权归邓钦艺所有---------\n");
    }
    
    //两算法共同循环遍历部分 
    void loop(struct JCB* jcb, int i){
    	jcb[i].startTime = currentTime;
    	jcb[i].endTime = jcb[i].startTime + jcb[i].runTime;
    	jcb[i].turnoverTime = jcb[i].endTime - jcb[i].arriveTime;
    	jcb[i].useWeightTurnoverTime = jcb[i].turnoverTime * 1.0 / jcb[i].runTime;
    	strcpy(jcb[i].processStatus, RUN);
    	while(true){
    		if(currentTime == jcb[i].endTime){	
    			strcpy(jcb[i].processStatus, FINISH);
    			finishNumber++;
    			if(finishNumber == JOBNUMBER)
    				printJob(jcb);
    			currentTime--;
    			break;
    		}
    		else{
    			printJob(jcb);
    			currentTime++;	
    		}	
    	}
    } 
    
    //先来先服务调度算法
    void firstComeFirstServed(struct JCB* jcb){
    	createJCB(jcb);
    	compare(jcb);
    	int i = 0; 
    	//进程调度currentTime每次加1,直到进程全部被调度完成为止 
    	for(; finishNumber != JOBNUMBER; currentTime++){
    		if(currentTime < jcb[0].arriveTime)//当前时间小于第一个节点到来时间时,直接打印 
    			printJob(jcb);
    		else{
    			strcpy(JobArray[i], jcb[i].jobName);
    			loop(jcb, i);
    			i++;
    		}
    	}
    	printInfo(jcb);//打印进程调度顺序,平均周转时间及平均带权周转时间 
    	currentTime = 0;//静态变量当前时间置位
    	finishNumber = 0;//静态变量完成进程数量置位 
    }
    
    //高响应比优先调度算法 
    void highestResponseRatioNext(struct JCB* jcb){
    	createJCB(jcb);
    	compare(jcb);
    	int i = 0, j = 0; 
    	for(; finishNumber != JOBNUMBER; currentTime++){
    		float maxPriority = 0.0;
    		int indexPriority = 0;
    		if(currentTime < jcb[0].arriveTime)//当前时间小于第一个节点到来时间时,直接打印 
    			printJob(jcb);
    		else{
    			for(int i = 0; i < JOBNUMBER; i++){
    				if(strcmp(jcb[i].processStatus, FINISH) != 0){
    					int waitTime = currentTime - jcb[i].arriveTime;
    				 	priority[i] = (waitTime + jcb[i].runTime) * 1.0 / jcb[i].runTime;
    				 	if(priority[i] > maxPriority){
    			 			maxPriority = priority[i];
    			 			indexPriority = i;
    			 		}
    				}			 	
    			}
    			strcpy(JobArray[j++], jcb[indexPriority].jobName);
    			loop(jcb, indexPriority);
    		}
    	}
    	printInfo(jcb);//打印进程调度顺序,平均周转时间及平均带权周转时间 
    	currentTime = 0;//当前时间置位
    	finishNumber = 0;//完成进程数量置位 
    }
    
    //菜单函数
    void menu(struct JCB* jcb){
    	int input; 
    	while(true){
    		printf("------------3114005847 邓钦艺-----------------\n");
    		printf("|        1、先来先服务调度算法               |\n");
    		printf("|        2、响应比高者优先调度算法           |\n");
    		printf("|        3、退出                             |\n");
    		printf("----------------------------------------------\n");
    		printf("请输入序号以继续程序:");
    		scanf("%d", &input);
    		switch(input){
    			case 1:firstComeFirstServed(jcb);
    				break;
    			case 2:highestResponseRatioNext(jcb);
    				break;
    			case 3:
    				exit(0);
    			default:printf("输入有误,请重新输入!!!\n");
    				break; 
    		}	
    	}
    } 
    
    //主函数 
    int main(){
    	struct JCB jcb[JOBNUMBER];
    	menu(jcb);
        system("pause");
    	return 0;
    }
    

    6、测试用例:

    说明:其中三个参数分别是作业名称,到达时间以及需要运行时间

    图6.1 测试用例

    7、运行结果:

    1)菜单页面:

     

    图7.1 运行结果截图1

    2)先到先服务算法调度过程:

    ①当前时间为0时,模拟系统从外存的后备队列中选取五项作业(job1job2job3job4job5)调入内存,并为它们创建进程,分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度,其进程状态为wait状态。

     

    图7.2 运行结果截图2

    ②当前时间为1时,job5到达,并开始执行,进程状态由wait转换为run;当前时间为3时,job5执行完毕,开始时间1 + 需要运行时间2 =完成时间3,进程状态由run转换为finish。与此同时,job2开始执行,进程状态由wait转换为run

     

    图7.3 运行结果截图3

    ③当前时间为8时,job2执行完毕,进程状态由run转换为finish,与此同时job3开始执行,进程状态由wait转换为run

     

    图7.4 运行结果截图4

    ④当前时间为12时,job3运行完毕,进程状态由run转换为finish,与此同时job4开始执行,进程状态由wait转换为run

     

    图7.5 运行结果截图5

    ⑤当前时间为19时,job4运行完毕,进程状态由run转换为finish,与此同时job1开始执行,进程状态由wait转换为run

     

    图7.6 运行结果截图6

    ⑥当前时间为21时,job5执行完毕,进程状态由run转换为finish,此时五个进程状态全部转换为finish,进程调度算法停止,打印出进程调度顺序,平均周转时间,以及平均带权周转时间。算法调度完毕后回到菜单界面:

     

    图7.7 运行结果截图7

    3)高响应比优先算法调度过程:

    ①当前时间为0时,模拟系统从外存的后备队列中选取五项作业(job1job2job3job4job5)调入内存,并为它们创建进程,分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度,其进程状态为wait状态;

    当前时间为1时,只有job5到达,并开始执行,进程状态由wait转换为run

    当前时间为3时,job5执行完毕,开始时间1 +需要运行时间2 =完成时间3,进程状态由run转换为finish。与此同时,job3开始执行,进程状态由wait转换为run

     

    图7.8 运行结果截图8

    ②当前时间为7时,job3执行完毕,开始时间3 +需要运行时间4  =完成时间7,进程状态由run转换为finish。与此同时,job2开始执行,进程状态由wait转换为run

     

    图7.9 运行结果截图9

    ③当前时间为12时,job2执行完毕,进程状态由run转换为finish,与此同时job1开始执行,进程状态由wait转换为run

     

    图7.10 运行结果截图10

    ④当前时间为14时,job5执行完毕,进程状态由run转换为finish,与此同时job4开始执行,进程状态由wait转换为run

     

    图7.11 运行结果截图11

    ⑤当前时间为21时,job4执行完毕,进程状态由run转换为finish,此时五个进程状态全部转换为finish,进程调度算法停止,打印出进程调度顺序,平均周转时间,以及平均带权周转时间。算法调度完毕后回到菜单界面:

     

    图7.12 运行结果截图12

    ⑥按3退出

     

    图7.13 运行结果截图13

    (4)对实现高响应比的验证:

    优先权 = (等待时间 + 需要运行时间) / 需要运行时间

    ①当前时间为1时,只有job5到了,那就先运行它,需要运行时间为2,运行到时间3结束,开始调度下一进程;

    ②当前时间为3时,job5运行完毕,job2job3job4也已经到达,比较三者的优先权:

    Job2:(1 + 5/ 5 = 1.2job3:(1 + 4/  4  = 1.25job4:(0 + 7/ 7  = 1,优先权最大为job3,执行它,需要运行时间为4,因此直到时间7结束,开始调度下一进程;

    ③当前时间为7时,job3运行完毕,此时job2,job4,job1全都已经到达,比较三者的优先权:

    Job2:(5 + 5/ 5 = 2job4:(4+ 7/  7  = 1.57job1:(2 + 2/ 2  = 2,优先权最大为job2job1,优先权相同时执行先到的进程,因此执行进程job2,需要运行时间为5,因此直到时间12结束,开始调度下一进程;

    ④当前时间为12时,job2运行完毕,比较job1job4的优先权:

    Job1:(7 + 2/ 2 = 4.5job4:(9 + 7/  7  = 2.29, 优先权最大为job1,执行它,需要运行时间为2,因此直到时间14结束,开始调度下一进程;

    ⑤当前时间为14时,剩余进程job4,执行它,需要运行时间为7,因此直到时间21结束,此时后备队列中五个进程执行完毕,调度完毕。

    验证结果为:job5 >> job3 >> job2 >> job1 >> job4,与程序运行结果一致。

    5)二者对比:

    先来先服务算法:

     

    图7.14 先来先服务算法运行结果

    高响应比优先算法:

     

    图7.15 高响应比优先算法运行结果

    二者在调度顺序上出现了不一致,

    在平均周转时间上:先来先服务 > 高响应比优先

    在平均带权周转时间上:先来先服务 > 高响应比优先

    在这次运行的测试用例中可以看出,二者算法在两项指标性能上,高响应比优先算法要优于先来先服务算法。

    首先高响应比优先算法兼顾了等待时间和需要运行时间,其短进程的优先权高,与此同时长作业的优先级可以随着等待时间的增加而提高,因此长作业等待一段时间后仍能得到调度而不会长期得不到服务。而先来先服务算法则很容易导致长作业到来过多时,短作业再到达造成的“饥饿”现象;也避免了短进程优先中存在大量短作业时造成的长作业“饥饿”现象;高响应比算法在优先权相同的时候,执行到达时间早的进程。


    展开全文
  • 高响应比优先调度算法(HRRN)

    万次阅读 2015-12-01 01:51:47
    高响应比算法,是一种动态调整优先级的算法,在上面介绍的PSA算法中,给每个作业安排一个优先级后,始终这个优先级不再改变,这有些不合理。 因为可能造成一个低优先级作业始终得不到执行。 为了解决这个问题,HRRN...

    BOOM,困到不行,这个写完就睡觉了,今天好像有点感冒 ,翘了晚上的课一直睡到10点起来,睡不着在写代码,现在又困了


    高响应比算法,是一种动态调整优先级的算法,在上面介绍的PSA算法中,给每个作业安排一个优先级后,始终这个优先级不再改变,这有些不合理。

    因为可能造成一个低优先级作业始终得不到执行。

    为了解决这个问题,HRRN算法每次都计算作业的优先级,随着作业等待时间的变长,优先级不断的提高,所以能够得到更快的执行。

    这个优先级可以描述为: 优先级 = (作业已等待时间 + 作业的服务时间) / 作业的服务时间

    从上式可以看到,作业的服务时间是固定的, 优先级随着已等待时间的提高而变大





    //main.cpp
    #include "HRRN.h"
    
    int main()
    {
    	std::vector<PCB> PCBList;
    
    	//输入作业信息
    	InputPCB(PCBList);
    
    	//HRRN算法
    	HRRN(PCBList);
    
    	//显示结果
    	show(PCBList);
    
    	return 0;
    }
    
    //HRRN.h
    #ifndef HRRN_H_
    #define HRRN_H_
    
    #include <iostream>
    #include <algorithm>
    #include <iomanip>
    #include <vector>
    
    //作业结构体
    typedef struct PCB
    {
    	int ID;							//标识符
    	double Level;					//优先级
    	int ComeTime;					//到达时间
    	int ServerTime;					//服务时间
    	int FinishTime;					//完成时间
    	int TurnoverTime;				//周转时间
    	double WeightedTurnoverTime;	//带权周转时间
    }PCB;
    
    /*
    函数功能:输入作业信息
    参数说明:
    PCBList		std::vector<PCB>&		PCB链
    */
    void InputPCB(std::vector<PCB> &PCBList);
    
    /*
    函数功能:HRRN算法
    参数说明:
    PCBList		std::vector<PCB>&		PCB链
    */
    void HRRN(std::vector<PCB> &PCBList);
    
    /*
    函数功能:计算优先级
    参数说明:
    b		std::vector<PCB>::iterator		起始位置
    e		std::vector<PCB>::iterator		结束位置
    CurTime int								当前时间
    */
    void CalPriority(std::vector<PCB>::iterator b, std::vector<PCB>::iterator e, int CurTime);
    
    /*
    函数功能:显示结果
    参数说明:
    PCBList		std::vector<PCB>&		PCB链
    */
    void show(std::vector<PCB> &PCBList);
    
    /*
    函数功能:比较函数,用于sort(),按ComeTime升序排列
    参数说明:
    p1			const PCB&				PCB
    p2			const PCB&				PCB
    */
    bool CmpByComeTime(const PCB &p1, const PCB &p2);
    
    /*
    函数功能:比较函数,用于sort(),按Level降序排列
    参数说明:
    p1			const PCB&				PCB
    p2			const PCB&				PCB
    */
    bool CmpByLevel(const PCB &p1, const PCB &p2);
    
    #endif
    
    //HRRN.cpp
    #include "HRRN.h"
    
    //输入作业信息
    void InputPCB(std::vector<PCB> &PCBList)
    {
    	do {
    		PCB temp;
    		std::cout << "输入标识符: ";
    		std::cin >> temp.ID;
    		std::cout << "输入到达时间: ";
    		std::cin >> temp.ComeTime;
    		std::cout << "输入服务时间: ";
    		std::cin >> temp.ServerTime;
    		PCBList.push_back(temp);
    
    		std::cout << "继续输入?Y/N: ";
    		char ans;
    		std::cin >> ans;
    		if ('Y' == ans || 'y' == ans)
    			continue;
    		else
    			break;
    	} while (true);
    }
    
    //HRRN算法
    void HRRN(std::vector<PCB> &PCBList)
    {
    	std::sort(PCBList.begin(), PCBList.end(), CmpByComeTime);		//按到达时间排序
    
    	//同时到达的按优先级降序排序,决定首先运行的作业
    	int i = 1;
    	std::vector<PCB>::iterator it = PCBList.begin() + 1;
    	while ((*it).ComeTime == (*(it - 1)).ComeTime)
    	{
    		++i;
    		++it;
    	}
    	CalPriority(PCBList.begin(), PCBList.begin() + i, 0);		//计算优先级
    	std::sort(PCBList.begin(), PCBList.begin() + i, CmpByLevel);
    
    	int FinishTime = -1;
    	for (it = PCBList.begin(); it < PCBList.end(); ++it)
    	{
    		if ((*it).ComeTime >= FinishTime)		//没有作业正在运行,取队首作业运行
    			(*it).FinishTime = (*it).ComeTime + (*it).ServerTime;
    		else									//有作业正在运行,等待作业完毕,此作业再运行
    			(*it).FinishTime = FinishTime + (*it).ServerTime;
    		(*it).TurnoverTime = (*it).FinishTime - (*it).ComeTime;
    		(*it).WeightedTurnoverTime = (double)(*it).TurnoverTime / (*it).ServerTime;
    		FinishTime = (*it).FinishTime;
    
    		//在一个作业运行期间,如果有其他作业到达,将他们按照优先级降序排列
    		i = 1;
    		while ((it + i) < PCBList.end() && (*(it + i)).ComeTime <= FinishTime)
    			++i;
    		CalPriority(it + 1, it + i, FinishTime);
    		std::sort(it + 1, it + i, CmpByLevel);
    	}
    
    	std::sort(PCBList.begin(), PCBList.end(), CmpByComeTime);		//重新排列,用于显示结果
    }
    
    //计算优先级
    void CalPriority(std::vector<PCB>::iterator b, std::vector<PCB>::iterator e, int CurTime)
    {
    	while (b < e)
    	{
    		(*b).Level = (double)((*b).ServerTime + (CurTime - (*b).ComeTime)) / (*b).ServerTime;
    		++b;
    	}
    }
    
    //显示结果
    void show(std::vector<PCB> &PCBList)
    {
    	int SumTurnoverTime = 0;
    	double SumWeightedTurnoverTime = 0;
    
    	std::cout.setf(std::ios::left);
    
    	std::cout << std::setw(20) << "标识符";
    	for (std::vector<PCB>::iterator it = PCBList.begin(); it < PCBList.end(); ++it)
    		std::cout << std::setw(5) << (*it).ID;
    	std::cout << std::endl;
    
    	std::cout << std::setw(20) << "到达时间";
    	for (std::vector<PCB>::iterator it = PCBList.begin(); it < PCBList.end(); ++it)
    		std::cout << std::setw(5) << (*it).ComeTime;
    	std::cout << std::endl;
    
    	std::cout << std::setw(20) << "服务时间";
    	for (std::vector<PCB>::iterator it = PCBList.begin(); it < PCBList.end(); ++it)
    		std::cout << std::setw(5) << (*it).ServerTime;
    	std::cout << std::endl;
    
    	std::cout << std::setw(20) << "完成时间";
    	for (std::vector<PCB>::iterator it = PCBList.begin(); it < PCBList.end(); ++it)
    		std::cout << std::setw(5) << (*it).FinishTime;
    	std::cout << std::endl;
    
    	std::cout << std::setw(20) << "周转时间";
    	for (std::vector<PCB>::iterator it = PCBList.begin(); it < PCBList.end(); ++it)
    	{
    		std::cout << std::setw(5) << (*it).TurnoverTime;
    		SumTurnoverTime += (*it).TurnoverTime;;
    	}
    	std::cout << std::endl;
    
    	std::cout << std::setw(20) << "带权周转时间";
    	for (std::vector<PCB>::iterator it = PCBList.begin(); it < PCBList.end(); ++it)
    	{
    		std::cout << std::setw(5) << (*it).WeightedTurnoverTime;
    		SumWeightedTurnoverTime += (*it).WeightedTurnoverTime;;
    	}
    	std::cout << std::endl;
    
    	std::cout << "平均周转时间: " << (double)SumTurnoverTime / PCBList.size() << std::endl;
    	std::cout << "平均带权周转时间: " << SumWeightedTurnoverTime / PCBList.size() << std::endl;
    }
    
    //比较函数,按ComeTime升序排列
    bool CmpByComeTime(const PCB &p1, const PCB &p2)
    {
    	return p1.ComeTime < p2.ComeTime;
    }
    
    //比较函数,按Level降序排列
    bool CmpByLevel(const PCB &p1, const PCB &p2)
    {
    	return p1.Level > p2.Level;
    }


    展开全文
  • 非抢占的高响应比优先调度算法

    千次阅读 2017-04-30 00:31:05
    模拟操作系统进程调度算法流程图测试数据进程名: A B C D E 需要运行时间: 3 6 4 5 2代码实现#include #include #include #include #include #include usin

    模拟操作系统进程调度

    算法流程图

    这里写图片描述

    测试数据

    进程名: A B C D E
    需要运行时间: 3 6 4 5 2

    5
    ProcA 8 3
    ProcB 10 6
    ProcC 7 4
    ProcD 12 5
    ProcE 6 2

    代码实现

    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<algorithm>
    #include<queue>
    #include<functional>
    using namespace std;
    /**
     *  非抢占的高响应比优先调度算法
     */
    
    double avg1 = 0, avg2 = 0;
    
    enum State  // 进程状态
    {
        ready, // 就绪
        run, // 运行
        finish // 完成
    };
    
    class PCB
    {
    public:
        string name; // 进程名
        State state; // 进程状态
        double priority; // 优先数
        int needTime; // 需要运行时间
        int runTime; // 已运行时间
        int turnOverTime; //周转时间
        PCB(){}
    
        PCB(string _name, State _state, double _priority, int _needTime, int _runTime)
        {
            name = _name;
            state = _state;
            priority = _priority;
            needTime = _needTime;
            runTime = _runTime;
        }
        void PCB::show()
        {
            cout << "进程名:" << name << ", "
                << "优先数:" << priority << ", "
                << "已运行时间:" << runTime << ", "
                << "还需要时间:" << needTime - runTime << endl;
        }
    
        void PCB::runShow()
        {
            cout << "正在运行:进程名:" << name << ", "
                << "优先数:" << priority << ", "
                << "已运行时间:" << runTime << ", "
                << "还需要时间:" << needTime - runTime << endl;
        }
    
        void PCB::end()
        {
            cout << "\n\n-----------进程:" << name << "运行结束------------------\n\n" << endl;
        }
    
    
        void PCB::ShowServiceTime()
        {
            cout << "进程名:" << name << ", "
                << "周转时间:" << turnOverTime << ", "
                << "带权周转时间:" << turnOverTime*1.0/needTime << ", "
                << "平均周转时间:" << avg1/5 << ", "
                << "平均带权周转时间:" << avg2/5 << endl;
        }
    
        bool operator<(const PCB &pcb)const
        {
            return pcb.priority > this->priority;
        }
    };
    
    priority_queue<PCB>PCBqueue;
    
    queue<PCB>finishQueue;
    
    void readFile(){
        ios::sync_with_stdio(false);
        freopen("i.txt", "r", stdin);
        //freopen("o.txt", "w", stdout);
        int n,priority,needTime;
        string PCBname;
        cin >> n;
        for (int i =0 ;i<n;i++)
        {
            cin >> PCBname >> priority >> needTime;
            PCBqueue.push(PCB(PCBname,ready,1.0,needTime,0));
        }
    }
    
    void startService()
    {
    
        vector<PCB>temp;
        int waitTime = 0, runTime = 0;
        PCB top;
    
    
        while (PCBqueue.size()>0)
        {
            PCB pcb = PCBqueue.top();
            PCBqueue.pop();
            runTime = 0;
            for(int i = 0;i< pcb.needTime;i++)
            {
                pcb.runTime++;
                pcb.runShow();
                waitTime++;
                temp.clear();
                while (PCBqueue.size() > 0) 
                {
                    top = PCBqueue.top();
                    PCBqueue.pop();
                    top.show();
                    top.priority = (top.needTime + waitTime) / (top.needTime*1.0);
                    temp.push_back(top);
                }
                for (int i = 0; i < temp.size(); i++) 
                {
                    PCBqueue.push(temp[i]);
                }
                puts("=====================================================================");
            }
            pcb.turnOverTime = waitTime;
            pcb.end();
            finishQueue.push(pcb);
            avg1 += pcb.turnOverTime;
            avg2 += (pcb.turnOverTime*1.0 / pcb.needTime);
        }
    
        puts("\n\n--------------------------所有进程已完成-------------------------\n\n");
    
    
        while (finishQueue.size() > 0) 
        {
            finishQueue.front().ShowServiceTime();
            finishQueue.pop();
        }
    }
    
    int main()
    {
        readFile();
        startService();
        return 0;
    }

    结果输出

    正在运行:进程名:ProcA, 优先数:1, 已运行时间:1, 还需要时间:2
    进程名:ProcC, 优先数:1, 已运行时间:0, 还需要时间:4
    进程名:ProcE, 优先数:1, 已运行时间:0, 还需要时间:2
    进程名:ProcB, 优先数:1, 已运行时间:0, 还需要时间:6
    进程名:ProcD, 优先数:1, 已运行时间:0, 还需要时间:5
    =====================================================================
    正在运行:进程名:ProcA, 优先数:1, 已运行时间:2, 还需要时间:1
    进程名:ProcE, 优先数:1.5, 已运行时间:0, 还需要时间:2
    进程名:ProcC, 优先数:1.25, 已运行时间:0, 还需要时间:4
    进程名:ProcD, 优先数:1.2, 已运行时间:0, 还需要时间:5
    进程名:ProcB, 优先数:1.16667, 已运行时间:0, 还需要时间:6
    =====================================================================
    正在运行:进程名:ProcA, 优先数:1, 已运行时间:3, 还需要时间:0
    进程名:ProcE, 优先数:2, 已运行时间:0, 还需要时间:2
    进程名:ProcC, 优先数:1.5, 已运行时间:0, 还需要时间:4
    进程名:ProcD, 优先数:1.4, 已运行时间:0, 还需要时间:5
    进程名:ProcB, 优先数:1.33333, 已运行时间:0, 还需要时间:6
    =====================================================================
    
    
    -----------进程:ProcA运行结束------------------
    
    
    正在运行:进程名:ProcE, 优先数:2.5, 已运行时间:1, 还需要时间:1
    进程名:ProcC, 优先数:1.75, 已运行时间:0, 还需要时间:4
    进程名:ProcD, 优先数:1.6, 已运行时间:0, 还需要时间:5
    进程名:ProcB, 优先数:1.5, 已运行时间:0, 还需要时间:6
    =====================================================================
    正在运行:进程名:ProcE, 优先数:2.5, 已运行时间:2, 还需要时间:0
    进程名:ProcC, 优先数:2, 已运行时间:0, 还需要时间:4
    进程名:ProcD, 优先数:1.8, 已运行时间:0, 还需要时间:5
    进程名:ProcB, 优先数:1.66667, 已运行时间:0, 还需要时间:6
    =====================================================================
    
    
    -----------进程:ProcE运行结束------------------
    
    
    正在运行:进程名:ProcC, 优先数:2.25, 已运行时间:1, 还需要时间:3
    进程名:ProcD, 优先数:2, 已运行时间:0, 还需要时间:5
    进程名:ProcB, 优先数:1.83333, 已运行时间:0, 还需要时间:6
    =====================================================================
    正在运行:进程名:ProcC, 优先数:2.25, 已运行时间:2, 还需要时间:2
    进程名:ProcD, 优先数:2.2, 已运行时间:0, 还需要时间:5
    进程名:ProcB, 优先数:2, 已运行时间:0, 还需要时间:6
    =====================================================================
    正在运行:进程名:ProcC, 优先数:2.25, 已运行时间:3, 还需要时间:1
    进程名:ProcD, 优先数:2.4, 已运行时间:0, 还需要时间:5
    进程名:ProcB, 优先数:2.16667, 已运行时间:0, 还需要时间:6
    =====================================================================
    正在运行:进程名:ProcC, 优先数:2.25, 已运行时间:4, 还需要时间:0
    进程名:ProcD, 优先数:2.6, 已运行时间:0, 还需要时间:5
    进程名:ProcB, 优先数:2.33333, 已运行时间:0, 还需要时间:6
    =====================================================================
    
    
    -----------进程:ProcC运行结束------------------
    
    
    正在运行:进程名:ProcD, 优先数:2.8, 已运行时间:1, 还需要时间:4
    进程名:ProcB, 优先数:2.5, 已运行时间:0, 还需要时间:6
    =====================================================================
    正在运行:进程名:ProcD, 优先数:2.8, 已运行时间:2, 还需要时间:3
    进程名:ProcB, 优先数:2.66667, 已运行时间:0, 还需要时间:6
    =====================================================================
    正在运行:进程名:ProcD, 优先数:2.8, 已运行时间:3, 还需要时间:2
    进程名:ProcB, 优先数:2.83333, 已运行时间:0, 还需要时间:6
    =====================================================================
    正在运行:进程名:ProcD, 优先数:2.8, 已运行时间:4, 还需要时间:1
    进程名:ProcB, 优先数:3, 已运行时间:0, 还需要时间:6
    =====================================================================
    正在运行:进程名:ProcD, 优先数:2.8, 已运行时间:5, 还需要时间:0
    进程名:ProcB, 优先数:3.16667, 已运行时间:0, 还需要时间:6
    =====================================================================
    
    
    -----------进程:ProcD运行结束------------------
    
    
    正在运行:进程名:ProcB, 优先数:3.33333, 已运行时间:1, 还需要时间:5
    =====================================================================
    正在运行:进程名:ProcB, 优先数:3.33333, 已运行时间:2, 还需要时间:4
    =====================================================================
    正在运行:进程名:ProcB, 优先数:3.33333, 已运行时间:3, 还需要时间:3
    =====================================================================
    正在运行:进程名:ProcB, 优先数:3.33333, 已运行时间:4, 还需要时间:2
    =====================================================================
    正在运行:进程名:ProcB, 优先数:3.33333, 已运行时间:5, 还需要时间:1
    =====================================================================
    正在运行:进程名:ProcB, 优先数:3.33333, 已运行时间:6, 还需要时间:0
    =====================================================================
    
    
    -----------进程:ProcB运行结束------------------
    
    
    
    
    --------------------------所有进程已完成-------------------------
    
    
    进程名:ProcA, 周转时间:3, 带权周转时间:1, 平均周转时间:10.2, 平均带权周转时间:2.37667
    进程名:ProcE, 周转时间:5, 带权周转时间:2.5, 平均周转时间:10.2, 平均带权周转时间:2.37667
    进程名:ProcC, 周转时间:9, 带权周转时间:2.25, 平均周转时间:10.2, 平均带权周转时间:2.37667
    进程名:ProcD, 周转时间:14, 带权周转时间:2.8, 平均周转时间:10.2, 平均带权周转时间:2.37667
    进程名:ProcB, 周转时间:20, 带权周转时间:3.33333, 平均周转时间:10.2, 平均带权周转时间:2.37667
    
    展开全文
  • 经过调试程序 代码成功的运行 做出实验
  • 这里记录一下操作系统的实验,几个调度算法的原理很好理解,网上也有很多解释,这里不再解释,直接上代码。 一、JCB类 public class JCB { public int id; /** * 剩余服务时间 */ public int leftTime; /** *...

    这里记录一下操作系统的实验,几个调度算法的原理很好理解,网上也有很多解释,这里不再解释,直接上代码。

    一、JCB类

    public class JCB {
        public int id;
        /**
         * 剩余服务时间
         */
        public int leftTime;
        /**
         * 要求服务时间
         */
        public int serviceTime;
        /**
         * 到达时间
         */
        public int arriveTime;
        /**
         * 开始时间
         */
        public int beginTime;
    
        /**
         * 结束时间
         */
        public int finishTime;
        /**
         * 优先权
         */
        public float priority;
    
        public JCB(int id, int serviceTime, int arriveTime,float priority) {
            this.id = id;
            this.leftTime = serviceTime;
            this.serviceTime = serviceTime;
            this.arriveTime = arriveTime;
            beginTime =0;
            this.priority=priority;
            finishTime=0;
        }
    
    
    
        @Override
        public String toString() {
            return "JCB{" +
                    "id=" + id +
                    ", serviceTime=" + serviceTime +
                    ", arriveTime=" + arriveTime +
                    ", priority=" + priority +
                    '}';
        }
    }
    
    

    二、定义所需数据结构

    /**
     * 时间片轮转算法
     *
     * @author MaoLin Wang
     * @date 2019/11/3020:03
     */
    public class SchedulingAlgorithm {
        /**
         * 就绪队列
         */
        LinkedList<JCB> readyQueue = null;
        /**
         * 结束调度队列
         */
        LinkedList<JCB> finishQueue = null;
    
        /**
         * 时间段
         */
        private int cpuTime;
    
        /**
         * 时间片大小
         */
        private int timeSize;
    
        /**
         * 作业数
         */
        private int jobNum;
    
        private String dispatchName;//调度算法名
    
        /**
         * 作业周转时间
         */
        private int[] turnoverTime;
        /**
         * 作业带权周转时间·
         */
        private float[] turnoverTimeWithWeight;
    
        /**
         * 平均带权周转时间
         */
        private float ave;
    }
    

    三、初始化

    这里将最高响应比的初始化拉了出来,因为要设置响应比

     /**
         * 初始化
         */
        public void init(int jobNum, int timeSize, String dispatchName) {
            System.out.println("开始" + dispatchName + "调度");
            readyQueue = new LinkedList<>();
            finishQueue = new LinkedList<>();
            this.turnoverTime = new int[jobNum];
            this.turnoverTimeWithWeight = new float[jobNum];
            this.cpuTime = 0;
            JCB jcb;
            for (int i = 1; i <= jobNum; i++) {
                jcb = new JCB(i, (int) (Math.random() * 10 + 1), i - 1, 0);
                readyQueue.offer(jcb);
            }
            this.timeSize = timeSize;
            this.jobNum = jobNum;
            this.dispatchName = dispatchName;
            printInitQueue();
        }
    
        /**
         * 初始化高响应比优先队列
         *
         * @param jobNum
         * @param timeSize
         * @param dispatchName
         */
        public void HRNInit(int jobNum, int timeSize, String dispatchName) {
            System.out.println("开始" + dispatchName + "调度");
            readyQueue = new LinkedList<>();
            finishQueue = new LinkedList<>();
            this.turnoverTime = new int[jobNum];
            this.turnoverTimeWithWeight = new float[jobNum];
            this.cpuTime = 0;
            JCB jcb;
            for (int i = 1; i <= jobNum; i++) {
                float v = (float) (Math.random() * 5 + 1);
                jcb = new JCB(i, (int) (Math.random() * 10 + 1), i - 1, (float) (Math.random() * 5 + 1));
                readyQueue.offer(jcb);
            }
            this.timeSize = timeSize;
            this.jobNum = jobNum;
            this.dispatchName = dispatchName;
            printInitQueue();
        }
    
    

    作业id默认为序号i,所需服务时间随机生成,到达时间默认从0开始,响应比其他调度算法为0,高响应比算法为随机生成。

    四、高响应比优先算法实现

    逻辑很简单,使用递归实现,参数初始为0,每次取出对头作业,因为这里所有的作业在初始化时数据都初始化好了,所以需判断作业到达时间是否小于cpu时间片,因为只有小于时间片,说明其实际是到达的。
    如果小于,则设置其开始时间为cpu当前时间,结束时间为开始时间+服务时间,剩余时间设为0,同时增加cpu时间,将该作业加入已完成队列中,否则,递归调用该算法,参数为index+1,一轮结束后,对作业按响应比排序,继续递归,知道就绪队列为空。

    
         /**
         * 最高响应比优先算法
         */
        public void HRNAlgorithm(int index) {
            if (readyQueue.size() == 0) {
                System.out.println("就绪队列为空,调度完毕!");
                return;
            }
            JCB head = readyQueue.get(index);
            if (head.arriveTime <= cpuTime) {
                readyQueue.poll();
                System.out.println("-----------------------------------------------------");
                System.out.println("时间片: " + cpuTime + "开始调度作业:" + head.id + ", 剩余服务时间: " + head.leftTime);
                head.beginTime = cpuTime;
                head.finishTime = head.beginTime + head.serviceTime;
                head.leftTime = 0;
                cpuTime += head.serviceTime;
                finishQueue.offer(head);
                System.out.println("时间片: " + cpuTime + "结束调度作业:" + head.id + ", 剩余服务时间: " + head.leftTime);
    
            } else {
                HRNAlgorithm(index++);
            }
            sortByPriority();
            HRNAlgorithm(0);
        }
    
        /**
         * 根据响应比排序
         */
        private void sortByPriority() {
            readyQueue.sort((o1, o2) -> o1.priority > o2.priority ? -1 : 1);
        }
    

    五、短作业优先调度算法

    同高响应比优先类似,只是按照要求服务时间排序。

     /**
         * 短作业优先调度算法
         */
        public void SJFAlgorithm(int index) {
            if (readyQueue.size() == 0) {
                System.out.println("就绪队列为空,调度完毕!");
                return;
            }
            JCB head = readyQueue.get(index);
            if (head.arriveTime <= cpuTime) {
                readyQueue.poll();
                System.out.println("-----------------------------------------------------");
                System.out.println("时间片: " + cpuTime + "开始调度作业:" + head.id + ", 剩余服务时间: " + head.leftTime);
                head.beginTime = cpuTime;
                head.finishTime = head.beginTime + head.serviceTime;
                head.leftTime = 0;
                cpuTime += head.serviceTime;
                finishQueue.offer(head);
                System.out.println("时间片: " + cpuTime + "结束调度作业:" + head.id + ", 剩余服务时间: " + head.leftTime);
    
            } else {
                sortByServiceTime();
                SJFAlgorithm(index++);
            }
    
            sortByServiceTime();
            SJFAlgorithm(0);
        }
    
    
        /**
         * 根据要求服务时间从小到大排序
         */
        private void sortByServiceTime() {
            readyQueue.sort((o1, o2) -> o1.serviceTime < o2.serviceTime ? -1 : 1);
        }
    

    六、先来先服务

    最简单的一个算法,直接按顺序取出队头作业执行。

      /**
         * 先来先服务调度算法
         */
        public void FCFSAlgorithm() {
            if (readyQueue.size() == 0) {
                System.out.println("就绪队列为空,调度完毕!");
                return;
            }
            JCB head = readyQueue.poll();
            System.out.println("-----------------------------------------------------");
            System.out.println("时间片: " + cpuTime + "开始调度作业:" + head.id + ", 剩余服务时间: " + head.leftTime);
    
            head.beginTime = cpuTime;
            head.leftTime = 0;
            head.finishTime = head.beginTime + head.serviceTime;
            cpuTime += head.serviceTime;
            finishQueue.offer(head);
            System.out.println("时间片: " + cpuTime + "结束调度作业:" + head.id + ", 剩余服务时间: " + head.leftTime);
    
            FCFSAlgorithm();
    
        }
    

    七、时间片轮转算法

    这里需要根据作业剩余需要服务的时间跟时间片大小做对比,代码很好理解。

     /**
         * 时间片轮转算法
         */
        public void RRAlgorithm() {
            if (readyQueue.size() == 0) {
                System.out.println("就绪队列为空,调度完毕!");
                return;
            }
            JCB head = readyQueue.poll();
            System.out.println("-----------------------------------------------------");
            System.out.println("时间片: " + cpuTime + "开始调度作业:" + head.id + ", 剩余服务时间: " + head.leftTime);
            head.beginTime = cpuTime;
            if (head.leftTime > timeSize) {
                //服务时间大于时间片大小
                head.leftTime -= timeSize;
                //重新加入到就绪队列尾部
                readyQueue.offer(head);
                cpuTime += timeSize;
    
            } else if (head.leftTime == timeSize) {
                //服务时间等于时间片大小
                cpuTime += timeSize;
                head.finishTime = cpuTime;
                head.leftTime = 0;
                //加入结束队列
                finishQueue.offer(head);
            } else {
                //服务时间小于时间片大小
                head.finishTime = cpuTime + head.leftTime;
                head.leftTime = 0;
                cpuTime += head.leftTime;
                finishQueue.offer(head);
            }
            System.out.println("时间片: " + cpuTime + "结束调度作业:" + head.id + ", 剩余服务时间: " + head.leftTime);
            RRAlgorithm();
        }
    

    八、计算周转时间和带权周转时间

    /**
         * 计算周转时间和带权周转时间
         * @param finishQueue
         */
        public void R_Dis(Queue<JCB> finishQueue) {
            Queue<JCB>temp=finishQueue;
            JCB tempJcb;
            float sum = 0;
            for (int i = 0; i < jobNum; i++) {
                tempJcb=temp.poll();
                turnoverTime[i] = tempJcb.finishTime - tempJcb.arriveTime;
                turnoverTimeWithWeight[i] =(float) turnoverTime[i] / tempJcb.serviceTime;
                sum += turnoverTimeWithWeight[i];
                temp.offer(tempJcb);
            }
            float ave = sum / jobNum;
    
            this.ave = ave;
        }
    

    九、打印结果

    public void printResult(boolean isHRN) {
            R_Dis(this.finishQueue);
            System.out.println("=====================" + this.dispatchName + "调度结果为=========================");
            if (isHRN) {
    
                System.out.println("进程名\t" + "到达时间\t" + "要求服务时间\t" + "响应比\t" + "开始时间\t" + "完成时间\t" + "周转时间\t" + "带权周转时间\t"+"平均带权周转时间\t");
            } else {
    
                System.out.println("进程名\t" + "到达时间\t" + "要求服务时间\t" + "开始时间\t" + "完成时间\t" + "周转时间\t" + "带权周转时间\t"+"平均带权周转时间\t");
            }
            int count = 0;
    
            for (JCB jcb : this.finishQueue) {
                if (isHRN) {
                    System.out.println("  " + jcb.id + "\t\t\t" + jcb.arriveTime + "\t\t" + jcb.serviceTime + "\t\t" + jcb.priority + "\t\t" + jcb.beginTime + "\t\t"
                            + jcb.finishTime + "\t\t" + turnoverTime[count] + "\t\t" + turnoverTimeWithWeight[count]+"\t\t"+this.ave);
                    count = count + 1;
                } else {
                    System.out.println("  " + jcb.id + "\t\t\t" + jcb.arriveTime + "\t\t" + jcb.serviceTime + "\t\t" + jcb.beginTime + "\t\t"
                            + jcb.finishTime + "\t\t" + turnoverTime[count] + "\t\t" + turnoverTimeWithWeight[count]+"\t\t"+this.ave);
                    count = count + 1;
                }
    
            }
        }
    
    
        /**
         * 打印初始化队列
         */
        private void printInitQueue() {
            System.out.println("当前就绪队列为:");
            for (JCB jcb2 : readyQueue) {
                System.out.println(jcb2);
            }
        }
    

    测试

    public class Test {
        public static void main(String[] args) {
            SchedulingAlgorithm schedulingAlgorithm = new SchedulingAlgorithm();
            schedulingAlgorithm.init(5, 2,"轮转");
            schedulingAlgorithm.RRAlgorithm();
            schedulingAlgorithm.printResult(false);
    
            schedulingAlgorithm.init(5,3,"先来先服务");
            schedulingAlgorithm.FCFSAlgorithm();
            schedulingAlgorithm.printResult(false);
    
            schedulingAlgorithm.init(5,3,"短作业优先服务");
            schedulingAlgorithm.SJFAlgorithm(0);
            schedulingAlgorithm.printResult(false);
    
            schedulingAlgorithm.HRNInit(5,3,"高响应比优先");
            schedulingAlgorithm.HRNAlgorithm(0);
            schedulingAlgorithm.printResult(true);
    
    
    
        }
    }
    

    结果:

    开始轮转调度
    当前就绪队列为:
    JCB{id=1, serviceTime=1, arriveTime=0, priority=0.0}
    JCB{id=2, serviceTime=5, arriveTime=1, priority=0.0}
    JCB{id=3, serviceTime=4, arriveTime=2, priority=0.0}
    JCB{id=4, serviceTime=6, arriveTime=3, priority=0.0}
    JCB{id=5, serviceTime=6, arriveTime=4, priority=0.0}
    -----------------------------------------------------
    时间片: 0开始调度作业:1, 剩余服务时间: 1
    时间片: 0结束调度作业:1, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 0开始调度作业:2, 剩余服务时间: 5
    时间片: 2结束调度作业:2, 剩余服务时间: 3
    -----------------------------------------------------
    时间片: 2开始调度作业:3, 剩余服务时间: 4
    时间片: 4结束调度作业:3, 剩余服务时间: 2
    -----------------------------------------------------
    时间片: 4开始调度作业:4, 剩余服务时间: 6
    时间片: 6结束调度作业:4, 剩余服务时间: 4
    -----------------------------------------------------
    时间片: 6开始调度作业:5, 剩余服务时间: 6
    时间片: 8结束调度作业:5, 剩余服务时间: 4
    -----------------------------------------------------
    时间片: 8开始调度作业:2, 剩余服务时间: 3
    时间片: 10结束调度作业:2, 剩余服务时间: 1
    -----------------------------------------------------
    时间片: 10开始调度作业:3, 剩余服务时间: 2
    时间片: 12结束调度作业:3, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 12开始调度作业:4, 剩余服务时间: 4
    时间片: 14结束调度作业:4, 剩余服务时间: 2
    -----------------------------------------------------
    时间片: 14开始调度作业:5, 剩余服务时间: 4
    时间片: 16结束调度作业:5, 剩余服务时间: 2
    -----------------------------------------------------
    时间片: 16开始调度作业:2, 剩余服务时间: 1
    时间片: 16结束调度作业:2, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 16开始调度作业:4, 剩余服务时间: 2
    时间片: 18结束调度作业:4, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 18开始调度作业:5, 剩余服务时间: 2
    时间片: 20结束调度作业:5, 剩余服务时间: 0
    就绪队列为空,调度完毕!
    =====================轮转调度结果为=========================
    进程名	到达时间	要求服务时间	开始时间	完成时间	周转时间	带权周转时间	平均带权周转时间	
      1			0		1		0		1		1		1.0		2.3733335
      3			2		4		10		12		10		2.5		2.3733335
      2			1		5		16		17		16		3.2		2.3733335
      4			3		6		16		18		15		2.5		2.3733335
      5			4		6		18		20		16		2.6666667		2.3733335
    开始先来先服务调度
    当前就绪队列为:
    JCB{id=1, serviceTime=3, arriveTime=0, priority=0.0}
    JCB{id=2, serviceTime=10, arriveTime=1, priority=0.0}
    JCB{id=3, serviceTime=7, arriveTime=2, priority=0.0}
    JCB{id=4, serviceTime=1, arriveTime=3, priority=0.0}
    JCB{id=5, serviceTime=1, arriveTime=4, priority=0.0}
    -----------------------------------------------------
    时间片: 0开始调度作业:1, 剩余服务时间: 3
    时间片: 3结束调度作业:1, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 3开始调度作业:2, 剩余服务时间: 10
    时间片: 13结束调度作业:2, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 13开始调度作业:3, 剩余服务时间: 7
    时间片: 20结束调度作业:3, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 20开始调度作业:4, 剩余服务时间: 1
    时间片: 21结束调度作业:4, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 21开始调度作业:5, 剩余服务时间: 1
    时间片: 22结束调度作业:5, 剩余服务时间: 0
    就绪队列为空,调度完毕!
    =====================先来先服务调度结果为=========================
    进程名	到达时间	要求服务时间	开始时间	完成时间	周转时间	带权周转时间	平均带权周转时间	
      1			0		3		0		3		3		1.0		8.154286
      2			1		10		3		13		12		1.2		8.154286
      3			2		7		13		20		18		2.5714285		8.154286
      4			3		1		20		21		18		18.0		8.154286
      5			4		1		21		22		18		18.0		8.154286
    开始短作业优先服务调度
    当前就绪队列为:
    JCB{id=1, serviceTime=8, arriveTime=0, priority=0.0}
    JCB{id=2, serviceTime=10, arriveTime=1, priority=0.0}
    JCB{id=3, serviceTime=1, arriveTime=2, priority=0.0}
    JCB{id=4, serviceTime=10, arriveTime=3, priority=0.0}
    JCB{id=5, serviceTime=1, arriveTime=4, priority=0.0}
    -----------------------------------------------------
    时间片: 0开始调度作业:1, 剩余服务时间: 8
    时间片: 8结束调度作业:1, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 8开始调度作业:3, 剩余服务时间: 1
    时间片: 9结束调度作业:3, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 9开始调度作业:5, 剩余服务时间: 1
    时间片: 10结束调度作业:5, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 10开始调度作业:2, 剩余服务时间: 10
    时间片: 20结束调度作业:2, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 20开始调度作业:4, 剩余服务时间: 10
    时间片: 30结束调度作业:4, 剩余服务时间: 0
    就绪队列为空,调度完毕!
    =====================短作业优先服务调度结果为=========================
    进程名	到达时间	要求服务时间	开始时间	完成时间	周转时间	带权周转时间	平均带权周转时间	
      1			0		8		0		8		8		1.0		3.72
      3			2		1		8		9		7		7.0		3.72
      5			4		1		9		10		6		6.0		3.72
      2			1		10		10		20		19		1.9		3.72
      4			3		10		20		30		27		2.7		3.72
    开始高响应比优先调度
    当前就绪队列为:
    JCB{id=1, serviceTime=1, arriveTime=0, priority=5.41018}
    JCB{id=2, serviceTime=6, arriveTime=1, priority=5.1338425}
    JCB{id=3, serviceTime=6, arriveTime=2, priority=3.1670618}
    JCB{id=4, serviceTime=6, arriveTime=3, priority=2.0463989}
    JCB{id=5, serviceTime=1, arriveTime=4, priority=4.711568}
    -----------------------------------------------------
    时间片: 0开始调度作业:1, 剩余服务时间: 1
    时间片: 1结束调度作业:1, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 1开始调度作业:2, 剩余服务时间: 6
    时间片: 7结束调度作业:2, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 7开始调度作业:5, 剩余服务时间: 1
    时间片: 8结束调度作业:5, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 8开始调度作业:3, 剩余服务时间: 6
    时间片: 14结束调度作业:3, 剩余服务时间: 0
    -----------------------------------------------------
    时间片: 14开始调度作业:4, 剩余服务时间: 6
    时间片: 20结束调度作业:4, 剩余服务时间: 0
    就绪队列为空,调度完毕!
    =====================高响应比优先调度结果为=========================
    进程名	到达时间	要求服务时间	响应比	开始时间	完成时间	周转时间	带权周转时间	平均带权周转时间	
      1			0		1		5.41018		0		1		1		1.0		2.1666665
      2			1		6		5.1338425		1		7		6		1.0		2.1666665
      5			4		1		4.711568		7		8		4		4.0		2.1666665
      3			2		6		3.1670618		8		14		12		2.0		2.1666665
      4			3		6		2.0463989		14		20		17		2.8333333		2.1666665
    
    展开全文
  • 最高响应比优先算法

    2017-12-16 16:26:26
    本文件是对操作系统作业调度算法中的最高响应比优先算法的设计与实现,代码和报告都放在了压缩文件中,代码使用的文件输入输出。
  • 0)个作业,输入每个作业的名字,到达时间,服务时间,按照高响应比优先算法,计算每个作业的完成时间,周转时间,带权周转时间(保留2位小数)。 输入格式: 第一行输入作业数目,第二行输入作业的名字,第三行输入...
  • 主要参考链接: 代码绝大多数都是从网上拷下来再自己改了一点。本来想附上参考链接,但时间有点久,找不到主要参考的那个连接。 [声明]本文为转载是因为代码大多数都是网上copy的,然后自己也...1.进程调度算法...
  • 代码块: import java.util.Arrays; import java.util.Scanner; public class OS3 { static class HomeWork{ private String name; private int ArrivalTime; private int ServiceTime; private int ...
  • 本次试验是使用程序来模拟操作系统中进程调度的三种不同的调度策略,分别为最短作业有限、时间片轮转、最高响应比。 模拟的情况下,进程数为8,进程所需执行时间为随机产生的整数,单位为1S,默认进程同时到达。 ...
  • Java模拟最短作业优先、时间片轮转、最高响应比和先来先服务进程调度算法 rar中有四种算法和俩个对进程用时和周转时间制图的java源代码,另外有jcommon-1.0.23.jar和jfreechart-1.0.19.jar俩个制图包
  • 设计要求(多道、单处理机): 1) 每一个进程有一个PCB,其内容可以...6) 采用可视化界面,可在进程调度过程中随时暂停调度,查看当前进程的状态以及相应的阻塞队列 7) 具有一定的数据容错性 有些代码需要自己适当改下
  • 进程调度算法模拟 本次操作系统试验是使用程序来模拟操作系统中进程调度的不同的调度策略,分别为FIFO先进先出,SJF最短时间优先,RR时间片轮换以及HRRN最高响应比算法。 模拟的情况下,进程数为8,进程所需执行时间...
  • 先来先服务(FCFS) 短作业(SJF) 高响应比优先(HRRN)
  • 操作系统最高响应比优先进程调度算法的实现 代码绝对可直接运行 欢迎大家加以改进分享 内附运行结果图片
  • 具体的要求是这样的:编写程序完成批处理系统中的作业调度,要求采用响应比高者优先的作业调度算法。实验具体包括:首先确定作业控制块的内容,作业控制块的组成方式;然后完成作业调度;最后编写主函数对所作工作...
  • 银行家算法 分页管理 模拟处理机调度算法 高响应比优先调度算法
  • 操作系统四种调度算法

    千次阅读 2019-03-31 18:09:47
    一、 实验目的: ...3、 实现 非抢占式高响应比优先调度算法 4、 实现 抢占式高响应比优先调度算法 三、实验代码 实验全部代码见附件code.txt 实验的主要代码如下: //进程结构体 struct Task { char name[10...
  • 处理机调度常用的算法有:先来先服务算法,高响应比优先算法,时间片轮转算法和短作业优先调度算法。本次课程设计就将模拟先来先服务,时间片轮转,短作业优先,高响应比优先4种调度算法,并对他们的性能进行比较。
  • 编写程序模拟进程调度过程,能够按照时间片轮转,短进程优先法,可抢占式和不可抢占式优先级法,以及先来先服务和高响应比优先法处理输入的数据,运行结果包含界面。
  • 处理机调度算法:Highest Response Ratio Next 运行结果 流程图 ---------------------java代码------------------------ ... * 高响应比优先 * 非抢占式 (完成) * @author ymj * @Date: 2019...
  • 文章目录什么是作业调度什么是进程调度FCFS(先来先服务调度算法)SJF(短作业优先调度算法)HRRN(高响应比优先调度算法)优先级调度算法RR(时间片轮转调度算法)多级反馈队列调度算法代码分析节点代码创建与检查节点...
  • 调度算法实验

    2018-06-13 01:14:16
    4种调度算法(先来先服务、短作业优先高响应比、时间片轮转),含代码和分析以及运行结果
  • (1)能够选择进程调度算法(先来先服务、短进程优先算法和高响应比优先算法)。 (2)可以输入进程数目(至少4个进程),以及各进程的提交时间和运行时间。 (3)能够以图表形式显示调度过程及平均周转时间和平均...
  • 能够选择进程调度算法(先来先服务、短进程优先算法和高响应比优先算法)。可以输入进程数目(至少4个进程),以及各进程的提交时间和运行时间。能够以图表形式显示调度过程及平均周转时间和平均带权周转时间。
  • 通过设计先来先服务调度算法、短作业优先调度算法高响应比调度算法,模拟多个进程调度方式,进一步理解先来先服务和短作业优先调度算法的实质,掌握周转时间、带权周转时间以及动态优先级等基本概念,并对三种算法...
  • 操作系统实验(作业调度算法源代码),包含3种算法:先来先服务、最高响应比和短作业优先,包含实验报告。
  • 高响应比优先调度算法(HRRN) 源代码 Process class package com.company.schedulingalgorithm; /** * @author hudongsheng * @date 2020/12/14 - 20:25 */ public class Process { //进程名 private

空空如也

空空如也

1 2 3
收藏数 58
精华内容 23
关键字:

高响应比优先调度算法代码