操作系統(tǒng)存儲(chǔ)管理實(shí)驗(yàn)介紹

1、河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告實(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)不再被訪問的頁(yè)面。因此如何找出這樣的頁(yè)面是該算法的關(guān)鍵?？蔀槊總€(gè)頁(yè)面設(shè)置一個(gè)步長(zhǎng)變量，其初值為一足夠大的數(shù)，對(duì)于不在內(nèi)存的頁(yè)面，將其值重置為零，對(duì)于位于內(nèi)存的頁(yè)面，其值重置為當(dāng)前訪問頁(yè)面與之后首次出現(xiàn)該頁(yè)面時(shí)兩者之間的距離，因此該值越大表示該頁(yè)是在最長(zhǎng)時(shí)間內(nèi)不再

2、被訪問的頁(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)中的訪問時(shí)間time來(lái)實(shí)現(xiàn)，time記錄了一個(gè)頁(yè)面上次的訪問時(shí)間，因此，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇處于內(nèi)存的頁(yè)面中其time值最小的頁(yè)面，即最近最久未使用的頁(yè)面予以淘汰。LFU頁(yè)面置換

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

4、存中所有頁(yè)面的訪問位置0,當(dāng)開始下一輪掃描時(shí)，便一定能找到counter。的頁(yè)面。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)typedefstructintpn,pfn,counter,time;pl_type;pl_typepltotal_vp;其中pn為頁(yè)面號(hào)(頁(yè)號(hào))，pfn為頁(yè)幀號(hào)(物理塊號(hào))，counter為一個(gè)周期內(nèi)訪問該頁(yè)面的次數(shù)，time為訪問時(shí)間；pltotal_vp為頁(yè)

5、面結(jié)構(gòu)數(shù)組，由于共有320條指令，每頁(yè)可裝入10條指令，因此虛頁(yè)長(zhǎng)total_vp的值為32。(2)頁(yè)幀控制結(jié)構(gòu)structpfc_structintpn,pfn;structpfc_struct*next;typedefstructpfc_structpfc_type;pfc_typepfctotal_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

6、為忙頁(yè)幀頭的指針*busypf_tail忙頁(yè)幀尾的指針2、變量定義intatotal_instruction:指令流數(shù)組(2) intdiseffect:頁(yè)面失效次數(shù)(3) intpagetotal_instruction:每條指令所屬頁(yè)面號(hào)(4) intoffsettotal_instruction:每頁(yè)裝入10條指令后取模運(yùn)算得出的頁(yè)內(nèi)偏移地址(5) int total_pf:用戶進(jìn)程的內(nèi)存頁(yè)幀數(shù)3、主要函數(shù)voidinitialize(int):初始化函數(shù)該函數(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為空，訪問次數(shù)counter

7、為0,訪問時(shí)間time為-1;同樣對(duì)頁(yè)幀數(shù)組進(jìn)行初始化，形成一個(gè)空閑頁(yè)幀隊(duì)列。(2)voidOPT(int):計(jì)算使用最佳頁(yè)面算法時(shí)的命中率voidFIFO(int):計(jì)算使用先進(jìn)先出頁(yè)面置換算法時(shí)的命中率(4)voidLRU(int):計(jì)算使用最近最久未使用頁(yè)面置換算法時(shí)的命中率(5) void LFU(int):計(jì)算使用最少使用置換算法時(shí)的命中率(6) void NUR(int):計(jì)算使用最近未使用置換算法時(shí)的命中率四、主要算法的設(shè)計(jì)與實(shí)現(xiàn)voidFIFO(inttotal_pf)/*先進(jìn)先出頁(yè)面置換算法*/inti,j;pfc_type*p;initialize(total_pf);bu

8、sypf_head=busypf_tail=NULL;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-next=NULL;freepf_head-pn=pagei;/*將所需頁(yè)面調(diào)入空閑頁(yè)幀*/plpagei.pfn=freepf_head-pfn;if(busypf_tail=NULL)/*若忙頁(yè)幀隊(duì)列為空，則將其頭

9、尾指針都指向剛調(diào)入頁(yè)面所在的頁(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-(float)diseffect/320);void LRU(int total_pf) /*最近最久未使用頁(yè)面置換算法*/int i,j；int min,minj,present_time;initialize(total_pf);prese

10、nt_time=0;for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID) /*頁(yè)面失效 */diseffect+;if(freepf_head=NULL) /* 無(wú)空閑頁(yè)幀 */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;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn; /

