操作系統(tǒng)存儲管理實驗報告課案

1、實驗五存儲管理一、實驗?zāi)康? 、加深對操作系統(tǒng)存儲管理的理解2、能過模似頁面調(diào)試算法，加深理解操作系統(tǒng)對內(nèi)存的高度管理二、總的設(shè)計思想、環(huán)境語言、工具等總的設(shè)計思想：1、編寫函數(shù)計算并輸出下述各種算法的命中率 OPT頁面置換算法OPT所選擇被淘汰的頁面是已調(diào)入內(nèi)存，且在以后永不使用的，或是在最長時間內(nèi)不再被訪問的頁面。因此如何找出這樣的頁面是該算法的關(guān)鍵。可為每個頁面設(shè)置一 個步長變量，其初值為一足夠大的數(shù)，對于不在內(nèi)存的頁面，將其值重置為零，對于 位于內(nèi)存的頁面，其值重置為當(dāng)前訪問頁面與之后首次出現(xiàn)該頁面時兩者之間的距離， 因此該值越大表示該頁是在最長時間內(nèi)不再被訪問的頁面，可以選擇其作為換

2、出頁面。 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記錄了一個頁面上次的訪問時間，因此，當(dāng)須淘汰一個頁面時，選擇處于內(nèi)存的頁面中其time值最小的頁面，即最近最久未使用的頁面予以淘汰。 LFU頁面置換算法LFU要求為每

3、個頁面配置一個計數(shù)器（即頁面結(jié)構(gòu)中的counter），一旦某頁被訪問，則將其計數(shù)器的值加 1,在需要選擇一頁置換時， 則將選擇其計數(shù)器值最小的頁面， 即內(nèi)存中訪問次數(shù)最少的頁面進(jìn)行淘汰。 NURM面置換算法NUR要求為每個頁面設(shè)置一位訪問位（該訪問位仍可使用頁面結(jié)構(gòu)中的cou nter表示），當(dāng)某頁被訪問時，其訪問位counter置為1。需要進(jìn)行頁面置換時，置換算法從替換指針開始（初始時指向第一個頁面）順序檢查處于內(nèi)存中的各個頁面，如果其 訪問位為0，就選擇該頁換出，否則替換指針下移繼續(xù)向下查找。如果內(nèi)存中的所有頁面掃描完畢未找到訪問位為0的頁面，則將替換指針重新指向第一個頁面，同時將內(nèi)存中所

4、有頁面的訪問位置0,當(dāng)開始下一輪掃描時，便一定能找到counter為0的頁面。2、在主函數(shù)中生成要求的指令序列，并將其轉(zhuǎn)換成頁地址流；在不同的內(nèi)存容量下調(diào)用上述函數(shù)使其計算并輸出相應(yīng)的命中率。環(huán)境語言：Linux下的GNU編譯環(huán)境三、數(shù)據(jù)結(jié)構(gòu)與模塊說明程序中用到的數(shù)據(jù)結(jié)構(gòu)、類型定義及主要的函數(shù)原型如下：1、數(shù)據(jù)結(jié)構(gòu)(1) 頁面結(jié)構(gòu)typedef structint pn, pfn, counter, time; pl_type ;pl_type pltotal_vp;其中pn為頁面號(頁號)，pfn為頁幀號(物理塊號)，counter為一個周期內(nèi)訪問該頁面的 次數(shù)，time為訪問時間；plto

5、tal_vp為頁面結(jié)構(gòu)數(shù)組，由于共有320條指令，每頁可裝入 10條指令，因此虛頁長total_vp 的值為32。(2) 頁幀控制結(jié)構(gòu)struct pfc_structint pn, pfn;struct pfc_struct *n ext;typedef 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_h

6、ead 為空閑頁幀頭的指針*busypf_head為忙頁幀頭的指針*busypf_tail 忙頁幀尾的指針2、變量定義(1) int atotal_i nstructio n:指令流數(shù)組(2) int diseffect:頁面失效次數(shù)(3) in t pagetotal_i nstructio n:每條指令所屬頁面號(4) int offsettotal_instruction:每頁裝入10條指令后取模運算得出的頁內(nèi)偏移地址3、主要函數(shù)(1) void in itialize(i nt):初始化函數(shù)該函數(shù)主要對頁面結(jié)構(gòu)數(shù)組pl和頁幀結(jié)構(gòu)數(shù)組pfc進(jìn)行初始化，如置頁面結(jié)構(gòu)中的頁面號pn,初始化頁

