进程调度模拟实现

1、共享知识分享快乐盛年不重来，一日难再晨。及时宜自勉，岁月不待人。操作系统课程设计报告题目：进程调度算法的模拟实现专 业计算机科学与技术学生姓名刘远强班级计算机131学号1310704109指导教师韩立毛完成日期2015.7.10信息工程学院卑微如蟋蚁、坚强似大象1概述1.1 设计目的1.2 设计要求2设计原理2.1 先来先服务算法2.2 短进程优先算法 2.3 高优先权优先算法 2.4 高响应比优先算法 2.5 设计3.1功能结构4详细设计4.1 用户界面模块设计 4.2 算法模块设计5测试与分析 1.25.1 测试方案125.2 测试结果12.141.51.51.55.3 结果分析.6设计小

2、结7参考文献. 附录源程序代码题目：进程调度算法的模拟实现1概述1.1 设计目的在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个， 也就是 说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某 种调度策略，选择一进程占用处理机。要求学生设计一个模拟处理机调度算法， 以巩固和 加深处理机调度的概念。1.2 设计要求a）至少有四种作业调度算法；b）能根据不同的调度算法算出每个作业的周转时间和带权周转时间，并通过一组作业算出系统的平均周转时间和平均带权周转时间，比较各种算法的优缺点；c）设计一个实用的用户界面，以便选择不同的作业调度算法。2设计原理2.1

3、先来先服务算法每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源创建进程，然后放入就绪队列。2.2 短进程优先算法短进程优先调度算法是从就绪队列中选出一个估计运行时间最短的进程，将处理机 分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新 调度。2.3 高优先权优先算法a）当该算法用于作业调度时，系统从后备作业队列中选择若干个优先级最高的，且系 统能满足资源要求的作业装入内存运行。b）当该算法用于进程调度时，将把处理机分配给就绪进程队列中优先级最高的进程。2.4 高响应比优先算法高响应比优先调度算法既考虑作业的执行时间也考

4、虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。3概要设计3.1功能结构函数调用流程图如图3-14详细设计4.1用户界面模块设计用户界面包含4种算法的选择项及退出项,并能根据对应选项做出相应反应。选择算计算，选择退出则关闭界面，输入其他错误字符会显示错误法则进入所选算法进行进提示。void main()int choice; cout cout”*1.进程调度算法模拟实现*“endl;先来先服务算法*2.短作业优先算法*endl;cout*3.高优先权优先算法*4.高响应比优先算法*endl;cout*5.退出 *endl;11: cout”请输入您的选择：choice;JCB

5、 *head=NULL;switch(choice)case 1:head=create(head);FCFS(head);goto l1;case 2:head=create(head);SJF(head,jnum);goto l1;case 3:head=create(head);SUPER(head,jnum);goto l1;case 4:head=create(head);HRN(head,jnum);goto l1;case 5:break;default:cout 输入错误！ n 请重新输入：next;cout”作业执行顺序为：;while(p!=NULL)cout-name;p

6、=p-next;coutendl;coutnext;while(s!=NULL)coutsetw(4)namesetwhtimesetw(10)starttimesetw(11)ftimesetw(10)zhouzhuansetw(10)daiquannext;coutendl;cout平均周转时间：total/(double)jnumendl;cout平均带权周转时间：weight/(doubjnumendl; cout*endl;total=0;weight=0;b）短作业优先算法：每次查找所有 HEAD的结点，并将结点中最小作业所需运行时 间的结点复制并连接到短作业优先链表的最后节点中。

7、每复制一个结点，结点的是否被复制位置。共复制HEAD链表长度的LENGTH次，就复制完毕。这样形成的最短作业优先 链表就刚刚好是按作业所需运行时间按从小到大的顺序排列的了。void SJF(JCB *head,int n)JCB *p,*p1;JCB *flag=NULL;JCB *q=NULL;double time=0,j=0,runTime=0, drunTime=0;int xuhao=0;string pnameMAX_NUM;for(int ss=0;ssMAX_NUM;ss+)pnamess=;sortFCFS(head);coutendl;coutnext;p=head;whi

8、le(head)q=head;if(time htime) /如果该作业提交时间早于其它作业，则先执行该作业 time=p-htime;flag=head;/用于暂存将要执行的作业while(q & q-htime ntimentime)flag=q;q=q-next;/输出当前执行作业的信息coutsetw(4)xuhao+1;coutsetw(8)name;coutsetw(8)ntime;coutsetw(8)time;coutsetw(10)ntime);coutsetw(10)htime + flag-ntime);coutsetw(11)htime+flag-ntime)/flag

