(完整word版)頁(yè)面置換算法實(shí)驗(yàn)報(bào)告

1、綜合性實(shí)驗(yàn)報(bào)告專(zhuān)業(yè) 年級(jí)班級(jí):課程名稱(chēng)操作系統(tǒng)指導(dǎo)教師學(xué)號(hào)姓名實(shí)驗(yàn)地點(diǎn)實(shí)驗(yàn)時(shí)間項(xiàng)目名稱(chēng)頁(yè)匍置換算法實(shí)驗(yàn)類(lèi)型綜合性一、實(shí)驗(yàn)?zāi)康?.學(xué)習(xí)常見(jiàn)的4種頁(yè)面置換算法：最佳置換算法（OPT ,先進(jìn)先出頁(yè)面置換算 法（FIFO）,最近最久未使用頁(yè)面算法（LRU ,最少使用置換算法（LFU 。 2.編寫(xiě)函數(shù)并計(jì)算輸出上述各種算法的命中率。二、總體設(shè)計(jì)（設(shè)計(jì)原理、設(shè)計(jì)方案及流程等）設(shè)計(jì)原理：OPT頁(yè)面置換算法OPT所選擇被淘汰的頁(yè)面是已調(diào)入內(nèi)存，且在以后永不使用的，或是在最長(zhǎng)時(shí)間內(nèi)不再被訪(fǎng)問(wèn)的頁(yè)面。因此如何找出這樣的頁(yè)面是該算法的關(guān)鍵?？蔀槊總€(gè)頁(yè)面設(shè)置一個(gè)步長(zhǎng)變量，其初值為一足夠大的數(shù)，對(duì)于不在內(nèi)存的頁(yè)面，將其

2、值重置為零，對(duì)于位于內(nèi)存的頁(yè)面，其值重置為當(dāng)前訪(fǎng)問(wèn)頁(yè)面與之后首次出現(xiàn)該頁(yè)面時(shí)兩者之間的距離，因此該值越大表示該頁(yè)是在最長(zhǎng)時(shí)間內(nèi)不再被訪(fǎng)問(wèn)的頁(yè)面，可以選擇其作為換出頁(yè)面。FIFO頁(yè)面置換算法FIFO總是選擇最先進(jìn)入內(nèi)存的頁(yè)面予以淘汰，因此可設(shè)置一個(gè)先進(jìn)先出的忙頁(yè)幀隊(duì)列，新調(diào)入內(nèi)存的頁(yè)面掛在該隊(duì)列的尾部，而當(dāng)無(wú)空閑頁(yè)幀時(shí)，可從該隊(duì)列首部取下一個(gè)頁(yè)幀作為空閑頁(yè)幀，進(jìn)而調(diào)入所需頁(yè)面。LRU頁(yè)面置換算法LRU是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的，它利用“最近的過(guò)去”作為“最近的將來(lái)”的近似，選擇最近最久未使用的頁(yè)面予以淘汰。該算法主要借助于頁(yè)面結(jié)構(gòu)中的訪(fǎng)問(wèn)時(shí)間time來(lái)實(shí)現(xiàn)，time記錄了一個(gè)頁(yè)面上

3、次的訪(fǎng)問(wèn)時(shí)間，因此，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇 處于內(nèi)存的頁(yè)面中其time值最小的頁(yè)面，即最近最久未使用的頁(yè)面予以淘汰。LFU頁(yè)面置換算法LFU要求為每個(gè)頁(yè)面配置一個(gè)計(jì)數(shù)器（即頁(yè)面結(jié)構(gòu)中的counter ）, 一旦某頁(yè)被訪(fǎng)問(wèn)，則將其計(jì)數(shù)器的值加1,在需要選擇一頁(yè)置換時(shí)，則將選擇其計(jì)數(shù)器值最小的頁(yè)面，即內(nèi)存中訪(fǎng) 問(wèn)次數(shù)最少的頁(yè)面進(jìn)行淘汰。設(shè)計(jì)流程:1 .通過(guò)隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令。2 .指令序列變換成頁(yè)地址流3 .計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。4 .在主函數(shù)中生成要求的指令序列，并將其轉(zhuǎn)換成頁(yè)地址流；在不同的內(nèi)存容量下調(diào)用上述函數(shù)使其計(jì)算并輸出相應(yīng)的命中率。三、實(shí)

