完整版面置換算法試驗(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í)間工程名稱(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)不再被訪問(wèn)的頁(yè)面.因此如何找出這樣的頁(yè)面是該算法的關(guān)鍵.可為每個(gè)頁(yè)面設(shè)置一個(gè)步長(zhǎng)變量,其初值為一足夠大的數(shù),對(duì)于不在內(nèi)存的頁(yè)面,將其值重置為零,對(duì)

2、于位于內(nèi)存的頁(yè)面,其值重置為當(dāng)前訪問(wèn)頁(yè)面與之后首次出現(xiàn)該頁(yè)面時(shí)兩者之間的距離,因此該值越大表示該頁(yè)是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(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)中的訪問(wèn)時(shí)間time來(lái)實(shí)現(xiàn),time記錄了一個(gè)頁(yè)面上次的訪問(wèn)時(shí)間,因

3、此,當(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è)被訪問(wèn),那么將其計(jì)數(shù)器的值加1,在需要選擇一頁(yè)置換時(shí),那么將選擇其計(jì)數(shù)器值最小的頁(yè)面,即內(nèi)存中訪 問(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í)驗(yàn)步驟(包括主

4、要步驟、代碼分析等) 主要代碼：1. 頁(yè)面結(jié)構(gòu)typedef struct(int 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)訪問(wèn)該 頁(yè)面的次數(shù),time為訪問(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_struct(int pn, pfn;struct pfc_struct *next;t

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

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

7、pe *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;

8、busypf_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) /*假設(shè)忙頁(yè)幀隊(duì)列為空,那么將其頭尾指針都指向剛調(diào)入頁(yè)面所在的頁(yè)幀*/busypf_head=busypf_tail=freepf_head;else( / 否那么,將剛調(diào)入頁(yè)面所在的頁(yè)幀掛在忙頁(yè)幀隊(duì)列尾部 busypf_tail->next=

9、freepf_head;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è)面失效 */diseffe

10、ct+;if(freepf_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; / plp

11、agei.time=present_time; / freepf_head=freepf_head->next; /騰出一個(gè)單元有空閑頁(yè)面,改為有效修改頁(yè)面的訪問(wèn)時(shí)間減少一個(gè)free 頁(yè)面 elseplpagei.time=present_time; /命中那么修改該單元的訪問(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_

12、pf);for(i=0;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)前訪問(wèn)頁(yè)面之后將再次被訪問(wèn)的頁(yè)面,dist重置為當(dāng)前頁(yè)面與之后首次出現(xiàn)該頁(yè)面時(shí)兩者之間的距離*/for(j=i+1;

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

14、>pfn; /有空閑頁(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)

15、/ 無(wú)空閑頁(yè)幀 ( min=32767; for(j=0;j<total_vp;j+) ( /查找位于內(nèi)存且訪問(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è)單元 plmi npage.pfn=INVALID;freepf_head->next=NULL;plpagei.pfn=freepf_head->pfn; /有空閑頁(yè)面,改

16、為有效plpagei.counter+; /增加頁(yè)面訪問(wèn)次數(shù)freepf_head=freepf_head->next; / 減少一個(gè) free 頁(yè) else plpagei.counter+; / 命中增加頁(yè)面訪問(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),如下列圖：17root1o carhost; 成作系條/綜合性室登.' nX文

17、件(E)編輯9 查看終端標(biāo)管host 綜合性實(shí)驗(yàn)忡 gr -o main main.cppMemory h: In constructor CMeimry： :CMenKiry： J :Memory ,h：35：警告：當(dāng)轉(zhuǎn)換到inf (從floalj 時(shí)Memory.h:警吾：當(dāng)轉(zhuǎn)換薊int' (Ariggiz)時(shí)Memory h ； 44 ：警告：當(dāng)轉(zhuǎn)供到inf (從float WroDtlocalhost 綜合性實(shí)臉./mainFIFO.0.54375LRL：0,543750FT：0.984375LFU：0.528125FIFO.0.553125LRC0,5fi250PT：O,98

18、125LFU10.5375FIFO.0.578125LRI0.57B1230PT：0.97B125LFU：0.55625FIFO.0.5S125LRU：0.593750PI:C-S75LFU：0.565625FIFO.0.39373LRL'：0.60PT：0.97IS75LFL：0.575FIFO.0.6125LRU：0.6I56230PIJ0.96B75LFU：0.6FIFO.6跆LF?山0.643750PT；0.965625LFU：0.61875FIFO.0.6375LRU：0.656250FT：0.0625LFIU0*621575rii;o.0.65LRC：0.66250FT：0

19、.959375LFU：0.621B75FIFO,0.69375LRU：0.6a43750PT：0,95625LFU：0.634373FIFO.0.696875LRI0.6906250PT：0.953125LFU：0.653125FIFO-0.703125LRI0.7093750PT：0-S5LFUJ0.665625FIFO.0.715625LRL0.7281250PT：O-946B7SLFU：0.S84375FIFO.0.71B75LRE：0.7406250PT：O.g4373LFL：0.70625FIFO.0.75&375LRU0.750PT：0.940625LFU：0.721375I-IFO.0.75S375LRUOA6B750PT：0.9375LFU10.7J0625FIFO.0.7S9375LRL0.7750FI：O.934375LFU：0.5625FIFO,0,B03l25LRL0,793750PI：O,93125LFU：0,7S873FIFO.0.S03125LRI0.81250FT：0.92fil25LFU：0.7875FIR).0.E03125LRU0.8250P