实验六 请求分页存储管理.doc

_ _ 精品资料 实验实验六：六：请求分页存储管理 一一实验实验目的目的 深入理解请求页式存储管理的基本概念和实现方法，重点认识其中的 地址变换、缺页中断、置换算法等实现思想。 二二实验实验属性属性 该实验为综合性、设计性实验。 三三实验仪实验仪器器设备设备及器材及器材 普通 PC386 以上微机 四四实验实验要求要求 本实验要求 2 学时完成。 本实验要求完成如下任务： （1） 建立相关的数据结构：页表、页表寄存器、存储块表等； （2） 指定分配给进程的内存物理块数，设定进程的页面访问顺序； （3） 设计页面置换算法，可以选择 OPT、FIFO、LRU 等，并计算相应的 缺页率，以比较它们的优劣； （4） 编写地址地址转换转换函数函数，实现通过查找页表完成逻辑地址到物理地址 的转换；若发生缺页则选择某种置换算法（OPT、FIFO、LRU 等）完成页 面的交换； （5） 将整个过程可视化显示出来。 实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基 本代码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、 记录并分析实验结果。实验后认真书写符合规范格式的实验报告（参见附 录 A），并要求用正规的实验报告纸和封面装订整齐，按时上交。 三、设计过程 3.1 算法原理分析 OPT 算法是未来最远出现，当当前内存中没有正要访问的页面时， 置换出当前页面中在未来的访问页中最远出现的页面或再也不出现的 页面。 FIFO 算法是先进先出，当当前内存中没有正要访问的页面时，置换 出最先进来的页面。 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; /记录缺页数组 void opt() /最佳 void fifo() /先进先出 bool search(int n) /查找当前内存中是否已存在该页 3.3 流程图与运行截图 否 是 是 否 开始 得到执行的指令 指令是否在内存中 最先存入指 令被淘汰 下面是否还有指令 结束 得出命中率 图 6.1 FIFO（）函数流程图; _ _ 精品资料 开始 输入内存中分配页 数 据第一个访问页初始化第一列值 还有请求访问页？ 直接复制前一列内容 内存中是否已存在？ 内存有空页？ 直接插入 替换内存中将来不出现或离当前最 远的页 输出全部页面变 化情况 结束 否 是 否 是 否 是 图 2.2 OPT 算法流程图 _ _ 精品资料 四、小结 本次课程设计目的是通过请求页式管理中页面置换算法模拟设计， 了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。 要求设计随机页面产生程序，并说明随机的性能和其性能可能对算法 的影响，对随机性要有一定的参数控制能力；计算并输出 FIFO 及 LRU 算法在不同内存容量下的命中率。 由于上学期做过页面置换的实验，内容包括先进先出算法（FIFO）、 最近最久未使用页面置换算法（LRU）和理想淘汰算法（OPT），3 种算法 思想简单明确，选好数据结构，思路清晰便基本没问题了。所以相对来 说，这次操作系统的课程设计容易许多，只是在之前实验基础上，要附 加设计随机页面产生程序，对随机性要有一定的参数控制能力。对于 随机页面产生程序，我们之前没做过，在网上查阅资料，使用了库函数 srand（）和 rand（），实现了简单的随机页面产生程序，功能基本完成。我 们知识所限，没有使用漂亮可视化界面编程实现功能，用简单的 C 语 言编程实现的。不管怎么样，最终还是实现的本次课程设计要求的。 五、源程序 #include #include using 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(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(%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=*; 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=1; coutendl; int max=-10,max_pos; for( k=0;knum_page;k+)/找出位置最远的那个值 if(posk=-1)/未出现则跳出，替换该值 max_pos=k;break; 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 _ _ 精品资料 void fifo() /先进先出 int i,thisn=0; while(1) count=0; flag1=flag2=0; for(i=pos1;i=num_page)thisn=0; 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 void main() /主函数 int m; printf( 1.OPT.n); printf( 2.FIFO.n); printf( 0.退出.n); printf( 选择所要操作:); scanf(%d, switch(m) case 1: init()