操作系统实验报告页面置换

1、实验三 内存页面置换算法的设计l 实习内容设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换： 1. 先进先出的算法（FIFO）2. 最近最久未使用算法（LRU）3. 最佳置换算法（OPT）l 实习目的本实习要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的技术特点，掌握请求页式存储管理的页面置换算法。LINUX中，为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其一部分（段或页）调入内存便可运行，还支持请求调页的存储管理方式。当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（

2、向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。 当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。l 实习原理算法思想：1先进先出(FIFO)置换算法的思路该算法总是淘汰最先进入内存的页

3、面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。2最近久未使用(LRU)置换算法的思路最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。3.最佳（OPT）置换算法的思路其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。l 实习编程思路和流程数据结构s

4、truct pageInforint content;/页面号int timer;/被访问标记;class PRApublic: PRA(void);int findSpace(void); /查找是否有空闲内存int findExist(int curpage); /查找内存中是否有该页面int findReplace(void); /查找应予置换的页面void display(void); /显示void FIFO(void); /FIFO算法void LRU(void); /LRU算法void BlockClear(void);/BLOCK清空，以便用另一种方法重新演示pageInfor

5、 * block; /物理块pageInfor * page; /页面号串private:;Ø FIFO页面置换算法当需要访问一个新的页面时，首先调用findExist(i)函数来查看物理块中是否就有这个页面，若要查看的页面物理块中就有，则调用display函数直接显示，不需要替换页面；如果要查看的页面物理块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；若没有空闲物理块，则调用findReplace函数替换页面。并将物理块中所有页面timer+。Ø LRU页面置换算法当需要访问一个新的页面时，首先调用findExist(i)函数来查看物理块中是否就有这

6、个页面Ø OPT页面置换算法当需要访问一个新的页面时，也首先调用findExist(i)函数来查看物理块中是否就有这个页面寻找应予置换页面函数findReplace比较三个物理块中的时间标记timer，找到时间最久的。开始取一条指令取指令中访问的页号=>L查 页 表页标记=1？形成绝对地址是“存”指令？置L页修改标记“1”输出绝对地址输出“*页号”有后继指令？取一条指令结 束J:=PkJ页的修改标记=1？输出“OUTj”输出“INL”Pk:=L k:=(k+1) mod m修改页面是否是否否（产生缺页中断）是否程序流程图l 源程序结构分析程序结构程序共有以下九个部分：int f

7、indSpace(void);/查找是否有空闲内存int findExist(int curpage);/查找内存中是否有该页面int findReplace(void);/查找应予置换的页面void display(void);/显示void FIFO(void);/FIFO算法void LRU(void);/LRU算法void OPT(void);/OPT算法；void BlockClear(void);/BLOCK清空，以便用另一种方法重新演示int main() /主程序10 / 10文档可自由编辑打印Ø 源程序代码#include <iostream.h>#de

8、fine Bsize 3#define Psize 20struct pageInforint content;/页面号int timer;/被访问标记;class PRApublic: PRA(void);int findSpace(void);/查找是否有空闲内存int findExist(int curpage);/查找内存中是否有该页面int findReplace(void);/查找应予置换的页面void display(void);/显示void FIFO(void);/FIFO算法void LRU(void);/LRU算法void Optimal(void);/OPTIMAL算法

9、void BlockClear(void);/BLOCK恢复pageInfor * block;/物理块pageInfor * page;/页面号串private:;PRA:PRA(void)int QString20=7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1; block = new pageInforBsize;for(int i=0; i<Bsize; i+) blocki.content = -1; blocki.timer = 0;page = new pageInforPsize;for(i=0; i<Psize; i+) page

10、i.content = QStringi; pagei.timer = 0;int PRA:findSpace(void)for(int i=0; i<Bsize; i+) if(blocki.content = -1) return i;/找到空闲内存，返回BLOCK中位置return -1;int PRA:findExist(int curpage)for(int i=0; i<Bsize; i+) if(blocki.content = pagecurpage.content) return i;/找到内存中有该页面，返回BLOCK中位置return -1;int PRA:f

11、indReplace(void)int pos = 0;for(int i=0; i<Bsize; i+) if(blocki.timer >= blockpos.timer) pos = i;/找到应予置换页面，返回BLOCK中位置return pos;void PRA:display(void)for(int i=0; i<Bsize; i+) if(blocki.content != -1) cout<<blocki.content<<" "cout<<endl;void PRA:Optimal(void)int

12、exist,space,position ;for(int i=0; i<Psize; i+) exist = findExist(i); if(exist != -1) cout<<"不缺页"<<endl; else space = findSpace(); if(space != -1) blockspace = pagei; display(); else for(int k=0; k<Bsize; k+) for(int j=i; j<Psize; j+) if(blockk.content != pagej.content

13、) blockk.timer = 1000; /将来不会用，设置TIMER为一个很大数 else blockk.timer = j; break; position = findReplace(); blockposition = pagei; display(); void PRA:LRU(void)int exist,space,position ;for(int i=0; i<Psize; i+) exist = findExist(i); if(exist != -1) cout<<"不缺页"<<endl; blockexist.tim

14、er = -1;/恢复存在的并刚访问过的BLOCK中页面TIMER为-1 else space = findSpace(); if(space != -1) blockspace = pagei; display(); else position = findReplace(); blockposition = pagei; display(); for(int j=0; j<Bsize; j+) blockj.timer+;void PRA:FIFO(void)int exist,space,position ;for(int i=0; i<Psize; i+) exist =

15、findExist(i); if(exist != -1) cout<<"不缺页"<<endl; else space = findSpace(); if(space != -1) blockspace = pagei; display(); else position = findReplace(); blockposition = pagei; display(); for(int j=0; j<Bsize; j+) blockj.timer+;/BLOCK中所有页面TIMER+void PRA:BlockClear(void)for(in

16、t i=0; i<Bsize; i+) blocki.content = -1; blocki.timer = 0;void main(void)cout<<"|-页 面 置 换 算 法-|"<<endl;cout<<"|-power by wangxinchuang(080501228)-|"<<endl;cout<<"|-|"<<endl; cout<<"页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,

17、1,7,0,1"<<endl;cout<<"-"<<endl;cout<<"选择<1>应用Optimal算法"<<endl;cout<<"选择<2>应用FIFO算法"<<endl;cout<<"选择<3>应用LRU算法"<<endl;cout<<"选择<0>退出"<<endl;int select;PRA t

18、est;while(select) cin>>select; switch(select) case 0: break; case 1: cout<<"Optimal算法结果如下:"<<endl; test.Optimal(); test.BlockClear(); cout<<"-"<<endl; break; case 2: cout<<"FIFO算法结果如下:"<<endl; test.FIFO(); test.BlockClear(); cout<<"-"<<endl; break; case 3: cout<<"LRU算法结果如下