进程调度算法磁盘调度算法银行家算法操作系统课程设

1、PAGE PAGE 60操作系统课程设计说明书学院名称： 专业班级： 姓 名： 学 号： 2013年1月月1日评分标准优秀：有完整的的符合标准的的文档，文档档有条理、文文笔通顺，格格式正确，程程序完全实现现设计要求，独独立完成；良好：有完整的的符合标准的的文档，文档档有条理、文文笔通顺，格格式正确；程程序完全实现现设计要求，独独立完成，但但存在少量错错误；中等：有完整的的符合标准的的文档，有基基本实现设计计方案的软件件，设计方案案正确；及格：有完整的的符合标准的的文档，有基基本实现设计计方案的软件件，设计方案案基本正确；不及格：没有完完整的符合标标准的文档，软软件没有基本本实现设计方方案，设计

2、方方案不正确。没没有独立完成成，抄袭或雷雷同。成绩评定为： 。 指导教师： 年年 月 日目 录 一进程调度算算法 423 页二银行家算法法 24344 页三磁盘调度算算法 35466页进程调度算法1设计目的 在多多道程序设计计中，经常是是若干个进程程同时处于就就绪状态，必必须依照某种种策略决定哪哪个进程优先先占有处理机机，因而必须须解决进程调调度的问题，进进程调度算法法就是要解决决进程调度的的问题。2. 任务及要要求2.1 设计任任务 设计计程序来模拟拟进程的四种种调度算法，模模拟实现调度度的基本功能能。2.2 设计要要求 产生生的各种随机机数要加以限限制，如allltimee限制在400以内

3、的整数数。进程的数量n不不能取值过大大。3. 算法及数数据结构3.1算法的总总体思想（流流程） 每个个用来标识进进程的进程控控制块PCBB用结构来描描述，包括以以下字段：（1）进程优先先数ID，其其中0为闲逛逛进程，用户户进程的标识识数为1，22，3。（2）进程优先先级Prioority，闲闲逛进程（iidle）的的优先级为00，用户进程程的优先级大大于0，且随随机产生，优优先数越大，优优先级越高。（3）进程占用用的CPU时时间CPUttime，进进程每运行一一次，累计值值等于4。（4）进程总共共需要运行时时间Allttime，利利用随机函数数产生。（5）进程状态态，0：就绪绪态；1：运运行态

