操作系統(tǒng)存儲(chǔ)管理試驗(yàn)報(bào)告課案資料

1、實(shí)驗(yàn) 五 存儲(chǔ)管理一、實(shí)驗(yàn)?zāi)康? 、加深對(duì)操作系統(tǒng)存儲(chǔ)管理的理解2 、能過(guò)模似頁(yè)面調(diào)試算法，加深理解操作系統(tǒng)對(duì)內(nèi)存的高度管理二、總的設(shè)計(jì)思想、環(huán)境語(yǔ)言、工具等總的設(shè)計(jì)思想：1、編寫函數(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ì)于位于內(nèi)存的頁(yè)面， 其值重置為當(dāng)前訪問(wèn)頁(yè)面與之后首次出現(xiàn)該頁(yè)面時(shí)兩者之間的距離，因此該值越大表示該頁(yè)是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面，可以選擇其作為

2、換出頁(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í)間， 因此， 當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇處于內(nèi)存的頁(yè)面中其 time 值最小的頁(yè)面，即最近最久未使用的頁(yè)面予以淘汰。LFU頁(yè)面置換算法L

3、FU 要求為每個(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)行淘汰。NUR頁(yè)面置換算法NUR要求為每個(gè)頁(yè)面設(shè)置一位訪問(wèn)位（該訪問(wèn)位仍可使用頁(yè)面結(jié)構(gòu)中的counter表示），當(dāng)某頁(yè)被訪問(wèn)時(shí)，其訪問(wèn)位 counter 置為 1。需要進(jìn)行頁(yè)面置換時(shí)，置換算法從替換指針開(kāi)始（初始時(shí)指向第一個(gè)頁(yè)面）順序檢查處于內(nèi)存中的各個(gè)頁(yè)面，如果其訪問(wèn)位為 0，就選擇該頁(yè)換出， 否則替換指針下移繼續(xù)向下查找。 如果內(nèi)存中的所有頁(yè)面掃描完畢未找到訪問(wèn)位為 0 的頁(yè)面，則將替換指針重新指向第

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

5、） ， 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。2）頁(yè)幀控制結(jié)構(gòu)struct pfc_structint pn, pfn;struct pfc_struct *next;typedef struct pfc_struct pfc_type;pfc_type pfctotal_vp, *freepf_head, *busypf_head, *busypf_tail;其中 pfctotal_vp 定義用戶進(jìn)

6、程的頁(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è)幀尾的指針指令流數(shù)組2、 變量定義(1) int atotal_instruction:(2) int diseffect:頁(yè)面失效次數(shù)每條指令所屬頁(yè)面號(hào)(3) int pagetotal_instruction:(4) int offsettotal_instruction:每頁(yè)裝入 10 條指令后取模運(yùn)算得出的頁(yè)內(nèi)偏移地址初始化函數(shù)3、 主要函數(shù)(1) void initi

7、alize(int):該函數(shù)主要對(duì)頁(yè)面結(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) vOidOPT(int):計(jì)算使用最佳頁(yè)面算法時(shí)的命中率(3) vOidFIFO(int):計(jì)算使用先進(jìn)先出頁(yè)面置換算法時(shí)的命中率(4) vOidLRU(int):計(jì)算使用最近最久未使用頁(yè)面置換算法時(shí)的命中率(5) vOidLFU(int):計(jì)算使用最少使用置換算法時(shí)的命中率(6) vOidNUR(int):計(jì)算使用最近未使用置換算法時(shí)的命中率

8、四、主要算法的設(shè)計(jì)與實(shí)現(xiàn)vOid FIFO(int tOtal_pf)/* 先進(jìn)先出頁(yè)面置換算法 */int i,j;pfC_type *p;initialize(tOtal_pf);busypf_head=busypf_tail=NULL;頁(yè)面失效 */fOr(i=0;inext;plbusypf_head-pn.pfn=INVALID; /將忙頁(yè)幀隊(duì)首頁(yè)面作為換出頁(yè)面freepf_head=busypf_head;freepf_head-next=NULL; busypf_head=p; / 忙頁(yè)幀頭指針后移p=freepf_head-next; /有空閑頁(yè)幀freepf_head-nex

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

10、t)diseffect/320);void LRU(int total_pf)/*最近最久未使用頁(yè)面置換算法 */int i,j;int min,minj,present_time;initialize(total_pf);present_time=0;頁(yè)面失效 */for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID) /*diseffect+;if(freepf_head=NULL) /*無(wú)空閑頁(yè)幀 */min=32767;for(j=0;jplj.time & plj.pfn!=INVALID)min=plj.time;minj=j;f

