頁面置換算法 實驗報告

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

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

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

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

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

6、數(shù)組pl和頁幀結(jié)構(gòu)數(shù)組pfc進(jìn)行初始化，如置頁面結(jié)構(gòu)中的頁面號pn，初始化頁幀號pfn為空，訪問次數(shù)counter為0，訪問時間time為-1；同樣對頁幀數(shù)組進(jìn)行初始化，形成一個空閑頁幀隊列。(2) void OPT(int): 計算使用最佳頁面算法時的命中率(3) void FIFO(int): 計算使用先進(jìn)先出頁面置換算法時的命中率(4) void LRU(int): 計算使用最近最久未使用頁面置換算法時的命中率(5) void LFU(int): 計算使用最少使用置換算法時的命中率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;inext;plbusypf_head-pn.pfn=INVALID; /將忙頁幀隊首頁面作為換出頁面freepf_head=busypf_head; freepf_head-next=NULL;busypf_head=p; /忙頁幀頭指針后移p=freepf_head-next; /有空閑頁幀freepf_head-next=NULL;freepf_head-pn=pagei; /* 將所需頁面調(diào)入空閑頁幀 */plpagei.pfn=freepf_head-p

8、fn;if(busypf_tail=NULL) /* 若忙頁幀隊列為空，則將其頭尾指針都指向剛調(diào)入頁面所在的頁幀 */busypf_head=busypf_tail=freepf_head;else /否則，將剛調(diào)入頁面所在的頁幀掛在忙頁幀隊列尾部busypf_tail-next=freepf_head;busypf_tail=freepf_head;freepf_head=p; /空閑頁幀頭指針后移 printf(FIFO:%6.4f ,1-(float)diseffect/320);void LRU(int total_pf) /*最近最久未使用頁面置換算法*/ int i,j; int

9、min,minj,present_time; initialize(total_pf); present_time=0;for(i=0;itotal_instruction;i+) if(plpagei.pfn=INVALID) /*頁面失效*/diseffect+;if(freepf_head=NULL) /*無空閑頁幀*/min=32767;for(j=0;jplj.time & plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head=&pfcplminj.pfn; /騰出一個單元plminj.pfn=INVALID;plminj.time=-1;

10、freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn; /有空閑頁面,改為有效plpagei.time=present_time; /修改頁面的訪問時間freepf_head=freepf_head-next; /減少一個free 頁面elseplpagei.time=present_time; /命中則修改該單元的訪問時間present_time+; printf(LRU:%6.4f ,1-(float)diseffect/320);void OPT(int total_pf) /* 最佳頁面置換算法 */ int i,j,max,maxpage

11、,d,disttotal_vp; initialize(total_pf); for(i=0;itotal_instruction;i+) if(plpagei.pfn=INVALID) /*頁面失效*/ diseffect+; if(freepf_head=NULL) /*無空閑頁面*/ for(j=0;jtotal_vp;j+)if(plj.pfn!=INVALID)/所有位于內(nèi)存頁面的距離變量賦一足夠大的數(shù)distj=32767; else /不在內(nèi)存的頁面該變量則置為0distj=0;d=1; /* 對于位于內(nèi)存且在當(dāng)前訪問頁面之后將再次被訪問的頁面，dist重置為當(dāng)前頁面與之后首次出

12、現(xiàn)該頁面時兩者之間的距離 */for(j=i+1;jtotal_instruction;j+) if(plpagej.pfn!=INVALID & distpagej=32767) distpagej=d; d+;max=-1;/查找dist變量值最大的頁面作為換出頁面for(j=0;jtotal_vp;j+) if(maxnext=NULL;plmaxpage.pfn=INVALID; plpagei.pfn=freepf_head-pfn; /有空閑頁面,改為有效 freepf_head=freepf_head-next; /減少一個free 頁面 printf(OPT:%6.4f ,1-

13、(float)diseffect/320);void LFU(int total_pf) /* 最少使用頁面置換算法 */ int i,j,min,minpage; initialize(total_pf); for(i=0;itotal_instruction;i+) if(plpagei.pfn=INVALID) /頁面失效 diseffect+; if(freepf_head=NULL) /無空閑頁幀 min=32767;for(j=0;jplj.counter&plj.pfn!=INVALID) min=plj.counter; minpage=j; plj.counter=0; fr

14、eepf_head=&pfcplminpage.pfn; /騰出一個單元 plminpage.pfn=INVALID; freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn; /有空閑頁面,改為有效plpagei.counter+; /增加頁面訪問次數(shù)freepf_head=freepf_head-next; /減少一個free 頁 elseplpagei.counter+; /命中增加頁面訪問次數(shù) printf(LFU:%6.4f ,1-(float)diseffect/320);將上述函數(shù)寫成頭文件的格式封裝在Memory.h頭文件中，由主函數(shù)main調(diào)用使用。運行結(jié)果打開linux虛擬機(jī)，用vim編輯器打開代碼進(jìn)行修改和調(diào)整。用g+編譯器進(jìn)行編譯運,如圖所示：四、 結(jié)果分析與總結(jié) 由實驗結(jié)果可知opt算法可保證