存储管理模拟程序 - 存储管理模拟程序.doc

存储管理模拟程序1. 设计目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。2. 设计内容（1）通过输入或由程序产生程序执行时的页号序列，共32个页号。页号序列按下述原则生成：页号序列应具有一定随机性。（如：50%的顺序访问）；（2）计算并输出下述各种算法在不同内存容量（432内存页面）下的命中率。先进先出的算法（FIFO）最近最少使用算法（LRU）最佳淘汰算法（OPT）：先淘汰最不常用的页地址最少访问页面算法（LFR）其中和为选择内容命中率 = 1 - （页面失效次数/页地址流长度）3.程序设计：本程序首先用rand()函数定义和产生地址流序列，并针对不同的算法计算出相应的命中率。I 根据实验内容将函数分成五个模块：1主程序模块，主要包括页面结构数组及页面控制结构定义，将指令流转换成页地址流 2 三个置换算法程序模块：FIFO算法模块，LRU算法模块，OPT算法模块，LFU算法模块 II 总程序模块流程图如下：4.源程序如下：#include #include#define maxsize 32#include define vpf 200void FIFO(int a);void LRU(int a);void OPT(int a);void LFU(int a);int countmaxsize;/int bpf;int avpf;void main() / 定义主函数。for(int i=0;i200;i+) /用随机数产生页地址流 ai=rand()%32;FIFO(a);LFU(a);OPT(a);LRU(a);void LFU(int a) /LFU算法for(int n=4;n33;n+) /不同的页面数计算命中率 int num=0; int same=0; int min; int minpage=0; int dis=0; int i=0; int k=0; int sum=n; /空白页面数 int num2=2; /设置清零时间间隔 int bmaxsize; for (k=0;kn;k+) /页面数组，计数数组初始化 bk=-1; countk=0; for (i=0;ivpf;i+) num=0; for (k=0;kn;k+) /测试是否命中 if(ai=bk) same=k; num+; if(num!=0) /命中页面计数器加1 countsame+; else dis+; /未命中，缺页次数加1 if(sum=0) /无空白页面 min=201; for(k=0;kcountk) min=countk; minpage=k; bminpage=ai; if(num2=0) /每两次缺页计数器清零for(k=0;kn;k+)countk=0;num2=3;countminpage=1; num2-; /countminpage=0; else /有空白页面 bn-sum=ai;if(num2=0) /每两次缺页计数器清零for(k=0;kn;k+)countk=0;num2=3;num2-; countn-sum=1;sum-; printf(%d,n); printf( page frames LFU:%3d,dis); printf( LFU:%6.4fn,1-(float)dis/32); void OPT(int a) /OPT算法 for(int n=4;n33;n+) /不同的页面数计算命中率int num1=0,num2=0,num3=0,num4=0; int d; int dis=0; int bmaxsize; int sum=n; int max; int maxpage; int distvpf; for(int i=0;ivpf;i+) num1=0; for(int j=0;jn;j+) /测试是否命中 if(ai=bj) num1+;if(num1=0) /未命中 dis+; /缺页次数加1 if (sum!=0) /有空白页面时 bn-sum=ai;sum-; else /无空白页面 for(int k=0;kvpf;k+)/初始化页地址离当前页地址的距离 distak=0; for (k=0;kvpf;k+) num2=0; for(j=0;jn;j+) if(bj=ak) /测试未来页地址是否在内存 num2+; if(num2!=0) distak=201; /在内存的页地址的距离赋予最大值。 else distak=0; 不在内存的页地址的距离先全赋予0。 d=1; for( k=i+1;kvpf;k+) /测试未来的地址流是否在当前的内存。 num3=0; for(int j=0;jn;j+) if (ak=bj) num3+; if (num3!=0) /未来的某些地址在当前在内存 num4=0; for(int l=i+1;lk;l+) 测试未来的地址流的是否有相同的。 if (ak=al) num4+; if(num4=0)若不同则将其距离赋予相应的值，越在后面其距离值越大 distak=d; d+; max=-1; maxpage=0; for(int c=0;cvpf;c+) 找出距离最大的页号 if(maxdistac) max=distac; maxpage=ac; for(j=0;jn;j+) /找出在内存中距离与最大距离相等的页号并替换掉 if(bj=maxpage) bj=ai; printf(%d,n); printf( page frames OPT:%d ,dis); printf( OPT:%6.4fn,1-(float)dis/32);void FIFO(int a) FIFO算法for(int n=4;n33;n+) /不同的页面数计算命中率 int num; int max; int maxpage=0; int dis=0; int i=0; int k=0; int sum=n; int bmaxsize; for (k=0;kn;k+) /页面数组，计数数组初始化 bk=-1; countk=0; for (i=0;ivpf;i+) num=0; for (k=0;kn;k+) /测试是否命中 if(ai=bk) num+; if(num=0) /未命中 dis+; for(k=0;kn;k+) /所有页面计数器加一 countk+; if(sum=0) /没空白页面时 max=0; for(k=0;kn;k+) if(maxcountk) /找出计数器值最大的替换 max=countk; maxpage=k; bmaxpage=ai; countmaxpage=0; /被替换页面计数器清零 else bn-sum=ai;countn-sum=0; /有空白页面时，将所缺页放入空白页面，sum-; 并将该页面计数器清零 printf(%d,n); printf( page frames FIFO:%3d,dis); printf( FIFO:%6.4fn,1-(float)dis/32);void LRU(int a) /LRU算法for(int n=4;n33;n+) int num=0; int same=0; int max; int maxpage=0; int dis=0; int i=0; int k=0; int sum=n; int bmaxsize; for (k=0;kn;k+) /初始化页面数组和计数数组 bk=-1; countk=0; for (i=0;ivpf;i+) num=0; for (k=0;kn;k+) if(ai=bk) /测试是否命中 same=k; num+; for(k=0;kn;k+) countk+; if(num!=0) countsame=0; /命中时，该页面计数器清零 else dis+; /未命中时 if(sum=0) /当没空白页面时 max=0; for(k=0;kn;k+) if(maxcountk) /找出计数器值最大的页面替换 max=countk; maxpage=k; bmaxpage