操作系统置换试验报告

1、实验四页置换实验目的:通过请求页式存储管理中页面置换算法模拟程序，了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。二、实验环境说明：此实验在MacOS10.9的Xcode软件下编译运行。三、实验内容：写一个程序来实现本章中介绍的FIFO和LRU页置换算法。首先，产生一个随机的页面引用序列，页面数从09。将这个序列应用到每个算法并记录发生的页错误的次数。实现这个算法时，要将贡帧的数量设置为可变(从17)假设使用请求调页。四、程序设计说明：1. 全局变量：定义bsize为页帧的数量，可以手动修改，初始值为4。定义psize为进程请求次数，可以手动修改，初始值为16。定义Page结构体，

2、内含页面编号和调入时间。i*t#defineb&ije&/*pagetablesize*/#tlefinepsize16/*physicalmemorysize+/IS1, typedefstructpagelotnum：pagenumber*/inttime;/*swdpintimePage;22Pafleframebsize/+francnumber+/intbutbizefp&ize;/*buffer*/intqueue:/*processesinmeniory*/intK;/*number0+processesirrfiemory+/intphbbsize=-4

3、);/*physicalmemarynunber*/intprotpsi2e)=0-；/*processesnumber*/intflagbs=0；/*processestildes*/inti-j=0；31irtri-1(n*-1;"if“me*/intmax3-1.maxflaq=0；，*victimframenumberintcount=电；/*numberofpaqefault*/2. 初始化缓冲区和物理内存：/水initalizethebufferandmemoryspace*/，口一dInitJage(intbufferbsizesize(1or(i=0;i<psi

4、ze；i+i9fli.nun-1；f(1).time-psize-i-1;收)lor(i=0；1<bsize;i+for(r=ft;j<psize;j+)buffer'llj=1;.7.获得随机序列(09),共psize个数：3/*random(h9)*/int+generateC)printf("Therandompage-referencestringis:n(l);52sr«nd(tinie(NLlLL);for(int曰=;a<psize;a+)5protai=rand)%10;printf('%d|b,pra);)p

