进程调度模拟优先级和最高相应比

1、学 号： 课 程 设 计题 目进程调度模拟设计优先级法、最高响应比优先调度算法学 院计算机科学与技术专 业计算机科学与技术班 级计算机 班姓 名指导教师2012年1月12日目 录1课程设计目的与功能描述31.1目的描述31.2功能描述32.需求分析42.1基本原理4优先级调度算法4最高响应比调度算法42.2基本需求设计53程序设计53.1数据结构53.2模块说明6主要函数模块及功能6模块框图63.2.4 程序流程图74. 开发平台及源程序的主要部分104.1开发平台104.2源程序的主要部分105. 程序测试175.1测试用例175.2程运行结果及分析18对测试用例的验证18对基本错误处理20

2、其他功能226. 自我评价与总结256.1自我评价256.2经验与收获256.3对算法改进的想法27本科生课程设计成绩评定表28课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位： 计算机科学与技术学院 题 目: 进程调度模拟设计优先级法、最高响应比优先调度算法 初始条件：1预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1模拟进程调度，能够处理以下的情形： 能够选择不同的调度算法（要求中给出的调度算法）； 能够输入进程的

3、基本信息，如进程名、优先级、到达时间和运行时间等； 根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。2设计报告内容应说明： 课程设计目的与功能； 需求分析，数据结构或模块说明(功能与框图)； 源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。时间安排：设计安排一周：周1

4、、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日进程调度模拟设计优先级法、最高响应比优先调度算法1课程设计目的与功能描述1.1目的描述学习完计算机操作系统这门专业课后，对计算机操作系统的组成和功能有了一定的了解；基于此，在掌握操作系统实现进程调度以及对进程调度算法了解的基础上，编写一个程序，来模拟计算机操作系统进程的调度过程，从而加深对计算机操作系统进程调度各算法的在认识和理解；我抽到的题目为：进程调度模拟设计优先级法、最高响应

5、比优先调度算法。1.2功能描述此次我编写程序为C+语言模拟进程调度的程序，主要功能有：1 选择不同的调度算法，主要为选择优先级法、最高响应比优先调度算法；2 输入进程的基本信息，如进程名、优先级、到达时间和运行时间；3 根据选择的调度算法显示进程调度队列；4 根据选择的调度算法计算平均周转时间和平均带权周转时间并显示。5 对基本的输入错误进行处理，如：输入进程信息时要求进程名不能相同，到达时间、运行时间和优先级必须为正等输入错误。2.需求分析2.1基本原理2.1.1优先级调度算法优先级法可被用作作业或进程的调度策略。首先，系统或用户按某种原则为作业或进程指定一个优先级来表示该作业或进程所享有的

6、调度优先权。该算法的核心是确定进程或作业的优先级，此次课程设计采用静态优先级。作业调度中的静态优先级大多按以下原则确定： 1 由用户自己根据作业的紧急程度输入一个适当的优先级。为防止各用户都将自己的作业冠以高优先级，系统应对高优先级用户收取较高的费用。 2 由系统或操作员根据作业类型指定优先级。作业类型一般由用户约定或由操作员指定。可将作业分为： IO繁忙的作业、CPU繁忙的作业、IO与CPU均衡的作业、一般作业等，系统或操作员可以给每类作业指定不同的优先级。 3 系统根据作业要求资源情况确定优先级。例如根据估计所需处理机时间、内存量大小、IO设备类型及数量等，确定作业的优先级。 进程的静态优

7、先级确定原则可以是： Ø 按进程的类型给予不同的优先级。例如，在有些系统中，进程被划分为系统进程和用户进程。系统进程享有比用户进程高的优先级。对于用户进程来说，则可以分为： IO繁忙的进程、CPU繁忙的进程、IO与CPU均衡的进程、其他进程。对系统进程，也可以根据其所要完成的功能划分为不同的类型，例如，调度进程、IO进程、中断处理进程、存储管理进程等。Ø 将作业的静态优先级作为它所属进程的优先级。2.2.2最高响应比调度算法最高响应比优先法（HRN）是对FCFS方式和SJF 方式的一种综合平衡。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响