4、驗(yàn)步驟（包括主要步驟、代碼分析等）主要代碼：1.頁(yè)面結(jié)構(gòu)typedef structint pn, pfn, counter, time; pl_type ;pl_type pltotal_vp;其中pn為頁(yè)面號(hào)（頁(yè)號(hào)），pfn為頁(yè)幀號(hào)（物理塊號(hào)），counter為一個(gè)周期內(nèi)訪(fǎng)問(wèn)該 頁(yè)面的次數(shù)，time為訪(fǎng)問(wèn)時(shí)間；pltotal_vp 為頁(yè)面結(jié)構(gòu)數(shù)組，由于共有 320條指令，每 頁(yè)可裝入10條指令，因此虛頁(yè)長(zhǎng) total_vp 的值為32。將此結(jié)構(gòu)封裝到Pahg.h文件中。2.頁(yè)幀控制結(jié)構(gòu)struct pfc_structint pn, pfn;struct pfc_struct *next;

5、typedef struct pfc_struct pfc_type;pfc_type pfctotal_vp, *freepf_head, *busypf_head, *busypf_tail;其中pfctotal_vp定義用戶(hù)進(jìn)程的頁(yè)幀控制結(jié)構(gòu)數(shù)組，在該實(shí)驗(yàn)中，用戶(hù)內(nèi)存工作區(qū)是動(dòng)態(tài)變化的，最多可達(dá)到用戶(hù)進(jìn)程的虛頁(yè)數(shù)目，即32個(gè)物理塊。*freepf_head為空閑頁(yè)幀頭的指針*busypf_head為忙頁(yè)幀頭的指針*busypf_tail忙頁(yè)幀尾的指針講此結(jié)構(gòu)封裝到PageControl.h 頭文件中。3.主要函數(shù) void initialize（int）:初始化函數(shù)該函數(shù)主要對(duì)頁(yè)面結(jié)構(gòu)數(shù)

6、組pl和頁(yè)幀結(jié)構(gòu)數(shù)組 pfc進(jìn)行初始化，如置頁(yè)面結(jié)構(gòu)中的頁(yè)面號(hào)pn,初始化頁(yè)幀號(hào) pfn為空，訪(fǎng)問(wèn)次數(shù) counter為0,訪(fǎng)問(wèn)時(shí)間time為-1 ;同樣對(duì)頁(yè) 幀數(shù)組進(jìn)行初始化，形成一個(gè)空閑頁(yè)幀隊(duì)列。(2) void OPT(int):(3) void FIFO(int):(4) void LRU(int):(5) void LFU(int):void FIFO(int total_pf)計(jì)算使用最佳頁(yè)面算法時(shí)的命中率計(jì)算使用先進(jìn)先出頁(yè)面置換算法時(shí)的命中率計(jì)算使用最近最久未使用頁(yè)面置換算法時(shí)的命中率計(jì)算使用最少使用置換算法時(shí)的命中率/*先進(jìn)先出頁(yè)面置換算法*/int i,j;pfc_type

7、*p;initialize(total_pf);busypf_head=busypf_tail=NULL;for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID)/*頁(yè)面失效 */diseffect=diseffect+1;if(freepf_head=NULL)/*無(wú)空閑頁(yè)幀 */p=busypf_head->next;plbusypf_head->pn.pfn=INVALID; /將忙頁(yè)幀隊(duì)首頁(yè)面作為換出頁(yè)面freepf_head=busypf_head;freepf_head->next=NULL;busypf_

