进程调模拟实现

1、操作系统课程设计报告题目： 进程调度算法的模拟实现 专业计算机科学与技术学生姓名刘远强班级计算机131学号1310704109指导教师韩 立 毛完成日期信 息 工 程 学 院目 录1 概述21.1 设计目的21.2 设计要求22 设计原理22.1 先来先服务算法22.2 短进程优先算法22.3高优先权优先算法22.4高响应比优先算法33 概要设计33.1 功能结构34 详细设计44.1 用户界面模块设计44.2 算法模块设计45 测试与分析125.1 测试方案125.2 测试结果125.3 结果分析146 设计小结157 参考文献15附录 源程序代码16题目：进程调度算法的模拟实现1 概述1.

2、1 设计目的在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个，也就是说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某种调度策略，选择一进程占用处理机。要求学生设计一个模拟处理机调度算法，以巩固和加深处理机调度的概念。1.2 设计要求a)至少有四种作业调度算法；b)能根据不同的调度算法算出每个作业的周转时间和带权周转时间，并通过一组作业算出系统的平均周转时间和平均带权周转时间，比较各种算法的优缺点；c)设计一个实用的用户界面，以便选择不同的作业调度算法。2 设计原理2.1 先来先服务算法 每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作

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

4、1 功能结构函数调用流程图如图31图314 详细设计4.1 用户界面模块设计用户界面包含4种算法的选择项及退出项，并能根据对应选项做出相应反应。选择算法则进入所选算法进行进一步计算，选择退出则关闭界面，输入其他错误字符会显示错误提示。void main()int choice;cout<<" *进程调度算法模拟实现*"<<endl;cout<<"*1.先来先服务算法*2.短作业优先算法*"<<endl;cout<<"*3.高优先权优先算法*4.高响应比优先算法*"<&l

5、t;endl;cout<<"*5.退出*"<<endl;l1:cout<<"请输入您的选择："<<endl; l2:cin>>choice;JCB *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:he

6、ad=create(head);HRN(head,jnum);goto l1;case 5:break;default:cout<<"输入错误！n请重新输入："<<endl;goto l2;4.2 算法模块设计先来先服务算法:直接复制首个作业的链表HEAD作为先来先服务的链表（因为首个原始输入作业的链表就是按输入顺序进行链接形成的）。 void FCFS(JCB *head)/先来先服务算法dealFCFS(head);JCB *p,*q,*s;p=head->next;cout<<"作业执行顺序为："while

7、(p!=NULL)cout<<"-"<<p->name;p=p->next;cout<<endl;cout<<"作业名 提交时间 开始时间 结束时间 周转时间 带权周转时间n" s=head->next;while(s!=NULL)cout<<setw(4)<<s->name<<setw(7)<<s->htime<<setw(10)<<s->starttime<<setw(11)<&

8、lt;s->ftime<<setw(10)<<s->zhouzhuan<<setw(10)<<s->daiquan<<endl;s=s->next;cout<<endl; cout<<" 平均周转时间："<<total/(double)jnum<<endl;cout<<"平均带权周转时间："<<weight/(double)jnum<<endl;cout<<"*&qu

9、ot;<<endl;total=0;weight=0;b)短作业优先算法：每次查找所有HEAD的结点，并将结点中最小作业所需运行时间的结点复制并连接到短作业优先链表的最后节点中。每复制一个结点，结点的是否被复制位置。共复制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;stri

10、ng pnameMAX_NUM;for(int ss=0;ss<MAX_NUM;ss+)pnamess=""sortFCFS(head);cout<<endl;cout<<" 顺序 作业名 提交时间 开始时间 结束时间 周转时间 带权周转时间n"head=head->next;p=head;while(head)q=head;if(time < p->htime) /如果该作业提交时间早于其它作业，则先执行该作业time=p->htime;flag=head; /用于暂存将要执行的作业while(q

11、&& q->htime <= time)if(q->ntime<flag->ntime)flag=q;q=q->next;/输出当前执行作业的信息 cout<<setw(4)<<xuhao+1;cout<<setw(8)<<flag->name;cout<<setw(8)<<flag->ntime;cout<<setw(8)<<time;cout<<setw(10)<<(time + flag->ntime

12、);cout<<setw(10)<<(time - flag->htime + flag->ntime);cout<<" "<<setw(11)<<(double)(time-flag->htime + flag->ntime)/flag->ntime)<<endl; j=(time-flag->htime+flag->ntime); /当前执行作业的周转时间runTime +=j; /记录周转时间time+=flag->ntime;drunTime+=j