8、应比最高的作业投入执行。 响应比R定义： R=(W+T)/T=1+W/T其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。 每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W/T也就随着增加，也就有机会获得调度执行。2.2基本需求设计程序实现模拟进程调度的优先级调度算法和最高响应比调度算法；基本需求设计如下：进程信息的输入、输出采用命令行界面；程序执行过程如下：首先 输入进程信息，可连续添加；其次 选择调度算法：优先级和最高响应比调度算法；然后 根据选择的调度算法，执行相关函数，显示进程调度序列，输出总进程

9、周转时间、总带权周转时间、平均周转时间、平均带权周转时间；最后 可再次选择调度算法、重新创建进程链、销毁进程链，如果选择销毁进程队列，则退出程序。3程序设计3.1数据结构此次课程设计的存储结构采用链表的数据结构，用链表的各个接点保存进程的相关信息，可实现对进程链的排序、删除、比较查找等。存储结构如下：struct ProcessProcess *pNext; string name; /进程名double readytime; /进程提交时间double runtime; /运行时间double priority; /进程的优先级;3.2模块说明3.2.1主要函数模块及功能主要函数模块及功能如

10、下：Process * Add( Process * pHead)功能：主要完成要求用户输入进程的相关信息：进程名、进程提交时间、进程运行时间、进程优先级；按输入的提交时间的先后顺序组织进程链，同时对用户的一些简单的错误输入进行处理。Process * Copy(Process * pHead) 功能：实现对用户创建的进程链的深复制，由于要进行多次的进程调度，而每次的调度均会删除进程链中的各个接点，直至链表为空，因此要将原进程链保存，每次只是对复制链进行操作。Process* Destroy(Process *pHead) 功能：实现对进程各个接点的销毁回收。void Hrn(Process*

11、pHead,int n) 功能：最高响应比调度算法执行函数，采用最高响应比的调度算法，实现对进程链的执行，并输出周转时间、带权周转时间、平均周转时间、平均带权周转时间。void Highpriority(Process*pHead,int n)功能：优先级调度算法执行函数，采用高优先级调度算法，实现对进程链的执行，并输出周转时间、带权周转时间、平均周转时间、平均带权周转时间。int main()功能：程序的入口，提供人机交互函数，提示用户创建进程序列，选择调度算法。3.2.2模块框图主函数模块销毁进程链模块最高响应比调度模块优先级调度模块输入进程模块图 3 - 13.2.4 程序流程图本次程序

12、流程图如下其他输入YN cpHead->pnext31优先级调度算法24选择操作：优先级1、最高响应比2、重新创建进程链3、销毁进程链4开始选择 1、2、3、4最高响应比优先算法重新创建进程链销毁进程链创建进程链继续？Y/N结束退出图 3 - 2优先级调度算法流程图：否是否是否是开始复制进程链取cpHeadtime =头接点提交时间从所有提交时间不大于time中选取一个优先级最大进程flagtime<flag->readytime ?cpHead是否为空？time = flag->readytime 输出flag执行信息删除flagFlag = c pHead ？输出周

13、转时间和带权周转时间完毕返回cpHead = cpHead->pnext图 3 - 3最高响应比调度算法流程图：否是否是否是开始复制进程链取cpHeadtime =头接点提交时间从提交时间不大于time进程中选取一个响应比最大进程flagtime<flag->readytime ?cpHead是否为空？time = flag->readytime 输出flag执行信息删除flagFlag = c pHead ？输出周转时间和带权周转时间完毕返回cpHead = cpHead->pnext图 3 - 44. 开发平台及源程序的主要部分4.1开发平台开发环境：Wind

