操作系統(tǒng)實(shí)驗(yàn)報(bào)告(共12頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)名稱：存儲(chǔ)管理學(xué)號(hào) 班級(jí) 姓名 1 實(shí)驗(yàn)?zāi)康模捍鎯?chǔ)管理的主要功能之一是合理地分配空間。請(qǐng)求頁式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。 本實(shí)驗(yàn)的目的是通過請(qǐng)求頁式存儲(chǔ)管理中頁面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的技術(shù)特點(diǎn)，掌握請(qǐng)求頁式存儲(chǔ)管理的頁面置換算法。2 實(shí)驗(yàn)預(yù)備內(nèi)容：（1）通過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令。指令的地址按下述原則生成： 50%的指令是順序執(zhí)行的； 50%的指令是均勻分布在前地址部分； 50%的指令是均勻分布在后地址部分。 具體的實(shí)施方法是： 在 0，319 的指令之間隨即選取一起點(diǎn)m; 順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令； 在前地

2、址0，m+1中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為m； 順序執(zhí)行一條指令，其地址為 m+ 1； 在后地址m+ 2，319中隨機(jī)選取一條指令并執(zhí)行； 重復(fù)上述步驟-，直到執(zhí)行320次指令。 （2）將指令序列變換為頁地址流 設(shè)：頁面大小為1k； 用戶內(nèi)存容量為4頁到32頁； 用戶虛存容量為32k。 在用戶虛存中，按每k存放10條指令排在虛存地址，即320條指令在虛存中的存放方式為： 第0條-第9條指令為第0頁（對(duì)應(yīng)虛存地址為0，9）； 第10條-第19條指令為第一頁（對(duì)應(yīng)虛存地址為10，19）； 第310條第319條指令為第31頁（對(duì)應(yīng)虛地址為310，319）。 按以上方式，用戶指令可組成32頁

3、。 （3）計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。 先進(jìn)先出的算法（FIFO）； 最近最少使用算法（LRR)； 最佳淘汰算法（OPT）先淘汰最不常用的頁地址； 最少訪問頁面算法（LFR）； 最近最不經(jīng)常使用算法（NUR）。 其中和為選擇內(nèi)容。命中率=1-頁面失效次數(shù)/頁地址流長(zhǎng)度 在本實(shí)驗(yàn)中，頁地址流長(zhǎng)度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時(shí)，該指令所對(duì)應(yīng)的頁不在內(nèi)存的次數(shù)。3、隨機(jī)數(shù)產(chǎn)生辦法，Linux或UNIX系統(tǒng)提供函數(shù)strand()和rand(),分別進(jìn)行初始化和產(chǎn)生隨機(jī)數(shù)。例如： srand (); 語句可初始化一個(gè)隨機(jī)數(shù)； a0=10*rand()/65535*319

4、+1; a1=10*rand()/65535*a0;語句可用來產(chǎn)生a0與a1中的隨機(jī)數(shù)。3 實(shí)驗(yàn)內(nèi)容：<任務(wù)>設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū),并使用下列算法計(jì)算訪問命中率.（1） 進(jìn)先出的算法（FIFO）（2） 最近最少使用的算法（LRU）（3） 最佳淘汰算法(OPT)（4） 最少訪問頁面算法(LFU)（5） 最近最不經(jīng)常使用算法(NUR)命中率=(1-頁面失效次數(shù))/頁地址流長(zhǎng)度4 實(shí)驗(yàn)步驟:本實(shí)驗(yàn)的程序設(shè)計(jì)基本上按照實(shí)驗(yàn)內(nèi)容進(jìn)行。即首先用srand()和rand()函數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對(duì)不同的算法計(jì)算出相應(yīng)的命中率。相關(guān)定義如下：1

5、數(shù)據(jù)結(jié)構(gòu)(1)頁面類型 typedef struct int pn,pfn,counter,time; pl-type;其中pn 為頁號(hào),pfn為面號(hào), counter為一個(gè)周期內(nèi)訪問該頁面的次數(shù), time為訪問時(shí)間.(2) 頁面控制結(jié)構(gòu)pfc-struct int pn,pfn; struct pfc_struct *next; typedef struct pfc_struct pfc_type;pfc_type pfc_structtotal_vp,*freepf_head,*busypf_head;pfc_type *busypf_tail; 其中pfctotal_vp定義用戶進(jìn)程虛

6、頁控制結(jié)構(gòu),*freepf_head為空頁面頭的指針,*busypf_head為忙頁面頭的指針,*busypf_tail為忙頁面尾的指針.2函數(shù)定義（1）Void initialize( ):初始化函數(shù),給每個(gè)相關(guān)的頁面賦值.（2）Void FIFO( ):計(jì)算使用FIFO算法時(shí)的命中率.（3）Void LRU( ):計(jì)算使用LRU算法時(shí)的命中率.（4）Void OPT( ):計(jì)算使用OPT算法時(shí)的命中率.（5）Void LFU( ):計(jì)算使用LFU算法時(shí)的命中率.（6）Void NUR( ):計(jì)算使用NUR算法時(shí)的命中率.3.變量定義(1)int atotal_instruction: 指令

