南昌大学实验报告
---（3）存储管理的模拟实现
学生姓名： 张晨欣 学 号： 61004011132 专业班级： 电Ⅲ114班 实验类型：□ 验证 ■ 综合 □ 设计 □ 创新 实验日期： 实验成绩：
一、 实验目的
存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。
二、 实验内容
1． 过随机数产生一个指令序列，共320条指令。其地址按下述原则生成：
①50%的指令是顺序执行的；
②25%的指令是均匀分布在前地址部分； ③25%的指令是均匀分布在后地址部分； 具体的实施方法是：
A. 在[0，319]的指令地址之间随机选区一起点M; B. 顺序执行一条指令，即执行地址为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]）； 。。。。。。。。。。。。。。。。。。。。。
第310条—第319条指令为第31页（对应虚存地址为[310，319]）； 按以上方式，用户指令可组成32页。
3． 计算并输出下述各种算法在不同内存容量下的命中率。
A. FIFO先进先出的算法 B. LRU最近最少使用算法 C. LFU最少访问页面算法
三、 实验要求
1、 需写出设计说明； 2、 设计实现代码及说明 3、 运行结果；
四、 主要实验步骤
1、 分析算法结构；
2、 画出算法的流程图，即设计说明；
3、 根据画出的流程图使用C语言编写相应的代码（代码过长，放到最后）；
程序主要由main函数和以下几个函数组成： void initialization();初始化内存数据 void FIFO();FIFO先进先出算法； void LRU();LRU最久未使用算法； void LFU();LFU最近最久未使用算法；
4、 检查代码，将编出的代码编译、链接，验证其正确性。
开始按要求产生320个随机数将随机数转换成页面用户内存容量i=4FIFO页面置换算法LRU页面置换算法LFU页面置换算法i=i+1Ni>32?Y结束 页面置换算法整体结构
开始内存数据初始化，物理块0 FIFO页面置换算法 开始内存数据初始化，物理块0 开始内存数据初始化，物理块0 五、 实验数据及处理结果 六、 实验体会或对改进实验的建议 我做实验的时候，主要的难度是在几个特殊情况的处理上，如LRU内存中的页面都是之前没有调用过的，那怎么办，还有就是LFU中还没有达到“一定时间间隔”的条件时怎么办？ 另外就是由于实验使用的是系统产生的随机数，所以难以验证实验结果的正确性。 七、 参考资料 《计算机操作系统》 《计算机操作系统实验指导书》 《C程序设计》 《C语言程序设计_现代方法》 《计算机操作系统教程习题解答与实验指导(第二版)》 八、 实验代码 #include int s,i; //s表示产生的随机数，i表示物理块数 int m,n,h; //循环专用 int k,g,f; //临时数据 int sum; //缺页次数 float r; //rate命中率 int p[320]; //page页数 int a[320]; //执行的指令 int pb[32]; //physical block用户内存容量（物理块） void initialization(); void FIFO(); void LRU(); void LFU(); void line(); void start(); void end(); void main() { start(); srand((int) time (NULL)); //以计算机当前时间作为随机数种子 for (n=0;n<320;n+=3) { s=rand()%320+0; //随机产生一条指令 a[n]=s+1; //顺序执行一条指令 s=rand()%(a[n]+1); //执行前地址指令M` a[n+1]=s+1; s=rand()%(319-a[n+1])+(a[n+1]+1); a[n+2]=s; } for (n=0;n<320;n++) p[n]=a[n]/10; //得到指令相对的页数 printf(\"物理块数\ FIFO\\ LRU\\ LFU\\n\"); line(); for (i=4;i<=32;i++) { printf(\"\\n %2d：\",i); FIFO(); LRU(); LFU(); } end(); } void initialization() //用户内存及相关数据初始化 { for (n=0;n<32;n++) pb[n]=-1; sum=0; r=0; k=0; g=-1; f=-1; } void FIFO() //先进先出置换算法 { int time[32]; //定义进入内存时间长度数组 int max; //max表示进入内存时间最久的，即最先进去的 initialization(); for(m=0;m for (m=0;m g=m; break; } for (m=0;m f=m; break; } if (g!=-1) g=-1; else { if (f==-1) //找到最先进入内存的页面 { max=time[0]; for(m=0;m { max=time[m]; k=m; } pb[k]=p[n]; time[k]=0; //该物理块中页面停留时间置零 sum++; //缺页数+1 } else { pb[f]=p[n]; time[f]=0; sum++; f=-1; } } for (m=0;mtime[m]++; //物理块中现有页面停留时间+1 } r=1-(float)sum/320; printf(\"\\%6.4f\",r); } void LRU() //最近最少使用算法 { int time[32]; int max; initialization(); for (m=0;m for (m=0;m for (m=0;m } if (g!=-1) { time[g]=0; g=-1; } else { if (f==-1) { max=time[0]; for (m=0;m k=m; max=time[m]; } pb[k]=p[n]; time[k]=0; sum++; } else { pb[f]=p[n]; time[f]=0; sum++; f=-1; } } for (m=0;mr=1-(float)sum/320; printf(\"\\%6.4f\",r); } void LFU() //最少访问页面算法 { initialization(); int time_lru[32],time[32],min,max_lru,t; for (m=0;m time_lru[m]=m+1; } for (n=0;n<320;n++) { k=0; t=1; for (m=0;m for (m=0;m if (g!=-1) { time_lru[g]=0; g=-1; } else { if (f==-1) { if (n<=20) //将最少使用的间隔时间定位个单位 { max_lru=time_lru[0]; //在未达到“一定时间”的要求时，先采用LRU进行页面置换 for (m=0;m k=m; max_lru=time_lru[m]; } pb[k]=p[n]; time_lru[k]=0; sum++; } else { for (m=0;m time[m]++; min=time[0]; for (m=0;m for (m=0;m { max_lru=time_lru[k]; for (m=0;mmax_lru) { k=m; max_lru=time_lru[m]; } } pb[k]=p[n]; time_lru[k]=0; sum++; } } else { pb[f]=p[n]; time_lru[f]=0; sum++; f=-1; } } for (m=0;mr=1-(float)sum/320; printf(\"\\%6.4f\",r); } void line() //美化程序，使程序运行时更加明朗美观 { printf(\"------------------------------------------------------------------\"); } void start() //表示算法开始 { line(); printf(\"\\n 页面置换算法开始\\n\"); printf(\" ——Designed by Zhang Hong\\n\"); line(); printf(\"\\n\\n\"); } void end() //表示算法结束 { printf(\"\\n\"); line(); printf(\"\\n line(); } 页面置换算法结束,谢谢使用\\n\"); 因篇幅问题不能全部显示，请点此查看更多更全内容