4、；2：阻塞态。 利用链表将数数据连接起来来，实现数据据的存储。3.2 链表模模块3.2.1 功功能 实现链链表的存储功功能，以及实实现存储的查查找功能。3.2.2 数数据结构 构造链链表这个数据据结构，以及及链表的初始始化，链表的的插入，链表表的长度。3.2.3 算算法 typeddef sttruct EllemTyppe *eelem; innt leength; innt liistsizze; SqLisst;Status InitLList(SSqListt &l)l.elemm=(EleemTypee*)mallloc(LLIST_IINIT_SSIZE*ssizeoff(Elem

5、mType);if(!l.elem) exxit(OVVERFLOOW);l.lenggth=0;l.listtsize=LIST_INIT_SIZE;returnn OK;int LisstLenggth(SqqList l)returnn(l.leength);Status ListIInsertt_Sq(SSqListt &L,iint i, ElemmType e)/在顺序表LL的第i个位位置前插入元元素e,i的的合法值为11.L.llengthh+1 if(iL.lenngth+11) retuurn ERRROR; if(L.lengtth=L.listssize) EElemTy

6、ype*neewbasee=(EleemTypee *)reeallocc(L.ellem,(LL.listtsize+LISTIINCREMMENT)*sizeoof(EleemTypee); iif(!neewbasee) exitt(OVERRFLOW); LL.elemm=newbbase; L.liistsizze+=LIISTINCCREMENNT; ElemTType *q=&L.elemi-1, *p=&L.eleemL.llengthh-1; whilee(p=qq) *(p+1)=*pp; -pp; /插入位置后后的元素右移移 *q=e; +L.llengthh; retu

7、rrn OK;Status GetEllem(SqqList L,intt i,EllemTyppe &e)if(iL.lenngth)returrn ERRROR;elsee=*(LL.elemm+i-1);returnn OK;void Ouutputllist(SSqListt &L)if(0=L.lenngth)printtf(空集集!);else for(int ii=0;iL.lenngth;+i) priintf(%c,*(L.ellem+i);3.3 主函数数模块3.3.1功能能 实现进程程调度的四种种算法，以及及人机交互的的菜单。3.3.2 数数据结构 主要包括括五个部分，分

8、分别是四种算算法，和进程程的输入和菜菜单部分，功功能分别实现现。3.3.3算法法void maain()for(1;)int nnumberr; PCBB pcbb100 ;srand(time(0);int maax;int pppp1000;int ttime=00;int ttime1;int mm;int aa100;a0=00;printff(n*进进程调度算法法的模拟*n);printff(* 1.先先到先服务调调度 2.最最短作业优先先调度 *nn);printff(* 3.优优先权调度 44.轮转发调调度 *nn);printff(*);printff(n请请选择调度的的方法:

9、 );scanf(%d,&m);if(m!=1&m!=2&mm!=3&m!=4) priintf(输入错误! 重新输入入: ); scaanf(%d,&mm); if(m!=1&m!=22&m!=3&m!=4) prrintf(输入错误误! 重新输输入: ); scannf(%dd,&m); iff(m!=11&m!=2&m!=3&mm!=4) pprintff(输入错错误! 重新新输入: ); scanff(%d,&m); iif(m!=1&m!=2&mm!=3&m!=4) printtf(输入入错误! 重重新输入: ); sscanf(%d,&m); printff(请输入入进程的个数数:

10、 );scanf(%d,&numbber);printff(n开开始时用户进进程均为就绪绪状态,运行行时间随机产产生nnn);SqListt sq;InitLiist(sqq);for(innt r=00;rnuumber;r+)pcbrr.CPUUtime=0;for(innt i=00;inuumber;i+) pccbi.Priorrity=rrand()%50;whilee(1) iff(pcbi.Prrioritty20) pcbii.Priiorityy=randd()%500; ellse bbreak; pccbi.Alltiime=raand()%40;whilee(1) i

11、if(pcbbi.AAlltimme10) pcbii.Allltime=rand()%40;elsee breeak;for(innt j=00;jnuumber;j+)ListLLengthh(sq);ListIInsertt_Sq(ssq,LisstLenggth(sqq),pcbbi ); if(m=1) pprintff(n*程序演示开开始*nn); intt counn=0; /计数数变量 intt waitt100; /等待待时间数组 wwait00=0; iint Alllwaitt=0; ffor(innt i1=0;i1numbeer;i1+)priintf(下面开始调调用

12、第%d个个进程； n,i11); printtf(开始始时间为%dd 执执行时间为%dn,coun,pcbii1.Allltimee); coun+=pcbi1.AAlltimme; if(i11!=0)waaiti11=pcbbi1-11.Allltime+waiti1-1; ffor(innt i2=0;i2numbeer;i2+)Alllwait=waiti2+AAllwaiit; pprintff(平均等等待时间为:%dn,Allwwait/nnumberr); if(m=2) innt minn=pcb0.Allltimee; iint waait11100; waitt10=0;

13、int in=0; innt couun1=0; prrintf(*最短短作业优先调调度!*n); coout进程所需时时间分别是:enndl; foor(i=00;inuumber;i+) ccoutpcbii.Allltimeendll; prrintf(进程调度度的顺序为: ); foor(i=00;inuumber;i+) mmin=500; foor(j=00;jnuumber;j+) if(pccbj.Alltiimemiin) min=pcbjj.Allltime; iin=j; pprintff(%d ,inn+1); ppcbinn.Allltime+=50; if(m=3)

14、 prrintf(ID 优优先级 运行总总时间 进进程状态nn); foor(intt k=0; knuumber; k+) pprintff(%d %d %d 就绪nn,k+11, pcbbk.PPrioriity, ppcbk.Allttime); prrintf(n*程序调度度演示开始*n); foor(intt f=1;f10000;f+) iint ccount=0,couunt1=00; ffor(innt i=00;inuumber;i+) pppii=pcbbi.PPrioriity; if(ppcbi.Allttime!=0) counnt1+; ccount11-; tii

15、me=tiime+coount1*4; max=MMax(pppp,nummber); if(pcbmmax.AAlltimme=0) pppmmax=-1; pcbmax.Priorrity=-1; maax=Maxx(ppp,numbeer); ppcbmaax.Prrioritty-=4; pcbmmax.AAlltimme-=4; pcbbmax.CPUttime+=4; iff(pcbmax.Alltiime=00) pcbmmax.AAlltimme=0; foor(intt w=0;wnummber;ww+) if(pccbw.Alltiime=00) pppw=-11; pcb

16、bw.PPrioriity=-11; ffor(innt e=00; ennumberr;e+) pcbee.Priiorityy+; prrintf(n#第%d个进程正正在执行!#n,maax+1); priintf(n第%dd次调度结束束，运行结果果为:nn,f); priintf(ID 优先先级 需要总时时间 执行时间n); forr(int k=0; knummber; k+) printtf(%dd %d %d %d n,k+1, pcbk.Prrioritty, pccbk.Alltiime,pccbk.CPUtiime); forr(int l=0;llnumbber;l+) i

17、f(pccbl.Alltiime=00) counnt+; if(countt=nummber) breakk; tiime1=ttime/nnumberr; pprintff(n*用户户进程全部执执行完毕!*); prrintf(nnn平均等待时时间是: ); prrintf(%dnnn,ttime1); if(m=4) prrintf(ID 运行总总时间 进进程状态nn); for(iint k=0; knumbeer; k+)priintf(%d %d 就绪nn,k+11, pccbk.Alltiime); printtf(nn*程序序调度演示开开始*n); for(iint f=1;f

18、11000;ff+)intt couunt=0; for(ii=0;i0)ppcbi.Allttime-=4; pcbii.CPUUtime+=4; if(pccbi.Alltiime0)ppcbi.Allttime=00; / printtf(nn#第%d个进进程正在执行行!#n,i+1); printtf(nn第%d次调调度结束，运运行结果为:nn,f); pprintff(ID 需要时时间 执行行时间n); for(iint k=0; knumbeer; k+) pprintff(%d %dd %d n,k+1, pccbk.Alltiime,pccbk.CPUtiime);/forr(

19、int l=0;llnumbber;l+)iff(pcbl.Allltimee=0)ccount+; if(ccount=numbber)brreak;prinntf(n*用户进程全全部执行完毕毕!*); 4. 实验结果果及分析4.1 实验结结果 先到先服务算法法的实验结果果如下：最短作业优先调调度的实验结结果如下：优先权调度算法法的实验结果果如下：轮转法调度的实实验结果如下下：4.2 结果分分析 本次试验基本本实现了进程程调度的四种种算法，每一一种算法都能能模拟出算法法的具体过程程。相应的结结果也完全符符合预想的结结果。同时，对对于算法的实实践编写进一一步增加了编编程的技巧，以以及编程的熟熟

20、练程度。银行家算法1设计目的 银行家算法法是避免死锁锁的一种十分分重要的方法法，通过编写写一个模拟的的动态的银行行家算法的程程序，能够进进一步加深对对死锁的理解解，以及产生生死锁的必要要条件。并掌掌握通过银行行家算法来避避免死锁。2. 任务及要要求2.1 设计任任务 根据据银行家算法法的基本思想想来设计程序序，模拟银行行家算法的过过程。用程序序来实现银行行家算法的具具体动态过程程。2.2 设计要要求 根据据银行家算法法的基本思想想，编写和调调试一个能实实现动态的分分配资源的模模拟程序。并并能够有效的的防止死锁的的发生。3. 算法及数数据结构3.1算法的总总体思想（流流程） 银行行家算法的基基本

21、思想是，系系统中的所有有进程放入进进程集合，在在安全状态下下系统受到进进程的请求后后会试探性的的把资源分配配给他，现在在系统将剩下下的资源和进进程集合中其其他进程还需需要的资源作作对比，找出出剩余资源能能满足的进程程，从而保证证进程运行完完并释放资源源继续满足剩剩下进程对资资源的需要。最最后检查集合合为空集时表表明本次申请请可行，系统统继续处于安安全状态，可可以实施本次次分配。否则则不能实施本本次分配。3.2 显示资资源矩阵 sshowdaata() 模块3.2.1 功功能 主主要是显示资资源的矩阵，包包括输入的已已分配的的资资源矩阵，以以及输出的资资源矩阵。3.2.2 数数据结构 最最大需求

22、矩阵阵max以及及已分配矩阵阵alloccationn，分别定义义为m*n阶阶的矩阵，利利用二维数组组来存储。3.2.3 算算法void shhowdatta() /显示资源矩矩阵 int i,j; coutt系统统目前可用的的资源Avvaliabble:enddl; for(i=0;iiN;i+) couutnaamei ; couttenddl; for (j=0;jN;jj+) ccoutAvaliiablej ; /输出分分配资源 couttenddl; coutt Max Alloccationn Needenddl; couttenddl; coutt进程程名 ; for(j=0;

23、jj3;j+) ffor(i=0;iNN;i+) ccoutnamei ; ccout ; couttenddl; for(i=0;iiM;i+) ccout i ; ffor(j=0;jNN;j+) couutMaaxij ; ccout ; ffor(j=0;jNN;j+) couutAlllocattioniij ; ccout ; ffor(j=0;jNN;j+) couutNeeedij ; ccoutendl; 3.3 申请资资源判定模块块3.3.1功能能 利用用银行家实现现对申请的资资源进行判定定。3.3.2 数数据结构 对已已经存储的矩矩阵进行比较较。3.3.3算法法void

24、shhare() /利用银行行家算法对申申请资源对进进行判定 chaar ch; intt i=0,j=0; ch=y; couut请请输入要求分分配的资源进进程号(0-M-1i; /输入须申申请的资源号号 couut请请输入进程 i 申请请的资源:enddl; forr(j=0;jN;jj+) couttnammejRequuestjj; /输入需需要申请的资资源 foor (j=0;jNeeddijj) /判断申请是是否大于需求求，若大于则则出错 couut进进程 i申申请的资源大大于它需要的的资源; couut 分配不合理理，不予分配配！Avaliiablej) /判断申请请是否大于当当

25、前资源，若若大于则 couut进进程ii申请请的资源大于于系统现在可可利用的资源源; couut 分配出错，不不予分配!enddl; ch=n; breeak; if(ch=y) changgdata(i); /根据进程程需求量变换换资源 showddata(); /根据进程程需求量显示示变换后的资资源 safe(); /根据进程程需求量进行行银行家算法法判断 3.4 主函数数模块3.4.1功能能 实现现银行家算法法对资源的增增加、删除、修修改。3.4.2 数数据结构 对已已经完成的模模块进行功能能集成。3.4.3算法法int maiin() intt i,j,numbeer,chooice,

26、mm,n,fllag; chaar minng; coutendll; cout* 银*行*家家*算*法 *enndl;coutendl; couutn;coutendl; N=nn; forr(i=0;in;ii+) couut资资源ii+1mingg; nameei=mming; couttnumbber; Avalliableei=nnumberr; couutenndl; couutm; M=mm; couut请请输入各进程程的最大需求求量(m*n矩阵):eendl; forr(i=0;im;ii+) forr(j=0;jMaxij; doflag=0; coutt请输输入各进程已已经

27、申请的资资源量(m*nn矩阵阵):endl; for(i=0;iim;i+) for(j=0;jjAlloccationnijj; if(AlllocattioniijMaxiij) flag=1; Needdijj=Maxxijj-Alllocatiionij; if(fflag) cout申请的的资源大于最最大需求量，请请重新输入!nendl;whilee(flagg); shoowdataa(); /显示各各种资源 saffe(); /用银行行家算法判定定系统是否安安全 whiile(chhoice)cout*银行行家算法演示示*enddl; coutt 1:增加资源 ; coutt 2

28、:删除资源 endl; coutt 3:修改资源 ; coutt 4:分配资源 endl; coutt 5:增加进程 ; coutt 0:离开 enddl; coutt*endl; couttchoiice; swittch(chhoice) casee 1: aaddressourcees();bbreak; case 2: deelresoourcess();brreak; case 3: chhangerresourrces();breaak; case 4: shhare();breaak; case 5: adddproccess();breaak; case 0: chhoice=

29、0;breeak; defauult: ccout请正确选选择功能号(0-5)!next; forr(int i=0;iidatta-f); f=l-dataa; l=l-nextt; numm=num/c; couut先先来先服务的的寻道顺序是是:eendl; priint(heead); couut平平均寻道长度度:nnumnext=NULL; m=ll; q=hhead; p=hhead-next; s=hhead; r=hhead-next; flooat nuum=0; forr(int i=0;iidatta); for(int jj=0;jnextt; q=q-next; if(

30、abbs(f-pp-datta)data); rr=p; ss=q; num+=abs(f-r-data); f=r-dataa; s-nnext=rr-nexxt; r-nnext=NNULL; m-nnext=rr; m=r; q=heead; p=heead-nnext; s=heead; r=heead-nnext; numm=num/c; couut最最短寻道时间间优先顺序是是:eendl; priint(l); couut平平均寻道长度度:nnumnext=NULL; s=rr; m=(Node *)mallloc(ssizeoff(Nodee); /存放放比开始磁道道大的磁道 m-next=NULL; n=mm; x=(Node *)mallloc(ssizeoff(Nodee); x-next=NULL; y=xx; q=hhead; p=hhead-next; whiile(p-nextt!=NULLL)if(p-dataa-f0)q-nnext=pp-nexxt; p-neext=NUULL; n-neext=p; n=p; p=q-next; i+; elseeq-nnext=pp-nexxt; p-n