7、流數(shù)據(jù)組.(2)int pagetotal_instruction: 每條指令所屬的頁號(hào).(3)int offsettotal_instruction: 每頁裝入10條指令后取模運(yùn)算頁號(hào)偏移值.(4)int total_pf: 用戶進(jìn)程的內(nèi)存頁面數(shù).(5)int disaffect: 頁面失效次數(shù).4.程序參考源碼及結(jié)果<程序>#define TRUE 1#define FALSE 0#define INVALID -1#define NULL 0#define total_instruction 320 /*指令流長(zhǎng)*/#define total_vp 32 /*虛頁長(zhǎng)*/#de

8、fine clear_period 50 /*清0周期*/typedef struct /*頁面結(jié)構(gòu)*/int pn; /頁號(hào) logic numberint pfn; /頁面框架號(hào) physical frame numberint counter; /計(jì)數(shù)器int time; /時(shí)間pl_type;pl_type pltotal_vp; /*頁面線性結(jié)構(gòu)-指令序列需要使用地址*/typedef struct pfc_struct /*頁面控制結(jié)構(gòu)，調(diào)度算法的控制結(jié)構(gòu)*/ int pn;int pfn;struct pfc_struct *next;pfc_type;pfc_type pfct

9、otal_vp, *freepf_head, *busypf_head, *busypf_tail;int diseffect, atotal_instruction; /* a為指令序列*/int pagetotal_instruction, offsettotal_instruction;/*地址信息*/int initialize(int);int FIFO(int);int LRU(int);int LFU(int);int NUR(int); /not use recentlyint OPT(int);int main( )int s,i,j;srand(10*getpid(); /

10、*由于每次運(yùn)行時(shí)進(jìn)程號(hào)不同，故可用來作為初始化隨機(jī)數(shù)隊(duì)列的“種子”*/s=(float)319*rand( )/32767/32767/2+1; /*正態(tài)分布*/for(i=0;i<total_instruction;i+=4) /*產(chǎn)生指令隊(duì)列*/if(s<0|s>319)printf("When i=%d,Error,s=%dn",i,s);exit(0); ai=s; /*任選一指令訪問點(diǎn)m*/ai+1=ai+1; /*順序執(zhí)行一條指令*/ai+2=(float)ai*rand( )/32767/32767/2; /*執(zhí)行前地址指令m*/ai+3=a

11、i+2+1; /*順序執(zhí)行一條指令*/s=(float)(318-ai+2)*rand( )/32767/32767/2+ai+2+2;if(ai+2>318)|(s>319)printf("a%d+2,a number which is :%d and s=%dn",i,ai+2,s);for (i=0;i<total_instruction;i+) /*將指令序列變換成頁地址流*/pagei=ai/10;offseti=ai%10;for(i=4;i<=32;i+) /*用戶內(nèi)存工作區(qū)從4個(gè)頁面到32個(gè)頁面*/printf("-%2d

12、page frames-n",i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);return 0;/*初始化相關(guān)數(shù)據(jù)結(jié)構(gòu) total_pf表示內(nèi)存的塊數(shù) */int initialize(int total_pf) int i;diseffect=0;for(i=0;i<total_vp;i+)pli.pfn=INVALID; /*置頁面控制結(jié)構(gòu)中的頁號(hào)，頁面為空*/pli.counter=0; /*頁面控制結(jié)構(gòu)中的訪問次數(shù)為0*/pli.time=-1; /*訪問的時(shí)間*/for(i=0;i<total_pf-1;i+)/*建立pfci-1和

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

14、忙頁面隊(duì)列頭，隊(duì)列尾鏈接*/for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID) /*頁面失效*/diseffect+=1; /*失效次數(shù)*/if(freepf_head=NULL) /*無空閑頁面*/p=busypf_head->next; plbusypf_head->pn.pfn=INVALID;freepf_head=busypf_head; /*釋放忙頁面隊(duì)列的第一個(gè)頁面*/freepf_head->next=NULL; /*表明還是缺頁*/busypf_head=p;p=freepf_head->

15、next; freepf_head->pn=pagei;plpagei.pfn=freepf_head->pfn;freepf_head->next=NULL; /*使busy的尾為null*/if(busypf_tail=NULL)busypf_tail=busypf_head=freepf_head;elsebusypf_tail->next=freepf_head;busypf_tail=freepf_head;freepf_head=p;printf("FIFO:%6.4fn",1-(float)diseffect/320);return 0

16、;int LRU (int total_pf) /*最近最久未使用算法least recently used*/int min,minj,i,j,present_time; /*minj為最小值下標(biāo)*/initialize(total_pf);present_time=0;for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID) /*頁面失效*/diseffect+;if(freepf_head=NULL) /*無空閑頁面*/min=32767;/*設(shè)置最大值*/for(j=0;j<total_vp;j+) /*找出time的最小

17、值*/ if(min>plj.time&&plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head=&pfcplminj.pfn; /騰出一個(gè)單元plminj.pfn=INVALID;plminj.time=0;freepf_head->next=NULL;plpagei.pfn=freepf_head->pfn; /有空閑頁面,改為有效plpagei.time=present_time;freepf_head=freepf_head->next; /減少一個(gè)free 頁面elseplpagei.time=

18、present_time; /命中則增加該單元的訪問次數(shù)present_time+;printf("LRU:%6.4fn",1-(float)diseffect/320);return 0;int NUR(int total_pf ) /*最近未使用算法Not Used recently count表示*/ int i,j,dp,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;i<total_instruction;i+) if (plpagei.pfn=INVALID) /*頁面失效*/d

