存储管理模拟实现

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

2、M+1的指令；C. 在前地址0，M+1中随机选取一条指令并执行，该指令的地址为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）；。第3

3、10条第 319条指令为第 31页（对应虚存地址为 310， 319）； 按以上方式，用户指令可组成 32页。3. 计算并输出下述各种算法在不同内存容量下的命中率。B. LRU最近最少使用算法C. LFU最少访问页面算法三、实验要求1、需写出设计说明；2、设计实现代码及说明3、运行结果；四、主要实验步骤1、分析算法结构； 画出算法的流程图，即设计说明； 根据画出的流程图使用 C语言编写相应的代码(代码过长，放到最后) 程序主要由 main 函数和以下几个函数组成： void initialization();初始化内存数据void FIFO();FIFO 先进先出算法； void LRU();

4、LRU 最久未使用算法； void LFU();LFU 最近最久未使用算法：流程图如下：页面置换算法整体结构开始FIFO页面置换算法LRU页面置换算法LFU页面置换算法2、设计说明及源代码FIFO算法设计说明：按照所要求的产生随机指令序列，存放在order320这个数组中。通过循环产生这些随机指令，每产生一条都要进行下列判断：是否和内存中即mem_volume4中存放的页面相同，如果相同则不做任何操作，如果不相同，则产生缺页，相应的缺页次数加一，按照 fcfs 将最先进入内存的页数淘汰，并将该页写到内存中去。重复上面的操作直到完成这 320 条指令。 源代码：/ 储存管理 .cpp : 定义控

5、制台应用程序的入口点。 /#include "stdafx.h"int _tmain(int argc, _TCHAR* argv) return 0;#include <stdio.h>#include <stdlib.h>#include <time.h>#define N 5 / 总共运行的次数 void main()int order320,mem_volume4=100,100,100,100;/ 使得 mem_volume 的值大于 100>32，这样我们便可使其在开始就产生缺页 / 定义 add 为缺页次数 sign

6、作为标识符判断所调页数是否在内存中int l=0,i=0,j,num=0,cx,sign=0,add=0;float value=O,sum=O; /定义 sum为缺页率 srand(time(NULL);总共运行 N 次产生随机数放 order 中for(cx=0;cx<N;cx+) /while(i<320)orderi=rand()%320; / for(j=0;j<4;j+)if(orderi+1)/10=mem_volumej)sign=1; / 通过 sign 标识判断所调页数是否在内存块中if(sign)sign=0;elsel+;if(mem_volume3=

7、100)mem_volume3=(orderi+1)/10;/保证第一次调入的页面都产生缺页elsemem_volumenum=(orderi+1)/10; / 将所缺页调入到内存块中 num=(num+1)%4;/num 值为下次所要置换出去的内存块中对应的页数i+;orderi=rand()%(orderi-1+2);for(j=0;j<4;j+)if(orderi/10=mem_volumej)sign=1;if(sign)sign=0;elsel+;if(mem_volume2=100) mem_volume2=orderi/10;elsemem_volumenum=orderi