14、ows7平台开发平台：VC+6.04.2源程序的主要部分输入进程信息源程序：Process * Add( Process * pHead)int mksure=1,i=1; /用来判断是否继续输入的标志cout<<"*<请输入进程队列!>*n"while(mksure=1) Process *p,*q;p=new Process;cout<<"请输入第 "<<i<<" 个进程的信息："<<endl;cout<<" 进程名: "cin

15、>>p->name;do cout<<"提交时间: "cin>>p->readytime;if(p->readytime<0)cout<<"输入时间有误，重新输入！"while(p->readytime<0);do cout<<"运行时间: "cin>>p->runtime;if(p->runtime<0)cout<<"输入时间有误，重新输入！"while(p->runti

16、me<0);do cout<<" 优先级: "cin>>p->priority;if(p->priority<0)cout<<"输入优先级有误，重新输入！"while(p->priority<0);p->pNext=NULL;if(pHead = NULL) /假如链表为空，加到链表头 pHead=p; else /其他情况 q=pHead;while(q) if(p->name = q->name) cout<<"你输入的进程名字与已创建进程

17、重名，请重新输入！"<<endl;break;else q=q->pNext;if(q) continue;i- else q=pHead;while( q ) if(q->pNext!=NULL) && (p->readytime >= q->pNext->readytime) /当q节点的下一结点不为空，或提交时间小于要添加节点的提交时间q=q->pNext;else break; /如果要加入进程提交时间早于头结点，将该节点作为头结点if(q = pHead && q->readytim

18、e > p->readytime) pHead=p;p->pNext=q; /如果加入的进程提交时间早于q节点进程，则将其插入q之前else p->pNext=q->pNext;q->pNext=p; cout<<"继续添加? 是 - 1，否 - 0 n"cout<<"你的选择："cin>>mksure;if(mksure=1) i+;cout<<"-n" cout<<"*<进程队列创建完毕!>*n"retu

19、rn pHead;优先级调度算法源程序：void Highpriority(Process*pHead,int n)Process *p,*cpHead,*p1;Process *flag=NULL;Process *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=""cpHead=Copy(pHead);if(cpHead=NULL)return ;cout<<"*&

20、lt;优先级调度算法，进程调度结果如下：>*n"cout<<" 顺序 进程名 优先级 开始时间 结束时间 周转时间 带权周转时间n"p=cpHead;while(cpHead) q=cpHead;if(time < p->readytime) /如果进程提交时间早于要比较的进程，则先执行time=p->readytime; flag=cpHead;while( q && q->readytime <= time) if(q->priority > flag->priority) /比

21、较进程的优先级flag=q;q=q->pNext; if(time < flag->readytime)/如果上一次结束时间比当前选中要执行进程的结束时间小time=flag->readytime; /则当前进程开始时间为提交时间cout<<setw(4)<<xuhao+1;cout<<setw(8)<<flag->name;cout<<setw(8)<<flag->priority;cout<<setw(8)<<time;cout<<setw(10)

22、<<(time + flag->runtime);cout<<setw(10)<<(time - flag->readytime + flag->runtime);cout<<setw(11)<<(double)(time-flag->readytime + flag->runtime)/flag->runtime)<<endl;j=(time - flag->readytime + flag->runtime); /当前执行进程的周转时间runTime+=j; /记录周转时

23、间time += flag->runtime;drunTime=drunTime+j/flag->runtime; /带权周转时间pnamexuhao=flag->name;xuhao+; /将执行过的进程从链表中删除if(flag=cpHead) /最先开始执行的进程就在链表头cpHead=cpHead->pNext;else /最先开始执行的进程在链表中p1=cpHead;while(p1->pNext!=flag)p1=p1->pNext;p1->pNext=flag->pNext;delete flag; /删除这个进程所占的节点 cou

