实验三(2)页面置换算法(优.选)

1、实验三 存储管理（ 2）1目的和要求存储管理的主要功能之一是合理地分配空间。 请求页式管理是一种常用的虚 拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计， 了解虚拟 存储技术的特点，掌握请求页式管理的页面置换算法。2实验内容1过随机数产生一个指令序列，共 320 条指令。其地址按下述原则生成： 50%的指令是顺序执行的； 25%的指令是均匀分布在前地址部分； 25%的指令是均匀分布在后地址部分；#具体的实施方法是：A. 在0，319的指令地址之间随机选区一起点 M;B. 顺序执行一条指令，即执行地址为 M+1 的指令；C. 在前地址0 , M+1中随机选取一条指令并执

2、行，该指令的地址为M D. 顺序执行一条指令，其地址为 M+1；E. 在后地址 M +2， 319中随机选取一条指令并执行；F. 重复A E,直到执行320次指令。2指令序列变换成页地址流设：（ 1 ）页面大小为 1K；（2）用户内存容量为 4页到 32页；（3）用户虚存容量为 32K。在用户虚存中，按每 K 存放 10 条指令排列虚存地址，即 320 条指令在虚存 中的存放方式为：第0条第9条指令为第 0页（对应虚存地址为 0， 9）；第 10条第 19条指令为第 1 页（对应虚存地址为 10， 19）；。第 310条第319条指令为第 31 页（对应虚存地址为 310， 319）；按以上方

3、式，用户指令可组成32页。3.计算并输出下述各种算法在不同内存容量下的命中率A. FIFO先进先出的算法B. LRR最近最少使用算法C. OPT最佳淘汰算法（先淘汰最不常用的页地址）D. LFR最少访问页面算法E. NUR最近最不经常使用算法3 .实验提示提示：A.命中率=1-页面失效次数/页地址流长度B. 本实验中，页地址流长度为320,页面失效次数为每次访问相应指 令时，该指令所对应的页不在内存的次数。C. 关于随机数产生方法，采用TC系统提供函数RAND（）和 RANDOMIZE。来产生。4.实验运行结果（TC+环境）试验输出如下（输出包括了用户内存从 3K到32K的各种不同情况）PAG

4、E FIFOLRROPTLFRNUR0 丄 234吕 678y0123 啣吕G7S 一145GI7019|1|1丄丄|111!11|1,丄 IZBJtM 進快laCNJJSlgO.340G0.37810.12&0 8侗im 0.449G 0.4S12 0.50000.5375 a.5625 0.6000 0.6125 61S7 t）.62Hl U.bJ7b Mrb4Ub 0.6E25 0.67S1 0.7312 B.7S31 0.7719O.7R12 n.efifis 0.8400.34&90.366Q.390G0.41S60.4344B.468Q0.49G90.518He.540G0.565

5、69.59066.60946.6Z 丄丁H .bbbklB.bvyi 97125S.72S00.7b310.7688 n.RnnnB.8188fl.A440.49QI.S531fi.4969 0.344 B.5GSS Q.99 0.2&0 0G531 0.G750 W.GVG? 0.7180 0 7344 9.7500 0.7656 0.77丄 9 770b O.HM31 M.U12b B.S219 .8313 0.3406 0.850Q 0.8FA2 0.SC25 B.aCA? W.R7SW 0.88120.3498.3&E&0.39QG 0.415G0.4344 04&SB0.49G90.

6、51S80.54660.5656O.59S60.60?40.6219.64UbO.656ZW.b781H.712S0.72500.75310.7688 R.RHRH8.aiasA.A244R.R49 8.8510.35620.38440.40940.4344B.45GJ0.40?S0.47S10.49180.50943.54960.S4690.56560.6156B.&62 B.65620.7063 0.7Q000.72500.74370.77fil 0一79%98.9Q31试验结论（略）参考程序见下：#in clude#in clude#in clude #includestruct aai

7、nt 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;mm=1;for(nn=4;nn32;nn+)for(mm=1;mm5;mm+)*/cinm;/m=nn;coutendl;coutfangfa: 1-FIFO;2-LRR;3-OPT;4-LFR;5-NURendl; co

8、utfangfa;/fangfa=mm;ffalse=0;answer=0;table=new(aa);temp=table;table-page=-1;3 / 9word.table-count=0;head=table;for(ii=2;iipage=-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(ipage=j)answer=1;table-count=2;table=table-next;if (a

9、nswer!=1)table=head;while (table!=NULL)if (table-countcount;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=4)|(fangfa=3)5 / 9word.wh

10、ile(table!=NULL)if (table-page=j)answer=1;+(table-count);table=table-next;if(answer!=1) table=head;while (table!=NULL)if (table-countcount;table=table-next;if (temp-page!=-1)+ffalse;temp-page=j;table=head;while(table)table-count=1;table=table-next;elsetemp-page=j;+(temp-count);if (fangfa=2)while(tab

11、le!=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-page=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 (tem

12、p!=NULL)temp-page=temp-next-page; temp=temp-next; tail-page=j; table=head; while(table!=NULL)&(fangfa=1)7 / 9word.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;/*coutnn ;if (fangfa=1) coutFIFO:sum ;if (fangfa=2)