7、幀號 pfn為空，訪問次數(shù)counter為0，訪問時間time為-1 ;同樣對頁幀數(shù)組進(jìn)行初始化，形成一個空閑頁幀隊列。 void OPT(i nt):計算使用最佳貝面算法時的命中率 void FIFO(i nt):計算使用先進(jìn)先出頁面置換算法時的命中率 void LRU(i nt):計算使用最近最久未使用頁面置換算法時的命中率(5) void LFU(int):計算使用最少使用置換算法時的命中率 void NUR(i nt):計算使用最近未使用置換算法時的命中率四、主要算法的設(shè)計與實現(xiàn)void FIFO(int total_pf)/*先進(jìn)先出頁面置換算法 */int i,j;pfc_type

8、 *p;in itialize(total_pf);busypf_head=busypf_tail=NULL;for(i=0;i<total_i nstructio n; i+)if(plpagei.pfn=INVALID)/*頁面失效 */diseffect=diseffect+1;if(freepf_head=NULL) /* 無空閑頁幀 */p=busypf_head->n ext;plbusypf_head->p n.pfn=INVALID; /將忙頁幀隊首頁面作為換出頁面freepf_head=busypf_head;freepf_head->n ext=NU

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

10、freepf_head;busypf_tail=freepf_head;freepf_head=p; II空閑頁幀頭指針后移prin tf("FIFO:%6.4f ",1-(float)diseffect/320);void LRU(i nt total_pf)/*最近最久未使用頁面置換算法*/int i,j;int min, minj,prese nt_time;in itialize(total_pf);prese nt_time=0;for(i=0;i<total_i nstructio n;i+)頁面失效*/if(plpagei.pfn=INVALID) /*

11、diseffect+;if(freepf_head=NULL) /*無空閑頁幀*/min=32767;for(j=0;j<total_vp;j+) /*找出位于內(nèi)存且time值最小的頁面作為置換頁騰出一個單元有空閑頁面，改為有效面*/if(min>plj.time && plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head=&pfcplminj.pfn; / plminj.pfn=INVALID;plminj.time=-1;freepf_head->n ext=NULL;plpagei.pfn=freepf

12、_head->pfn; /freepf_head=freepf_head->next; /減少一個 free 頁面elseplpagei.time=prese nt_time; /命中則修改該單元的訪問時間prese nt_time+;prin tf("LRU:%6.4f ",1-(float)diseffect/320);void NUR(i nt total_pf)/*最近未使用頁面置換算法*/int i,j,dp,c on t_flag,old_dp;in itialize(total_pf);dp=0;for(i=0;i<total_i nstru

13、ctio n; i+)if(plpagei.pfn=INVALID)/*頁面失效 */diseffect+;if(freepf_head=NULL) /* 無空閑頁幀 */con t_flag=TRUE;old_dp=dp;while(c on t_flag)if(pldp.cou nter=0&&pldp.pfn!=INVALID)con t_flag=FALSE; /找到位于內(nèi)存且未被訪問的頁面elsedp+;if(dp=total_vp) dp=0; /將替換指針重新指向第一個頁面if(dp=old_dp)/*若內(nèi)存中所有頁面掃描完畢未找到訪冋位為0的頁面，將內(nèi)存中所有頁

14、面的訪問位置0 */for(j=0;j<total_vp;j+)plj.co un ter=0;freepf_head=&pfcpldp.pfn; /騰出一個單元pldp.pfn=INVALID; freepf_head->n ext=NULL;plpagei.pfn=freepf_head->pfn; /有空閑頁面，改為有效freepf_head=freepf_head->next; /減少一個 free 頁面elseplpagei.cou nter=1; /命中則將訪問位置 1if(i%clear_period=0) /清零周期到，將所有訪問位清零for(j

15、=0;j<total_vp;j+)plj.co un ter=0;prin tf("NUR:%6.4f ",1-(float)diseffect/320);void OPT( int total_pf)/*最佳頁面置換算法*/int i,j,max,maxpage,d,disttotal_vp;in itialize(total_pf);for(i=0;i<total_i nstructio n;i+)if(plpagei.pfn=INVALID) /*頁面失效 */diseffect+;if(freepf_head=NULL) /* 無空閑頁面 */for(j

16、=0;j<total_vp;j+)if(plj.pfn!=INVALID)所有位于內(nèi)存頁面的距離變量賦一足夠大的數(shù)distj=32767;else II不在內(nèi)存的頁面該變量則置為0distj=0;d=1;I*對于位于內(nèi)存且在當(dāng)前訪問頁面之后將再次被訪問的頁面，dist重置為當(dāng)前頁面與之后首次出現(xiàn)該頁面時兩者之間的距離*/for(j=i+1;j<total_ in struct ion ;j+)if(plpagej.pfn!=INVALID && distpagej=32767) distpagej=d;d+;max=-1;/查找dist變量值最大的頁面作為換出頁面

17、for(j=0;j<total_vp;j+) if(max<distj) max=distj; maxpage=j;freepf_head=&pfcplmaxpage.pfn; /騰出一個單元freepf_head->n ext=NULL;有空閑頁面，改為有效減少一個free頁面plmaxpage.pfn=INVALID;plpagei.pfn=freepf_head->pfn; / freepf_head=freepf_head->n ext; /prin tf("OPT:%6.4f ",1-(float)diseffect/320)

18、;void LFU(i nt total_pf)/*最少使用頁面置換算法*/int i,j,mi n,min page;in itialize(total_pf);for(i=0;i<total_i nstructio n;i+)if(plpagei.pfn=INVALID) /頁面失效diseffect+;if(freepf_head=NULL) /無空閑頁幀min=32767;for(j=0;j<total_vp;j+) /查找位于內(nèi)存且訪問次數(shù)最少的頁面作為換出頁面if(mi n>plj.cou nter&& plj.pfn!=INVALID)min=p

19、lj.co un ter;min page=j;plj.co un ter=0;freepf_head=&pfcplm in page.pfn; /騰出一個單元plmi npage.pfn=INVALID; freepf_head->n ext=NULL;/有空閑頁面，改為有效增加頁面訪問次數(shù)/減少一個free 頁面 plpagei.pfn=freepf_head->pfn; plpagei.co un ter+;/freepf_head=freepf_head->n ext;elseplpagei.cou nter+; /命中增加頁面訪問次數(shù)prin tf(&quo

20、t;LFU:%6.4f ",1-(float)diseffect/320);五、運行結(jié)果OPT FIFO、LRU為例）：本實驗的運行結(jié)果如下圖所示（以4frames OPT6.6563 FIFA0.5&87 LRU0.56565 page frames OPTB.£S13 FIFOU.b«44 LRU6 nage frames OPT0.7063 FIFAU.bVOE LRU8.60317 Daqe frames OPT0.7312 FIFOo.bisa LRUe.fiies8 naqeOPT0.7500 FIFOB.6250 LRU9 Daqe fram

21、es OPT0.7656 FIFCtB.6438 LRU.G59410 naqe frames OPT0.7813 FIF<tB.6Sb3 LRUe.G6S711 page frames OPT0.7937 FIFCtB.6625 LRU0.675(912 pa<fe frames OPT0.S031 FIF<tB.b719 LRU0.675013 aq-e尸耳耐乞OPT0.8125 FIFCtB.7331 LRUfl.684414 mite fr'anies OPT0.8219 FIF<tB.?0b3 LRU0.703115Frames OPT0.8313 F

22、IFCt0.7344 LRU0.71SS16 XffE fr-ames OPT0.8406 FIFOB.7433 LRU0.737517fr-ames OPT0.S5S0 FIFOLRU思.?4t918 pae fr-aniES OPT歐S594 FIFO；Q7656 LRUS.76S819 page fraines OPT0.8656 FIFOQ.7&BS LRUQ.781320 pasfeOPT0.86S8 FIFO；Q7875 LRU0.787521 wsfe fvanes OPT0.8719 FIFO:<.?844 LRUB.8M22 puse frames OPT0.8750 FIFOa.*088 LRUB.B1S6