8、/10;num=(num+1)%4;i+;orderi=orderi-1+1;for(j=0;j<4;j+)if(orderi/10=mem_volumej)sign=1;if(sign)sign=0;elsel+;if(mem_volume1=100) mem_volume1=orderi/10;elsemem_volumenum=orderi/10;num=(num+1)%4;i+; orderi=rand()%(319-orderi-1-2)+(orderi-1+2); for(j=0;j<4;j+)if(orderi/10=mem_volume0)sign=1;if(sig

9、n)sign=0;elsel+;if(mem_volume0=100)mem_volume0=(orderi+1)/10;else mem_volumenum=orderi/10; num=(num+1)%4;i+; value=l/320.0*100; add=add+l; sum=sum+value;页面置换算法 最后一次指令序列*n");*");printf( "* FIFOprintf( "* for(i=0;i<320;i+) if(i%10=0) printf("n");printf("%5d",

10、orderi);printf("n");printf( "*n");printf("tt%d 次 的 平 均 缺 页 数 为 %dntt%d 次 的 平 均 缺 页 率 为 .3f%n",N,add/N,N,sum/N);printf("n");LRU页面置换算法设计说明：这个算法同FCFS算法的不同之处在于，每产生一条随机指令，如果和 4 个内存块中的某一个页数相同的话，就要对这 4 个内存块中的页数重新排序，将每次要置换 出去的页数放在 mem_volume3中，这样，在每次产生缺页的时候，都先将所缺页数写入到

11、该内存 块，然后再排序，将其放到 mem_volume0 中去。源代码：/ 储存管理 .cpp : 定义控制台应用程序的入口点。/#include "stdafx.h"int _tmain(int argc, _TCHAR* argv)return 0;#include <stdio.h>#include <stdlib.h>#include <time.h>#define N 5int main(void)int order320,mem_volume4=100,100,100,100;int l=0,i=0,j,cx;int num,

12、temp=0,ex_chan=0,add=0;float value=0,sum=0;srand(time(NULL);for(cx=0;cx<N;cx+)while(i<320)orderi=rand()%320;if(orderi+1)/10=mem_volume0); / 如果所调页数同第一个内存块中页数相同，则执行空操作 else if(orderi+1)/10=mem_volume1)temp=mem_volume1;mem_volume1=mem_volume0;mem_volume0=temp;/ 如果所调页数同第二个内存块相同，则排序只需交换一次 else if(o

13、rderi+1)/10=mem_volume2)for(j=2;j>0;j-)temp=mem_volumej;mem_volumej=mem_volumej-1;mem_volumej-1=temp;else if(orderi+1)/10=mem_volume3)for(j=3;j>0;j-)temp=mem_volumej;mem_volumej=mem_volumej-1;mem_volumej-1=temp; / 如果所调页数同第 3、4 个内存块中页数相同，则通过循环进行排序 else l+;if(mem_volume3=100) mem_volume3=(orderi

14、+1)/10;/ 保证刚开始调入内存块中就产生缺页 elsemem_volume3=(orderi+1)/10;for(num=3;num>0;num-) ex_chan=mem_volumenum; mem_volumenum=mem_volumenum-1;mem_volumenum-1=ex_chan; / 写人后重新排序 i+; orderi=rand()%(orderi-1+2); if(orderi/10=mem_volume0)Jelse if(orderi/10=mem_volume1) temp=mem_volume1; mem_volume1=mem_volume0;

15、 mem_volume0=temp;else if(orderi/10=mem_volume2) for(j=2;j>0;j-) temp=mem_volumej; mem_volumej=mem_volumej-1; mem_volumej-1=temp;else if(orderi/10 = mem_volume3) for(j=3;j>0;j-) temp=mem_volumej; mem_volumej=mem_volumej-1; mem_volumej-1=temp;else l+; if(mem_volume2=100) mem_volume2=orderi/10;e

16、lsemem_volume3=orderi/10; for(num=3;num>0;num-) ex_chan=mem_volumenum; mem_volumenum=mem_volumenum-1; mem_volumenum-1=ex_chan; i+;orderi=orderi-1+1; if(orderi/10= mem_volume0)else if(orderi/10 = mem_volume1)temp=mem_volume1; mem_volume1=mem_volume0;mem_volume0=temp;else if(orderi/10 = mem_volume2

17、)for(j=2;j>0;j-) temp=mem_volumej; mem_volumej=mem_volumej-1; mem_volumej-1=temp;else if(orderi/10=mem_volume3)for(j=3;j>0;j-) temp=mem_volumej; mem_volumej=mem_volumej-1; mem_volumej-1=temp;elsel+;if(mem_volume1=100)mem_volume1=orderi/10;elsemem_volume3=orderi/10;for(num=3;num>0;num-) ex_c

18、han=mem_volumenum; mem_volumenum=mem_volumenum-1; mem_volumenum-1=ex_chan;i+; orderi=rand()%(319-orderi-1-2)+(orderi-1+2); if(orderi/10=mem_volume0)Jelse if(orderi/10=mem_volume1) temp=mem_volume1; mem_volume1=mem_volume0; mem_volume0=temp;else if(orderi/10=mem_volume2)for(j=2;j>0;j-)temp=mem_vol

19、umej;mem_volumej=mem_volumej-1; mem_volumej-1=temp;else if(orderi/10= mem_volume3) for(j=3;j>0;j-) temp=mem_volumej; mem_volumej=mem_volumej-1; mem_volumej-1=temp;else l+;if(mem_volume0=100)mem_volume0=orderi/10;elsemem_volume3=orderi/10;for(num=3;num>0;num-)ex_chan=mem_volumenum;mem_volumenum

