页面置换算法实验报告.docx

《页面置换算法实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、实验目的通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。二、实验内容基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。1、最佳淘汰算法（OPT）2、先进先出的算法（FIFO）3、最近最久未使用算法（LRU）4、简单时钟(钟表)算法（CLOCK）命中率＝１－页面失效次数／页地址流(序列)长度三、实验原理UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分

2、配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。为实现请求调页，核心配置了四种数据结构：页表、页帧（框）号、访问位、修改位、有效位、保护位等。当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内

3、存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。四、算法描述本实验的程序设计基本上按照实验内容进行。即使用srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。（1）通过随机数产生一个指令序列，共3

4、20条指令。指令的地址按下述原则生成：A：50%的指令是顺序执行的B：25%的指令是均匀分布在前地址部分C：25%的指令是均匀分布在后地址部分具体的实施方法是：A：在[0，319]的指令地址之间随机选取一起点mB：顺序执行一条指令，即执行地址为m+1的指令C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’D：顺序执行一条指令，其地址为m’+1E：在后地址[m’+2，319]中随机选取一条指令并执行F：重复步骤A-E，直到320次指令（2）将指令序列变换为页地址流设：页面大小为1K；

5、用户内存（页帧）容量为4页~32页；用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条-第9条指令为第0页（对应虚存地址为[0，9]）第10条-第19条指令为第1页（对应虚存地址为[10，19]）………………………………第310条-第319条指令为第31页（对应虚存地址为[310，319]）按以上方式，用户指令可组成32页。一、算法实现与分析1.常量及变量#definetotal_instruction320//指令流长#definetot

6、al_vp32//虚页长#defineclear_period50//清周期pfc_typepfc[total_vp],//主存区页面控制结构数组pfc_type*freepf_head,//主存区页面控制结构的空闲页面头指针pfc_type*busypf_head,//主存区页面控制结构的忙页面头指针pfc_type*busypf_tail;//主存区页面控制结构的忙页面尾指针intdiseffect;//页错误计数器，初次把页面载入主存时也当做页错误pl_typepl[total_vp];//页面

7、结构数组2.数据结构typedefstruct//页面结构{intpn,//页面序号pfn,//页面所在内存区的帧号counter,//单位时间内访问次数time;//上次访问的时间}pl_type;structpfc_struct{//页面控制结构，模拟内存中的页集intpn,//页面号pfn;//内存区页面的帧号structpfc_struct*next;//页面指针，用于维护内存缓冲区的链式结构};3.函数定义intinitialize(int);//初始化页面结构数组和页面控制结构数组intF

8、IFO(int);//先进先出算法intLRU(int);//最近最久未使用算法intOPT(int);//最佳置换算法intCLOCK(int);//简单时钟(钟表)算法一、实验结果分析理论上，四种替换算法的命中率由高到底排列应该是OPT>LRU>CLOCK>FIFO。实际上，从实验数据观测得到，存在这种由高到低的趋势，由page=4时可以观测到，但是效果不是很明显。效果不明显的原因：推测与指令流的产生方式有关系。因为指令流的产生方式要能体现局部性原理