存儲管理實驗報告

1、軟件學(xué)院計算機課程實驗報課程名稱計算機操作系統(tǒng)實驗學(xué)期 2011 年至 2012 年 第 2 學(xué)期學(xué)生所在院（系）軟件學(xué)院年級 11 軟件 專業(yè)班級軟工（ 1）學(xué)生姓名 朱水云學(xué)號 1115114034陳自剛指導(dǎo)教師 實驗最終成績軟件學(xué)院實驗室制2012 年 4 月第 1 頁 共 11 頁實驗報告 （ 三 ）實驗名稱：存儲管理實驗時間：2012 年 4 月 25 號實驗性質(zhì)應(yīng)用性設(shè)計性綜合性一、實驗?zāi)康募耙?: 存儲管理的主要功能之一是合理地分配空間。請求頁式管理是一種常用的虛擬存儲管理技術(shù)。本實驗的目 的是通過請求頁式存儲管理中頁面置換算法模擬設(shè)計，了解虛擬存儲技術(shù)的技術(shù)特點，掌握請求頁式

2、存儲 管理的頁面置換算法。二、實驗內(nèi)容與分析設(shè)計 :（1）通過隨機數(shù)產(chǎn)生一個指令序列，共320 條指令。指令的地址按下述原則生成： 50%的指令是順序執(zhí)行的； 50%的指令是均勻分布在前地址部分； 50%的指令是均勻分布在后地址部分。具體的實施方法是： 在 0 ， 319 的指令之間隨即選取一起點 m; 順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令； 在前地址 0 ， m+1中隨機選取一條指令并執(zhí)行，該指令的地址為m； 順序執(zhí)行一條指令，其地址為m+ 1； 在后地址 m+ 2 ， 319 中隨機選取一條指令并執(zhí)行； 重復(fù)上述步驟 - ，直到執(zhí)行 320 次指令。（2）將指令序列變換為頁地址流設(shè)：

3、頁面大小為 1k ；用戶內(nèi)存容量為 4 頁到 32 頁；用戶虛存容量為 32k。在用戶虛存中，按每 k存放 10條指令排在虛存地址，即 320 條指令在虛存中的存放方式為： 第 0 條-第 9 條指令為第 0 頁（對應(yīng)虛存地址為 0 ，9）；第 10 條- 第 19 條指令為第一頁（對應(yīng)虛存地址為 10 ，19 ）；（3）計算并輸出下述各種算法在不同內(nèi)存容量下的命中率。 先進先出的算法（ FIFO）； 最近最少使用算法（ LRR）； 最佳淘汰算法（ OPT）先淘汰最不常用的頁地址； 最少訪問頁面算法（ LFR）； 最近最不經(jīng)常使用算法（ NUR）。 其中和為選擇內(nèi)容。命中率 =1-頁面失效次數(shù)

4、 / 頁地址流長度在本實驗中，頁地址流長度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時，該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。分析 ：隨機數(shù)產(chǎn)生辦法， Linux 或 UNIX系統(tǒng)提供函數(shù) strand（） 和 rand（）, 分別進行初始化和產(chǎn)生隨機數(shù)。 例如：srand （）;語句可初始化一個隨機數(shù)；a0=10*rand（）/65535*319+1;第 2 頁 共 11 頁a1=10*rand()/65535*a0;語句可用來產(chǎn)生 a0 與 a1 中的隨機數(shù)。啟動計算機并運行 linux 系統(tǒng) 打開中斷進行程序書寫 根據(jù) Linux 系統(tǒng)的 gcc自帶編譯器進行運行編譯 分析運行出現(xiàn)的問題 觀察運

5、行結(jié)果，并思考 退出中斷并寫出實驗報告三、實驗步驟與調(diào)試過程1， 2， 3， 4， 5， 6， 調(diào)試過程 : 根據(jù)編譯提示的錯誤進行修改四、實驗結(jié)果： 結(jié)果一：4 page framesFIFO:0.2562LRU:0.2531OPT:0.3031LFU:0.2812NUR:0.28125 page framesFIFO:0.2969LRU:0.2906OPT:0.3500LFU:0.3219NUR:0.30946 page framesFIFO:0.3375LRU:0.3281OPT:0.3844LFU:0.3375NUR:0.3344 7 page framesFIFO:0.3563LRU

