頁(yè)面置換算法模擬設(shè)計(jì)

1、頁(yè)面置換算法模擬設(shè)計(jì)課程設(shè)計(jì)報(bào)告課程名稱操作系統(tǒng)課題名稱專(zhuān)業(yè)通信工程班級(jí)學(xué)號(hào)姓名指導(dǎo)教師2019年6月29日湖南工程學(xué)院課程設(shè)計(jì)任務(wù)書(shū)課程名稱課題專(zhuān)業(yè)班級(jí)學(xué)生姓名學(xué)號(hào)指導(dǎo)老師審批任務(wù)書(shū)下達(dá)日期2019年6月23日任務(wù)完成日期2019年6月29日目錄1 課題概述41.1 設(shè)計(jì)要求41.2理論分析42系統(tǒng)分析63程序?qū)崿F(xiàn)84程序測(cè)試135心得體會(huì)156附錄167評(píng)分表30課題：頁(yè)面置換算法模擬設(shè)計(jì)1 課題概述1.1 設(shè)計(jì)要求計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。A.FIFO先進(jìn)先出的算法B.LRR最近最少使用算法D. LFR 最少訪問(wèn)頁(yè)面算法C.OPT最佳淘汰算法（先淘汰最不常用的頁(yè)地址

2、）E.NUR最近最不經(jīng)常使用算法設(shè)計(jì)技術(shù)參數(shù)：（1）命中率=1-頁(yè)面失效次數(shù)/頁(yè)地址流長(zhǎng)度（2）本實(shí)驗(yàn)中，頁(yè)地址流長(zhǎng)度為320，頁(yè)面失效次數(shù)為每次訪問(wèn)相應(yīng)指令時(shí)，該指令所對(duì)應(yīng)的頁(yè)不在內(nèi)存的次數(shù)。（3）隨機(jī)數(shù)產(chǎn)生方法，采用系統(tǒng)提供函數(shù)SRAND（和RAND（）來(lái)產(chǎn)生1.2理論分析在進(jìn)程運(yùn)行過(guò)程中，若其所要訪問(wèn)的頁(yè)面不在內(nèi)存所需把他們調(diào)入內(nèi)存，但內(nèi)存已無(wú)空閑時(shí)，為了保證進(jìn)程能夠正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)入一頁(yè)程序或數(shù)據(jù)送磁盤(pán)的對(duì)換區(qū)中。但應(yīng)將那個(gè)頁(yè)面調(diào)出，須根據(jù)一定的算法來(lái)確定。通常，把選擇換出頁(yè)面的算法稱為頁(yè)面置換算法。置換算法的好壞，將直接影響到系統(tǒng)的性能。一個(gè)好的頁(yè)面置換算法，應(yīng)具有較低的

3、頁(yè)面更換頻率。從理論上將講，應(yīng)將那些以后不再訪問(wèn)的頁(yè)面換出，或把那些較長(zhǎng)時(shí)間內(nèi)不再訪問(wèn)的頁(yè)面調(diào)出。目前存在著不同的算法，他們都試圖更接近與理論上的目標(biāo)。擁有頁(yè)面交換機(jī)制的操作系統(tǒng)總是把當(dāng)前進(jìn)程中急需處理的部分頁(yè)面換入到內(nèi)存當(dāng)中，而把更多暫時(shí)不需要處理的頁(yè)面放置在外存當(dāng)中。由于進(jìn)程需要處理的頁(yè)面順序不同，因此必須要在內(nèi)存與外存之間進(jìn)行頁(yè)面交換，頁(yè)面置換算法也就應(yīng)運(yùn)而生。1.先進(jìn)先出（FIFO）算法這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存停留時(shí)間最久的給予淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替代指針，使它

4、總是指向最老的頁(yè)面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵趇ncheng中，有些頁(yè)面經(jīng)常被訪問(wèn)，比如，含有全局變量，常用函數(shù)，例程等方面，F(xiàn)IFO算法并不能保證這些頁(yè)面不被淘汰。當(dāng)需要選擇一個(gè)頁(yè)面淘汰時(shí)，總是選擇最先進(jìn)入內(nèi)存空間的那一個(gè)頁(yè)面。只要在系統(tǒng)中建立一個(gè)FIFO隊(duì)列，以反映頁(yè)面的活動(dòng)情況。被選擇的頁(yè)面總是處于隊(duì)首的頁(yè)面，而最近調(diào)入的頁(yè)面永遠(yuǎn)存放在隊(duì)列的尾部。2.最近最少使用（LRR算法FIFO置換算法的性能之所以較差，是因?yàn)樗罁?jù)的條件是各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間，而頁(yè)面調(diào)入的先后不能反映頁(yè)面的使用情況。最近最少使用（LRR）的頁(yè)面置換算法，是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的

