进程调度算法的模拟实现

1、精选优质文档-倾情为你奉上操作系统课程设计报告题目： 进程调度算法的模拟实现_专业计算机科学与技术学生姓名班级学号指导教师发放日期2015.1.30信 息 工 程 学 院专心-专注-专业目 录进程调度算法的模拟实现1 概述选择一个调度算法，实现处理机调度，进程调度算法包括：先来先服务算法，短进程优先算法，时间片轮转算法，动态优先级算法。可选择进程数量，本程序包括四种算法，用C或C+语言实现，执行时在主界面选择算法（可用函数实现），进入子页面后输入进程数，（运行时间，优先数由随机函数产生），执行，显示结果。2 设计原理2.1先来先服务(FCFS)算法 每次调度都是从后备作业队列中选择一个或多个最

2、先进入该队列的作业，将它们调入内存，为它们分配资源创建进程，然后放入就绪队列2.2 时间片轮转法(RR)算法系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。2.3短作业优先(SJF)算法短作业优先调度算法是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞

3、放弃处理机时再重新调度。 2.4最高优先权优先(HRRN)算法 优先权调度算法是为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入最高优先权优先调度算法。动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。 3 详细设计与编码3.1 模块设计(1) 进入系统模块，进入登陆界面。(3) 菜单选择模块。选择相应的进程调度方式，选择相应的数字，进入相应的功能。(4) 算法模块。选择相应的进程调度算法。(5) 显现输出模块。显示每种进程调度算法情况。(6) 平均周转时间与平均带权周转时间的计算结果。(7) 退出系统模块。开始3.2 系

4、统流程图FCFS算法，对于先到达的进程优先分配CPUSJF算法，每次都从未完成的队列中选取服务时间最短的作业进行调度RR算法，每次调度时将CPU 分派给队首进程，按照时间片依次执行进程HRRN算法，考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出最高的作业投入执行。结束3.3 系统详细设计(1) 系统主界面设计（包含登陆模块设计）首先将各种进程调度算法放入不同的头文件，在主函数引用，是系统结构更加清晰。设置一个mean()方法，让用户选择不同的进程调度算法，mean()方法返回一个char类型字符，以便在主函数的switch语句中选择调用不同的进程调度方法。(2) 系统模块1.先来

5、先服务算法 对于先到达的进程优先分配CPU，按照先来先服务的原则依次执行各进程。算法：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); deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); Print(p,arrivetim

6、e,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该算法的平均周转时间为:%-.2ft",avzztime); avdqzztime= sumdqzztime/N; printf("该算法的平均带权周转时间为:%-.2ftnn",avdqzztim

7、e); 2.短进程优先算法先找到运行时间最短的程序，然后执行，再从剩余的程序中找到运行时间最短的在执行，依次每次都执行运行时间最短的，直到程序执行完毕。算法： void sjff(sjf *p,int N1)float sumzztime=0, sumdqzztime=0,avzztime,avdqzztime;float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztim

8、e,N1); Print(p,arrivetime,servicetime,starttime,finishtime,N1);for(int k=0;k<=N1-1;k+) sumzztime=sumzztime+pk.zztime;sumdqzztime=sumdqzztime+ pk.dqzztime;avzztime=sumzztime/N1; printf("n该算法的平均周转时间为:%-.2ft",avzztime);avdqzztime= sumdqzztime/N1; printf("该算法的平均带权周转时间为:%-.2ftnn",a

9、vdqzztime); 3.时间片轮转算法按照轮转的次序分配给每个程序一定的时间执行，执行完成后执行后面的进程 ，依次循环执行直到所有进程执行完成。算法： void tt(rr *p,int N2) 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