20、=mem_volumenum-1; mem_volumenum-1=ex_chan;i+;value=l/320.0*100; sum=sum+value; add=add+l;printf( "*页面置换算法);printf(指令序列*");for(i=0;i<320;i+)if(i%10=0) printf("n");printf("%5d",orderi);printf("n");printf(H*n");printf("tt%d 次 的 平 均 缺 页 数 为 %dntt%d 次

21、的 平 均 缺 页 率 为 .3f%n",N,add/N,N,sum/N);printf("n");LFU 页面置换算法设计说明： 该算法主要是将最近时期页面使用最少的页面作为淘汰页。这里 通过设立 count32 这个计数数组记录 32 页的调用次数， 通过比较来确定要调出的页面。 但如果没产生缺页就只需对所调页数对应的 count 值加 1 即可。 源代码：/ 储存管理 .cpp : 定义控制台应用程序的入口点。/#include "stdafx.h"int _tmain(int argc, _TCHAR* argv) return 0;#

22、include <stdio.h>#include <stdlib.h>#include <time.h>#define N 5 / 定义运行次数 void main()int order320,count32=0,compare4=0,mem_volume4=100,100,100,100; /compare 数组中存放了每次要比较的四个内存块中页数的调用次数 int l=0,i=0,j,k=0,cx=0;int min,num=0,n,sign=0,add=0;float value=0,sum=0; srand(time(NULL); for(cx=0

23、;cx<N;cx+) while(i<320) orderi=rand()%320; for(j=0;j<4;j+) if(orderi+1)/10=mem_volumej) n=(orderi+1)/10; countn+=1; sign=1; / 相同执行加 1 操作 if(sign)sign=0;else l+; if(mem_volume3=100) mem_volume3=(orderi+1)/10; n=(orderi+1)/10; countn+=1;else min=1000;for(num=0;num<4;num+)k=mem_volumenum;co

24、mparenum=countk;if(comparenum<min)min=comparenum;j=num; / 通过比较确定最少使用的页数，mem_volumej=(orderi+1)/10;i+;orderi=rand()%(orderi-1+2);for(j=0;j<4;j+)if(orderi/10=mem_volumej)n=orderi/10;countn+=1;sign=1;if(sign)sign=0;else l+;if(mem_volume2=100)mem_volume2=(orderi+1)/10;n=(orderi+1)/10;countn+=1;els

25、e min=1000;for(num=0;num<4;num+)k=mem_volumenum;comparenum=countk;if(comparenum<min)min=comparenum;j=num;mem_volumej=(orderi+1)/10;i+;orderi=orderi-1+1;for(j=0;j<4;j+)if(orderi/10= mem_volumej)n=orderi/10;countn+=1;sign=1;if(sign)sign=0;elsel+;if(mem_volume1=100)mem_volume1=(orderi+1)/10;n=

26、(orderi+1)/10;countn+=1;else min=1000;for(num=0;num<4;num+) k=mem_volumenum; comparenum=countk; if(comparenum<min) min=comparenum; j=num;mem_volumej=(orderi+1)/10;i+; orderi=rand()%(319-orderi-1-2)+(orderi-1+2); for(j=0;j<4;j+)if(orderi/10=mem_volume0)n=orderi/10;countn+=1;sign=1;if(sign)si

27、gn=0;else l+;if(mem_volume0=100)mem_volume0=(orderi+1)/10;n=(orderi+1)/10;countn+=1;else min=1000;for(num=0;num<4;num+) k=mem_volumenum; comparenum=countk; if(comparenum<min) min=comparenum; j=num; mem_volumej=(orderi+1)/10;i+;value=l/320.0*100;add=add+l;sum=sum+value;页面置换算法 最后一次指令序列"* LF

28、U*n");*"); printf( printf( "* for(i=0;i<320;i+) if(i%10=0) printf("n");printf("%5d",orderi);printf("n");printf( "*n");printf("t%d 次 的 平 均 缺 页 数 为 %dnt%d 次 的 平 均 缺 页 率 为 .3f%",N,add/10,N,sum/10);printf("n");五、实验数据及处理结果FIFO页面置换算法运行结果： "G： vc6 Microsoft VisuaI StudiM MyProjects456Debug' 456,etc"913?78页一FO后 3FI曰<9*1EH算序8310 189 112 161102 316112624114 1S 2 S3 1432295173 305 18018123G2?98282920512812? 128 1?3165 1081092692188788144 1542829 151230 1631&42232062021 143228 1531S4 200