文档介绍：实验三 内存页面置换算法的设计实****内容设计一个虚拟存储区和内存工作区,并使用下述算法来模拟实现页面的置换:      (FIFO)(LRU)(OPT)实****目的本实****要求学生通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的技术特点,掌握请求页式存储管理的页面置换算法。LINUX中,为了提高内存利用率,提供了内外存进程对换机制,内存空间的分配和回收均以页为单位进行,一个进程只需将其一部分(段或页)调入内存便可运行,还支持请求调页的存储管理方式。当进程在运行中需要访问某部分程序和数据时,发现其所在页面不在内存,就立即提出请求(向CPU发出缺中断),由系统将其所需页面调入内存。这种页面调入方式叫请求调页。当CPU接收到缺页中断信号,中断处理程序先保存现场,分析中断原因,转入缺页中断处理程序。该程序通过查找页表,得到该页所在外存的物理块号。如果此时内存未满,能容纳新页,则启动磁盘I/O将所缺之页调入内存,然后修改页表。如果内存已满,则须按某种置换算法从内存中选出一页准备换出,是否重新写盘由页表的修改位决定,然后将缺页调入,修改页表。利用修改后的页表,去形成所要访问数据的物理地址,再去访问内存数据。整个页面的调入过程对用户是透明的。实****原理——算法思想:(FIFO)置换算法的思路该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单,只需把一个进程已调入内存的页面,按照先后次序连接成一个队列,并设置一个替换指针,使它总指向最老的页面。(LRU)置换算法的思路最近久未使用置换算法的替换规则,是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间,当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。(OPT)置换算法的思路其所选择的被淘汰的页面,奖是以后不使用的,或者是在未来时间内不再被访问的页面,采用最佳算法,通常可保证获得最低的缺页率。实****编程思路和流程——数据结构structpageInfor{intcontent;//页面号inttimer;//被访问标记};classPRA{public:PRA(void);intfindSpace(void); //查找是否有空闲内存intfindExist(intcurpage); //查找内存中是否有该页面intfindReplace(void); //查找应予置换的页面voiddisplay(void); //显示voidFIFO(void); //FIFO算法voidLRU(void); //LRU算法voidBlockClear(void);//BLOCK清空,以便用另一种方法重新演示pageInfor*block; //物理块pageInfor*page; //页面号串private:};?FIFO页面置换算法当需要访问一个新的页面时,首先调用findExist(i)函数来查看物理块中是否就有这个页面,若要查看的页面物理块中就有,则调用display函数直接显示,不需要替换页面;如果要查看的页面物理块中没有,就需要寻找空闲物理块放入,若存在有空闲物理块,则将页面放入;若没有空闲物理块,则调用findReplace函数替换页面。并将物理块中所有页面timer++。?LRU页面置换算法当需要访问一个新的页面时,首先调用findExist(i)函数来查看物理块中是否就有这个页面?OPT页面置换算法当需要访问一个新的页面时,也首先调用findExist(i)函数来查看物理块中是否就有这个页面寻找应予置换页面函数findReplace比较三个物理块中的时间标记timer,找到时间最久的。程序流程图源程序结构分析——程序结构程序共有以下九个部分:intfindSpace(void);//查找是否有空闲内存intfindExist(intcurpage);//查找内存中是否有该页面intfindReplace(void);//查找应予置换的页面voiddisplay(void);//显示voidFIFO(void);//FIFO算法voidLRU(void);//LRU算法voidOPT(void);//OPT算法;voidBlockClear(void);//BLOCK清空,以便用另一种方法重新演示intmain() //主程序?源程序代码#include<>#defineBsize3#definePsize20structpageInfor{intcontent;//页面号inttimer;//被访问标记};classPRA{public:PRA(void);in