南 昌 大 學(xué) 實(shí) 驗(yàn) 報(bào) 告-（ 5） 存 儲(chǔ) 管 理 的 模 擬 實(shí) 現(xiàn)學(xué)生姓名： 張皓然 學(xué) 號(hào)： 5501215001 專業(yè)班級(jí)： 本碩 151 實(shí)驗(yàn)類型： 驗(yàn)證 綜合 設(shè)計(jì) 創(chuàng)新 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績(jī)： 一、實(shí)驗(yàn)?zāi)康拇鎯?chǔ)管理的主要功能之一是合理地分配空間。請(qǐng)求頁(yè)式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。本實(shí)驗(yàn)的目的是通過(guò)請(qǐng)求頁(yè)式存儲(chǔ)管理中頁(yè)面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁(yè)式管理的頁(yè)面置換算法。二、實(shí)驗(yàn)內(nèi)容1過(guò)隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共 320 條指令。其地址按下述原則生成：50%的指令是順序執(zhí)行的；25%的指令是均勻分布在前地址部分；25%的指令是均勻分布在后地址部分；#具體的實(shí)施方法是：A. 在0，319的指令地址之間隨機(jī)選區(qū)一起點(diǎn) M;B. 順序執(zhí)行一條指令，即執(zhí)行地址為 M+1 的指令；C. 在前地址0，M+1中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為 M;D. 順序執(zhí)行一條指令，其地址為 M+1；E. 在后地址M+2，319中隨機(jī)選取一條指令并執(zhí)行；F. 重復(fù) AE，直到執(zhí)行 320 次指令。2指令序列變換成頁(yè)地址流設(shè)：（1）頁(yè)面大小為 1K；（2） 用戶內(nèi)存容量為 4 頁(yè)到 32 頁(yè)；（3） 用戶虛存容量為 32K。在用戶虛存中，按每 K 存放 10 條指令排列虛存地址，即 320 條指令在虛存中的存放方式為：第 0 條第 9 條指令為第 0 頁(yè)（對(duì)應(yīng)虛存地址為0，9） ；第 10 條第 19 條指令為第 1 頁(yè)（對(duì)應(yīng)虛存地址為10，19） ；。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。第 310 條第 319 條指令為第 31 頁(yè)（對(duì)應(yīng)虛存地址為310，319） ；按以上方式，用戶指令可組成 32 頁(yè)。3. 計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。A. FIFO 先進(jìn)先出的算法B. LRU 最近最少使用算法CLFU 最少訪問(wèn)頁(yè)面算法三、實(shí)驗(yàn)要求1、需寫出設(shè)計(jì)說(shuō)明；2、設(shè)計(jì)實(shí)現(xiàn)代碼及說(shuō)明3、運(yùn)行結(jié)果；四、主要實(shí)驗(yàn)步驟代碼如下：#include #include #include #include #ifndef _UNISTD_H#define _UNISTD_H#include #include #endif#define TRUE 1#define FALSE 0#define INVALID -1#define total_instruction 320 /指令流長(zhǎng)#define total_vp 32 /虛頁(yè)頁(yè)長(zhǎng)#define clear_period 50 /清零周期typedef struct /頁(yè)面結(jié)構(gòu)int pn, /頁(yè)面序號(hào)pfn, /頁(yè)面所在內(nèi)存區(qū)的幀號(hào)counter, /單位時(shí)間內(nèi)訪問(wèn)量time;pl_type;pl_type pltotal_vp; /頁(yè)面結(jié)構(gòu)數(shù)組struct pfc_struct /頁(yè)面控制結(jié)構(gòu)int pn, /頁(yè)面號(hào)pfn; /內(nèi)存區(qū)頁(yè)面的幀號(hào)/頁(yè)面指針，用于維護(hù)內(nèi)存緩沖區(qū)的鏈?zhǔn)浇Y(jié)構(gòu)struct pfc_struct *next;typedef struct pfc_struct pfc_type; /主存區(qū)頁(yè)面控制結(jié)構(gòu)名稱pfc_type pfctotal_vp, /主存區(qū)頁(yè)面控制結(jié)構(gòu)數(shù)組*freepf_head, /空閑頁(yè)面頭指針*busypf_head, /忙頁(yè)面頭指針*busypf_tail; /忙頁(yè)面尾指針int diseffect; /缺頁(yè)計(jì)數(shù)器int atotal_instruction; /指令流數(shù)組int pagetotal_instruction; /指令對(duì)應(yīng)的頁(yè)面號(hào)int offsettotal_instruction; /指令所在頁(yè)面的偏移量/初始化頁(yè)面結(jié)構(gòu)數(shù)組和頁(yè)面控制結(jié)構(gòu)數(shù)組int initialize(int);int FIFO(int); /先進(jìn)先出int LRU(int); /最近最久未使用int OPT(int); /最佳置換算法int CLOCK(int); /clock 置換算法int main( )int s;int i;srand(10*getpid(); s = (int)(float)(total_instruction-1)*(rand()/(RAND_MAX+1.0);printf("n-隨機(jī)產(chǎn)生指令流 -n");for (i=0; iplj.time&&plj.pfn!=INVALID)MinT=plj.time;MinPn=j;/釋放最久未訪問(wèn)的頁(yè)面freepf_head= /最久未訪問(wèn)頁(yè)面被換出主存plMinPn.pfn=INVALID;/最久未訪問(wèn)頁(yè)面的訪問(wèn)時(shí)間設(shè)置為無(wú)效 plMinPn.time=-1;freepf_head->next=NULL;plpagei.pfn=freepf_head->pfn; plpagei.time=CurrentTime;freepf_head=freepf_head->next; elseplpagei.time=CurrentTime; CurrentTime+; printf("%6.3ft",1-(float)diseffect/320);return 0;/最佳置換算法int OPT(int total_pf)int i,j;int MaxD; /將來(lái)最近一次訪問(wèn)距離的最大值int MaxPn; /對(duì)應(yīng)的頁(yè)號(hào)int dis; /距離計(jì)數(shù)器int disttotal_vp;initialize(total_pf); diseffect=0;for(i=0;inext=NULL;plMaxPn.pfn=INVALID;plpagei.pfn=freepf_head->pfn; freepf_head=freepf_head->next;/if/forprintf("%6.3ft",1-(float)diseffect/320);return 0;int CLOCK(int total_pf)int i;int usetotal_vp; /使用位int swap;swap=0; initialize(total_pf);pfc_type *pnext; /時(shí)鐘指針pfc_type *head; /隊(duì)列頭指針pnext=freepf_head;head=freepf_head;for(i=0;ipfn=1) usepnext->pfn=0;pnext=pnext->next;if(pnext=NULL) pnext=head; /形成循環(huán)隊(duì)列/換出被替換的頁(yè)plpnext->pn.pfn=INVALID;swap=1;if(usepnext->pfn=0) /換入相應(yīng)的頁(yè) plpagei.pfn=pnext->pfn; pnext->pn=pagei; usepnext->pfn=1;pnext=pnext->next;if(pnext=NULL) pnext=head;if(swap=0) freepf_head=freepf_head->next; else/頁(yè)面在主存中useplpagei.pfn=1; /使用位置 1 printf("%6.3ft",1-(float)diseffect/320);return 0;int FIFO(int total_pf)int i;int usetotal_vp;int swap=0;initialize(total_pf);pfc_type *pnext,*head;pnext=freepf_head;head=freepf_head;for(i=0;ipfn=1)usepnext->pfn=0;pnext=pnext->next;if(pnext=NULL) pnext=head;plpnext->pn.pfn=INVALID;swap=1;if(usepnext->pfn=0) plpagei.pfn=pnext->pfn; pnext->pn=pagei; usepnext->pfn=1;pnext=pnext->next;if(pnext=NULL) pnext=head;if(swap=0) freepf_head=freepf_head->next; printf("%6.3ft",1-(float)diseffect/320);return 0;FIFO 算法流程圖：開始頁(yè)面存入數(shù)組 p初始化內(nèi)存塊 page結(jié)束Pi是否已在內(nèi)存中i+Page是否有空將最先裝入 page中的頁(yè)面置換出去直接將 pi裝入內(nèi)存i+i<32輸出當(dāng)前頁(yè)面的 命中率是否是否是否LRU 算法流程圖：開始頁(yè)面存入數(shù)組 p初始化內(nèi)存塊 page結(jié)束Pi是否已在內(nèi)存中i+Page是否有空將最近最久未使用的頁(yè)面從 page中的頁(yè)面置換出去直接將 pi裝入內(nèi)存i+i<32輸出當(dāng)前頁(yè)面的 命中率是否是否是否OPT 算法流程圖：開始頁(yè)面存入數(shù)組 p初始化內(nèi)存塊 page結(jié)束Pi是否已在內(nèi)存中i+Page是否有空將距離最遠(yuǎn)的頁(yè)面從page中的頁(yè)面置換出去直接將 pi裝入內(nèi)存i+i<32輸出當(dāng)前頁(yè)面的 命中率是否是否是否Clock 算法流程圖：開始查詢指針前進(jìn)一步頁(yè)面訪問(wèn)位=0 置頁(yè)面訪問(wèn)位=0選擇該頁(yè)面淘汰結(jié)束是否五、實(shí)驗(yàn)數(shù)據(jù)及處理結(jié)果隨機(jī)產(chǎn)生指令流，并給出不同置換策略的命中率表。發(fā)現(xiàn) OPT 命中率較高。六、實(shí)驗(yàn)體會(huì)或?qū)Ω倪M(jìn)實(shí)驗(yàn)的建議存儲(chǔ)管理子系統(tǒng)是操作系統(tǒng)中最重要的組成部分之一，它的目的是方便用戶使用和提高存儲(chǔ)器利用率。通過(guò)這次實(shí)驗(yàn)更加清楚了四種頁(yè)面置換算法的實(shí)現(xiàn)過(guò)程，通過(guò)比較了解到了他們的異同之處。七、參考資料計(jì)算機(jī)操作系統(tǒng)西安電子科技大學(xué)出版社