操作系统课程设计报告-进程调度算法模拟.doc

操作系统原理及应用课程设计报告进程调度算法模拟 学院（系）： 计算机科学与工程学院 班 级：学号11403070 学生姓名： 同组人员： 时间： 从 2016年 12 月27日 到 2017 年01月03日1课程设计的目的操作系统原理课程设计我们专业实践性环节之一，是学习完操作系统原理课程后进行的一次较全面的综合练习。其目的在于加深对操作系统的理论、方法和基础知识的理解，掌握操作系统结构、实现机理和各种典型算法，系统地了解操作系统的设计和实现思路，培养学生的系统设计能力，并了解操作系统的发展动向和趋势。2课程设计的内容及要求先来先服务、短作业优先、时间片轮转、基于静态优先级的调度，基于高响应比优先的动态优先级调度算法实现，能够输出调度情况，并计算周转时间和平均周转时间。要求使用链表，进程个数由用户提供，按照进程的实际个数生成PCB，程序能够让用户选择使用哪种调度算法，能够在Linux环境运行并验证结果。程序要考虑用户界面的友好性和使用方便性。进程基本信息可从文件读入，也可手动输入。3、设计原理3.1先来先服务调度算法每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源创建进程，然后放入就绪队列 3.2短作业优先调度算法 短作业优先调度算法是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。 3.3时间片轮转调度算法 系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。 3.4静态优先级调度算法 把处理机分配给优先级最高的进程，使之执行。但在其执行期间，只要出现了另一个比其优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。这样就可以保证紧迫性作业优先运行。 3.5最高响应比优先的动态优先级调度算法 优先权调度算法是为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入最高优先权优先调度算法。动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。4设计说明4.1结构设计(1) 菜单选择模块。选择相应的进程调度方式，选择相应的数字，进入相应的功能。(2) 调度算法模块。选择相应的进程调度算法。(3) 显现输出模块。显示每种进程调度算法情况。(4) 平均周转时间与平均带权周转时间的计算结果。(5) 退出系统模块。4.2功能设计（1）菜单选择模块 设计方案：首先将各种进程调度算法放入不同的头文件，在主函数引用，是系统结构更加清晰。 实现方法：设置一个menu()方法，让用户选择不同的进程调度算法，menu()方法返回一个char类型字符，以便在主函数的switch语句中选择调用不同的进程调度方法。（2）调度算法模块 A、先来先服务调度算法 设计方案：对于先到达的进程优先分配CPU，按照先来先服务的原则依次执行各进程。 实现方法：每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源创建进程，然后放入就绪队列 B、短作业优先调度算法 设计方案：短作业优先调度算法是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。 实现方法：先找到运行时间最短的程序，然后执行，再从剩余的程序中找到运行时间最短的在执行，依次每次都执行运行时间最短的，直到程序执行完毕。C、时间片轮转调度算法 设计方案：系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。 实现方法：按照轮转的次序分配给每个程序一定的时间执行，执行完成后执行后面的进程 ，依次循环执行直到所有进程执行完成。D、静态优先级调度算法 设计方案：把处理机分配给优先级最高的进程，使之执行。但在其执行期间，只要出现了另一个比其优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。这样就可以保证紧迫性作业优先运行。 实现方法：按照优先级从高到低依次执行程序。E、最高响应比优先的动态优先级调度算法 设计方案：优先权调度算法是为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入最高优先权优先调度算法。动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。 实现方法：按照优先级从高到低依次执行程序。（3）平均周转时间与平均带权周转时间的计算 设计方案：周转时间=完成时间-到达时间 带权周转时间=周转时间/服务时间平均周转时间=总的周转时间/进程个数平均带权周转时间=总的带权周转时间/进程个数 实现方法：系统自行根据程序及输入的数据计算出平均周转时间和平均带权周转时4.3程序中使用的数据结构及使用的变量说明和作用 （1）结构体/*先来先服务调度算法结构体*/struct fcfs char name10; /作业名float arrivetime; /作业到达时间float servicetime; /作业服务时间float starttime; /作业开始时间float finishtime; /作业完成时间float zztime; /周转时间float dqzztime; /带权周转时间; /*短作业优先调度算法结构体*/struct jcb /作业控制块JCB,定义为结构体 char name10; /作业名 float arrivetime; /作业到达时间 float servicetime;/作业服务时间 float starttime; /作业开始时间 float finishtime; /作业完成时间 float zztime; /周转时间 float dqzztime; /带权周转时间;/*时间片轮转调度算法结构体*/struct rr /定义时间片轮转调度算法结构体，里面包含得有一个进程相关的信息char name10; /作业名float arrivetime; /作业到达时间float servicetime; /作业服务时间float starttime; /作业开始时间float finishtime; /作业结束时间 float zztime; /作业周转时间float dqzztime; /作业带权周转时间float avzztime;/作业平均周转时间 float avdqzztime;/作业平均带权周转时间 float lefttime; /剩余时间float stoptime;/停止时间int timeprice;/时间片设置的大小;/*静态优先级调度算法结构体*/struct sp char name10; /作业号float arrivetime; /作业到达时间float servicetime; /服务时间float waittime; /等待时间float starttime; /开始运行时间float finishtime; /结束运行时间float zztime; /周转时间float dqzztime; /带权周转时间float priority; /优先权float finish; /是否已经完成sta10;/作业控制块，这是一个结构体数组/*最高响应比调度算法结构体*/struct task char name10; /作业号float arrivetime; /作业到达时间float servicetime; /服务时间float waittime; /等待时间float starttime; /开始运行时间float finishtime; /结束运行时间float zztime; /周转时间float dqzztime; /带权周转时间float priority; /优先权float finish; /是否已经完成JCB10;/作业控制块，这是一个结构体数组（2）基本变量char name10; /作业名float arrivetime; /作业到达时间float servicetime; /作业服务时间float starttime; /作业开始时间float finishtime; /作业完成时间float zztime; /周转时间float dqzztime; /带权周转时间float avzztime;/作业平均周转时间 float avdqzztime;/作业平均带权周转时间 float lefttime; /剩余时间float stoptime;/停止时间int timeprice;/时间片设置的大小float priority; /优先权float finish; /是否已经完成5具体实现5.1菜单选择模块（1）功能说明按照工作台提示，选择调度算法。（2）函数实现过程清屏 清空缓存设计菜单用户输入选择返回用户输入选择（3）关键程序char Menu()/用来输出相关信息的函数 char choice;/用户选择while(1)system(cls);/清屏fflush(stdin);/清空缓存coutendl; coutendl; coutendl; coutendl; coutt t*进程调度算法模拟*tt endl;coutt endl;coutt t*t 1.先来先服务调度算法 t*t endl;coutt endl;coutt t*t 2.短作业优先调度算法 t*t endl;coutt endl;coutt t*t 3.时间片轮转调度算法tt*t endl; coutt endl;coutt t*t 4.静态优先级调度算法tt*t endl; coutt endl;coutt t*t 5.最高响应比优先调度算法 t*t endl; coutt endl;coutt t*t 0.退出系统 t*t endl; coutt t*tt endl;coutendl;couttt 请输入您的选择(0/1/2/3/4/5)：endl;choice=getchar();if(choice5)/若输入有误coutendl; cout您的输入有误!请重新输入正确的字符! endl; coutendl; system(PAUSE);/输出“按任意键继续”，等待用户按一个键，然后返回主菜单elsebreak;return choice;5.2调度算法模块（1）先来先服务调度算法 a、功能说明按照先来先服务原则调度用户输入的进程 b、函数实现过程输入进程数目 输入进程的基本信息（名字、到达时间、服务时间）按照进程到达时间按冒泡排序法排序作业运行，按先来先服务原则处理选择最先进入的作业，记录各类时间 记录各个进程的周转时间和带权周转时间计算平均周转时间和平均带权周转时间输出调度结果和计算结果到屏幕先来先服务调度算法至此结束 c、关键程序void DealByFCFS(fcfs *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N)/运行阶段,根据先来先服务的原则进行处理 int k; for(k=0;k=N-1;k+) if(k=0)/进程个数为1 pk.starttime=pk.arrivetime;/开始时间=到达时间 pk.finishtime=pk.arrivetime+pk.servicetime;/完成时间=到达时间+服务时间 else pk.starttime=pk-1.finishtime;/开始时间=前一个作业的完成时间 pk.finishtime=pk-1.finishtime+pk.servicetime;/完成时间=前一个作业的完成时间+服务时间 for(k=0;k=N-1;k+) pk.zztime=pk.finishtime-pk.arrivetime; /周转时间=完成时间-到达时间 pk.dqzztime=pk.zztime/pk.servicetime; /带权周转时间=周转时间/服务时间 void FCFS(fcfs *p,int N) float sumzztime=0, sumdqzztime=0, avzztime, avdqzztime;/总的周转时间、总的带权周转时间、平均周转时间、平均带权周转时间 float arrivetime=0, servicetime=0, starttime=0, finishtime=0, zztime=0, dqzztime=0; Sort(p,N);/按进程的到达时间进行排序（参数为存放进程的数组和进程个数） DealByFCFS(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);/运行阶段,根据先来先服务的原则进行处理 Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); /屏幕输出处理 for(int k=0; k=N-1; k+) sumzztime=sumzztime+pk.zztime;/总的周转时间=前一个作业的周转时间+本次作业的周转时间（循环加） sumdqzztime=sumdqzztime+ pk.dqzztime;/总的带权周转时间=前一个作业的带权周转时间+本次作业的带权周转时间（循环加） avzztime=sumzztime/N;/平均周转时间=总的周转时间/进程个数 printf(* *n); printf(*该算法的平均周转时间为:%-.2ft,avzztime); avdqzztime= sumdqzztime/N; /平均带权周转时间=总的带权周转时间/进程个数 printf(该算法的平均带权周转时间为:%-.2ft *,avdqzztime); printf(n*n ); （2）短作业优先调度算法 a、功能说明按照短作业优先原则调度用户输入的进程 b、函数实现过程输入作业数目 输入作业的基本信息（名字、到达时间、服务时间）按照进程到达时间按冒泡排序法排序找出到达时间在上一个作业完成之前的作业，并统计数目规定一个最短作业min，再将其后作业与之比较 找出真正最短作业，进行作业调度记录各类时间记录各个进程的周转时间和带权周转时间计算平均周转时间和平均带权周转时间输出调度结果和计算结果到屏幕短作业优先调度算法至此结束 c、关键程序void DealBySJF(jcb *p,float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N) /按短作业优先原则进行进程服务处理 int k; for(k=0; k=N-1; k+) if(k=0)/进程个数为1 pk.starttime=pk.arrivetime; /开始时间=到达时间 pk.finishtime=pk.arrivetime+pk.servicetime;/完成时间=到达时间+服务时间 else pk.starttime=pk-1.finishtime; /开始时间=前一个作业的完成时间 pk.finishtime=pk-1.finishtime+pk.servicetime; /完成时间=前一个作业的完成时间+服务时间 for(k=0; k=N-1; k+) pk.zztime=pk.finishtime-pk.arrivetime;/周转时间=完成时间-到达时间 pk.dqzztime=pk.zztime/pk.servicetime;/带权周转时间=周转时间/服务时间 void SJF(jcb *p,int N) /短作业优先调度算法处理过程 float sumzztime=0, sumdqzztime=0,avzztime,avdqzztime;/总的周转时间、总的带权周转时间、平均周转时间、平均带权周转时间float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;Sort(p,N); /按进程的到达时间进行排序（参数为存放作业的数组和作业个数） for(int m=0; mN-1; m+) if(m=0) /进程个数为0 pm.finishtime=pm.arrivetime+pm.servicetime; /完成时间=到达时间+服务时间 else pm.finishtime=pm-1.finishtime+pm.servicetime; /完成时间=前一个作业的完成时间+服务时间 int i=0; for(int n=m+1;n=N-1;n+) if(pn.arrivetime=pm.finishtime) /找出服务时间较短的作业的个数i i+; float min=pm+1.servicetime;/min为服务时间最短的作业，先将服务时间较短的作业队列中的第一个付给min int next=m+1;/m+1=n ，next为服务时间最短的作业序号 for(int k=m+1;km+i;k+) /在i个服务时间较短的作业队列中找出服务时间最短的作业 if(pk+1.servicetimemin) /再从剩余的作业中找出运行时间最短的，从队列中第二个作业开始比较 min=pk+1.servicetime; /第k+1个作业为新的服务时间最短的作业 next=k+1; jcb temp; /第m+1个作业的服务时间小于第k+1个，所以交换顺序temp=pm+1; pm+1=pnext; pnext=temp; /找到了服务时间最短的作业后 DealBySJF(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);/按短作业优先原则进行进程服务处理 Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);/屏幕输出处理 for(int k=0; k=N-1; k+) sumzztime=sumzztime+pk.zztime;/总的周转时间=前一个作业的周转时间+本次作业的周转时间（循环加） sumdqzztime=sumdqzztime+ pk.dqzztime;/总的带权周转时间=前一个作业的带权周转时间+本次作业的带权周转时间（循环加） avzztime=sumzztime/N;/平均周转时间=总的周转时间/进程个数 printf(* *n); printf(*该算法的平均周转时间为:%-.2ft,avzztime); avdqzztime= sumdqzztime/N; /平均带权周转时间=总的带权周转时间/进程个数 printf(该算法的平均带权周转时间为:%-.2ft *,avdqzztime); printf(n*n ); getchar();/此处必须要有这个函数，否则就看不到显示器上面的输出，可以看到的结果只是一闪而过的一个框剪 （3）时间片轮转调度算法 a、功能说明按照时间片轮转原则调度用户输入的进程 b、函数实现过程输入作业数目 输入作业的基本信息（名字、到达时间、服务时间）设置时间片大小timeprice按先来先服务原则将就绪进程排列成一个队列调度队首进程，并令其执行一个时间片 判断是否有剩余时间，记录停止时间将执行过的进程调往就绪队列末尾，继续下一轮调度，直至所有作业调度完毕记录各类时间记录各个进程的周转时间和带权周转时间计算平均周转时间和平均带权周转时间输出调度结果和计算结果到屏幕时间片轮转调度算法至此结束 c、关键程序void Print(rr *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N) /屏幕打印输出处理int k; printf(*调用时间片轮转调度算法以后进程的调度顺序是: ); /输出进程调度顺序 printf(%s,); /输出第一个 for(k=1;k%s,); /输出第2到第N coutendl; printf(*具体的进程调度信息: *n); printf(* *n); printf(* 进程名 到达时间 服务时间 开始时间 结束时间 周转时间 带权周转时间 *n); for(k=0;ktimeprice;Sort(p,N);/按进程的到达时间排序float d20,h20;/分别用在服务时间和开始时间for(int k=0; k0)/剩余时间0（服务时间时间片大小）c=c+1;/记录还未执行完的作业个数 pk.stoptime=pk.starttime+timeprice;/停止时间=开始时间+时间片大小 pk.finishtime=pk.stoptime;/完成时间=停止时间 else/剩余时间=0（服务时间=时间片大小） pk.stoptime=pk.finishtime;/停止时间=完成时间 w=pk.stoptime;/记录作业的停止时间printf(n*结果如下*n); printf(*第1轮进程调度信息: *n); printf(* *n); printf(* 进程名 到达时间 服务时间 开始时间 停止时间 剩余时间 *n); for(k=0; k0)/还有未执行完的作业 printf(* *); printf(n*第 %d 轮具体进程调度信息(时间片为 %d ): *n,i,timeprice);printf(* *n); printf(* 进程名 服务时间 开始时间 停止时间 剩余时间 *n); for(k=0;k0)/剩余时间0（服务时间时间片大小） pk.servicetime=pk.lefttime;/本次的服务时间=运行一次过后的剩余时间pk.starttime=w;/上一个作业的停止时间就是本次作业的开始时间pk.finishtime=pk.starttime+pk.servicetime;/完成时间=开始时间+服务时间pk.lefttime=pk.servicetime-timeprice;/剩余时间=服务时间-时间片的大小if(pk.lefttime0)/若作业的剩余时间仍0（服务时间仍时间片大小）pk.stoptime=pk.starttime+timeprice;/停止时间=开始时间+时间片的大小 if(pk.lefttime=0)/剩余时间=0（服务时间=时间片大小）c=c-1;/完成一个作业，c减1 pk.stoptime=pk.finishtime;/停止时间=完成时间 w=pk.stoptime;/记录作业的停止时间 printf(*t%st%-.2ft %-.2f %-.2f %-.2fn,, pk.servicetime,pk.starttime,pk.stoptime,pk.lefttime); printf(* *n); i=i+1;if(c=0)/所有作业调度完毕printf(n*时间片轮转调度过程结束！ *n);printf(* *); for(k=0;k=N-1;k+) /记录信息 pk.servicetime=dk;/服务时间 pk.starttime=hk;/开始时间 pk.zztime=pk.finishtime-pk.arrivetime;/周转时间=完成时间-到达时间 pk.dqzztime=pk.zztime/pk.servicetime; /带权周转时间=周转时间/服务时间 void tt(rr *p,int N) float sumzztime=0, sumdqzztime=0, avzztime=0, avdqzztime=0;/总的周转时间、总的带权周转时间、平均周转时间、平均带权周转时间 int timeprice=0;/时间片大小float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0,lefttime=0;ptt(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,avzztime,avdqzztime,lefttime,timeprice,N);/时间片设置处理与程序运行printf(n*综合信息为： *n);Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);/屏幕打印输出处理 for(int k=0;k=N-1;k+) sumzztime=sumzztime+pk.zztime;/总的周转时间=前一个作业的周转时间+本次作业的周转时间（循环加）sumdqzztime=sumdqzztime+ pk.dqzztime;/总的带权周转时间=前一个作业的带权周转时间+本次作业的带权周转时间（循环加）avzztime=sumzztime/N;/平均周转时间=总的周转时间/进程数 printf(* *n); printf(*该算法的平均周转时间为:%-.2ft,avzztime);avdqzztime= sumdqzztime/N;/平均带权周转时间=总的带权周转时间/进程数 printf(该算法的平均带权周转时间为:%-.2ft *,avdqzztime);printf(n*n ); getchar();（4）静态优先级调度算法 a、功能说明按照优先级调度原则调度用户输入的进程输入作业数目 b、函数实现过程输入作业的基本信息（名字、到达时间、服务时间） 初始化优先级为0设置优先级（优先级=（等待时间+服务时间）/服务时间）找出优先级最高的作业，并返回其序号 执行该作业，直至所有作业执行完毕记录各类时间记录各个进程的周转时间和带权周转时间计算平均周转时间和平均带权周转时间输出调度结果和计算结果到屏幕最高响应比动态优先级调度算法至此结束 c、关键程序int prio(int pre)/设置优先权 /优先权 =(等待时间+服务时间)/服务时间int current=1,i,j;/current为当前作业for(i=0; iN1; i+)stai.waittime=stapre.finishtime-stai.arrivetime; /等待时间 =上一个作业的完成时间-到达时间 s