8、head=p; /忙頁(yè)幀頭指針后移p=freepf_head->next; / 有空閑頁(yè)幀freepf_head->next=NULL;freepf_head->pn=pagei; /*將所需頁(yè)面調(diào)入空閑頁(yè)幀*/plpagei.pfn=freepf_head->pfn;if(busypf_tail=NULL) /*若忙頁(yè)幀隊(duì)列為空，則將其頭尾指針都指向剛調(diào)入頁(yè)面所在的頁(yè)幀*/busypf_head=busypf_tail=freepf_head;else / 否則，將剛調(diào)入頁(yè)面所在的頁(yè)幀掛在忙頁(yè)幀隊(duì)列尾部 busypf_tail->next=freepf_head

9、;busypf_tail=freepf_head; freepf_head=p; / 空閑頁(yè)幀頭指針后移 printf("FIFO:%6.4f ",1-(float)diseffect/320); void LRU(int total_pf)/*最近最久未使用頁(yè)面置換算法*/int i,j；int min,minj,present_time;initialize(total_pf);present_time=0;for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID) /*頁(yè)面失效 */diseffect+;if(f

10、reepf_head=NULL) /*無(wú)空閑頁(yè)幀 */min=32767;for(j=0;j<total_vp;j+) /*if(min>plj.time && plj.pfn!=INVALID)找出位于內(nèi)存且time值最小的頁(yè)面作為置換頁(yè)面*/ min=plj.time; minj=j; freepf_head=&pfcplminj.pfn; plminj.pfn=INVALID;plminj.time=-1;freepf_head->next=NULL;plpagei.pfn=freepf_head->pfn; / plpagei.time=

11、present_time; / freepf_head=freepf_head->next; /騰出一個(gè)單元有空閑頁(yè)面，改為有效修改頁(yè)面的訪(fǎng)問(wèn)時(shí)間減少一個(gè)free 頁(yè)面 elseplpagei.time=present_time; /命中則修改該單元的訪(fǎng)問(wèn)時(shí)間present_time+; printf("LRU:%6.4f ",1-(float)diseffect/320);void OPT(int total_pf) /*最佳頁(yè)面置換算法*/int i,j,max,maxpage,d,disttotal_vp;initialize(total_pf);for(i=0

12、;i<total_instruction;i+) if(plpagei.pfn=INVALID) /*頁(yè)面失效 */ diseffect+;if(freepf_head=NULL) /* 無(wú)空閑頁(yè)面 */ for(j=0;j<total_vp;j+) if(plj.pfn!=INVALID)所有位于內(nèi)存頁(yè)面的距離變量賦一足夠大的數(shù)distj=32767; else /不在內(nèi)存的頁(yè)面變量則置為0distj=0; d=1; /*對(duì)于位于內(nèi)存且在當(dāng)前訪(fǎng)問(wèn)頁(yè)面之后將再次被訪(fǎng)問(wèn)的頁(yè)面，dist重置為當(dāng)前頁(yè)面與之后首次出現(xiàn)該頁(yè)面時(shí)兩者之間的距離*/for(j=i+1;j<total_in

13、struction;j+) if(plpage皿pfn!=INVALID && distpagej=32767) distpagej=d;d+; max=-1; /查找dist變量值最大的頁(yè)面作為換出頁(yè)面 for(j=0;j<total_vp;j+)if(max<dist)max=distj; maxpage=j; freepf_head=&pfcplmaxpage.pfn; /騰出一個(gè)單元freepf_head->next=NULL; plmaxpage.pfn=INVALID; plpagei.pfn=freepf_head->pfn; /有

14、空閑頁(yè)面，改為有效freepf_head=freepf_head->next; /減少一個(gè) free 頁(yè)面 printf("OPT:%6.4f ",1-(float)diseffect/320); void LFU(int total_pf)/*最少使用頁(yè)面置換算法*/ int i,j,min,minpage;initialize(total_pf);for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID) /頁(yè)面失效diseffect+;if(freepf_head=NULL) / 無(wú)空閑頁(yè)幀min=3276