10、,finishtime,zztime,dqzztime,avzztime,avdqzztime,lefttime,timeprice,N2);printf("n 综合信息为：n");Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N2); for(int k=0;k<=N2-1;k+) sumzztime=sumzztime+pk.zztime;sumdqzztime=sumdqzztime+ pk.dqzztime;avzztime=sumzztime/N2; printf(&q

11、uot;n该算法的平均周转时间为:%-.2ft",avzztime);avdqzztime= sumdqzztime/N2; printf("该算法的平均带权周转时间为:%-.2ftn",avdqzztime);getchar(); 4.最高响应比优先算法按照优先级从高到低依次执行程序。算法：int HRN(int pre)int current=1,i,j;/* 优先权 =(等待时间+服务时间)/服务时间*/for(i=0; i<N4; i+)JCBi.waiTime=JCBpre.finTime-JCBi.arrTime; /*等待时间 =上一个作业的完

12、成时间-到达时间*/JCBi.priority=(JCBi.waiTime+JCBi.serTime)/JCBi.serTime;for(i=0; i<N4; i+)if(!JCBi.finish)current=i; /*找到第一个还没完成的作业*/break;for( j=i; j<N4; j+) /*和后面的作业比较*/if( !JCBj.finish) /* 还没完成(运行)*/if(JCBcurrent.arrTime<=JCBpre.finTime) /*如果作业在上一个作业完成之前到达*/if(JCBj.arrTime<=JCBpre.finTime &a

13、mp;& JCBj.priority>JCBcurrent.priority )current=j;/* 找出到达时间在上一个作业完成之前，优先权高的作业*/else /* 如果作业是在上一个作业完成之后到达*/if(JCBj.arrTime<JCBcurrent.arrTime)current=j; /* 找出比较早到达的一个*/if(JCBj.arrTime=JCBcurrent.arrTime) /* 如果同时到达*/if(JCBj.priority>JCBcurrent.priority)current=j; /*找出服务时间比较短的一个*/return cu

14、rrent;/*返回当前作业*/4 结果与分析4.1 测试方案(1) 测试方案(一) 在主界面输入1，选择先来先服务调度算法，然后输入进程数目5，然后输入各个进程信息，观察测试结果。(2) 测试方案（二)在主界面输入2，选择最短进程优先调度算法，然后输入进程数目5，然后输入各个进程信息,进程信息与测试方案(一)保持一致，观察测试结果，对比方案一。 (3) 测试方案（三) 在主界面输入3，选择时间片轮转调度算法，然后输入进程数目5，然后输入各个进程信息，进程信息与测试方案(一)保持一致，观察测试结果，对比方案一和二。(4) 测试方案（四)在主界面输入4，选择时间片轮转调度算法，然后输入进程数目5

15、，然后输入各个进程信息，进程信息与测试方案(一)保持一致，观察测试结果，对比方案一和二和三。4.2 测试结果 (1) 测试方案（一)结果。输入测试进程数5，测试用例分别为(A 0 4)，(B 1 3),(C 2 5),(D 3 2),(E 4 4)，测试结果见图（图4-1 先来先服务调度算法） 图4-1 先来先服务调度算法由运行结果可以看出，短作业D的服务时间最短，但带权周转时间高达5.5,而长作业C的服务时间为5，带权周转时间仅为2,因此先来先服务算法比较有利于长作业，而不利于短作业(2) 测试方案（2)结果。输入测试进程数5，测试用例分别为(A 0 4)，(B 1 3),(C 2 5),(

16、D 3 2),(E 4 4)，测试结果见图（图4-2 短作业优先调度算法） 图4-2 短作业优先调度算法由运行结果可以看出，短作业优先算法每次都从未完成的队列中选取服务时间最短的作业进行调度。通过比较，短作业优先算法的平均带权周转时间小于先来先服务算法，提高了系统的吞吐量。因此，相对于短作业较多或者较为重要的系统中，可选这短作业优先调度算法。(3) 测试方案（三)结果。输入测试进程数5，测试用例分别为(A 0 4)，(B 1 3),(C 2 5),(D 3 2),(E 4 4)，测试结果见图（图4-3.1,4-3.2，4-3.3时间片轮转调度算法） 图4-3.1 时间片轮转调度算法 图4-3.