24、t<<"进程执行顺序为："for(int ss=0;ss<n;ss+) cout<<pnamess;if(pnamess+1 !="")cout<<" -> " cout<<endl;cout<<" 总周转时间为："<<runTime<<endl;cout<<" 总带权周转时间为："<<drunTime<<endl;cout<<" 平均周转时间

25、为："<<runTime/n<<endl; cout<<"平均带权周转时间为："<<drunTime/n<<endl;cout<<"*<进程执行结束!>*n"最高响应比调度算法源程序：void Hrn(Process*pHead,int n)Process *p,*cpHead,*p1;Process *flag=NULL;Process *q=NULL; double time=0,j=0,runTime=0, drunTime=0;int xuhao=0;s

26、tring pnameMAX_NUM;for(int ss=0;ss<MAX_NUM;ss+)pnamess=""cpHead=Copy(pHead);if(cpHead=NULL)return ;cout<<"*<最高响应比优先算法，进程调度结果如下：>*n"cout<<" 顺序 进程名 优先级 开始时间 结束时间 周转时间 带权周转时间n"p=cpHead;while(cpHead) q=cpHead;if(time < p->readytime) /如果该进程提交时间早于其它

27、进程，则先执行该进程time=p->readytime;flag=cpHead; /用于暂存将要执行的进程/计算当前链表中进程的响应比while(q && q->readytime <= time)if(time - q->readytime)/(q->runtime) > (time - flag->readytime)/(flag->runtime)flag=q;q=q->pNext; if(time < flag->readytime) /如果上一次结束时间比当前选中要执行进程的结束时间小time=flag

28、->readytime; /则当前进程开始时间为提交时间 cout<<setw(4)<<xuhao+1;cout<<setw(8)<<flag->name;cout<<setw(8)<<flag->priority;cout<<setw(8)<<time;cout<<setw(10)<<(time + flag->runtime);cout<<setw(10)<<(time - flag->readytime + flag

29、->runtime);cout<<" "<<setw(11)<<(double)(time-flag->readytime + flag->runtime)/flag->runtime)<<endl; j=(time-flag->readytime+flag->runtime); /当前执行进程的周转时间runTime +=j; /记录周转时间time+=flag->runtime;drunTime+=j/flag->runtime; /带权周转时间pnamexuhao=flag

30、->name;xuhao+;/将执行过的进程从链表中删除if(flag=cpHead) /在链表头cpHead=cpHead->pNext; else /在链表中p1=cpHead;while(p1->pNext!=flag)p1=p1->pNext;p1->pNext=flag->pNext;delete flag; /删除这个进程所占的节点 cout<<"进程执行顺序为："for(int ss=0;ss<n;ss+) out<<pnamess;if(pnamess+1 !="")cou

31、t<<" -> " cout<<endl;cout<<" 总周转时间为："<<runTime<<endl;cout<<" 总带权周转时间为："<<drunTime<<endl;cout<<" 平均周转时间为："<<runTime/n<<endl; cout<<"平均带权周转时间为："<<drunTime/n<<endl;co

32、ut<<"*<进程执行结束!>*n"主函数源程序如下：int main() cout<<"tt*"<<endl;cout<<"tt* 欢迎使用模拟进程调度程序! *"<<endl;cout<<"tt* 当前没有可执行进程，进程请先创建进程！ *"<<endl;cout<<"tt* 输入的提交时间、运行时间、优先级均需大于零！ *"<<endl;cout<<"

33、;tt*"<<endl;Process * pHead = NULL; pHead=Add(pHead);Output(pHead);char again;do cout<<"*n"/输入选择的算法int decision;cout<<"tt*"<<endl;cout<<"tt* 请选择进程调度算法! *"<<endl;cout<<"tt* 1.优先级调度算法！ *"<<endl;cout<<&qu

