实验3-页面调度算法.doc

.实验报告院 （系）： 专业班级： 学 号: 姓 名: 实验地点: 实验日期: 课程名称实验项目名称实验学时实验类型计算机操作系统页面调度算法2验证型一、实验目的及要求通过本实验可以加深理解有关虚拟存储器的工作原理，进一步体会和了解页面替换算法的具体实现方法。二、实验环境PC /Windows系统/Visual C+6.0三、实验内容 实现三种算法：先进先出；OPT；LRU 页面序列从指定的文本文件（TXT文件）中取出 输出：第一行：每次淘汰的页面号，第二行：显示缺页的总次数四、实验步骤 1先进先出(FIFO)置换算法的思路该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。2最近久未使用(LRU)置换算法的思路最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。3.最佳（OPT）置换算法的思路其所选择的被淘汰的页面，将是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。 4、流程图如下图所示：开始取一条指令取指令中访问的页号=L查 页 表页标记=1？形成绝对地址是“存”指令？置L页修改标记“1”输出绝对地址输出“*页号”有后继指令？取一条指令结 束J:=PkJ页的修改标记=1？输出“OUTj”输出“INL”Pk:=L k:=(k+1) mod m修改页面是否是否否（产生缺页中断）是否五、调试过程程序结构分析：程序共有以下九个部分：int findSpace(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() /主程序六、实验结果及分析程序源代码：#include #define 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算法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; iBsize; i+) blocki.content = -1; blocki.timer = 0;page = new pageInforPsize;for(i=0; iPsize; i+) pagei.content = QStringi; pagei.timer = 0;int PRA:findSpace(void)for(int i=0; iBsize; i+) if(blocki.content = -1) return i;/找到空闲内存，返回BLOCK中位置return -1;int PRA:findExist(int curpage)for(int i=0; iBsize; i+) if(blocki.content = pagecurpage.content) return i;/找到内存中有该页面，返回BLOCK中位置return -1;int PRA:findReplace(void)int pos = 0;for(int i=0; i= blockpos.timer) pos = i;/找到应予置换页面，返回BLOCK中位置return pos;void PRA:display(void)for(int i=0; iBsize; i+) if(blocki.content != -1) coutblocki.content ;coutendl;void PRA:Optimal(void)int exist,space,position ;for(int i=0; iPsize; i+) exist = findExist(i); if(exist != -1) cout不缺页endl; else space = findSpace(); if(space != -1) blockspace = pagei; display(); else for(int k=0; kBsize; k+) for(int j=i; jPsize; j+) if(blockk.content != pagej.content) 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; iPsize; i+) exist = findExist(i); if(exist != -1) cout不缺页endl; blockexist.timer = -1;/恢复存在的并刚访问过的BLOCK中页面TIMER为-1 else space = findSpace(); if(space != -1) blockspace = pagei; display(); else position = findReplace(); blockposition = pagei; display(); for(int j=0; jBsize; j+) blockj.timer+;void PRA:FIFO(void)int exist,space,position ;for(int i=0; iPsize; i+) exist = 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; jBsize; j+) blockj.timer+;/BLOCK中所有页面TIMER+void PRA:BlockClear(void)for(int i=0; iBsize; i+) blocki.content = -1; blocki.timer = 0;void main(void)cout|-页 面 置 换 算 法-|endl;cout|-power by kangyan(1318064008)-|endl;cout|-|endl; cout页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1endl;cout-endl;cout选择应用Optimal算法endl;cout选择应用FIFO算法endl;cout选择应用LRU算法endl;cout选择退出select; switch(select) case 0: break; case 1: coutOptimal算法结果如下:endl; test.Optimal(); test.BlockClear(); cout-endl; break; case 2: coutFIFO算法结果如下:endl; test.FIFO(); test.BlockClear(); cout-endl; break; case 3: coutLRU算法结果如下:endl; test.LRU(); test.BlockClear(); cout-endl; break; default: cout请输入正确功能号endl; break; 实验截图如下图所示：键入1选择运行LRU算法的置换初始化信息：3个页块，20个页面号引用串存入前三个页，有空闲内存，无需置换3，4页已经在内存中无需再写入因为3是最久的页面所以将其置换下面原理相同所有命中的页面数命中率0.5七、总结页面置换算法的思想可以说比较简单，易懂，但是在实现的时候，也遇到了很多的问题，比如说