實驗五存儲管理實驗報告VIP

1、word計算機(jī)與信息技術(shù)學(xué)院綜合性實驗報告專業(yè)：計算機(jī)科學(xué)與技術(shù) 年級/班級：2009級 20222012學(xué)年第一學(xué)期課程名稱計算機(jī)操作系統(tǒng)指導(dǎo)教師 齊娜學(xué)號姓名0908114006 司景霞實驗地點過街樓D區(qū)實驗時間周三晚工程名稱基于優(yōu)先數(shù)的進(jìn)程調(diào)度實驗類型綜合性一、 實驗?zāi)康耐ㄟ^請求頁式存儲管理中頁面置換算法模擬設(shè)計，了解虛擬存儲技術(shù)的特點，掌握請求頁式管理的頁面置換算法。二、 實驗儀器或設(shè)備微型計算機(jī)、Linux操作系統(tǒng)、dev C+三、 總體設(shè)計1、通過隨機(jī)數(shù)產(chǎn)生一個指令序列，共320條指令。其地址按下述原那么生成：50%的指令是順序執(zhí)行的；25%的指令是均勻分布在前地址局部；25%的指

2、令是均勻分布在后地址局部；具體的實施方法是：A.在0，319的指令地址之間隨機(jī)選取一起點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、指令序列變換成頁地址流，設(shè)：頁面大小為1K；用戶內(nèi)存容量為4頁到32頁；用戶虛存容量為32K。在用戶虛存中，按每頁存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：第0條第9條指令為第0頁對應(yīng)虛存地址為0，9；第10條第19條指令為第1頁對應(yīng)虛存地址

3、為10，19；第310條第319條指令為第31頁對應(yīng)虛存地址為310，319；按以上方式，用戶指令可組成32頁。3、計算并輸出下述算法在不同內(nèi)存容量下的命中率。A. FIFO先進(jìn)先出置換算法；B. LRU最近最久未使用置換算法；C. NUR最近未使用置換算法。命中率=1-頁面失效次數(shù)/頁地址流長度在本實驗中，頁地址流長度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時，該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。4、相關(guān)定義(1)數(shù)據(jù)結(jié)構(gòu)頁面類型typedef struct /*頁面結(jié)構(gòu)*/int pn,pfn,time;pl_type;其中pn為頁面號，pfn為頁幀號，time為訪問時間頁幀控制結(jié)構(gòu)struc

4、t pfc_struct /*頁幀控制結(jié)構(gòu)*/int pn,pfn;struct pfc_struct *next;typedef struct pfc_struct pfc_type;pfc_type pfctotal_vp,*freepf_head,*busypf_head,*busypf_tail;其中pfc_type pfctotal_vp定義用戶進(jìn)程虛頁控制結(jié)構(gòu)*freepf_head為空閑頁幀頭的指針*busypf_head為忙頁幀頭的指針*busypf_tail忙頁幀尾的指針(2)函數(shù)定義void initialize(int):初始化函數(shù)void FIFO(int):計算使用F

5、IFO算法時的命中率void LRU(int):計算使用LRU算法時的命中率void NRU(int):計算使用NRU算法時的命中率 (3)變量定義int atotal_instruction:指令流數(shù)組int diseffect:頁面失效次數(shù)int pagetotal_instruction:每條指令所屬頁面號int offsettotal_instruction:每頁裝入10條指令后取模運算得出的頁內(nèi)偏移地址int total_pf:用戶進(jìn)程的內(nèi)存頁面數(shù)四、 實驗步驟按照流程圖編寫代碼、并上機(jī)調(diào)試運行 程序代碼：#include <stdlib.h>#include <s

6、tio.h>#define TRUE 1#define FALSE 0#define INVALID -1#define total_instruction 320 /*指令流長*/#define total_vp 32 /*虛頁長*/typedef struct /*頁面結(jié)構(gòu)*/int pn,pfn,time;pl_type;pl_type pltotal_vp; /*頁幀結(jié)構(gòu)數(shù)組*/struct pfc_struct /*頁幀控制結(jié)構(gòu)*/int pn,pfn;struct pfc_struct *next;typedef struct pfc_struct pfc_type;pfc_