34、ot;tt* 2.最高响应比优先算法！ *"<<endl;cout<<"tt* 3.重新创建进程链！ *"<<endl;cout<<"tt* 4.销毁进程队列，退出程序！ *"<<endl;cout<<"tt*"<<endl;do cout<<"你的选择："cin>>decision;if(decision=1) / 优先级调度算法 Highpriority(pHead,count);if(deci

35、sion =2)/最高响应比算法Hrn(pHead,count);if(decision =3) pHead=NULL;pHead=Add(pHead);Output(pHead); if(decision =4) pHead=Destroy(pHead);break; if(decision !=1 && decision!=2 && decision!=3 && decision!=4)cout<<"输入有误，请重新输入！n"while(decision !=1 && decision!=2 &

36、amp;& decision!=3);if(decision = 4)break;cout<<"继续选择调度算法？是（Y）否（N）n"cout<<"你的选择："cin>>again;while(again='Y' | again='y' | (char)again=1);system("pause"); return 0;复制进程链函数源程序如下：Process * Copy(Process * pHead)Process * p,*cpHead,*q,*te

37、mp;cpHead=NULL;q=pHead;p=new Process;int i=1;while(q)p->pNext=NULL;p->name=q->name;p->priority=q->priority;p->readytime=q->readytime;p->runtime=q->runtime;temp=p;if(cpHead=NULL)cpHead=p;q=q->pNext;if(q) p=new Process;if(i=1)cpHead->pNext=p;temp->pNext=p;i+; return

38、 cpHead;销毁进程链函数源代码如下:Process* Destroy(Process *pHead)Process *dp,*dq;dp=pHead->pNext;pHead=NULL;while(dp) dq=dp;dp=dp->pNext;delete dq;cout<<"进程队列已经销毁！不能执行再次进程调度了！n"return pHead;输出进程链信息函数源代码如下：void Output(Process * pHead)Process *s=pHead;cout<<"*生成的进程链表如下：*n"cou

39、t<<"t进程名 提交时间 运行时间 优先级"<<endl;while(s) cout<<"t"<<setw(4)<<s->name<<setw(8)<<s->readytime<<setw(10)<<s->runtime<<setw(9)<<s->priority<<"n"s=s->pNext; count+; 5. 程序测试5.1测试用例测试用例的输入进程信息

40、为：进程名提交时间运行时间优先级PP11.021PP22.012PP32.523表 5 1采用优先级调度算法1.0时刻 只有进程PP1提交到达系统，故执行进程PP13.0时刻 进程PP2、PP3均已到达系统，但由于PP3优先级高于PP2优先级，故执行进程PP35.0时刻 进程PP3执行完毕，执行进程PP26.0时刻 进程PP2执行完毕进程调度顺序为：PP1 à PP3 àPP2执行信息如表：进程名提交时间运行时间优先级开始时间结束时间周转时间带权周转时间PP11.0211.03.02.01.0PP22.0125.06.04.04.0PP32.5233.05.02.51.25

41、表 5 2平均周转时间：8.5/3=2.833平均带权周转时间：6.25/3=2.083采用最高响应比优先调度算法1.0时刻 只有进程PP1提交到达系统，故执行进程PP13.0时刻 进程PP2、PP3均已到达系统，响应比：RPP2=1+1.0/1=2；RPP3=1+0.5/2=1.25，故执行进程PP24.0时刻 进程PP2执行完毕，执行进程PP36.0时刻 进程PP3执行完毕进程调度顺序为：PP1 à PP2 àPP3执行信息如表：进程名提交时间运行时间优先级开始时间结束时间周转时间带权周转时间PP11.0211.03.02.01.0PP22.0123.04.02.02.

