實(shí)驗(yàn)三 (2)頁(yè)面置換算法

1、實(shí)驗(yàn)三 存儲(chǔ)管理（2）1目的和要求存儲(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è)面置換算法。2實(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. 順

2、序執(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)存容量下的命中率。

3、A. FIFO先進(jìn)先出的算法B. LRR最近最少使用算法C. OPT最佳淘汰算法（先淘汰最不常用的頁(yè)地址）D. LFR最少訪問(wèn)頁(yè)面算法E. NUR最近最不經(jīng)常使用算法3實(shí)驗(yàn)提示提示：A.命中率=1-頁(yè)面失效次數(shù)/頁(yè)地址流長(zhǎng)度 B.本實(shí)驗(yàn)中，頁(yè)地址流長(zhǎng)度為320，頁(yè)面失效次數(shù)為每次訪問(wèn)相應(yīng)指令時(shí)，該指令所對(duì)應(yīng)的頁(yè)不在內(nèi)存的次數(shù)。 C.關(guān)于隨機(jī)數(shù)產(chǎn)生方法，采用TC系統(tǒng)提供函數(shù)RAND()和RANDOMIZE()來(lái)產(chǎn)生。4實(shí)驗(yàn)運(yùn)行結(jié)果(TC+環(huán)境)試驗(yàn)輸出如下（輸出包括了用戶內(nèi)存從3K到32K的各種不同情況）PAGE FIFO LRR OPT LFR NUR試驗(yàn)結(jié)論(略)參考程序見(jiàn)下：#includ

4、e<stdio.h>#include<iostream.h>#include <stdlib.h>#include<time.h>struct aa int page; int count; aa* next; ;void main() time_t t; srand(unsigned(time(&t); int i,n,j,ii,m,answer,ffalse,count,fangfa,temp1,min,nn,mm; double sum; aa *head,*tail,*temp,*table,*first,*ti;/* nn=4;

5、mm=1; for(nn=4;nn>32;nn+) for(mm=1;mm>5;mm+) */ cin>>m; /m=nn; cout<<endl; cout<<"fangfa: 1-FIFO;2-LRR;3-OPT;4-LFR;5-NUR"<<endl; cout<<"Mothed:" cin>>fangfa; /fangfa=mm; ffalse=0; answer=0; table=new(aa); temp=table; table->page=-1; ta

6、ble->count=0; head=table; for(ii=2;ii<=m;ii+) table=new(aa); table->page=-1; table->count=0; temp->next=table; temp=table; if (ii=m)table->next=NULL; tail=table; temp=head; first=head; count=0; i=0; while(i<320) min=400; if (count=0) n=(rand()%320+1)%320; j=n/10;if (count=1) n=r

7、and()%(n+1);j=n/10;if(count=2) j=(n+1)%320)/10;if(count=3) j=(rand()%(320-n-2)+n+2)/10; table=head; temp=head; answer=0; min=400; if (fangfa=5) while(table!=NULL) if (table->page=j)answer=1;table->count=2; table=table->next; if (answer!=1) table=head; while (table!=NULL) if (table->count

8、<min)temp=table;min=table->count; table=table->next; if (temp->page!=-1) +ffalse; temp->page=j; temp->count=1; table=head; if (i%32)=0) while(table!=NULL) if (table->page!=-1) table->count=1; / if (table->page=j)answer=1;+(table->count); table=table->next; if (fangfa

9、=4)|(fangfa=3) while(table!=NULL) if (table->page=j)answer=1;+(table->count); table=table->next; if(answer!=1) table=head; while (table!=NULL) if (table->count<min)temp=table;min=table->count; table=table->next; if (temp->page!=-1) +ffalse; temp->page=j;table=head;while(ta

10、ble) table->count=1; table=table->next; else temp->page=j; +(temp->count); if (fangfa=2) while(table!=NULL)&&(fangfa=2) if (table->page=j)answer=1;temp=table; table=table->next; if(fangfa=2)&&(answer=1) /table=temp; temp1=temp->page; while (temp!=NULL) temp->p

11、age=temp->next->page; temp=temp->next;tail->page=temp1; if(answer!=1)&&(fangfa=2) if (first->page!=-1) ffalse=ffalse+1; first->page=j; temp=head; while (temp!=NULL) temp->page=temp->next->page; temp=temp->next;tail->page=j; table=head; while(table!=NULL)&

12、&(fangfa=1) if (table->page=j)answer=1; table=table->next; if (answer!=1)&&(fangfa=1) if (first->page!=-1) ffalse=ffalse+1; first->page=j; if (first->next!=NULL) first=first->next; else first=head; +i;+count; if (count=4)count=0; sum=1.0-ffalse/320.0;/*cout<<nn<

13、;<" "if (fangfa=1) cout<<"FIFO:"<<sum<<" "if (fangfa=2) cout<<" LRR:"<<sum<<" "if (fangfa=3) cout<<" OPT:"<<sum<<" "if (fangfa=4) cout<<" LFR:"<<sum<<" "if (fangfa=5) cout<