13、/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;ss<n;ss+)cout<<pnamess;if(pnamess

14、+1 !="")cout<<" -> "cout<<endl;cout<<" 平均周转时间为："<<runTime/n<<endl; cout<<"平均带权周转时间为："<<drunTime/n<<endl;cout<<"*"<<endl;c)高优先权优先算法：其中的操作和短作业优先差不多。因为作业在输入时已经有了作业时间和优先权，高优先权算法是查找HEAD中最高优先权的

15、结点进行复制。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;ss<MAX_NUM;ss+)pnamess=""sortFCFS(head);cout<<endl;cout<<" 顺序 作业名 提交时间 开始时间 结束时间 周转时间 带权周转时间n"head=head->

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

17、name;cout<<setw(8)<<flag->ntime;cout<<setw(8)<<time;cout<<setw(10)<<(time + flag->ntime);cout<<setw(10)<<(time - flag->htime + flag->ntime);cout<<" "<<setw(11)<<(double)(time-flag->htime + flag->ntime)/flag

18、->ntime)<<endl; j=(time-flag->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-&g

19、t;next=flag->next;delete flag; /删除这个作业所占的节点cout<<"作业执行顺序为："for(ss=0;ss<n;ss+)cout<<pnamess;if(pnamess+1 !="")cout<<" -> "cout<<endl;cout<<" 平均周转时间为："<<runTime/n<<endl; cout<<"平均带权周转时间为："<<

20、;drunTime/n<<endl;cout<<"*"<<endl;d)高响应比优先算法：首先是将HEAD整个链表复制过来形成高响应比链表，然后每执行一次就算出正在执行作业以后所有结点的响应比，查找出响应比最高的那个结点，将响应比最高的结点插入到正在执行作业后面。这样执行下一个结点时，必定是未执行所有结点中响应比最高的结点。 void HRN(JCB *head,int n)JCB *p,*p1;JCB *flag=NULL;JCB *q=NULL; double time=0,j=0,runTime=0, drunTime=0

21、;int xuhao=0;string pnameMAX_NUM;for(int ss=0;ss<MAX_NUM;ss+)pnamess=""sortFCFS(head);cout<<endl;cout<<" 顺序 作业名 提交时间 开始时间 结束时间 周转时间 带权周转时间n"head=head->next;p=head;while(head)q=head;if(time < p->htime) /如果该作业提交时间早于其它作业，则先执行该作业time=p->htime;flag=head; /用于

22、暂存将要执行的作业/计算当前链表中作业的响应比while(q && q->htime <= time)if(time - q->htime)/(q->ntime) > (time - flag->htime)/(flag->ntime)flag=q;q=q->next;if(time<flag->htime)/如果上一次结束时间比当前选中要执行作业的结束时间小time=flag->htime; /则当前作业开始时间为提交时间/输出当前执行作业的信息 cout<<setw(4)<<xuhao