9、-ntime)htime+flag-ntime); runTime +=j;/记录周转时间time+=flag-ntime;drunTime+=j/flag-ntime; pnamexuhao=flag-name; xuhao+;/将执行过的作业从链表中删除 if(flag=head)head=head-next; else(p1=head;while(p1-next!=flag) p1=p1-next;p1-next=flag-next;/当前执行作业的周转时间/带权周转时间/在链表头/在链表中delete flag;/删除这个作业所占的节点cout作业执行顺序为： for(ss=0;ssn

10、;ss+)coutpnamess;if(pnamess+1 !=)cout ;coutendl;cout平均周转时间为：runTime/nendl;cout平均带权周转时间为：drunTime/nendl;coutI*”endl;c)高优先权优先算法：其中的操作和短作业优先差不多。因为作业在输入时已经有了作 业时间和优先权，高优先权算法是查找HEAD中最高优先权的结点进行复制。void SUPER(JCB *head,int n)JCB *p,*p1;JCB *flag=NULL;JCB *q=NULL;double time=0,j=0,runTime=0, drunTime=0;int x

11、uhao=0;string pnameMAX_NUM;for(int ss=0;ssMAX_NUM;ss+)pnamess=;sortFCFS(head);coutendl;coutnext;p=head;while(head)q=head;if(time htime) /如果该作业提交时间早于其它作业，则先执行该作业time=p-htime;flag=head;/用于暂存将要执行的作业while(q & q-htime superflag-super) flag=q; q=q-next;/输出当前执行作业的信息coutsetw(4)xuhao+1;coutsetw(8)name;coutse

12、tw(8)ntime;coutsetw(8)time;coutsetw(10)ntime);coutsetw(10)htime + flag-ntime);coutsetw(11)htimeflag-ntime)/flag-ntime)htime+flag-ntime); 当前执行作业的周转时间 runTime +=j;记录周转时间time+=flag-ntime;drunTime+=j/flag-ntime;带权周转时间pnamexuhao=flag-name; xuhao+; /将执行过的作业从链表中删除 if(flag=head)/在链表头head=head-next; else /在链

13、表中p1=head; while(p1-next!=flag) p1=p1-next; p1-next=flag-next; delete flag;/删除这个作业所占的节点cout作业执行顺序为： for(ss=0;ssn;ss+)coutpnamess;if(pnamess+1 !=)cout ;coutendl;cout平均周转时间为：runTime/nendl;cout平均带权周转时间为：drunTime/nendl;cout*”endl;d）高响应比优先算法：首先是将 HEAD整个链表复制过来形成高响应比链表，然后每执行一次就算出正在执行作业以后所有结点的响应比，查找出响应比最高的那

14、个结点，将响应比最高的结点插入到正在执行作业后面。这样执行下一个结点时，必定是未执行所有结点中响应比最高的结点。void HRN(JCB *head,int n)JCB *p,*p1;JCB *flag=NULL;JCB *q=NULL;double time=0,j=0,runTime=0, drunTime=0;int xuhao=0;string pnameMAX_NUM;for(int ss=0;ssMAX_NUM;ss+)pnamess=;sortFCFS(head);coutendl;coutnext;p=head;while(head)q=head;if(time htime)/

15、如果该作业提交时间早于其它作业，则先执行该作业time=p-htime;flag=head;/用于暂存将要执行的作业/计算当前链表中作业的响应比while(q & q-htime htime)/(q-ntime) (time - flag-htime)/(flag-ntime) flag=q;q=q-next;if(timehtime)如果上一次结束时间比当前选中要执行作业的结束时间小 time=flag-htime; /则当前作业开始时间为提交时间/输出当前执行作业的信息coutsetw(4)xuhao+1;coutsetw(8)name;coutsetw(8)ntime;coutsetw(

16、8)time;coutsetw(10)ntime);coutsetw(10)htime + flag-ntime);coutsetw(11)htimeflag-ntime)/flag-ntime)htime+flag-ntime);当前执行作业的周转时间runTime +=j;记录周转时间time+=flag-ntime;drunTime+=j/flag-ntime;带权周转时间pnamexuhao=flag-name;xuhao+;/将执行过的作业从链表中删除if(flag=head)/在链表头head=head-next;else/在链表中p1=head;while(p1-next!=fl

17、ag)p1=p1-next;p1-next=flag-next;delete flag;/删除这个作业所占的节点cout”作业执行顺序为：;for(ss=0;ssn;ss+)coutpnamess;if(pnamess+1 !=)cout ;coutendl;cout平均周转时间为：runTime/nendl;cout平均带权周转时间为：drunTime/nendl;cout*”endl;5测试与分析5.1 测试方案先选择算法，输入进程数、作业名、优先级、到达时间、估计运行时间，得出相应的 作业名、提交时间、开始时间、结束时间、周转时间、带权周转时间。通过四种算法 之间的比较了解他们的优缺点。