5、rintf("n"returnpro);如搜索空内存，便于页的调入：/*searchemptyphysicalmennry*/intsearchPtiMt)1or(=0;.mbslze;.+)if(phb电)Im-j；701returnm；711br6ak;return-1;75)搜索是否有相同的进程已在内存中，有则不缺页，不需要置换:/*searchsaneprocess*/intsearchProf)(tor(=0;<bsize;:+)(if(phbfj1=pro：iI)S3(n=j；returnj;|B?ffireturn-1;|每次应用完一个算法后清空内存和缓

6、冲区,便于其他算法的页置换:PBbl/tclearthememoryaftereachalgorithm*/voidclear的<孰let1；forti=;i<bsize;1+)phbj*%count=e；9aFIFO算法：FIFO页置换算法为每个页记录着该页调入内存的时间。当必须置换一页时，将选择最旧的页。FIFO算法性能并不总是很好，可能会有Belady异常的出现。-o-4a_2iTF*|o-10-HAMdl-4aIXi*!*Bla-*IXIX/*FIFOAlgorithm*/voidFIFOtlprintf("Currentstateis:;printt("

7、;|n');for(i=0;i<psize；1+)<m=searchPhMf);n=searchProij;(j-9;j<Mi阳j+)(if(fTig(j>maxfIsg)maxflag=flag(imax=j;if(n=-1)/*nosameprocessm/<if(m!=-1/*existemptymemory*/<phbn=prolij;count+;flagImI=e；for(j=6；j=m;j+)<flaotj+：)m=-1;else/率noemptyneniory,needvlctin*/phbLnax)=proli;flagIni

8、axJ=g;fortj=肌jmb3ize;j+)(lagj)+;)=-1；Taxflag=0;count+;?else/*existsameprocess*/phb(n).pro.J;tor(j=fl;j«bsize;j+<fiBgtj+:c=-1;卜prdntf("|W2d|'proi);for(j=0;j<bsize；j*+)(printf("*s2d",phbj);printf("n|+n+1.n")Pri.ntf("Thereare如pagefaults.nRcount);orxntft'

9、Tagefaultratis4f.n'(floaticountipiize);8.获得置入时间最早的页面，用于FIFO算法:XW-T/*usedinFlrQjswapinearliest*/intGetMaxtPgqe*f)inti;intmax-1;inttag=%for(i=0;i<bsize;1+)4if(fltlie>max)max=f(iltag=i;)returntag;9.判断页面是否相同:Ms;髓不就同MnwgM的黑磬初啊10111213*151617":幻.，*itexist*/intEquatlon(intprOjPage*f)卬.<in

10、t1；for(1=6;1<bslze;i+)IB?if(pro*f1,nym)iwreturni;IK二父return-1；192卜1310.LRU#法：LRU页置换算法为每个页关联该页上次使用的时间。当必须置换一页时,LRU4择最长时间没有使用的页。这种策略为向后看最优页置换算法。7*LRUAlgonthfii*/voidLruu(intpro,Page*f)inti;intval;vat=EquatioMpr%f)；if(val>=0)<fvaltime*0;for(i=0;ivbsi2eji+)if(X!=val)fi»time+;else<queue(

11、+K1=pro;vatGetHaxlf);fval.nun=pro；fval.time-B;for(i=劭i<b$izeji+)if(i|=val)fi/time+;)11.12.210221223*及5226217229HO23123323323413s2M23713fi之葬12412M2<t3M5W242M1雪0isi152痴现voidLRU()(iniid；K父-1;Init(framefbuf);for(ik0;i<psl»1+*)(Lruu(pra11frame)1;buf01pnIiifor(J=0；J<ble;J*)ibufji=fran>

12、ej+num;prlntf("Currentstateis:n");printf(w|+<-rT):for(1=0;i<psize;1+-*)(printf('M*2dproil);forj=0j；j<bsiEE；j*)(if(buf(J|i)=-1)printf(!l%2c"，'x);eUe口rintf2dbMIjlhlhyprintf(l,!in|+卡-|Xn11);priMf(B,riiPagewaporderis：J;for(1.-a；1<K+ij1+<)printf(AJd1queueij);prtMf&qu

13、ot;n”hprintf("ThereareNdpagefaultsAntfK+lhprintf("PagefaultrateisW.lfAn",(float)(K+l)/psizeH主目录：voidmenu。25fi4£jtfPrxni>1*率率*本本净净室军军军率净KEtrafifC率率率不军军用木格军军年率寄*Gt?率星率率率率室率/律11Jprintf('"*WelcometothePage-ReplacementProj!printf("卡否水k*4*jMi社*林*4*水"")printf(

14、',*1,Generaterandompage-referencestring*rr的printft"*3FIFOAlgorithm*rT)printf("*3,LRUAlgorithm*n"2C5printfC1"*41Quit*+n'')printf(1t1MH1k*51dt：iM(1tt1tt1aMe)一.主函数：2tfi2TO27137?273an275276279279湖2B1施233孙205通287168iotmain(intargc,constchar*argv)<intchoi"=0;while(c

15、hoice!4)(me-nut);printf("Pleaseselectthefunction:H);scanf("'WS'choice);switch(choice)case 1 :geriperatei);break;case 2 :printf("FIFOAlgorithm:n,flhFIFOOjclearO;prlntf(,Bnw);break;case 3 :printf(SlLRU1AlgorithmLRU();cleart);printfbreak;case 4 ；printf(11End»W)；break；default

16、:printf("Wrongnurniber!Pleasein-putag3in!"p);printfCAn"hbreak;return0;五、运行结果:1. 运行程序显示主目录界面：* 9目印*»1£率*¥*9#军*|£*呼*总坤*：*坤中¥»归科£*半* *WelcometothePage-ReplacementProj!*3fCJC331C«C5e3|C3|C5(|C3C3|C3C3jC5|SS|t3|C5E5CJCSCC3fC3C3O|S|C3C31C* *1Generater

17、andompage-referencestring* *2.FIFOAlgorithm* *3.LRUAlgorithm* *4.Quit* *和£*t*中*种*Pleaseselectthefunction:2. 选择操作1,生成psize（此处为16）个随机数（09）序列:1rHe3M1nlit11r1n1n* *WelcometothePage-ReplacementProj!* *1.Generaterandonpage-referencestring* *2.FIFOAlgorithm* *3.LRUAlgorithm* *4.Quit*31第*iQ|t*m中坤*宰牛*j注

18、*/1松c*和*|e*1附"*3(蟀*率率*净平率率Pleaseselectthefunction:1Therandlompage-referencestringis:15336320820195913.选择操作2,执行FIFO算法，并输出运行结果:4ufuft3fc4ut31u(s|c31t4o|c*31o*3K>c34c|ejfufu|D|ca|u|u|u|e4u* *WelcometothePage-ReplacementProj1* 3和K* *1.Generaterandompage-referencestring* *2,FIFOAlgorithm* *3.LRUA

19、lgorithm* *4.Quit*Pleaseselectthefunction:2FIFOAlgorithm:Currentstateis：Thereare12pagefaults.Pagefaultrateis0.7500.4. 选择操作3,执行LRUB法，并输出运行结果:*1,*2.3.它4.2K率霹隼率半率宰*率率*宰军军军军*年率率率率率*隼帘K率率率*率率率本率率年率本年率率*WelcometothePage-ReplacementProj!-I.Li-|Uj_I35=K；35Generaterandompage-referencestring*FIFOAlgorithm*LRU

20、Algorithm*Quit*Thereare10pagefaults.PagefaultrateisEL6250.Pleaseselectthefunction:3LRUAlgorithm 选择操作4,输出end,结束程序:* *WelcometothePage-ReplacementProj!*#*44*110利*|£*3|坤*4£*3日1*3粒件*34*!*£*5"*利£料件*相4坤* *1.Generaterandompage-referencestring* *2.FIFOAlgorithm* *3.LRUAlgorithm* *4,Quit*Pleaseselectthefunction:4End.Programendedwithexitcode：0六、不同页帧数比较:1.3frames:Currentstateis:一?山.+一7|7ae1171g,ta1!