08级操作系统课程设计报告书

课程设计报告书2011/2012学年第1学期课程名称：操作系统实践课程设计专业班级：学号：姓名：指导教师：课程设计指导教师评语成绩：____________指导教师签字：________________题目1进程调度算法的模拟1．1题目的主要研究内容及预期达到的目标（1）编程序模拟实现进程调度算法中的FCFS、SJF和高响应比优先算法。（2）基本完成了模拟实现FCFS、SJF和HRN调度算法。1．2题目研究的工作基础或实验条件（1）硬件环境：windows系统（2）软件环境：VisualC++1．3设计思想（1）FCFS:将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。进程可以未使用完一个时间片，就出让CPU（如阻塞）。(2)SJF：对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。（3）HRN：HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。响应比R定义如下：R=(W+T)/T=1+W/T其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。1．4流程图1．5主要程序代码#includeiostream.h#includestdio.h#includestdlib.h#defineN100typedefstructJCB{intID;/*作业标识数*/intrequesttime;/*作业运行所需时间*/intruntime;/*作业实际运行所需时间*/intpriority;/*作业优先数*/intquick;/*作业紧迫程度*/}JCB;JCBjcb[N];intjcbnum;/*后备作业数*/voidinit();/*赋值函数*/voidFCFS();/*定义FCFS函数*/voidSJF();/*定义SJF函数*/voidHRN();/*定义HRN函数*/voidmain()/*main函数*/{inti=0;init();cout==============================endl;cout|1:FCFS2:SJF|endl;cout|3:HRN|endl;cout==============================endl;while(i=0||i=5)/*while循环选择算法*/{coutPleaseselectanumber(1,2,3,4):endl;cini;}switch(i)/*switch语句选择执行函数*/{case1:FCFS();break;case2:SJF();break;case3:HRN();break;}}voidinit()/*对定义的变量进行赋值的函数*/{inti=0;while(i=0||i=2000){coutInputtheJCBnumber:(1--2000)endl;cini;}jcbnum=i;for(i=0;ijcbnum;i++)/*for循环赋值语句*/{jcb[i].ID=i+1;jcb[i].priority=rand()%100+1;jcb[i].quick=rand()%5+1;jcb[i].requesttime=rand()%1000+1;}}voidFCFS()/*FCFS函数*/{inti;intw=0,t=0;intWaittime=0;/*给waitime赋值*/coutThisisfristcomefistserver:endl;for(i=0;ijcbnum;i++)/*for循环语句*/{coutTheNO.jcb[i].IDJCBenterMemory.endl;Waittime+=jcb[i].requesttime;w=(Waittime-t)/(jcb[i].requesttime);cout带权周转时间为：wendl;t++;}}voidSJF()/*SJF函数*/{inti,j,dest,Waittime,w,t=0;/*定义的变量*/coutThisisshortestjobfirst:endl;while(jcbnum0){dest=0;for(i=0;ijcbnum;i++)/*for循环语句*/if(jcb[dest].requesttimejcb[i].requesttime)/*条件语句*/dest=i;coutTheNO.jcb[dest].IDJCBenterMermoryendl;Waittime+=jcb[dest].requesttime;w=(Waittime-t)/(jcb[dest].requesttime);cout带权周转时间为：wendl;t++;for(j=dest;jjcbnum-1;j++)/*用for语句进行赋值*/{jcb[j].ID=jcb[j+1].ID;jcb[j].requesttime=jcb[j+1].requesttime;}jcbnum--;}}voidHRN()/*HRN函数*/{inti,j,dest;/*定义的变量*/intwaittime=0;/*给waitime赋值*/coutThisisHighestresponseratiofirstendl;while(jcbnum0){dest=0;for(i=0;ijcbnum;i++)/*for循环语句*/if(waittime/(jcb[dest].requesttime)(waittime/(jcb[i].requesttime)))/*条件语句*/dest=i;coutTheNO.jcb[dest].IDJCBenterMemory.endl;waittime+=jcb[dest].requesttime;/*给waittime赋新值*/for(j=dest;jjcbnum-1;j++)/*用for语句进行赋值*/{jcb[j].ID=jcb[j+1].ID;jcb[j].requesttime=jcb[j+1].requesttime;}jcbnum--;}}1．6运行结果及分析（1）FCFS算法运行结果（2）SJF算法运行结果：（3）HRN算法运行结果1．7心得体会整个设计中最麻烦的就是程序模块的划分和各模块之间接口设计，编程经常犯想当然的错误，出现了不少奇怪的错误。再调试中尝试使用了分割法,对错误模块进行定位,再进行排查.在算法实现上要有一定的思路体现设计的目的。同时上机调试也是十分重要的，在调试的过程中能够不断的发现在编写算法时应该注意的一些细节和算法语句的非法使用，在调试过程中通过对算法的不断测试、更正、扩充功能、修饰细节，使算法程序不断的得到完善。题目2银行家算法的实现1．1题目的主要研究内容及预期达到的目标（1）编程序模拟实现银行家算法。（2）基本完成了模拟实现银行家算法。1．2题目研究的工作基础或实验条件（1）硬件环境：windows系统（2）软件环境：C语言1．3设计思想（1）银行家算法假设在进程并发执行时进程i提出请求j类资源k个后，表示Requesti[j]=k。系统按下述步骤进行安全检查：1）如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。2）如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。（2）安全性算法1）设置两个向量：①工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;②Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false;当有足够资源分配给进程时，再令Finish［i］∶=true。2）从进程集合中找到一个能满足下述条件的进程：①Finish［i］=false;②Need［i,j］≤Work［j］；若找到，执行步骤(3)，否则，执行步骤(4)。3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;gotostep2;4）如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。1．4流程图1．5主要程序代码#includeiostreamusingnamespacestd;#defineMAXPROCESS50/*最大进程数*/#defineMAXRESOURCE100/*最大资源数*/intAVAILABLE[MAXRESOURCE];/*可用资源数组*/intMAX[MAXPROCESS][MAXRESOURCE];/*最大需求矩阵*/结束否是申请失败。以上分配作废，恢复原来的分配状态：Available[j]=Available[j]+Request[i][j]Allocation[i][j]=Allocation[i][j]－Request[i][j]Need[i][j]=Need[i][j]+Request[i][j]NYNYRequest[i][j]Need[i][j]出错返回：return(error)Request[i][j]Available[j]出错返回：(进程阻塞)return(error)Available[j]=Available[j]–Request[i][j]Allocation[i][j]=Allocation[i][j]+Request[i][j]Need[i][j]=Need[i][j]–Request[i][j]假定分配：输入初始参数（资源分配及请求情况）开始假定分配之后，系统安全吗？申请成功。输出各种数据的变化银行家算法流程图intALLOCATION[MAXPROCESS][MAXRESOURCE];/*分配矩阵*/intNEED[MAXPROCESS][MAXRESOURCE];/*需求矩阵*/intREQUEST[MAXPROCESS][MAXRESOURCE];/*进程需要资源数*/boolFINISH[MAXPROCESS];/*系统是否有足够的资源分配*/intp[MAXPROCESS];/*记录序列*/intm,n;/*m个进程,n个资源*/voidInit();boolSafe();voidDijkstra();intmain(){Init();Safe();Dijkstra();}voidInit()/*初始化算法*/{inti,j;cout请输入进程的数目:;cinm;cout请输入资源的种类:;cinn;cout请输入每个进程最多所需的各资源数,按照mxn矩阵输入endl;for(i=0;im;i++)for(j=0;jn;j++)cinMAX[i][j];cout请输入每个进程已分配的各资源数,也按照mxn矩阵输入e