11、plpagei.time=present_time; /騰出一個(gè)單元有空閑頁(yè)面，改為有效 修改頁(yè)面的訪問時(shí)間河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告freepf_head=freepf_head-next;/減少一個(gè)free頁(yè)面elseplpagei.time=present_time;/命中則修改該單元的訪問時(shí)間present_time+;printf(LRU:%6.4f,1-(float)diseffect/320);voidNUR(inttotal_pf)/*最近未使用頁(yè)面置換算法*/inti,j,dp,cont_flag,old_dp;initialize(total_pf);dp=0

12、;for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID)/*頁(yè)面失效*/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)存且未被訪問的頁(yè)面elsedp+;if(dp=total_vp)dp=0;/將替換指針重新指向第一個(gè)頁(yè)面if(dp=old_dp)/*若內(nèi)存中所有頁(yè)面掃描完畢未找到訪問位為。的頁(yè)面，將內(nèi)存中所有頁(yè)面

13、的訪問位置0*/for(j=0;jnext=NULL;plpagei.pfn=freepf_head-pfn;/有空閑頁(yè)面,改為有效freepf_head=freepf_head-next;/減少一個(gè)free頁(yè)面elseplpagei.counter=1;/命中則將訪問位置1if(i%clear_period=0)/清零周期到，將所有訪問位清零for(j=0;jtotal_vp;j+)plj.counter=0;printf(NUR:%6.4f,1-(float)diseffect/320);voidOPT(inttotal_pf)/*最佳頁(yè)面置換算法*/inti,j,max,maxpage,

14、d,disttotal_vp;initialize(total_pf);for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID)/*頁(yè)面失效*/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;d=1;/*對(duì)于位于內(nèi)存且在當(dāng)前訪問頁(yè)面之后將再次被訪問的頁(yè)面，dist重置為當(dāng)前頁(yè)面與之后首次出現(xiàn)該頁(yè)面時(shí)兩者之間的距離*/f

15、or(j=i+1;jtotal_instruction;j+)if(plpage皿pfn!=INVALID&distpagej=32767)distpagej=d;d+;max=-1;/查找dist變量值最大的頁(yè)面作為換出頁(yè)面for(j=0;jtotal_vp;j+)if(maxnext=NULL;plmaxpage.pfn=INVALID;plpagei.pfn=freepf_head-pfn;/有空閑頁(yè)面，改為有效freepf_head=freepf_head-next;/減少一個(gè)free頁(yè)面printf(OPT:%6.4f,1-(float)diseffect/320);voidLFU(

16、inttotal_pf)/*最少使用頁(yè)面置換算法*/inti,j,min,minpage;initialize(total_pf);for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID)/頁(yè)面失效diseffect+;if(freepf_head=NULL)/無(wú)空閑頁(yè)幀min=32767;for(j=0;jplj.counter&plj.pfn!=INVALID)河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告min=plj.counter;minpage=j;plj.counter=0;freepf_head=&pfcplminpage.pfn;/

17、騰出一個(gè)單元plminpage.pfn=INVALID;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn;/有空閑頁(yè)面，改為有效plpagei.counter+;/增加頁(yè)面訪問次數(shù)freepf_head=freepf_head-next;/減少一個(gè)free頁(yè)面elseplpagei.counter+;/命中增加頁(yè)面訪問次數(shù)printf(LFU:%6.4f,1-(float)diseffect/320);五、運(yùn)行結(jié)果本實(shí)驗(yàn)的運(yùn)行結(jié)果如下圖所示(以O(shè)PTFIFO、LRU為例)：4pageframesOPT0.6563FIFOQ.5687LRU0.5

18、65635pagefrancsOPT&.6813FIFO&.5844LRU0.59066pageframesOPT&.7063FIFO&.5906LRU&.60317pagefrancsOPT&.7312FIFO&.6188LRU&.61888pageframesOPT&.7500FIFO&.6250LRU&.64069pagefrancsOPT0.7656FIFO&.6438LRU&.659410pageframesOPT0.7813FIFO&.6563LRU&.668711pagefrancsOPT0.7937FIFO&.6625LRU&.675012pageframesOPT0.8031

19、FIFO&.6719LRU&.675013pagefrancsOPT0.8125FIFO&.7031LRU&.684414pageframesOPT0.8219FIFO&.7063LRU&.703115pagefrancsOPT0.8313FIFO&.7344LRU&.718816pageframesOPT0.8406FIFO&.7438LRU&.737517pagefrancsOPT0.8500FIFO&.7625LRU&.746918pageframesOPT0.8594FIFO&.7656LRU&.768819pagefrancsOPT0.8656FIFO&.7688LRU&.781320pageframesOPT0.8688FIFO&.7875LRU&.787521pageframesOPT0.8719FIFO&.7844LRU0.800022pageframesOPT0.8750FIFOQ.8000LRUQ.815623pageframesOPT0.8781FIFO&.8375LRU0.825024pagefra