19、iseffect+;if(freepf_head=NULL) /*無空閑頁面*/ cont_flag=TRUE;old_dp=dp;while(cont_flag) if(pldp.counter=0&&pldp.pfn!=INVALID)cont_flag=FALSE;elsedp+;if(dp=total_vp)dp=0;if(dp=old_dp)for(j=0;j<total_vp;j+) plj.counter=0;freepf_head=&pfcpldp.pfn;pldp.pfn=INVALID;freepf_head->next=NULL;plp

20、agei.pfn=freepf_head->pfn;freepf_head->pn=pagei;freepf_head=freepf_head->next;elseplpagei.counter=1;if(i%clear_period=0)for(j=0;j<total_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;p

21、fc_type *t;initialize(total_pf);for(i=0;i<total_instruction;i+) if(plpagei.pfn=INVALID) /*頁面失效*/diseffect+;if(freepf_head=NULL) /*無空閑頁面*/for(j=0;j<total_vp;j+)if(plj.pfn!=INVALID)distj=32767;elsedistj=0; for(j=0;j<total_vp;j+) if(plj.pfn!=INVALID)&&(distj=32767)distj=j;max=0;for(j=0

22、;j<total_vp;j+)if(max<distj)max=distj;maxpage=j;freepf_head=&pfcplmaxpage.pfn;freepf_head->next=NULL;plmaxpage.pfn=INVALID;plpagei.pfn=freepf_head->pfn;freepf_head=freepf_head->next;printf("OPT:%6.4fn",1-(float)diseffect/320);return 0;/*該算法時(shí)根據(jù)已知的預(yù)測(cè)未知的，least frequency Use

23、d是最不經(jīng)常使用置換法*/int LFU(int total_pf) int i,j,min,minpage;pfc_type *t;initialize(total_pf);for(i=0;i<total_instruction;i+) if(plpagei.pfn=INVALID) /*頁面失效*/ diseffect+;if(freepf_head=NULL) /*無空閑頁面*/ min=32767;/*獲取counter的使用用頻率最小的內(nèi)存*/for(j=0;j<total_vp;j+)if(min>plj.counter&&plj.pfn!=INV

24、ALID)min=plj.counter;minpage=j;freepf_head=&pfcplminpage.pfn;plminpage.pfn=INVALID;plminpage.counter=0;freepf_head->next=NULL;plpagei.pfn=freepf_head->pfn; /有空閑頁面,改為有效plpagei.counter+;freepf_head=freepf_head->next; /減少一個(gè)free 頁面elseplpagei.counter;plpagei.counter=plpagei.counter+1;printf

25、("LFU:%6.4fn",1-(float)diseffect/320);return 0;<結(jié)果一：4 page framesFIFO:0.2562LRU:0.2531OPT:0.3031LFU:0.2812NUR:0.2812 5 page framesFIFO:0.2969LRU:0.2906OPT:0.3500LFU:0.3219NUR:0.3094 6 page framesFIFO:0.3375LRU:0.3281OPT:0.3844LFU:0.3375NUR:0.3344 7 page framesFIFO:0.3563LRU:0.3563OPT:0.

26、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.406210 page framesFIFO:0.4375LRU:0.4313OPT:0.5062LFU:0.4313NUR:0.425011 page framesFIFO:0.4813LRU:0.4625OPT:0.5531LFU:0.4500NUR:0.465612 page framesFI

27、FO:0.5406LRU:0.4875OPT:0.5687LFU:0.4938NUR:0.487513 page framesFIFO:0.5500LRU:0.5188OPT:0.5969LFU:0.5062NUR:0.543714 page framesFIFO:0.5594LRU:0.5531OPT:0.6344LFU:0.5281NUR:0.546915 page framesFIFO:0.5687LRU:0.5844OPT:0.6687LFU:0.5469NUR:0.581316 page framesFIFO:0.5781LRU:0.5938OPT:0.6813LFU:0.5719N

28、UR:0.596917 page framesFIFO:0.5906LRU:0.6156OPT:0.6969LFU:0.6156NUR:0.615618 page framesFIFO:0.6156LRU:0.6312OPT:0.7156LFU:0.6344NUR:0.653119 page framesFIFO:0.6687LRU:0.6656OPT:0.7344LFU:0.6531NUR:0.671920 page framesFIFO:0.6875LRU:0.6969OPT:0.7500LFU:0.6719NUR:0.690621 page framesFIFO:0.6906LRU:0.7094OP