18、5.2 测试结果a）用户界面如图5.2.1图 5.2.1b）先来先服务算法如图5.2.2图 5.2.2c）短作业优先算法如图5.2.3图 5.2.3d）高优先权算法如图5.2.4图 5.2.4f）高响应比优先算法如图5.2.5图 5.2.5e）错误界面如图5.2.6图 5.2.65.3 结果分析由测试结果可知每种算法的优缺点：a）先来先服务算法：有利于长作业（进程）而不利于短作业（进程）有利于CPU1忙型作业（进程）而不利于I/O繁忙型作业（进程）。b）短作业优先算法：比FCF改善平均周转时间和平均带权周转时间短作业的等待时间；提高系统的吞吐量；对长作业非常不利，可能长时间得不到执行；未能依据

19、作业的紧迫程度来划分执行的优先级；c）难以准确估计作业（进程）的执彳T时间，从而影响调度性能。c）高优先权算法：动态优先级优点是使相应的优先级调度算法比较灵活、科学，可防止有些进程一直得不到调 度，也可防止有些进程长期垄断处理机。动态优先级缺点是需要花费相当多的执行程序时 间，因而花费的系统开销比较大。d）高响应比优先算法：短作业与先后次序的兼顾，且不 会使长作业长期得不到服务响应比计算系统开销，增加系统开销。6设计小结通过改程序对操作系统的基础知识了解得更透彻了，同时对磁盘调度的四种算法一一先来先服务算法，短进程优先调度算法，优先权算法，高响应比调度算法有了更深刻的理 解和掌握，使我能够为进

20、程调度选择适当的算法， 提高CPU作效率。进行进程调度程序 设计的过程中，得到老师的大力指导和同学的支持， 在此向他们表示感谢。经过自己的动 手操作和同学老师的指导我成功的做出了课程设自己感到很高兴。在整个过程中自己也感受到了集体团结的力量，今后无论是在工作还是学习中我都会发样这种精神。7参考文献1韩立毛，李先锋.计算机操作系统实践教程M,南京：南京大学出版社，2011.10.2严蔚敏，吴伟民.数据结构M,北京：清华大学出版社，1997.43张尧学，史美林.计算机操作系统教程M,北京：清华大学出版社，2000.8.4孙静宇.计算机操作系统课程设计指导书M,山西：太原理工出版社，2006.4.附

21、录源程序代码#include#include#include using namespace std;#define MAX_NUM 15 typedef struct JCB char name10;/f乍业名float htime;/作业到达时间float ntime;/作业估计运行的时间float starttime;/作业开始运行时间float ftime;作业完成的时间float zhouzhuan;/倜转时间float daiquan;/所权周转时间float xiangyingbi;/ 相应比int super;/优先级JCB *next;/定义指向下一个作业的指针 JCB;in

22、t jnum;/定义作业数为jnumfloat total;/记录所有作业的总时间double weight;/记录所有作业的带权周转时间JCB *create(JCB *head);/&建作业队列void dealFCFS(JCB *head);/FCFS 记录处理void sortFCFS(JCB *head);/t、业按到达的先后顺序排列void FCFS(JCB *head);/先来先月艮务算法void SJF(JCB *head,int n);/短作业优先算法void SUPER(JCB *head,int n);/高优先权优先算法void HRN(JCB *head,int n);

23、高响应比优先算法 void main() int choice;cout*进程调度算法实现*endl;cout *1.先来先服务算法*2.短作业优先算法*endl;cout *3.高优先权优先算法*4.高响应比优先算法*choice;JCB *head=NULL;switch(choice)case 1:head=create(head);FCFS(head);goto l1;case 2:head=create(head);SJF(head,jnum);goto 11;case 3:head=create(head);SUPER(head,jnum);goto 11;case 4:head=