42、0PP32.5234.06.03.51.75表 5 3平均周转时间：7.5/3=2.5平均带权周转时间：4.75/3=1.5835.2程运行结果及分析5.2.1对测试用例的验证输入用例中的进程信息，如图：图 5 1选择优先级调度算法，执行结果如图：图 5 2分析 从程序运行结果来看，结果与5.1理论分析一直，说明程序运行结果正确！采用最高响应比优先的调度算法，执行结果如图：图 5 3分析 从程序运行结果来看，结果与5.1理论分析一直，说明程序运行结果正确！5.2.2对基本错误处理本程序考虑的基本输入错误信息有：进程提交时间、运行时间、优先级小于零，选择算法操作时未按要求输入；其他异常情况为：进

43、程同名，由于每个进程有一个唯一的进程控制块（PCB），要求进程控制号、进程名字不一样，因此模拟时应考虑到输入进程同名的情况。Ø 当输入进程的提交时间、运行时间、优先级小于零时，程序提示输入错误，要求用户重新输入！程序执行结果如图：图 5 4图 5 5图 5 6Ø 当输入进程与已输入的进程同名时，程序进行检测，并提示用户重新输入该进程信息，执行结果如图：图 5 7Ø 当进程链创建完毕后，选择相关操作，当未按要求输入时，比如输入非1、2、3的数字，提示输入错误，并要求用户重新输入，执行结果如下：图 5 85.2.3其他功能本程序还可以重新创建进程链表，作为下一次调度算

44、法的检测，执行如下图：图 5 9图 5 10图 5 116. 自我评价与总结6.1自我评价计算机操作系统这门课程是计算机专业一门基础性学科，重要性可见一斑，学好这门课程对以后人生的发展具有深远的影响。而课程设计便是对学习效果的检验。数课程设计不仅可以锻炼我们独立思考问题、解决问题的能力，而且可以培养我们的整体性思维的能力；通过课程设计，使我加深了对操作系统进程调度各个调度算法的再认识，特别是优先级调度算法和最高响应比优先调度算法；巩固了很多操作系统和C+编程基础性知识，比如：存储结构、信息查找比较、算法设计等。出色的地方本次课程设计，刚开始看到课程设计题目时，感觉有些难度，通过对优先级和最高响

45、应比优先调度算法的再次复习，最终确定了其设计的算法。程序实现了用优先级和最高响应比优先调度算法模拟进程调度，而且结果与理论分析完全一致，说明程序正确，此外对于选中的满足调度算法的进程，如果提交时间比上一次进程执行完毕时的时间还大，则该进程的开始时间为自己的提交时间，而非上一次进程执行完成时的结束时间；同时，考虑到了用户的输入错误，对进程提交时间、运行时间、优先级小于零、选择操作未按要求等输入错误进行了处理；对输入进程同名的情况进行排除并要求用户重新输入。不好的地方程序总虽然考虑了一些用户输入错误，并对其进行处理，但是这种处理是不完善的，只能对如：进程提交时间、运行时间、优先级小于零、选择操作未

46、按要求等输入错误进行了处理，而对进程提交时间、运行时间、优先级、选择操作不为数值等情况进行了处理，这样异常处理是片面的不完善的，对于此种情况，可以用JAVA语言来编写这次程序，利用其强大的系统异常和处理机制可以很好的解决上述问题；两种调度算法输出各进程执行情况时，直接将输出语句放在调度算法之中，这样由于两种输出基本上一样，增加了程序的存储开销，可以将输出单独作为一个函数进行输出处理。6.2经验与收获这次课程设计，我明白了对于编写程序，解题的思路尤为重要。在编写程序之前，如果没有比较清晰的思路，根本不可能编出好的程序。就算马马虎虎的编出来，程序的逻辑性、健壮性、完善性、合理性也不会很强。在编程之前，我们应反复研究题目要求，对题目涉及的情况进行比较充分的分析，以便编写出更加符合题意的程序；其次要充分考虑各种临界情况，对一些错误的输入进行处理。因此在我们编程序之前一定要做好充分的准备，首先要理清自己的思路，然后再将思路分划成几个模块，逐块的写好算法，最后再将所有的模块有机的联系起来，组成一个完整的程