23、+1;cout<<setw(8)<<flag->name;cout<<setw(8)<<flag->ntime;cout<<setw(8)<<time;cout<<setw(10)<<(time + flag->ntime);cout<<setw(10)<<(time - flag->htime + flag->ntime);cout<<" "<<setw(11)<<(double)(tim

24、e-flag->htime + flag->ntime)/flag->ntime)<<endl; j=(time-flag->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

25、(p1->next!=flag)p1=p1->next;p1->next=flag->next;delete flag; /删除这个作业所占的节点cout<<"作业执行顺序为："for(ss=0;ss<n;ss+)cout<<pnamess;if(pnamess+1 !="")cout<<" -> "cout<<endl;cout<<" 平均周转时间为："<<runTime/n<<endl; co

26、ut<<"平均带权周转时间为："<<drunTime/n<<endl;cout<<"*"<<endl;5 测试与分析5.1 测试方案先选择算法，输入进程数、作业名、优先级、到达时间、估计运行时间，得出相应的作业名、提交时间 、开始时间 、结束时间 、周转时间、带权周转时间。通过四种算法之间的比较了解他们的优缺点。5.2 测试结果 5.3 结果分析由测试结果可知每种算法的优缺点：a）先来先服务算法：有利于长作业（进程）而不利于短作业（进程）有利于CPU繁忙型作业（进程）而不利于I/O繁忙型作业（进

27、程）。b)短作业优先算法：比FCFS改善平均周转时间和平均带权周转时间短作业的等待时间；提高系统的吞吐量；对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；c)难以准确估计作业（进程）的执行时间，从而影响调度性能。c)高优先权算法：动态优先级优点是使相应的优先级调度算法比较灵活、科学，可防止有些进程一直得不到调度，也可防止有些进程长期垄断处理机。动态优先级缺点是需要花费相当多的执行程序时间，因而花费的系统开销比较大。d)高响应比优先算法：短作业与先后次序的兼顾，且不会使长作业长期得不到服务响应比计算系统开销，增加系统开销。6 设计小结 通过改程序对操作系统的基础

28、知识了解得更透彻了，同时对磁盘调度的四种算法先来先服务算法，短进程优先调度算法，优先权算法，高响应比调度算法有了更深刻的理解和掌握，使我能够为进程调度选择适当的算法，提高CPU工作效率。进行进程调度程序设计的过程中，得到老师的大力指导和同学的支持，在此向他们表示感谢。经过自己的动手操作和同学老师的指导我成功的做出了课程设自己感到很高兴。在整个过程中自己也感受到了集体团结的力量，今后无论是在工作还是学习中我都会发样这种精神。7 参考文献1 韩立毛，李先锋. 计算机操作系统实践教程M，南京：南京大学出版社，2011.10.2 严蔚敏，吴伟民. 数据结构M，北京：清华大学出版社，1997.43 张尧

29、学，史美林. 计算机操作系统教程M，北京：清华大学出版社，2000.8.4 孙静宇. 计算机操作系统课程设计指导书M，山西：太原理工出版社，2006.4.附录 源程序代码#include<iostream>#include<string>#include<iomanip>using namespace std;#define MAX_NUM 15typedef struct JCBchar name10;/作业名float htime;/作业到达时间float ntime;/作业估计运行的时间float starttime;/作业开始运行时间float ft

30、ime;/作业完成的时间float zhouzhuan;/周转时间float daiquan;/带权周转时间float xiangyingbi;/相应比int super;/优先级JCB *next;/定义指向下一个作业的指针JCB;int jnum;/定义作业数为jnumfloat total;/记录所有作业的总时间double weight;/记录所有作业的带权周转时间JCB *create(JCB *head);/创建作业队列void dealFCFS(JCB *head);/FCFS记录处理void sortFCFS(JCB *head);/将作业按到达的先后顺序排列void FCFS

31、(JCB *head);/先来先服务算法void SJF(JCB *head,int n);/短作业优先算法void SUPER(JCB *head,int n);/高优先权优先算法void HRN(JCB *head,int n);/高响应比优先算法void main()int choice;cout<<" *进程调度算法实现*"<<endl;cout<<" *1.先来先服务算法*2.短作业优先算法*"<<endl;cout<<" *3.高优先权优先算法*4.高响应比优先算法*&qu

32、ot;<<endl;cout<<"*5. 退出*"<<endl;l1:cout<<"请输入您的选择："<<endl;l2:cin>>choice;JCB *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;

33、case 4:head=create(head);HRN(head,jnum);goto l1;case 5:break;default:cout<<"输入错误！n请重新输入："<<endl;goto l2;/创建节点与作业输入JCB *create(JCB *head)JCB *p1,*p2;p1=p2=new JCB;head=p1;cout<<"请输入作业数："cin>>jnum;for(int i=0;i<jnum;i+)p2=p1;p1=new JCB;p1->next=NULL;co