6、:0.3563OPT:0.4031LFU:0.3563NUR:0.3500 8 page framesFIFO:0.3937LRU:0.3750OPT:0.4531LFU:0.3937NUR:0.3719 9 page framesFIFO:0.4219LRU:0.4094OPT:0.4844LFU:0.4156NUR:0.4062 10 page framesFIFO:0.4375LRU:0.4313OPT:0.5062LFU:0.4313NUR:0.4250 11 page framesFIFO:0.4813LRU:0.4625OPT:0.5531LFU:0.4500NUR:0.4656

7、12 page framesFIFO:0.5406LRU:0.4875OPT:0.5687LFU:0.4938NUR:0.4875 13 page framesFIFO:0.5500LRU:0.5188OPT:0.5969LFU:0.5062NUR:0.5437 14 page framesFIFO:0.5594LRU:0.5531OPT:0.6344LFU:0.5281NUR:0.5469 15 page framesFIFO:0.5687LRU:0.5844OPT:0.6687LFU:0.5469NUR:0.5813 16 page framesFIFO:0.5781LRU:0.5938O

8、PT:0.6813LFU:0.5719NUR:0.5969 17 page framesFIFO:0.5906LRU:0.6156OPT:0.6969LFU:0.6156NUR:0.6156 18 page framesFIFO:0.6156LRU:0.6312OPT:0.7156LFU:0.6344NUR:0.6531 19 page framesFIFO:0.6687LRU:0.6656OPT:0.7344LFU:0.6531NUR:0.6719 20 page framesFIFO:0.6875LRU:0.6969OPT:0.7500LFU:0.6719NUR:0.6906 21 pag

9、e framesFIFO:0.6906LRU:0.7094OPT:0.7688LFU:0.6969NUR:0.7188 22 page framesFIFO:0.7125LRU:0.7219OPT:0.7969LFU:0.7156NUR:0.7344 23 page framesFIFO:0.7156LRU:0.7406OPT:0.8125LFU:0.7250NUR:0.7812 24 page framesFIFO:0.7281LRU:0.7625OPT:0.8187LFU:0.7406NUR:0.7719 25 page framesFIFO:0.7469LRU:0.7750OPT:0.8

10、344LFU:0.7594NUR:0.8000 26 page framesFIFO:0.8125LRU:0.8000OPT:0.8500LFU:0.7812NUR:0.8063 27 page framesFIFO:0.8313LRU:0.8187OPT:0.8594LFU:0.8031NUR:0.8281 28 page framesFIFO:0.8438LRU:0.8375OPT:0.8688LFU:0.8344NUR:0.8469 29 page framesFIFO:0.8688LRU:0.8531OPT:0.8750LFU:0.8562NUR:0.8562 30 page fram

11、esFIFO:0.8781LRU:0.8719OPT:0.8781LFU:0.8750NUR:0.8688 31 page framesFIFO:0.8938LRU:0.8750OPT:0.8844LFU:0.8844NUR:0.8906 32 page framesFIFO:0.9000LRU:0.9000OPT:0.9000LFU:0.9000NUR:0.9000 結(jié)果二： 4 page framesFIFO:0.2594LRU:0.2562OPT:0.2687LFU:0.2437NUR:0.26255 page framesFIFO:0.3000LRU:0.3000OPT:0.3000L

12、FU:0.2969NUR:0.2875第 3 頁 共 11 頁6 page framesFIFO:0.3375LRU:0.3281OPT:0.3281LFU:0.3094NUR:0.32817 page framesFIFO:0.3563LRU:0.3563OPT:0.3688LFU:0.3312NUR:0.34698 page framesFIFO:0.4031LRU:0.4094OPT:0.3875LFU:0.3406NUR:0.37819 page framesFIFO:0.4156LRU:0.4281OPT:0.4156LFU:0.3656NUR:0.412510 page frame

13、sFIFO:0.4281LRU:0.4469OPT:0.4313LFU:0.3750NUR:0.440611 page framesFIFO:0.4531LRU:0.4688OPT:0.4594LFU:0.4281NUR:0.465612 page framesFIFO:0.4656LRU:0.4813OPT:0.4906LFU:0.4375NUR:0.493813 page framesFIFO:0.4750LRU:0.5000OPT:0.5219LFU:0.4625NUR:0.531214 page framesFIFO:0.4906LRU:0.5125OPT:0.5375LFU:0.49