15、7;for(j=0;j<total_vp;j+) /查找位于內(nèi)存且訪(fǎng)問(wèn)次數(shù)最少的頁(yè)面作為換出頁(yè)面if(min>plj.counter&&plj.pfn!=INVALID)min=plj.counter;minpage=j;plj.counter=0;freepf_head=&pfcplminpage.pfn; /騰出一個(gè)單元plminpage.pfn=INVALID; freepf_head->next=NULL; plpagei.pfn=freepf_head->pfn; /有空閑頁(yè)面,改為有效plpagei.counter+; /增加頁(yè)面訪(fǎng)問(wèn)

16、次數(shù)freepf_head=freepf_head->next; /減少一個(gè) free 頁(yè)else plpagei.counter+; / 命中增加頁(yè)面訪(fǎng)問(wèn)次數(shù) printf("LFU:%6.4f ",1-(float)diseffect/320);將上述函數(shù)寫(xiě)成頭文件的格式封裝在Memory.h頭文件中，由主函數(shù) main調(diào)用使用。運(yùn)行結(jié)果打開(kāi)linux虛擬機(jī)，用vim編輯器打開(kāi)代碼進(jìn)行修改和調(diào)整。用g+編譯器進(jìn)行編譯運(yùn),如圖所示：rootlo c日I h st: r探作系統(tǒng)/叁合牲塞若文件編耨查看第終端標(biāo)簽幫助時(shí)rootwlocalhcsl 窈合性實(shí)驗(yàn)# g q

17、inain niain.cp口Memory.h： In 此欣心,h：33： Me儂. h ； 41 ； 肥gn . h ； 44 ：constructor： ：CMemary,：)'：警告：當(dāng)轉(zhuǎn)換到51(從警告；當(dāng)轉(zhuǎn)換到inf 警告：當(dāng)箱換到inffloat JBt門(mén)。自L(fǎng) )時(shí)門(mén)ci日I .)時(shí)rootftlocalhost 棠合性實(shí)臆作./matnFIFO : - I -'(J: FIFO： FIR： FIFO： FIFO, FIFO: FtFO： - I 70： Fl陽(yáng) FIFO： FI FC : FIFO： - I -(J i FIFO： FIFO： 7I -0： FI

18、FO： FIFO： FIFO： FIFO： FIFO： FIFO: FIR：； |;0J FIFO： FIFO： FIFO： 門(mén)【S.O.54375LRL： ,0,553125LRU： ,0.57B125LRU： ,O.5S125LRU： .O.59375LRL： ,0,6125LRU!.0.625LRU：,O.6375LRU： .0.65LRL： ,O.O9375LRU： ,O.6S6B75LRU： ,O.7C3125LRU； .O.715625LRI： ,O.71B75LRUs ,0.759375LRU： ,0.759375LRU： .O.759375LRU： .0.S03125LRU：

19、,0.803125LRli ,0.S03125LRU： .0.83125LRL： .0,B34375LRL： ,0.S375LRU：,0.B625LRU： .0.B78125LRU： -0,S90625LRI： ,0.fi90625LRU! .O.9LRU：0.543750FI： 0.56250PT： 0.578I250PT： 0.593750PTJ 0.60PT： 0,6156250PT1 0.643750PT： 04656250PT： 0.66250FT： 0,6S43750PT： 0.6900250PT： Q.7092T50PT： 0.72B1250FIJ 0.7406250PUO.75

20、OPT： 04768750： 0t775OPT： 0.793750PT： O.0125OPT： 0.8250PT： 04H8125OFT： 0,a468750PT： 0.8593750PT： 0.8718750PT： 0.8781250PT! 0,8843750PT： 0.88750PT：。.麗 6K7sop1 ： 0.90PI：0.9S4375LFUJ O,98125LFU1 O.97B125LFU： O.975LFU： O.97IS75LFC： 0.96B75LFU： 0.965625LFU： 0-9625LFL： 0.959375LFU： 0,95e25LF(J： 0.953125LFU： 0-95LFU； O-94