5、。由于無(wú)法預(yù)測(cè)各個(gè)頁(yè)面將來(lái)的使用情況，只能利用“最近的過(guò)去”，作為“最近的將來(lái)”的近似。該算法的基本思想是用最近的過(guò)去估計(jì)最近的將來(lái)。假定在內(nèi)存中的某個(gè)頁(yè)面，在最近一段時(shí)間內(nèi)未被使用的時(shí)間最長(zhǎng)，那么在最近的將來(lái)也可能不再被使用。3.理想頁(yè)面置換（OPT算法（本次程序中作兩個(gè)置換算法對(duì)比作用）最佳置換算法由Belady于1966年提出，這是一種理想情況下的頁(yè)面置換算法，但實(shí)際上不可能實(shí)現(xiàn)。但人們目前把還無(wú)法預(yù)知一個(gè)進(jìn)程在內(nèi)的若干頁(yè)面中，哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)，因而該算法無(wú)法實(shí)現(xiàn)?；舅枷胧莾?nèi)存中每個(gè)頁(yè)都用該頁(yè)面首次被訪問(wèn)前所要執(zhí)行的指令數(shù)進(jìn)行標(biāo)記，標(biāo)記最大的頁(yè)應(yīng)該被置換4.OPT最

6、佳淘汰算法（先淘汰最不常用的頁(yè)地址）OPTimalreplacement（OPT）它是一種理想化的算法，性能最好，但在實(shí)際上難于實(shí)現(xiàn)。即選擇那些永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面置換出去。但是要確定哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，目前來(lái)說(shuō)是很難估計(jì)的，所以該算法通常用來(lái)評(píng)價(jià)其它算法5.NUR最近最不經(jīng)常使用算法為每頁(yè)設(shè)置一位訪問(wèn)位，當(dāng)每頁(yè)被訪問(wèn)時(shí)，其訪問(wèn)位置1.置換算法在替換頁(yè)面時(shí)，只需要檢查它的訪問(wèn)位，如果是0，就將該頁(yè)換出，如果是1，則重新將它置為0，從而給該頁(yè)第二次駐留內(nèi)存的機(jī)會(huì)，再依次檢查下一個(gè)頁(yè)面。如果最后一個(gè)頁(yè)面依然沒(méi)有被換出，則到第一個(gè)頁(yè)面去重新檢查。2系統(tǒng)分

7、析1進(jìn)入系統(tǒng)模塊。進(jìn)入登陸界面，輸入內(nèi)存頁(yè)面數(shù)和實(shí)際頁(yè)數(shù)2頁(yè)面號(hào)打印模塊。打印輸入的頁(yè)面號(hào)。3 菜單選擇模塊。選擇相應(yīng)的頁(yè)面的置換方式，選擇相應(yīng)的字母，進(jìn)入相應(yīng)的功能。4 算法模塊。選擇相應(yīng)的頁(yè)面置換算法。5顯現(xiàn)輸出模塊。顯示頁(yè)面被置換的情況。5 .缺頁(yè)次數(shù)和缺頁(yè)率模塊。計(jì)算頁(yè)面號(hào)輸入的計(jì)算結(jié)果。6.退出系統(tǒng)模塊。退出置換頁(yè)面。如圖2.1模塊劃分:圖2.1模塊劃分之后進(jìn)入系統(tǒng)模塊如圖2.2:圖2.2系統(tǒng)流程圖3 程序?qū)崿F(xiàn)1. 首先貫穿全局的全局需要一系列的函數(shù)來(lái)實(shí)現(xiàn)本操作系統(tǒng)的各種功能。需要函數(shù)自帶的文件stdio.h和stdlib.h.2.以下通過(guò)FIFO、OPTLRR三個(gè)進(jìn)行舉例：FIFO