7、type pfctotal_vp,*freepf_head,*busypf_head,*busypf_tail;int diseffect,atotal_instruction;int pagetotal_instruction,offsettotal_instruction;void initialize(int);void FIFO(int);void LRU(int);void NRU(int);int main( )int s,i; /*由于每次運行時進(jìn)程號不同，故可用來作為初始化隨機(jī)數(shù)隊列的“種子*/srand(10*getpid();s=(float)319*rand( )/RAN

8、D_MAX+1;for(i=0;i<total_instruction;i+=4) /*產(chǎn)生指令隊列*/ ai=s; /*任選一指令訪問點m*/ ai+1=ai+1; /*順序執(zhí)行一條指令*/ ai+2=(float)ai*rand( )/RAND_MAX; /*執(zhí)行前地址指令m' */ ai+3=ai+2+1; /*順序執(zhí)行一條指令*/ s=(float)(318-ai+2)*rand( )/RAND_MAX+ai+2+2; for (i=0;i<total_instruction;i+) /*將指令序列變換成頁地址流*/ pagei=ai/10; offseti=ai%

9、10;for(i=4;i<=32;i+) /*用戶內(nèi)存工作區(qū)從4個頁幀到32個頁幀*/ printf("%2d page frames ",i);void FIFO(int);void LRU(int);void NRU(int); printf("n"); void initialize(int total_pf) /*初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)*/int i;diseffect=0;for(i=0;i<total_vp;i+) pli.pn=i; pli.pfn=INVALID; pli.time=-1; for(i=0;i<total_p

10、f-1;i+) pfci.next=&pfci+1; pfci.pfn=i; /*建立pfci-1和pfci之間的鏈接*/pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0; /*空頁面隊列的頭指針為pfc0*/void FIFO(int total_pf) /*先進(jìn)先出算法*/int total_pf; /* 用戶進(jìn)程的內(nèi)存頁面數(shù) */ int i,j;pfc_type *p, *t;initialize(total_pf); /* 初始化相關(guān)頁面控制用數(shù)據(jù)結(jié)構(gòu)*/busypf_head

11、=busypf_tail=NULL: /* 忙頁面隊列頭,隊列尾鏈接 */for(i=0;i=total_instruction;i+) if(p1pagei.pfn= =INVALID /* 頁面失效 */ disaffect+=1； /* 失效次數(shù) */ iffreep_headf= =NULL /* 無空閑頁面 */ p=busypf_head->next; p1busypf_head->pn.pfn=INVALID; freepf_head=busypf_head; /*釋放忙頁面隊列中的第一個頁面*/ freepf_head->next=NULL: busypf_h

12、ead=p; p=freepf_head->next; /* 按FIFO方式調(diào)新頁面入內(nèi)存頁面 */ freepf_head->next=NULL: freepf_head->pn=pagei; p1pagei.pfn=freepf_head->pfn; if(busypf_tail= =NULL) busypf_head=busypf_tail=freepf_head; else busypf_tail->next=freepf_head; busypf_tail=freepf_head; freepf_head=p; printf(“FIFO:%6.4f,1-

13、(float)disaffect/320);void LRU (int total_pf) /*最近最久未使用算法*/int total_pf; int min,minj,i,j,present_time; initialize(total_pf); present_time=0; for(i=0;i<total_instruction;i+) if(p1pagei.pfn= =INVALID) /* 頁面失效 */ disaffect+; if(freepf_head= =NULL) /* 無空閑頁面 */ min=32767; for(j=0;j<total_vp;j+) if

14、(min>p1j.time&&p1j.pfn !=INVALID) min=p1j.time;minj=j; freepf_head=&pfcp1minj.pfn; p1minj.pfn=INVALID; p1min.time=-1; freepf_head->next=NULL; p1pagei.pfn=freepf_head->pfn; p1pagei.time=present_time; freepf_head=freepf_head->next; else p1pagei.time=present_time; present_time+;

15、 printf(“LRU:%6.4f,1-(flaot)disaffect/320);void NRU(int total_pf) /*最近未使用置換算法*/int total_pf; int i,j,dp,cont_flag,old_dp; pfc_type *t; initialize(total_pf); dp=0; for(i=0;i<total_instruction;i+) if(p1pagei.pfn= =INVALID) /* 頁面失效 */ diseffect+; if(freepf_head= =NULL) /* 無空閑頁面 */ cont_flag=TRUE; ol

16、d_dp=dp; while(cont_flag) if(p1dp.counter= =0 && p1dp.pfn!=INVALID) cont_flag=FLASE; else dp+; if(dp= =total_vp) dp=0; if(dp= =old_dp) for(j=0;j<total_vp;j+) p1j.counter=0; freepf_head=&pfcp1dp.pfn; p1dp.pfn=INVALID; freepf_head->next=NULL: p1pagei.pfn=freepf_head->pfn; freepf_h

17、ead=freepf_head->next; else p1pagei.counter=1; if(i%clear_period= =0) for(j=0;j<total_vp;j+) p1j.counter=0; printf(“NUR:%6.4f,1-(float)disaffect/320);void OPT(total_pf)int total_pf; int i,j,max,maxpage,d,disttotal_vp; pfc_type *t; initialize(total_pf); for(i=0;i<total_instruction;i+) if(p1p

18、agei.pfn= =INVALID) diseffect+; if(freepf_head= =NULL) for(j=0;j<total_vp;j+) if(p1j.pfn !=INVALID) distj=32767; else distj=0; d=1; for(j=i+1;j<total_instruction;j+) if(p1pagej.pfn!=INVALID) distpagej=d; d+; max=-1; for(j=0;j<total_vp;j+) if(max<distj) max=distj; maxpage=j; freepf_head=&

19、amp;pfcp1maxpage.pfn; freepf_head->next=NULL; p1maxpage.pfn=INVALID; p1pagei.pfn=freepf_head->pfn; freepf_head=freepf_head->next; printf(“OPT:%6.4f,1-(float)disaffect/320);顯示結(jié)果：4 page frames FIFO:0.4969 LRU:0.5000 NUR:0.50005 page frames FIFO:0.5188 LRU:0.5125 NUR:0.50626 page frames FIFO:0

20、.5281 LRU:0.5188 NUR:0.53447 page frames FIFO:0.5406 LRU:0.5500 NUR:0.55628 page frames FIFO:0.5500 LRU:0.5719 NUR:0.55319 page frames FIFO:0.5625 LRU:0.5812 NUR:0.578110 page frames FIFO:0.5844 LRU:0.5969 NUR:0.596911 page frames FIFO:0.5938 LRU:0.6094 NUR:0.625012 page frames FIFO:0.6156 LRU:0.628

21、1 NUR:0.659413 page frames FIFO:0.6375 LRU:0.6344 NUR:0.650014 page frames FIFO:0.6844 LRU:0.6625 NUR:0.650015 page frames FIFO:0.6844 LRU:0.6812 NUR:0.687516 page frames FIFO:0.7062 LRU:0.7062 NUR:0.709417 page frames FIFO:0.7094 LRU:0.7125 NUR:0.725018 page frames FIFO:0.7188 LRU:0.7281 NUR:0.734419 page frames FIFO:0.7281 LRU:0.7531 NUR:0.753120 page frames FIFO:0.7281 LRU:0.7656 NUR:0.759421 page frames FIFO:0.7812 LRU:0.7781 NUR:0.790622 page frames FIFO:0.7875 LRU:0.7937 NUR:0.812523 page frames FIFO:0.7960 LRU:0.8094 NUR:0.81872