页面置换算法的模拟

1、课程设计报告课程名称：操作系统实验题目：页面置换算法的模拟日期：2010.07.01目录一、课程设计分析1二、相关知识1三、功能设计分析2四、程序设计2五、运行截图4六、参考程序6七、结果分析14八、心得体会14一、课程设计分析编写程序实现页面置换算法中常用的FIFO、LRU。FIFO页面置换算法：FIFO淘汰算法是最先使用的页面最先被淘汰。该算 法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。先进先出(FIFO)页面置换算法，是根据页面调入内存

2、后的使用情况进行决策的。该算法是选择在内存中驻留时间最久的页面予以淘汰。该算法赋于请求调入页面一个空间（工作集），淘汰掉最先调入的页，取而代之的是紧随它进来的页，这样就基本上实现了对最先进入内存的页面的淘汰。 LRU页面置换算法：该算法淘汰的页面是在最近一段时间里较久未被访问的那一页，它是根据程序执行时的局部性原理而设计的。二、相关知识1虚拟存储器的引入 局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。2虚拟存储器的定义 虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一

3、种存储器系统。3虚拟存储器的实现方式 分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。 请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。4页面分配 平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。 考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。5页面置换算法 先进先出页面置换算法，该算法总是淘汰最先进入内存的页面，即选择

4、在内存中驻留时间催久的页面予以淘汰。6最近最久未使用LRU置换算法个页面时，选择现有页面中T最大的，即最近最久未使用的页面予以淘汰三、功能设计分析在掌握基本的算法理论原理的基础上，能够选取合适的语言和开发工具，编写程序将虚拟存储管理中页面置换算法的机制动态的演示出来。具体功能主要包括：数据结构的定义：采用合适的数据结构描述页表；页面置换：采用选定的页面置换算法来模拟管理页表中页的置换过程；界面设计：要求有图形界面，能够直观的了解页面置换的过程，能够给出当前被置换出的页号，以及总的缺页次数。四、程序设计FIFO页面置换算法：4*4*4*3*3*3300011 定义一个二维数组，行数表示系统分配给

5、该作业的页架数，列数表示作业的页面访问序列的次数。算法可以设计：二维数组中每列的第一个数字表示的页面是当前最先进入主存的页面，意思就是说如果发生缺页中断，就应该将该页面移出，方法是将本列下面的两个数据前移，然后将移入的页面置入本列最后的位置。算法的伪代码描述形式：while (I页面访问序列的次数) if(要访问的页面在当前第I列中)不做任何处理，该列内容保持不变；else (要访问的页面不在当前第I列中)做页面置换处理；打印二维数组中的内容。 LRU页面置换算法：4*44303*3010*1*3* 定义一个二维数组，行数表示系统分配给该作业的页架数，列数表示作业的页面访问序列的次数。算法可以

6、设计：二维数组中每列的第一个数字表示的页面是当前最近最少用的页面，意思就是说如果发生缺页中断，就应该将该页面移出，方法是将本列下面的两个数据前移，然后将移入的页面置入本列最后的位置。算法的伪代码描述形式：while (I页面访问序列的次数) if(要访问的页面在当前第I列中)将该页面前移至该列最后一个位置，其余页面数字向前移动一位；else (要访问的页面不在当前第I列中)做页面置换处理；打印二维数组中的内容。五、运行截图六、参考程序#include #define Bsize 3#define Psize 20struct pageInforint content; /页面号int time

7、r; /被访问标记;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 *

8、 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; i

9、Bsize; 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中位置

10、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

11、();elsefor(int k=0; kBsize; k+)for(int j=i; jPsize; j+)if(blockk.content != pagej.content) blockk.timer = 1000; /将来不会用，设置TIMER为一个很大数elseblockk.timer = j;break;position = findReplace(); blockposition = pagei; display();void PRA:LRU(void)int exist,space,position ;for(int i = 0; i Psize; i+)exist = fin

12、dExist(i);if(exist != -1)cout不缺页endl;blockexist.timer = -1;/恢复存在的并刚访问过的BLOCK中页面TIMER为-1else space = findSpace();if(space != -1)blockspace = pagei; display();elseposition = findReplace();blockposition = pagei; display();for(int j=0; jBsize; j+)blockj.timer+;void PRA:FIFO(void)int exist,space,position

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

14、Bsize; i+)blocki.content = -1;blocki.timer = 0;void main(void)cout|-页 面 置 换 算 法-|endl;cout| |endl;cout|- -|endl;cout| |endl;cout|-|endl; cout| |endl;cout|页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1|endl;cout| |endl;cout|-|endl;cout选择应用LRU算法endl;cout选择应用FIFO算法endl;cout选择应用Optimal算法endl;cout选择退出sel

15、ect;switch(select)case 0:break;case 1:coutLRU算法结果如下:endl;test.LRU();test.BlockClear();cout-endl;break;case 2:coutFIFO算法结果如下:endl;test.FIFO();test.BlockClear();cout-endl;break;case 3: coutOptimal算法结果如下:endl;test.Optimal();test.BlockClear();cout-endl;break;default:cout请输入正确功能号endl;break;七、结果分析程序可以设计为动

16、态输入作业的页面访问序列，或将二维数组设计为动态数组，这样可以通过调整页面访问序列的次数或系统分配给作业的页架数，考察对缺页中断率的影响。八、心得体会通过两周的课程设计,加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对虚拟存储,页面置换有了深入的了解,并能够用高级语言进行模拟演示。在这短短的两周时间里，通过浏览、阅读有关的资料，学到了很多东西，同时也发现仅仅书本的知识是远远不够的，需要把知识运用到实践中去，能力才能得到提高。有如下几点体会： 1通过查阅相关资料对VC编程工具有了一定的了解，基本掌握了VC+ MFC应用程序编写的基本方法。2使用MFC可视化编程极大的减少了

17、编写的代码量，直观的界面设计，不但便于修改，而且简化了界面程序代码的编写，便于集中精力到主算法的编写上。 3两种页面置换算法FIFO和LRU理解起来相当容易，但在实际编程实现的时候需要注意各种细节，需要耐心细致，实际编程中遇到一些细节上的小问题确实需要仔细考虑才行。 4. 因为需要用户输入后才能知道实际内存块和最大页面数的大小，所以用到了动态数组函数CArray，在LRU算法中时间权值数组myb是关键，必须与页面变化同步。 另外，使我体会最深的是：任何一门知识的掌握，仅靠学习理论知识是远远不够的，要与实际动手操作相结合才能达到功效。通过这次的课程设计使自己的VC编程能力加强了不少，对页面置换有更深一层的了解。使我对操作系统特别是页面置换这一部分的认识有了很大的加深。一分耕耘，一分收获，这次的