17、2 时间片轮转调度算法 图4-3.3 时间片轮转调度算法从多次运行结果来看，时间片轮转调度算法不同的时间片对结果有很大的影响。(4) 测试方案（四)结果。输入测试进程数5，测试用例分别为(A 0 4)，(B 1 3),(C 2 5),(D 3 2),(E 4 4)，测试结果见图(图4-4 最高响应比优先调度算法） 图4-4 最高响应比优先调度算法由运行结果可以看出，该算法既照顾了短作业，有考虑了作业到达的先后次序，不会使长作业长期得不到服务。因此，该算法是一个很好的折衷4.3 测试结果分析四种调度算法各有优劣。先来先服务算法比较有利于长进程，而不利于短进程，有利于CPU 繁忙的进程，而不利于I

18、/O 繁忙的进程。短作业优先调度算法相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。缺点是对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。时间片轮转调度算法的特点是简单易行、平均响应时间短，但不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大，因此时间片的大小应选择恰当。高响应比优先调度策略是对FCFS方式和SJF方式的一种综合平衡，同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出最高的作业投入执行。5 设计小结经过一

19、周的努力，课程设计基本完成了，这次课程设计培养了我们耐心、慎密、全面地考虑问题的能力，从而加快了问题解决的速度、提高了个人的工作效率，以及锻炼围绕问题在短时间内得以解决的顽强意志。课程设计是我们专业课程知识综合应用的实践训练，也是为我们以后的工作夯实基础。通过改程序对操作系统的基础知识了解得更透彻了，同时对磁盘调度的四种算法先来先服务算法，短进程优先调度算法，时间片轮转调度算法，动态优先级调度有了更深刻的理解和掌握，使我能够为进程调度选择适当的算法，提高CPU工作效率。进行进程调度程序设计的过程中，得到老师的大力指导和同学的支持，在此向他们表示感谢。经过自己的动手操作和同学老师的指导我成功的做

20、出了课程设计自己感到很高兴。在编写程序的过程中，我们的能力得到了提高，同时养成了科学、严谨的作风和习惯。为此要感谢信息学院开设了这门操作系统课程设计，为我们提供了进一步学习算法、操作系统和巩固C语言程序计设的平台。6 参考文献1 严蔚敏，吴伟民. 数据结构M.清华大学出版社，1997.2 张尧学，史美林. 计算机操作系统教程M.清华大学出版社，2000.3 孙静宇. 计算机操作系统课程设计指导书M.太原理工出版社，2006.4 汤小丹,梁红兵,哲凤屏,汤子赢.计算机操作系统（第五版）M.西安：西安电子科技大学出版社，2007.5 何钦铭，颜晖.C语言程序设计M.北京：高等教育出版社,2008.

21、6 胡学刚，数据结构（C语言版）M.北京:高等教育出版社，2008.7 张小进，Linux系统应用基础教程M.北京:机械工业出版社，2008.8 孟庆昌，C语言程序设计M.北京:人民邮电出版社，2006.7 附录 程序代码Main.cpp#include <cstdlib>#include <iostream>#include <iomanip> #include "fcfs.h” /先来先服务#include "sjf.h" /短作业优先#include "rr.h"/时间片轮转#include "

22、;hrrn.h" /高响应比优先"using namespace std;char menu()/用来输出相关信息的函数 char cse1;while(1)system("cls");fflush(stdin);cout<<endl; cout<<endl; cout<<"t"<<" "<<"t 进程调度算法模拟 "<<"tt"<<" "<<endl;cout

23、<<"t"<<" "<<endl;cout<<"t"<<" "<<"tt 1.先来先服务调度算法 "<<"tt"<<" "<<endl;cout<<"t"<<" "<<endl;cout<<"t"<<" "<

24、;<"tt 2.短作业优先调度算法 "<<"tt"<<" "<<endl;cout<<"t"<<" "<<endl;cout<<"t"<<" "<<"tt 3.时间片轮转调度算法"<<"ttt"<<" "<<endl; cout<<&qu

25、ot;t"<<" "<<endl;cout<<"t"<<" "<<"tt 4.最高响应比优先调度算法 "<<"tt"<<" "<<endl; cout<<"t"<<" "<<endl;cout<<"t"<<" "<<&qu

26、ot;tt 0.退出系统 "<<"tt"<<" "<<endl; cout<<endl;cout<<endl;cout<<"tt 请输入您的选择（0/1/2/3/4）："cse1=getchar();if(cse1<'0'|cse1>'4')cout<<endl;cout<<" o()o 您的输入有误！请重新输入正确的字符 o()o "<<endl;cou

27、t<<endl;system("PAUSE");elsebreak;return cse1;int main(int argc, char *argv) while(1) switch(menu()case '1': fcfsRun();break;case '2': sjfRun();break;case '3': rrRun();break;case '4':hrrnRun();break;case '0':exit(0); system("PAUSE");

28、return EXIT_SUCCESS;fcfs.h#include <stdio.h>#include <stdlib.h>using namespace std;struct fcfs /定义先来先服务调度算法结构体char name10; /./作业名float arrivetime; /作业到达时间float servicetime; /作业服务float starttime; /作业开始时间float finishtime; /作业完成时间float zztime; /带权周转时间float dqzztime; /平均带权周转时间; fcfs a100;/定义

29、存放进程的数组void input(fcfs *p,int N) /输入处理 int i; cout<<endl; printf(" 请您输入进程的 名字 到达时间 服务时间: (例如: a 0 100)nn"); for(i=0;i<=N-1;i+) printf(" 请您输入进程%d的信息:t",i+1);scanf("ttt%s%f%f",&,&pi.arrivetime,&pi.servicetime); void Print(fcfs *p,float arriveti

30、me,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N) /屏幕输出处理int k; printf("nn调用先来先服务算法以后进程运行的顺序是: "); printf("%s",); for(k=1;k<N;k+) printf("->%s",); cout<<endl; printf("n 具体进程调度信息:n"); printf("

31、;t进程名 到达时间 服务时间 开始时间 结束时间 周转时间 带权周转时间n"); for(k=0;k<=N-1;k+) printf("t%st%-.2ft %-.2ft %-.2ft %-.2ft %-.2ft %-.2fn",,pk.arrivetime,pk.servicetime,pk.starttime,pk.finishtime,pk.zztime,pk.dqzztime); getchar(); /此处必须要有这个函数，否则就看不到显示器上面的输出，可以看到的结果只是一闪而过的一个框剪 void sort(fcfs *p,int

32、 N) /按进程的到达时间进行排序 for(int i=0;i<=N-1;i+) for(int j=0;j<=i;j+) if(pi.arrivetime<pj.arrivetime) fcfs temp; temp=pi; pi=pj; pj=temp; void deal(fcfs *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N) /运行阶段,根据先来先服务的原则进行处理 int k; f

33、or(k=0;k<=N-1;k+) if(k=0) 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,i

34、nt N) float sumzztime=0, sumdqzztime=0,avzztime,avdqzztime; float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; sort(p,N); deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); for(int

35、 k=0;k<=N-1;k+) sumzztime=sumzztime+pk.zztime; sumdqzztime=sumdqzztime+ pk.dqzztime; avzztime=sumzztime/N; printf("n该算法的平均周转时间为:%-.2ft",avzztime); avdqzztime= sumdqzztime/N; printf("该算法的平均带权周转时间为:%-.2ftnn",avdqzztime); void fcfsRun()/给主函数调用的方法int N; cout<<endl;cout<&l