14、38NUR:0.550015 page framesFIFO:0.5312LRU:0.5250OPT:0.5625LFU:0.5281NUR:0.556316 page framesFIFO:0.5406LRU:0.5625OPT:0.5813LFU:0.5531NUR:0.584417 page framesFIFO:0.5906LRU:0.5813OPT:0.6188LFU:0.5750NUR:0.603118 page framesFIFO:0.6000LRU:0.5906OPT:0.6344LFU:0.5906NUR:0.625019 page framesFIFO:0.6312LRU

15、:0.6156OPT:0.6438LFU:0.6219NUR:0.643820 page framesFIFO:0.6406LRU:0.6344OPT:0.6625LFU:0.6438NUR:0.675021 page framesFIFO:0.6969LRU:0.6594OPT:0.6875LFU:0.6656NUR:0.693722 page framesFIFO:0.7000LRU:0.6781OPT:0.7125LFU:0.6813NUR:0.684423 page framesFIFO:0.7156LRU:0.6906OPT:0.7312LFU:0.7188NUR:0.696924

16、page framesFIFO:0.7438LRU:0.7219OPT:0.7531LFU:0.7438NUR:0.746925 page framesFIFO:0.7594LRU:0.7562OPT:0.7656LFU:0.7656NUR:0.771926 page framesFIFO:0.7750LRU:0.7812OPT:0.7937LFU:0.7781NUR:0.778127 page framesFIFO:0.8125LRU:0.7969OPT:0.8094LFU:0.8125NUR:0.796928 page framesFIFO:0.8344LRU:0.8313OPT:0.82

17、81LFU:0.8313NUR:0.840629 page framesFIFO:0.8406LRU:0.8594OPT:0.8531LFU:0.8375NUR:0.840630 page framesFIFO:0.8625LRU:0.8781OPT:0.8750LFU:0.8562NUR:0.859431 page framesFIFO:0.8812LRU:0.8812OPT:0.8906LFU:0.8781NUR:0.865632 page framesFIFO:0.9000LRU:0.9000OPT:0.9000LFU:0.9000NUR:0.9000五、疑難與小結(jié)：本實驗的程序設(shè)計基本

18、上按照實驗內(nèi)容進行。即首先用 srand() 和 rand() 函數(shù)定義和產(chǎn)生指令序列，然后 將指令序列變換成相應(yīng)的頁地址流，并針對不同的算法計算出相應(yīng)的命中率。從實驗結(jié)果可知，在內(nèi)存頁面數(shù)較少( 45 頁)時，五種算法的命中率差別不大，都是30%左右。在內(nèi)存頁面為 718 個頁面之間時， 5 種算法的訪內(nèi)命中率大致在 35%60%之間變化。但是， FIFO算法與 OPT算法 之間的差別一般在 610 個百分點左右。在內(nèi)存頁面為 2532 個頁面時，由于用戶進程的所有指令基本上 都已裝入內(nèi)存，使命中率增加，從而算法之間的差別不大。 FIFO 的命中率比 OPT的還高。六、主要算法和程序清單#d

19、efine TRUE 1#define FALSE 0#define INVALID -1#define NULL 0 #definetotal_instruction 320 /*#define#define typedef struct total_vp 32clear_period/*50 /*/*指令流長 */ 虛頁長 */ 清 0 周期 */ 頁面結(jié)構(gòu) */第 4 頁 共 11 頁頁號 logic number 頁面框架號 physical frame number 計數(shù)器時間int pn; /int pfn; /int counter; / int time; /pl_type;

20、pl_type pltotal_vp;typedef struct pfc_structint pn; int pfn;struct pfc_struct *next;pfc_type;pfc_type pfctotal_vp, *freepf_head, *busypf_head, *busypf_tail; int diseffect, atotal_instruction; /* a int pagetotal_instruction, offsettotal_instruction;/* int int/*/*頁面線性結(jié)構(gòu) - 指令序列需要使用地址 */ 頁面控制結(jié)構(gòu)，調(diào)度算法的控制結(jié)