34、ut<<"请依次输入第"<<i+1<<"个作业的信息(作业名、优先级、到达时间、估计运行时间)："cin>>p1->name>>p1->super>>p1->htime>>p1->ntime; p2->next=p1;return head;/FCFS算法void sortFCFS(JCB *head)/将作业按到达的先后顺序排列JCB *p,*q,*r,*s;if(head->next!=NULL)p=head->next-&g

35、t;next;head->next->next=NULL;while(p)q=p;p=p->next;r=head;s=head->next;while(s&&s->htime<=q->htime)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

36、+q->ntime;q->zhouzhuan=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

37、=p->zhouzhuan/(double)p->ntime;total+=p->zhouzhuan; weight+=p->daiquan;q=p;p=p->next;void FCFS(JCB *head)/先来先服务算法dealFCFS(head);JCB *p,*q,*s;p=head->next;cout<<"作业执行顺序为："while(p!=NULL)cout<<"-"<<p->name;p=p->next;cout<<endl;cout<

38、<"作业名 提交时间 开始时间 结束时间 周转时间 带权周转时间n" s=head->next;while(s!=NULL)cout<<setw(4)<<s->name<<setw(7)<<s->htime<<setw(10)<<s->starttime<<setw(11)<<s->ftime<<setw(10)<<s->zhouzhuan<<setw(10)<<s->daiquan&

39、lt;<endl;s=s->next;cout<<endl; cout<<" 平均周转时间："<<total/(double)jnum<<endl;cout<<"平均带权周转时间："<<weight/(double)jnum<<endl;cout<<"*"<<endl;total=0;weight=0;/SJF短作业优先算法void SJF(JCB *head,int n)JCB *p,*p1;JCB *flag=N

40、ULL;JCB *q=NULL; double time=0,j=0,runTime=0, drunTime=0;int xuhao=0;string pnameMAX_NUM;for(int ss=0;ss<MAX_NUM;ss+)pnamess=""sortFCFS(head);cout<<endl;cout<<" 顺序 作业名 提交时间 开始时间 结束时间 周转时间 带权周转时间n"head=head->next;p=head;while(head)q=head;if(time < p->htime)

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

42、lt;setw(8)<<time;cout<<setw(10)<<(time + flag->ntime);cout<<setw(10)<<(time - flag->htime + flag->ntime);cout<<" "<<setw(11)<<(double)(time-flag->htime + flag->ntime)/flag->ntime)<<endl;j=(time-flag->htime+flag->

43、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<<

44、;"作业执行顺序为："for(ss=0;ss<n;ss+)cout<<pnamess;if(pnamess+1 !="")cout<<" -> "cout<<endl;cout<<" 平均周转时间为："<<runTime/n<<endl; cout<<"平均带权周转时间为："<<drunTime/n<<endl;cout<<"*"<<

45、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;ss<MAX_NUM;ss+)pnamess=""sortFCFS(head);cout<<endl;cout<<" 顺序 作业名 提交时间 开始时间 结束时间 周转时间 带权周转时间n"head=h

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

47、ag->name;cout<<setw(8)<<flag->ntime;cout<<setw(8)<<time;cout<<setw(10)<<(time + flag->ntime);cout<<setw(10)<<(time - flag->htime + flag->ntime);cout<<" "<<setw(11)<<(double)(time-flag->htime + flag->ntim

48、e)/flag->ntime)<<endl; j=(time-flag->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->nex

49、t;p1->next=flag->next;delete flag; /删除这个作业所占的节点cout<<"作业执行顺序为："for(ss=0;ss<n;ss+)cout<<pnamess;if(pnamess+1 !="")cout<<" -> "cout<<endl;cout<<" 平均周转时间为："<<runTime/n<<endl; cout<<"平均带权周转时间为："<<drunTime/n<<endl;cout<<"*"<<endl;/高相应比优先算法void HRN(JCB *head,int n)JCB *p,*p1;JCB *flag=NULL;JCB *