操作系统实验三.doc

成绩：实 验 报 告课程名称：操作系统实验项目：页面置换算法姓 名：专 业：计算机科学与技术班 级：学 号：计算机科学与技术学院2017年05月25日实验项目名称： 页面置换算法 一、实验目的1通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。2掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。3通过对几种置换算法页面的比较，来对比他们的优缺点，并通过比较更换频率来对比它们的效率。二、实验内容设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换：1. 先进先出的算法（FIFO）2. 最近最久未使用算法（LRU）3. 最佳置换算法（OPT）三、实验原理在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。一个好的页面置换算法，应该有较低的页面更换频率。假设分给一作业的物理块数为3 ，页面数为20个。页面号为(20个)：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，11先进先出(FIFO)置换算法的思路该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。2最近久未使用(LRU)置换算法的思路最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。3.最佳（OPT）置换算法的思路其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。4数据结构struct 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 * block; /物理块pageInfor * page; /页面号串private:;5FIFO页面置换算法当需要访问一个新的页面时，首先调用findExist(i)函数来查看物理块中是否就有这个页面，若要查看的页面物理块中就有，则调用display函数直接显示，不需要替换页面；如果要查看的页面物理块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；若没有空闲物理块，则调用findReplace函数替换页面。并将物理块中所有页面timer+。6LRU页面置换算法 当需要访问一个新的页面时，首先调用findExist(i)函数来查看物理块中是否就有这个页面。7. OPT页面置换算法当需要访问一个新的页面时，也首先调用findExist(i)函数来查看物理块中是否就有这个页面。8寻找应予置换页面函数findReplace比较三个物理块中的时间标记timer，找到时间最久的。四、源程序分析1 程序结构程序共有以下九个部分：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() /主程序2 源程序代码#include #define Bsize 3#define Psize 20using namespace std;struct pageInfor int content;/页面号 int timer;/被访问标记;class PRA public: 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(int 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; int 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,1,7,0,1endl; cout-endl; cout选择 1 应用Optimal算法endl; cout选择 2 应用FIFO算法endl; cout选择 3 应用LRU算法endl; cout选择 0 退出select; switch(select) case 0: break; case 1: coutOptimal算法结果如下:endl; test.Optimal(); test.BlockClear(); cout-endl; break; case 2: coutFIFO算法结果如