24、create(head);HRN(head,jnum);goto 11;case 5:break;default:cout输入错误！ n 请重新输入：endl;goto l2;/创建节点与作业输入JCB *create(JCB *head)JCB *p1,*p2;p1=p2=new JCB;head=p1;coutjnum;for(int i=0;inext=NULL;cout请依次输入第i+1p1-namep1-superp1-htimep1-ntime;p2-next=p1;return head;/FCFS算法void sortFCFS(JCB *head)/t、业按到达的先后顺序排列J

25、CB *p,*q,*r,*s;if(head-next!=NULL)p=head-next-next;head-next-next=NULL;)while(p)(q=p；p=p-next;r=head;s=head-next;while(s&s-htimehtime)(r=s;s=s-next;)r-next=q;q-next=s;)void dealFCFS(JCB *head)/FCFS 记录处理(sortFCFS(head);JCB *p,*q;q=head-next;q-starttime=q-htime;q-ftime=q-starttime+q-ntime;q-zhouzhuan=

26、q-ftime-q-htime;q-daiquan=q-zhouzhuan/(double)q-ntime;total+=q-zhouzhuan;weight+=q-daiquan;p=q-next;while(p!=NULL)(p-starttime=q-ftime;p-ftime=p-starttime+p-ntime;p-zhouzhuan=p-ftime-p-htime;p-daiquan=p-zhouzhuan/(double)p-ntime;total+=p-zhouzhuan;weight+=p-daiquan;q=p;p=p-next;void FCFS(JCB *head)/

27、先来先月艮务算法dealFCFS(head);JCB *p,*q,*s;p=head-next;cout”作业执行顺序为：;while(p!=NULL)cout-name;p=p-next;coutendl;coutnext;while(s!=NULL)coutsetw(4)namesetw(7)htimesetw(10)starttimesetw(11)ftimesetw(10)zhouzhuansetw(10)daiquannext;coutendl;cout平均周转时间：total/(double)jnumendl;cout平均带权周转时间：weight/(double)jnumendl

28、;cout*endl;total=0;weight=0;/SJF短作业优先算法 void SJF(JCB *head,int n)JCB *p,*p1;JCB *flag=NULL;JCB *q=NULL;double time=0,j=0,runTime=0, drunTime=0;int xuhao=0;string pnameMAX_NUM;for(int ss=0;ssMAX_NUM;ss+)pnamess=;sortFCFS(head);coutendl;coutnext;p=head;while(head)q=head;if(time htime)/如果该作业提交时间早于其它作业，

29、则先执行该作业time=p-htime;flag=head;/用于暂存将要执行的作业while(q & q-htime ntimentime)flag=q;q=q-next;/输出当前执行作业的信息coutsetw(4)xuhao+1;coutsetw(8)name;coutsetw(8)ntime;coutsetw(8)time;coutsetw(10)ntime);coutsetw(10)htime + flag-ntime);coutsetw(11)htime+flag-ntime)/flag-ntime)htime+flag-ntime); 当前执行作业的周转时间 runTime +=

30、j;记录周转时间time+=flag-ntime;drunTime+=j/flag-ntime;带权周转时间pnamexuhao=flag-name;xuhao+;/将执行过的作业从链表中删除if(flag=head)/在链表头head=head-next;else/在链表中p1=head;while(p1-next!=flag)p1=p1-next;p1-next=flag-next; delete flag; /删除这个作业所占的节点cout”作业执行顺序为：;for(ss=0;ssn;ss+)coutpnamess;if(pnamess+1 !=) cout ;coutendl;cout

31、平均周转时间为：runTime/nendl;cout平均带权周转时间为：drunTime/nendl;cout*”endl;/高优先权优先算法 void SUPER(JCB *head,int n) JCB *p,*p1;JCB *flag=NULL;JCB *q=NULL;double time=0,j=0,runTime=0, drunTime=0;int xuhao=0;string pnameMAX_NUM;for(int ss=0;ssMAX_NUM;ss+)pnamess=;sortFCFS(head);coutendl;coutnext;p=head;while(head)q=h

32、ead;if(time htime) /如果该作业提交时间早于其它作业，则先执行该作业 time=p-htime;flag=head;/用于暂存将要执行的作业while(q & q-htime superflag-super)flag=q;q=q-next;/输出当前执行作业的信息coutsetw(4)xuhao+1;coutsetw(8)name;coutsetw(8)ntime;coutsetw(8)time;coutsetw(10)ntime);coutsetw(10)htime + flag-ntime);coutsetw(11)htime+flag-ntime)/flag-ntime

33、)htime+flag-ntime);当前执行作业的周转时间runTime +=j;记录周转时间time+=flag-ntime;drunTime+=j/flag-ntime;带权周转时间pnamexuhao=flag-name; xuhao+; /将执行过的作业从链表中删除 if(flag=head)/在链表头head=head-next; else/在链表中p1=head;while(p1-next!=flag)p1=p1-next;p1-next=flag-next; delete flag;/删除这个作业所占的节点cout”作业执行顺序为：;for(ss=0;ssn;ss+)coutpnamess;if(pnamess+1 !=) cout ;coutendl;cout平均周转时间为：runTime/nendl;cout平均带权周转时间为：drunT