8、頁(yè)面置換和缺頁(yè)次數(shù)及缺頁(yè)率模塊實(shí)現(xiàn)如下：voidFIFO()intmemery10=0;inttime10=0;inti,j,k,m;intmax=0;intcount=0;for(i=0;imemeryi=pagei;timei=i;for(j=0;jtempij=memeryj;for(i=mSIZE;ifor(j=0,k=0;jif(memeryj!=pagei)k+;if(k=mSIZE)count+;max=time0for(m=2;mif(timemmax=m;memerymax=pagei;timemax=i;for(j=0;jtempij=memeryj;elsefor(j=0

9、;jtempij=memeryj;LRR 頁(yè)面置換和缺頁(yè)次數(shù)及缺頁(yè)率模塊實(shí)現(xiàn)如下：voidLRR()intmemery10=0;intflag10=0;inti,j,k,m;intmax=0;intcount=0;for(i=0;imemeryi=pagei;flagi=i;for(j=0;jtempij=memeryj;compute();print(count);for(i=mSIZE;ifor(j=0,k=0;jif(memeryj!=pagei)k+;elseflagj=i;if(k=mSIZE)count+;max=flag0for(m=2;mif(flagmmax=m;memery

10、max=pagei;flagmax=i;for(j=0;jtempij=memeryj;elsefor(j=0;jtempij=memeryj;OPT 頁(yè)面置換和缺頁(yè)次數(shù)及缺頁(yè)率模塊實(shí)現(xiàn)如下（本代碼在頁(yè)面置換中：void OPT()compute();print(count);intmemery10=0;intnext10=0;inti,j,k,l,m;intmax;intcount=0;for(i=0;imemeryi=pagei;for(j=0;jtempij=memeryj;for(i=mSIZE;ifor(j=0,k=0;jif(memeryj!=pagei)k+;if(k=mSIZE

11、)count+;for(m=0;mmax=next0>=next1?0:1;for(l=i+1;lif(memerym=pagel)break;nextm=l;for(m=2;mif(nextm>nextmax)max=m;memerymax=pagei;for(j=0;jtempij=memeryj;elsefor(j=0;jtempij=memeryj;compute();print(count);4程序測(cè)試系統(tǒng)剛剛進(jìn)入時(shí)，有一個(gè)自己手動(dòng)輸入的物理塊，輸入要置換的頁(yè)面號(hào)等，如圖：圖4.1物理塊如圖可知：產(chǎn)生一組隨機(jī)序列號(hào)，只要在主界面中選擇我們需要的算法便可以算出我們需要的數(shù)據(jù)

12、。圖4.2主界面當(dāng)我們選擇OPT算法時(shí)，等待幾秒鐘，便會(huì)出現(xiàn)各種數(shù)據(jù)信息，如圖：圖4.3OPT算法比較上述三種算法,以O(shè)PT算法的命中率最高，LRU算法次之,其次是FIFO算法5心得體會(huì)在這次課程設(shè)計(jì)的過(guò)程中，我了解到實(shí)踐大于理論的意義，我們平時(shí)不僅要加強(qiáng)理論知識(shí)的積累，更要強(qiáng)化實(shí)踐能力。對(duì)于操作系統(tǒng)，實(shí)踐能力更是考驗(yàn)一個(gè)人的能力所在。其中也有不少汗水，但是收獲大于付出。然其中也有不少幸酸，比如，看到別的學(xué)習(xí)能力強(qiáng)的同學(xué)一個(gè)個(gè)都完成了老師指定的任務(wù)，自己卻什么都沒(méi)完成的時(shí)候，心里無(wú)比的焦急，不知該如何是好。再比如，自己還是云里霧里的時(shí)候，內(nèi)心在無(wú)數(shù)次的自責(zé)為什么自己沒(méi)有別人一樣好用的腦子，為什

13、么別人經(jīng)過(guò)了老師的點(diǎn)撥之后就一點(diǎn)就通，而自己對(duì)于現(xiàn)學(xué)的知識(shí)卻什么都還是稚嫩的孩童的時(shí)候。雖然這一切給了我打擊，但是我想這不僅僅是給我在學(xué)習(xí)這條道路上給予動(dòng)力，更是讓我有求知欲的時(shí)候，這個(gè)時(shí)候我不會(huì)驕傲自大，我會(huì)虛心求學(xué)，我會(huì)不懂就問(wèn)，我會(huì)知道自己的弱點(diǎn)所在。人無(wú)完人，世界之大，青出于藍(lán)而勝于藍(lán)的大有人在。所以，我遇到的困難并沒(méi)有什么，關(guān)鍵在于我自己的心態(tài)，以及找到合適的方法去解決困難才是最重要的。總而言之，這次課程設(shè)計(jì)讓我收獲頗多。6 附錄#include#includeintmSIZE;intpSIZE;staticintmemery10=0;staticintpage100=0;stati

14、cinttemp10010=0;voidFIFO();voidLRR();voidOPT();voidLFR();voidNUR();voidprint(unsignedintt);voiddownload();voidmDelay(unsignedintDelay);voidmain()inti,k,code;/designBy();printf("請(qǐng)按任意鍵進(jìn)行初始化操作.printf("請(qǐng)輸入");getchar();system("cls");printf("請(qǐng)輸入物理塊的個(gè)數(shù)(Mn");scanf("%d

15、",&mSIZE);printf("請(qǐng)輸入頁(yè)面號(hào)引用串的個(gè)數(shù)(Pputs("請(qǐng)依次輸入頁(yè)面號(hào)引用串(連續(xù)輸入，無(wú)需隔開(kāi))：");for(i=0;iscanf("%1d",&pagei);download();system("cls");system("color0E");doputs("輸入的頁(yè)面號(hào)引用串為：");for(k=0;kprintf("%dn",pagei);elseprintf("%d",pagei);pr

16、intf(''* *n");最近printf("*請(qǐng)選擇頁(yè)面置換算法：printf("*1.先進(jìn)先出(FIFO)printf("*2.最少使用(LRR)printf("*3.最佳淘汰(OPT)printf("*4.最少訪問(wèn)頁(yè)面(LFR)printf("*5.最近最不經(jīng)常使用(NUR)printf("*6.退出printf(* *n");printf("請(qǐng)選擇操作：bb");*n");*n");*n");*n");*n")

17、;*n");*n");scanf("%d",&code);switch(code)case1:FIFO();getchar();break;case2:LRR();getchar();break;case3:OPT();getchar();break;case 4:LFR();getchar();break;case 5:NUR();getchar();break;case6:system("cls");system("color0A");printf("感謝您使用頁(yè)面置換算法軟件(庹雷制作)n&

18、quot;);exit(0);default:for(j=0;jprintf("輸入錯(cuò)誤，請(qǐng)重新輸入：");printf("按任意鍵重新選擇：>");getchar();system("cls");while(code!=4);getchar();voiddownload()inti;system("color0D");printf("請(qǐng)等待.n");printf("正在下載中.n");printf("for(i=0;iprintf("b"

19、);for(i=0;i");printf("nFinish.n請(qǐng)按任意鍵進(jìn)入置換算法選擇界面：>");getchar();voidmDelay(unsignedintDelay)unsignedinti;for(;Delay>0;Delay-)完成");for(i=0;iprintf("b");voidprint(unsignedintt)inti,j,k,l;intflag;for(k=0;kfor(i=20*k;(ifor(i=mSIZE+20*k;(iif(i+1)%20=0)|(i+1)%20)&&

20、(i=pSIZE-1)printf("%dn",pagei);elseprintf("%d",pagei);if(i>=j)printf("|%d|",tempij);elseprintf("|");for(flag=0,l=0;lvoidcompute()inti;printf("請(qǐng)等待計(jì)算結(jié)果：");for(i=1;ielseprintf(">");for(i=0;i+for(i=0;i+for(i=0;i+voidFIFO()memerymax=pagei;

21、inttime10=0;inti,j,k,m;intmax=0;intcount=0;for(i=0;imemeryi=pagei;timei=i;for(j=0;jtempij=memeryj;for(i=mSIZE;ifor(j=0,k=0;jif(memeryj!=pagei)k+;if(k=mSIZE)count+;max=time0for(m=2;mmax=m;timemax=i;for(j=0;jtempij=memeryj;elsefor(j=0;jtempij=memeryj;compute();print(count);voidLRR()intmemery10=0;intfl

22、ag10=0;inti,j,k,m;intmax=0;intcount=0;for(i=0;imemeryi=pagei;flagi=i;tempij=memeryj;tempij=memeryj;for(i=mSIZE;ifor(j=0,k=0;jif(memeryj!=pagei)k+;elseflagj=i;if(k=mSIZE)count+;max=flag0for(m=2;mmemerymax=pagei;flagmax=i;for(j=0;jtempij=memeryj;elsecompute();voidOPT()intmemery10=0;intnext10=0;inti,j,k,l,m;intmax;intcount=0;for(i=0;imemeryi=pagei;for(j=0;jtempij=memeryj;for(i=mSIZE;ifor(j=0,k=0;jif(memeryj!=pagei)k+;if(k=mSIZE)count+;for(m=0;mbreak;nextm=l;max=next0>=next1?0:1;fo