36、t;endl; printf("tt<<-!先来先服务调度算法!->>n"); cout<<endl;printf("输入进程数目:"); scanf("%d",&N); input(a,N); FCFS(a,N); getchar(); /先来先服务算法到此结束 Sjf.h#include<stdio.h>struct jcb /作业控制块JCB,定义为结构体 char name10; /作业名 float arrivetime; /作业到达时间 float serviceti

37、me;/作业服务时间 float starttime; /作业开始执行时间 float finishtime; /作业完成时间 float zztime; /作业周转时间 float dqzztime; /作业平均周转时间; jcb a1100; /最多能管理的作业数目void input(jcb *p,int N) /输入处理 int i;cout<<endl; printf(" 请您输入进程的 名字 到达时间 服务时间: (例如: a 0 100)n"); for(i=0;i<=N-1;i+) printf(" 请您输入进程%d的信息:t&q

38、uot;,i+1);scanf("ttt%s%f%f",&,&pi.arrivetime,&pi.servicetime);void Print(jcb *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N) /屏幕输出处理 int k;printf("nt调用最短进程优先调度算法以后进程的调度顺序为:");printf("%s",p0.nam

39、e);for(k=1;k<N;k+)printf("->%s",); cout<<endl; printf("n给个进程具体调度信息如下:n");printf("n进程名 到达时间 运行时间 开始时间 完成时间 周转时间 带权周转时间n"); for(k=0;k<=N-1;k+) printf("%st%4.2ft%6.2ft%8.2ft%3.2ft%6.2ft%7.2ftn",,pk.arrivetime,pk.servicetime,pk.startti

40、me,pk.finishtime,pk.zztime,pk.dqzztime); getchar(); void sort(jcb *p,int N) /按进程到达时间进行排序 for(int i=0;i<=N-1;i+) for(int j=0;j<=i;j+) if(pi.arrivetime<pj.arrivetime) jcb temp; temp=pi; pi=pj; pj=temp; void deal(jcb *p, float arrivetime,float servicetime,float starttime,float finishtime,float

41、 &zztime,float &dqzztime,int N) /./按短作业优先原则进行进程服务处理 int k; for(k=0;k<=N-1;k+) if(k=0) 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.a