21、構(gòu) */為指令序列 */地址信息 */int int intinitialize(int);FIFO(int);LRU(int);LFU(int);NUR(int); /not use recentlyOPT(int);intint main( )int s,i,j;srand(10*getpid();機數(shù)隊列的“種子” */*由于每次運行時進程號不同，故可用來作為初始化隨s=(float)319*rand( )/32767/32767/2+1; /* for(i=0;itotal_instruction;i+=4) /* 正態(tài)分布 */產(chǎn)生指令隊列 */if(s319)printf(When

22、 i=%d,Error,s=%dn,i,s);exit(0); ai=s; ai+1=ai+1; /* ai+2=(float)ai*rand( )/32767/32767/2; /* ai+3=ai+2+1; /*/*任選一指令訪問點 m*/ 順序執(zhí)行一條指令 */ 執(zhí)行前地址指令 m*/ 順序執(zhí)行一條指令 */s=(float)(318-ai+2)*rand( )/32767/32767/2+ai+2+2; if(ai+2318)|(s319)printf(a%d+2,a number which is :%d and s=%dn,i,ai+2,s);for (i=0;itotal_ins

23、truction;i+) /*將指令序列變換成頁地址流 */第 5 頁 共 11 頁pagei=ai/10;offseti=ai%10;用戶內(nèi)存工作區(qū)從 4 個頁面到 32 個頁面 */for(i=4;i=32;i+) /*printf(-%2d page frames-n,i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);return 0;表示內(nèi)存的塊數(shù) */* 初始化相關(guān)數(shù)據(jù)結(jié)構(gòu) total_pf int initialize(int total_pf) int i;diseffect=0; for(i=0;itotal_vp;i+)pli.pfn=INVALI

24、D;pli.counter=0;pli.time=-1;/*/*/*置頁面控制結(jié)構(gòu)中的頁號，頁面為空 */ 頁面控制結(jié)構(gòu)中的訪問次數(shù)為 0*/ 訪問的時間 */for(i=0;itotal_pf-1;i+)pfci.next=&pfci+1; pfci.pfn=i;pfctotal_pf-1.next=NULL; pfctotal_pf-1.pfn=total_pf-1; freepf_head=&pfc0;return 0;/* 建立 pfci-1 和 pfci 之間的鏈接 */*空頁面隊列的頭指針為 pfc0*/int FIFO(int total_pf)int i,j; pfc_type

25、 *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-pn=pagei; plpagei.pfn=freepf_head-pfn; freepf_head-next=NULL; /* 使 busy 的尾為 null*/ if(busypf

26、_tail=NULL) busypf_tail=busypf_head=freepf_head; else/*釋放忙頁面隊列的第一個頁面 */ 表明還是缺頁 */busypf_tail-next=freepf_head;busypf_tail=freepf_head; freepf_head=p;printf(FIFO:%6.4fn,1-(float)diseffect/320); return 0;int LRU (int total_pf)int min,minj,i,j,present_time; /*minj initialize(total_pf);present_time=0; f

27、or(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID)diseffect+;if(freepf_head=NULL)min=32767;for(j=0;jplj.time&plj.pfn!=INVALID)第 7 頁 共 11 頁min=plj.time;minj=j;freepf_head=&pfcplminj.pfn; / plminj.pfn=INVALID;plminj.time=0; freepf_head-next=NULL;騰出一個單元 else plpagei.pfn=freepf_head-pfn; / plpagei.tim

28、e=present_time; freepf_head=freepf_head-next; /有空閑頁面 , 改為有效減少一個 free 頁面plpagei.time=present_time; / present_time+;命中則增加該單元的訪問次數(shù) printf(LRU:%6.4fn,1-(float)diseffect/320); return 0;int NUR(int total_pf ) /* int i,j,dp,cont_flag,old_dp; pfc_type *t; initialize(total_pf);dp=0;最近未使用算法Not Used recently c

29、ount表示 */for(i=0;itotal_instruction;i+)if (plpagei.pfn=INVALID)diseffect+;if(freepf_head=NULL) cont_flag=TRUE; old_dp=dp;/*/*頁面失效 */無空閑頁面 */while(cont_flag)if(pldp.counter=0&pldp.pfn!=INVALID)cont flag=FALSE;第 8 頁 共 11 頁elsedp+;if(dp=total_vp)dp=0;if(dp=old_dp)for(j=0;jnext=NULL; plpagei.pfn=freepf_

30、head-pfn; freepf_head-pn=pagei; freepf_head=freepf_head-next;elseplpagei.counter=1;if(i%clear_period=0)for(j=0;jtotal_vp;j+) plj.counter=0; printf(NUR:%6.4fn,1-(float)diseffect/320); return 0;int OPT(int total_pf)int i,j, max,maxpage,d,disttotal_vp; pfc_type *t;initialize(total_pf);for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID) /* diseffect+; if(freepf_head=NULL) for(j=0;jt