实验六 请求分页存储管理

1、实验六：实验六：请求分页存储管理一实验目的一实验目的深入理解请求页式存储管理的基本概念和实现方法，重点认识其中的地址变换、缺页中断、置换算法等实现思想。二实验属性二实验属性该实验为综合性、设计性实验。三实验仪器设备及器材三实验仪器设备及器材普通 PC386 以上微机四实验要求四实验要求本实验要求 2 学时完成。本实验要求完成如下任务：（1） 建立相关的数据结构：页表、页表寄存器、存储块表等；（2） 指定分配给进程的内存物理块数，设定进程的页面访问顺序； （3） 设计页面置换算法，可以选择 OPT、FIFO、LRU 等，并计算相应的缺页率，以比较它们的优劣；（4） 编写地址转换函数地址转换函数，

2、实现通过查找页表完成逻辑地址到物理地址的转换；若发生缺页则选择某种置换算法（OPT、FIFO、LRU 等）完成页面的交换； （5） 将整个过程可视化显示出来。实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告（参见附录 A） ，并要求用正规的实验报告纸和封面装订整齐，按时上交。三、设计过程3.1 算法原理分析OPT 算法是未来最远出现，当当前内存中没有正要访问的页面时，置换出当前页面中在未来的访问页中最远出现的页面或再也不出现的页面。FIFO 算法是先进先出，当当

3、前内存中没有正要访问的页面时，置换出最先进来的页面。LRU 算法是最近最久未使用，当当前内存中没有正要访问的页面时，置换出在当前页面中最近最久没有使用的页面。3.2 数据定义int length,num_page,count,seed; /length 记录访问串的长度，num_page 页面数，count 记录缺页次数int result2030,order30,a10; /result 记录结果,order 存储访问串,a 存储当前页面中的值int pos1,flag1,flag2,flag3; /pos1 位置变量，flag1 等为标志变量char result130; /记录缺页数组

4、void opt() /最佳void fifo() /先进先出 bool search(int n) /查找当前内存中是否已存在该页3.3 流程图与运行截图否是是否开始得到执行的指令指令是否在内存中最先存入指令被淘汰下面是否还有指令结束得出命中率图 6.1 FIFO（）函数流程图;开始输入内存中分配页数据第一个访问页初始化第一列值还有请求访问页？直接复制前一列内容内存中是否已存在？内存有空页？直接插入替换内存中将来不出现或离当前最远的页输出全部页面变化情况结束否是否是否是图 2.2 OPT 算法流程图四、小结本次课程设计目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握

5、请求页式存储管理的页面置换算法。要求设计随机页面产生程序，并说明随机的性能和其性能可能对算法的影响，对随机性要有一定的参数控制能力；计算并输出 FIFO 及LRU 算法在不同内存容量下的命中率。由于上学期做过页面置换的实验，内容包括先进先出算法（FIFO） 、最近最久未使用页面置换算法（LRU）和理想淘汰算法（OPT） ，3 种算法思想简单明确，选好数据结构，思路清晰便基本没问题了。所以相对来说，这次操作系统的课程设计容易许多，只是在之前实验基础上，要附加设计随机页面产生程序，对随机性要有一定的参数控制能力。对于随机页面产生程序，我们之前没做过，在网上查阅资料，使用了库函数 srand（）和

6、rand（） ，实现了简单的随机页面产生程序，功能基本完成。我们知识所限，没有使用漂亮可视化界面编程实现功能，用简单的 C 语言编程实现的。不管怎么样，最终还是实现的本次课程设计要求的。五、源程序#include#includeusing namespace std;int length,num_page,count,seed;int result2030,order30,a10;int pos1,flag1,flag2,flag3;char result130;void init()memset(a,-1,sizeof(a); int i;coutlength;coutseed;srand(

7、seed);cout产生的随机访问串:;for(i=0;ilength;i+)orderi=rand()%10;coutorderi endl; coutnum_page;void print()int i,j;cout表示缺页endl;for( j=0;jlength;j+)printf(%2d ,orderj); coutendl;for( i=0;inum_page;i+)for( j=0;jlength;j+)if(resultij=-1) printf( );else printf(%2d ,resultij);coutendl;for( j=0;jlength;j+)printf(

8、%2c ,result1j); coutendl;cout缺页率：count/length;printf(=%.1lf,(count*1.0)/(length*1.0)*100);cout%endl;bool search(int n) /查找当期内存是否已存在int i;for(i=0;inum_page;i+)if(ai=n)return true;return false;void opt() /最佳int i,pos10,flag10;while(1) flag1=flag2=0;for(i=0;ilength;i+)if(!search(orderi)count+;result1i=

9、*;if(anum_page-1!=-1) /表示当前页面已满要淘汰一个memset(pos,-1,sizeof(pos);memset(flag,0,sizeof(flag);int j,k;for( j=i;jlength;j+)/找出当前页中的值在将来访问串中对应的最近位置for( k=0;knum_page;k+)if(orderj=ak&flagk=0)posk=j; flagk=1;coutendl;int max=-10,max_pos;for( k=0;knum_page;k+)/找出位置最远的那个值if(posk=-1)/未出现则跳出，替换该值max_pos=k;br

10、eak;else if(maxposk)max=posk;max_pos=k;amax_pos=orderi;else /还有空页for(int j=0;jnum_page;j+)if(aj=-1)aj=orderi; break;else result1i= ;for(int j=0;jnum_page;j+)resultji=aj;print(); if(flag1=0&flag2=0)break;void fifo() /先进先出int i,thisn=0;while(1)count=0; flag1=flag2=0;for(i=pos1;i=num_page)thisn=0;elsefor(int j=0;jnum_page;j+)if(aj=-1)aj=orderi; break;else result1i= ;for(int j=0;jnum_page;j+)resultji=aj; print(); if(flag1=0&flag2=0)break;void main() /主函数 int m;printf( 1.OPT.n);printf( 2.FIFO.n);printf( 0.退