42、rrivetime; pk.dqzztime=pk.zztime/pk.servicetime; void jcbf(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;m<N-1;m+) if(m=0) pm.finishtime=pm.arrivetime+pm.servic

43、etime; 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+; float min=pm+1.servicetime; int next=m+1;/m+1=n for(int k=m+1;k<m+i;k+) if(pk+1.servicetime<min) min=pk+1.servicetime; next=k+1; jcb temp; temp=pm+1; pm+1=pnex

44、t; pnext=temp; deal(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该算法的平均周转时间为:%-

45、.2ft",avzztime);avdqzztime= sumdqzztime/N; printf("该算法的平均带权周转时间为:%-.2ftnn",avdqzztime); getchar(); void sjfRun() /给主函数调用的方法 int N; printf("tt<<-!短作业优先调度算法!->>n"); printf("请输入作业数目:"); scanf("%d",&N); input(a1,N); jcb *b=a1; jcbf(b,N); Rr.h#

46、include <stdio.h>#include <stdlib.h>using namespace std;/定义时间片轮转调度算法结构体，里面包含的有一个进程相关的信息struct rrchar name10; /作业名float arrivetime; /作业到达时间float servicetime; /作业服务时间float starttime; /作业开始时间float finishtime; /作业结束时间 float zztime; /作业周转时间float dqzztime; /作业带权周转时间float avzztime;/作业平均周转时间 flo

47、at avdqzztime;/作业平均带权周转时间 float lefttime; /剩余时间float stoptime;/停止时间int timeprice;/时间片设置的大小;/时间片轮转调度算法从这里开始 rr a2100 ;void input(rr *p,int N2)/进程信息输入 int i;cout<<endl; printf(" 请您输入进程的 名字 到达时间 服务时间: (例如: a 0 100)n"); for(i=0;i<=N2-1;i+) printf(" 请您输入进程%d的信息:t",i+1);scanf(

48、"ttt%s%f%f",&,&pi.arrivetime,&pi.servicetime);void sort(rr *p,int N2) /到达时间排序 for(int i=0;i<=N2-1;i+) for(int j=0;j<=i;j+) if(pi.arrivetime<pj.arrivetime) rr temp; temp=pi; pi=pj; pj=temp; void Print(rr *p,float arrivetime,float servicetime,float starttime,float

49、 finishtime,float zztime,float dqzztime,int N2) /屏幕打印输出处理int k; printf("nt调用时间片轮转调度算法以后进程运行的顺序是: "); printf("%s",); for(k=1;k<N2;k+) printf("->%s",); cout<<endl; printf("n 具体进程调度信息:nn"); printf("t进程名 到达时间 服务时间 开始时间 结束时间 周转时间 带权周转

50、时间n"); for(k=0;k<=N2-1;k+) printf("t%st%-.2ft %-.2ft %-.2ft %-.2ft %-.2ft %-.2fn",,pk.arrivetime, pk.servicetime,pk.starttime,pk.finishtime,pk.zztime,pk.dqzztime); getchar(); void ptt(rr *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,floa

51、t dqzztime,float avzztime,float avdqzztime,float lefttime,int timeprice,int N2) /时间片设置处理与程序运行 float w=0;int c=0;float stoptime=0;printf("n 请输入时间片的值：");cin>>timeprice;sort(p,N2);/排序float d20,h20;for(int k=0;k<=N2-1;k+) dk=pk.servicetime; if(k=0) pk.starttime=pk.arrivetime; pk.finishtime=pk.arrivetim