11、reepf_head=&pfcplminj.pfn; / plminj.pfn=INVALID;plminj.time=-1;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn; /減少一個(gè) free 頁(yè)面freepf_head=freepf_head-next; /elseplpagei.time=present_time; /命中則修改該單元的訪問(wèn)時(shí)間present_time+;printf(LRU:%6.4f ,1-(float)diseffect/320);void NUR(int total_pf)/* 最近未使用頁(yè)面置換算法 */in

12、t i,j,dp,cont_flag,old_dp;initialize(total_pf);dp=0;頁(yè)面失效 */for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID) /*diseffect+;if(freepf_head=NULL) /*無(wú)空閑頁(yè)幀 */cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pldp.counter=0&pldp.pfn!=INVALID)cont_flag=FALSE; / 找到位于內(nèi)存且未被訪問(wèn)的頁(yè)面elsedp+;if(dp=total_vp) dp=0; /將替

13、換指針重新指向第一個(gè)頁(yè)面所有頁(yè)面的訪問(wèn)位置0 */if(dp=old_dp)/*若內(nèi)存中所有頁(yè)面掃描完畢未找到訪問(wèn)位為 0的頁(yè)面，將內(nèi)存中for(j=0;jnext=NULL;plpagei.pfn=freepf_head-pfn; / freepf_head=freepf_head-next; /else命中則將訪問(wèn)位置 1plpagei.counter=1; /if(i%clear_period=0) /清零周期到，將所有訪問(wèn)位清零for(j=0;jtotal_vp;j+)plj.counter=0;printf(NUR:%6.4f ,1-(float)diseffect/320);voi

14、d OPT(int total_pf)/* 最佳頁(yè)面置換算法 */int i,j,max,maxpage,d,disttotal_vp;initialize(total_pf);頁(yè)面失效 */for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID) /*diseffect+;if(freepf_head=NULL) /*無(wú)空閑頁(yè)面 */for(j=0;jtotal_vp;j+)if(plj.pfn!=INVALID)/所有位于內(nèi)存頁(yè)面的距離變量賦一足夠大的數(shù)distj=32767;else / 不在內(nèi)存的頁(yè)面該變量則置為 0distj=0;di

15、st 重置為當(dāng)d=1;/* 對(duì)于位于內(nèi)存且在當(dāng)前訪問(wèn)頁(yè)面之后將再次被訪問(wèn)的頁(yè)面，前頁(yè) 面 與之后首次出現(xiàn)該頁(yè)面時(shí)兩者之間的距離*/ for(j=i+1;jtotal_instruction;j+)if(plpagej.pfn!=INVALID & distpagej=32767)distpagej=d;d+;max=-1;/ 查找 dist 變量值最大的頁(yè)面作為換出頁(yè)面for(j=0;jtotal_vp;j+)if(maxnext=NULL;plmaxpage.pfn=INVALID;有空閑頁(yè)面 , 改為有效減少一個(gè) free 頁(yè)面plpagei.pfn=freepf_head-pfn; /

16、freepf_head=freepf_head-next; /printf(OPT:%6.4f ,1-(float)diseffect/320);void LFU(int total_pf)/* 最少使用頁(yè)面置換算法*/int i,j,min,minpage;initialize(total_pf);頁(yè)面失效for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID) /diseffect+;if(freepf_head=NULL) /無(wú)空閑頁(yè)幀min=32767;for(j=0;jplj.counter&plj.pfn!=INVALID)else

17、min=p lj.co un ter;minp age=j;p l|j.co un ter=0;freep f_head=&pfcp lm inp age. pfn; /plmi np age. pfn=INVALID;freep f_head-n ext=NULL;p l pagei .pfn=freep f_head-pfn; /p l pagei.co un ter+;/freep f_head=free pf_head-n ext; /p l pagei.co un ter+; /prin tf(LFU:%6.4f ,1-(float)diseffect/320);五、運(yùn)行結(jié)果本實(shí)驗(yàn)的

18、運(yùn)行結(jié)果如下圖所示（以456789 10 11 12131415 le17181920 21 2223242526272829303132pagepagepagepage page page pagepage page page pagepage page page pagepage page page pagepage page page pagepage page page page page pageframes frames frames frames frames frames frames frames frames frames frames frames frames fram

19、es frames frames frames frames frames frames frames frames frames frames frames frames frames frames francsOPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT OPT0.6563 0.6813 0.7063 0.7312FIFO FIFO FIFO FIFO0.7500 FIFO 0.7656 FIFO 0.7813 FIFO 0.7937 FIFO 0.8031 0.8125 0.8219 0.8313 0.8406FIFO FIFO FIFO FIFO FIFO0-8500 FIFO 0.8594 FIFO 0.8656 FIFO 0.8688 FIFO 0.8719 FIFO 0.8750 FIFO 0.8781 FIFO 0.8812 FIFO 0.8844 FIFO