范文一:页面置换算法的实现
题目5 页面置换算法的实现
5.1 题目的主要研究内容及预期达到的目标
(1)该程序模拟操作系统常用的页面置换算法;
A 、最佳置换算法(OPT )
B 、先进先出置换算法(FIFO )
C 、最近最久未使用置换算法(LRU )
(2)理解页面置换算法相关内容;
(3)掌握页面置换算法主要流程;
(4)掌握常用页面置换算法的实现过程。
5.2 题目研究的工作基础或实验条件
(1)硬件环境:装有Linux 操作系统(虚拟机)的计算机一台。
(2)软件环境:vim 编辑器、Visual C++。
5.3 设计思想
(1)页面的随机生成
使用rand ()函数随机产生页面号,用数组装入页面号,模拟页面调入内存中发生页面置换的过程。整个过程,都是使用数组来实现每个算法,模拟队列,模拟堆栈的功能,实现每一个置换算法。
(2)先进先出(FIFO)置换算法的思路
该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单,只需把一个进程已调入内存的页面,按照先后次序连接成一个队列,并设置一个替换指针,使它总指向最老的页面。
(3)最近久未使用(LRU)置换算法的思路
最近久未使用置换算法的替换规则,是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间,当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。
(4)最佳(OPT )置换算法的思路
其所选择的被淘汰的页面,奖是以后不使用的,或者是在未来时间内不再
被访问的页面,采用最佳算法,通常可保证获得最低的缺页率
5.4 流程图
图5-1 最佳置换算法(OPT )流程图
图5-2 先进先出置换算法(FIFO )
图5-3 最近最久未使用置换算法(LRU )
5.5 主要程序代码
#include #include using namespace std; intconstInsideCount=6;//内存中存放的页面数 int count=0; //用来记录已存放的页面数 int Inside[InsideCount]; //存放内存中的页号 intconstPageCount=10;//总的页面数 int Page[PageCount]; //存放产生的页面号 int insert=0;//先到先出置换算法fcfo 中表示当内存满的时候,新进入的页号放的位置 intsuiji=0; //随机置换算法randchange 当内存满的时候,新进入的页号放的位置 double lost=0.0; //缺失次数 boolisInside(intnum)//检测页号是否在内存中 { for(int i=0;i<> { if(Inside[i]==Page[num]) { return true; } } return false; } void LRU(intnum)//近久未使用置换算法 LRU { int max=0; // 表示内存中的页号,下一次出现的距离 intmaxchange; //表示内存中下次出现距离大的页号在内存中的位置 int k; if(isInside(num)) //判断是否命中 { cout<><> for(int i=0;i<> cout<<"内存><"内存><><><><> } else if(count==InsideCount) { lost++; //缺失次数+1 for(int j=0; j<> { for(k=num;k>0;k--) //从当前的页号向前,发现页号与内存中的页号相同,break ;比较内存中InsideCount 个页号,哪一个走的远,用 max 记录 { if(Inside[j]==Page[k]) break; } if(num-k>max)//求最旧未使用 { max=num-k; maxchange=j;//j 表示把内存中第 j 个 Inside 中的页面从内存拿出,把新的页面放入 } } Inside[maxchange] = Page[num]; for(int i=0;i<> cout<<" 内存=""><"><><><><> } else { Inside[count] = Page[num]; count++; for(int i=0;i<> cout<<" 内存=""><"><><><><> } } void FIFO(intnum)//先进先出置换算法(FIFO ): { if(isInside(num)) //判断是否命中 { cout<><> for(int i=0;i<> cout<<" 内存=""><"><><><><> } else if(count==InsideCount) //内存是否已满 { lost++; //缺页+1 Inside[insert]=Page[num]; //页面放入内存 insert++; //位置移到下一个 insert=insert%InsideCount; //保证循环 for(int i=0;i cout<<" 内存=""><"><><><><> } else //没命中且没满 { Inside[count]=Page[num]; count++; for(int i=0;i<> cout<<" 内存=""><"><><><><> } } void OPT(intnum)//最佳置换算法(OPT )(理想置换算法) { int max=0; // 表示内存中的页号,下一次出现的距离 intmaxchange; //表示内存中下次出现距离大的页号在内存中的位置 int k; if(isInside(num)) { cout<><> for(int i=0;i<> cout<<" 内存=""><"><><><><> } else if(count==InsideCount) { lost++; //缺页+1 for(int j=0;j<> { for(k=num;k { if(Inside[j]==Page[k]) break; } if(k>max) { max=k; //k 表示在这个地方会再次出现给定页面 maxchange=j;//j 表示把内存中第 j 个 Inside 中的页面从内存拿出,把新的页面放入 } } Inside[maxchange]=Page[num]; for(int i=0;i<> cout<<" 内存=""><"><><><><> } else //没命中且没满 { Inside[count]=Page[num]; count++; for(int i=0;i<> cout<<" 内存=""><"><><><><> } } int main() { char ch ;//选择使用哪种算法 while(1){ for(int i=0;i<> { Page[i]=rand()%9+1; } cout<<" 请选择置换算法=""><"><><> cout<<"o 最佳置换算法(opt=""><"o><> cout<<"u 近久未使用(lru=""><"u><><> cin>>ch; switch(ch){ case 'O':{ lost=0; count=0; for(int j=0;j<> { Inside[j]=0; } for(int i=0;i<> { cout<<"读入><"读入><><><><> OPT(i); } cout<><><<"次><"次><<"缺失><"缺失><><<"><"> } break; case 'F':{ lost=0; count=0; for(int j=0;j<> { Inside[j]=0; } for(int i=0;i<> { cout<<"读入><"读入><><><><> FIFO(i); } cout<<"共"><"共"><><<"次><"次><<"缺失><"缺失><><<"><"> } break; case 'U':{ lost=0; count=0; for(int j=0;j<> { Inside[j]=0; } for(int i = 0; i { 课程设计报告 课程名称:操作系统 实验题目:页面置换算法的模拟 日期:2010.07.01 目录 一、课程设计分析 .............................................................................................................................. 1 二、相关知识 ...................................................................................................................................... 1 三、功能设计分析 .............................................................................................................................. 2 四、程序设计 ...................................................................................................................................... 2 五、运行截图 ...................................................................................................................................... 4 六、参考程序 ...................................................................................................................................... 6 七、结果分析 .................................................................................................................................... 14 八、心得体会 .................................................................................................................................... 14 一、课程设计分析 编写程序实现页面置换算法中常用的FIFO、LRU。 FIFO页面置换算法:FIFO淘汰算法是最先使用的页面最先被淘汰。该算 法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。先进先出(FIFO)页面置换算法,是根据页面调入内存后的使用情况进行决策的。该算法是选择在内存中驻留时间最久的页面予以淘汰。该算法赋于请求调入页面一个空间(工作集),淘汰掉最先调入的页,取而代之的是紧随它进来的页,这样就基本上实现了对最先进入内存的页面的淘汰。 LRU页面置换算法:该算法淘汰的页面是在最近一段时间里较久未被访问的那一页,它是根据程序执行时的局部性原理而设计的。 二、相关知识 1.虚拟存储器的引入 局部性原理:程序在执行时在一较短时间内仅限于某个部分;相应的,它所访问的存储空间也局限于某个区域,它主要表现在以下两个方面:时间局限性和空间局限性。 2.虚拟存储器的定义 虚拟存储器是只具有请求调入功能和置换功能,能从逻辑上对内存容量进行扩充的一种存储器系统。 3.虚拟存储器的实现方式 分页请求系统,它是在分页系统的基础上,增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。 请求分段系统,它是在分段系统的基础上,增加了请求调段及分段置换功能后,所形成的段式虚拟存储系统。 4.页面分配 平均分配算法,是将系统中所有可供分配的物理块,平均分配给各个进程。 按比例分配算法,根据进程的大小按比例分配物理块。 考虑优先的分配算法,把内存中可供分配的所有物理块分成两部分:一部分按比例地分配给各进程;另一部分则根据个进程的优先权,适当的增加其相应份额后,分配给各进程。 5.页面置换算法 先进先出页面置换算法,该算法总是淘汰最先进入内存的页面,即选择在内存中驻 留时间催久的页面予以淘汰。 6.最近最久未使用LRU置换算法 个页面时,选择现有页面中T最大的,即最近最久未使用的页面予以淘汰 三、功能设计分析 在掌握基本的算法理论原理的基础上,能够选取合适的语言和开发工具,编写程序将虚拟存储管理中页面置换算法的机制动态的演示出来。具体功能主要包括: ①数据结构的定义:采用合适的数据结构描述页表; ②页面置换:采用选定的页面置换算法来模拟管理页表中页的置换过程; ③界面设计:要求有图形界面,能够直观的了解页面置换的过程,能够给出当前被置换出的页号,以及总的缺页次数。 四、程序设计 ①FIFO页面置换算法: √ √ √ √ 定义一个二维数组,行数表示系统分配给该作业的页架数,列数表示作业的页面访问序列的次数。算法可以设计:二维数组中每列的第一个数字表示的页面是当前最先进入主存的页面,意思就是说如果发生缺页中断,就应该将该页面移出,方法是将本列下面的两个数据前移,然后将移入的页面置入本列最后的位置。 算法的伪代码描述形式: while (I if(要访问的页面在当前第I列中) 不做任何处理,该列内容保持不变; else (要访问的页面不在当前第I列中) 做页面置换处理;} 打印二维数组中的内容。 ② LRU页面置换算法: √ √ √ √ 定义一个二维数组,行数表示系统分配给该作业的页架数,列数表示作业的页面访问序列的次数。算法可以设计:二维数组中每列的第一个数字表示的页面是当前最近最少用的页面,意思就是说如果发生缺页中断,就应该将该页面移出,方法是将本列下面的两个数据前移,然后将移入的页面置入本列最后的位置。 算法的伪代码描述形式: while (I if(要访问的页面在当前第I列中) 将该页面前移至该列最后一个位置,其余页面数字向前移动一位; else (要访问的页面不在当前第I列中) 做页面置换处理;} 打印二维数组中的内容。 五、运行截图 六、参考程序 #include #define Bsize 3 #define Psize 20 struct pageInfor { }; class PRA { public: PRA(void); int content; //页面号 int timer; //被访问标记 int findSpace(void); //查找是否有空闲内存 int findExist(int curpage); //查找内存中是否有该页面 int findReplace(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 QString[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}; block = new pageInfor[Bsize]; } int PRA::findSpace(void) { for(int i=0; i if(block[i].content == -1) for(int i=0; i page = new pageInfor[Psize]; for(i=0; i page[i].content = QString[i]; page[i].timer = 0; block[i].content = -1; block[i].timer = 0; } return -1; int PRA::findExist(int curpage) { } int PRA::findReplace(void) { } void PRA::display(void) { } void PRA::Optimal(void) { for(int i=0; i if(block[i].content != -1) cout int pos = 0; for(int i=0; i if(block[i].timer >= block[pos].timer) pos = i;//找到应予置换页面,返回BLOCK中位置 for(int i=0; i if(block[i].content == page[curpage].content) return i;//找到内存中有该页面,返回BLOCK中位置 return -1; return pos; cout for(int i=0; i else { } block[k].timer = j; break; } } } } position = findReplace(); block[position] = page[i]; display(); void PRA::LRU(void) { int exist,space,position ; for(int i = 0; i } else { space = findSpace(); if(space != -1) { } else block[space] = page[i]; display(); } } } } position = findReplace(); block[position] = page[i]; display(); for(int j=0; j void PRA::FIFO(void) { int exist,space,position ; for(int i=0; i } } } } display(); for(int j=0; j void PRA::BlockClear(void) { } void main(void) { cout cout cout cout cout |" cout cout cout cout应用LRU算法"应用FIFO算法"应用Optimal算法"退出">select; switch(select) { case 0: break; case 1: cout } } test.FIFO(); test.BlockClear(); cout 七、结果分析 程序可以设计为动态输入作业的页面访问序列,或将二维数组设计为动态数组,这样可以通过调整页面访问序列的次数或系统分配给作业的页架数,考察对缺页中断率的影响。 八、心得体会 通过两周的课程设计,加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对虚拟存储,页面置换有了深入的了解,并能够用高级语言进行模拟演示。在这短短的两周时间里,通过浏览、阅读有关的资料,学到了很多东西,同时也发现仅仅书本的知识是远远不够的,需要把知识运用到实践中去,能力才能得到提高。有如下几点体会: 1.通过查阅相关资料对VC编程工具有了一定的了解,基本掌握了VC++ MFC 应用程序编写的基本方法。 2.使用MFC可视化编程极大的减少了编写的代码量,直观的界面设计,不但 便于修改,而且简化了界面程序代码的编写,便于集中精力到主算法的编写上。 3.两种页面置换算法FIFO和LRU理解起来相当容易,但在实际编程实现的时 候需要注意各种细节,需要耐心细致,实际编程中遇到一些细节上的小问题确实需要仔细考虑才行。 4. 因为需要用户输入后才能知道实际内存块和最大页面数的大小,所以用到 了动态数组函数CArray,在LRU算法中时间权值数组myb是关键,必须与页面变化同步。 另外,使我体会最深的是:任何一门知识的掌握,仅靠学习理论知识是远远不够的,要与实际动手操作相结合才能达到功效。 通过这次的课程设计使自己的VC编程能力加强了不少,对页面置换有更深一层的了解。使我对操作系统特别是页面置换这一部分的认识有了很大的加深。一分耕耘,一分收获,这次的课程设计让我受益匪浅。虽然自己所做的很少也不够完善,但毕竟也是努力的结果。主要有以下几点收获: 1. 通过对上网和看书查阅相关资料,使自己对VC MFC语言的基本框架 有新的了解,加深了对可视化程序的认识。 2. 在使用VC语言来实现功能时,不像以往用的其他语言,它比较简练, 更容易理解,实用性很强。 3. 先进先出页面置换和LRU算法两者各有特点,但是实践起来却很大, 使自己对页面置换算法有了新的认识。 两周的课程设计就要结束了,不但对专业知识有了更深的理解,更使的自己认识到实践的重要性,理论、实践相结合才能达到很好的学习效果,特别是程序语言的学习。 西安邮电大学 (计算机学院) 操作系统课内实验报告 实验名称:页面置换算法的比较 专业名称:网络工程 班级: 1404 学生姓名:张帅 学号(8指导教师:任东陕 实验日期:2016年5月31日 一. 实验目的及实验环境 实验目的: 1. 掌握分页式存储管理及页面置换算法的实现机制, 2. 对最佳置换算法(OPT)和先进先出算法(FIFO)的性能进行分析比较。 实验环境:windowsXP 、VC6.0++ 二. 实验内容 内容:先生成255个符合实际情况的指令地址。然后,模拟这种指令序列的执行,分别计算使用最佳置换算法(OPT)或先进先出算法(FIFO)的访问命中率,在依据命中率比较两种算法的优劣。从而加深对这两种算法的了解。 三.方案设计 采用页式分配存贮管理方案, 1. 若为不同页面置换算法,则计算各页面置换算法的访问命中率, 比较各种算法的优劣。 2. 若为同一页面置换算法,则考虑改变页面尺寸大小和实际存储器容量对访问命中率的影响。 本程序是按下述原则生成指令序列的: 50%的指令是顺序执行的。 25%的指令均匀散布在前地址部分。 25%的指令均匀散布在后地址部分 程序中选用最佳淘汰算法(OPT )和最近最少使用页面淘汰算法 (LRU )计算页面命中率。公式为: 页面失败次数 命中率= 页地址流长度 四.算法分析 最佳置换算法(OPT )。这是一种理想的算法,必须先知道指令的全部地址流。置换的准则是置换表中以后不再访问或是最迟访问的页。要求将页表中的页逐个与后继指令访问的所有页比较,如后继指令不再访问,则把此页置换,否则找出后继指令中最迟访问的页面予以置换。该算法的准则是淘汰表中以后不再访问或是最迟访问的页。这就要求将页表中的页逐个与后继指令访问的所有页比较,如后继指令不再访问,则把此页淘汰,不然得找出后继指令中最迟访问的页面予以淘汰。可见最佳淘汰 算法要化较长的运算时间。 先进先出算法(FIFO)。这是一种经常使用的算法,置换的准则是置换页表链链首的页,而把新访问的页插入链尾。如果当前调用页已在页表内,则把它再次调整到链尾。这样就能保证最近使用的页,总是处于靠近链尾部分,而不常使用的页就移到链首,逐个被置换. 五.具体变量设定 length 被调试的指令地址流长度 called 当前请求的页面号 pagefault 页面失效标志, table 页表。table[i]=j ,表示虚存的第j 页在实存的第i 页中。 used 当前被占用的实存页面数,可用来判别当前实存中是否有空闲页 实验结果对比: 最佳置换算法(OPT ) 先进先出算法(FIFO) 五.总结 1.实验过程中遇到的问题及解决办法; 问题:不知怎么将参考程序的进程调度算法改为多级反馈队列法? 解决:提示请编写一个反馈排队法(FB 方法)的进程调度程序。该算法的基本思想是设置多个进程就绪队列,例如队列1...... 队列i ,同一队列中的进程优先级相同,可采用先进先出方法调度。各队列进程的优先级不同,逐队递降,即队列1的优先级最高,队列i 的最低。而时间片即一次占用CPU 的时间正好相反,队列1的最短,队列i 则最长。其调度方法是:开始进入的进程都在队列1中参加调度,如果某调入进程在一个时间片内完成不了,则调出后应排入队列2,即优先数要降低,但下一次运行的时间可加长(即队列2的时间片比队列1的长)。依次类推,直止排到队列i 。调度时先在队列1中找,待队列1中已无进程时,再调度队列2的进程,一旦队列1中有了进程,又应返回来调度队列1的进程,直止调度完所有队列的进程为止。 问题:如何理解当页面数=地址流实际大小/页面大小时,不同页面置换算法的访问命中率均相同的现象? 解决:由于页面置换算法是在程序运行过程中,若程序需要访问的页面不在内存内,就需要把该页面调入内存,但内存无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序送入磁盘的对换区,而当页面数=地址流实际大小/页面大小,缺页的次数就等于页面数,由于缺页数与页面总数均相等, 访问命中率=缺页数/页面总数,所以各算法的访问命中率均相同。 2.对设计及调试过程的心得体会。 心得:通过这次实验,根据书里的知识慢慢理解一句句代码。我们在实验慢慢、 对数进程调度的实现构成有了更加深刻的理解,通过不同的尝试来解决,之后不能解决的我们要多向老师同学请教。 网络教育学院 《操作系统》课 程 设 计 题 目: 页面置换算法FIFO算法 学习中心: 层 次: 专 业: 年 级: 年 春/秋 季 学 号: 学 生: 井杰 辅导教师: 龙珠 完成日期: 2016 年 1 月 28 日 页面置换算法FIFO算法 在地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页 中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。在请求分页存储器管理系统中,我们需要一个页面置换算法,而先进先出算法就是最早出现的一种算法,利用该算法可以实现页面的置换,实现内存的充分利用,使进程可以执行。 先进先出置换算法(FIFO) 最简单的页面置换算法是先入先出(FIFO)法。这种算法的实质是,总是选择在主存中停留时间最长(即最老)的一页置换,即先进入内存的页,先退出内存。理由是:最早调入内存的页,其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列,收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时,就把它插在队尾上。 这种算法只是在按线性顺序访问地址空间 时才是理想的,否则效率不高。因为那些常被访问的页,往往在主存中也停留得最久,结果它们因变“老”而不得不被置换出去。 FIFO的另一个缺点是,它有一种异常现象,即在增加存储块的情况下,反而使缺页中断率增加了。当然,导致这种异常现象的页面走向实际上是很少见的。优先淘汰最早进入内存的页面,亦即在内存中驻留时间最久的页面。该算法实现简单,只需把调入内存的页面根据先后次序链接成队列,设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应,因为在进程中,有的页面经常被访问。 1.先进先出(FIFO) 该算法实现简单,只需把一个进程已调入内存的页面,按先后顺序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。 1、输入当前要调用的页面号 2、判断该页面是否已在队列内,若在队列内,不执行任何操作 若不在队列内。则执行以下操作判断队列是否已满,若队列未满,直接把该页面号存入队列 若队列已满,删除并返回队头元素,然后把该页面号存入队 3、输出置换次数,依次输出置换出的页面。 2.先进先出算法思路 在请求分页存储器管理系统设计中,先进先出(FIFO)算法是一种给出页面访问的顺序与分配给作业的主存块数,使用队列作为数据结构编写算法,实现统计缺页次数与页面置换操作,该算法总是先淘汰最先进入内存的页面,即选择在内存中停留时间最久的页面予以淘汰。 3.先进先出算法步骤 1.设置一些页面参数, int pagenum=0 内存页面数 int total=0 要访问的页面总数 int lacknumber 缺页的总数 2.设置一个队列 int seque[20]={0}; 队列长度设置为20 ,且初值设为0 3.执行算法 输入1,2,3,4,1,2,5,1,2,3,4,5 以输入-1结束 4.算法数据结构 Array[0][20] Void main()系统主函数 Cin>> pagenum 键盘输入 页号 存储页面号序列page[] 存储装入物理块中的页面memery[] 访问函数 void Visit(int) void FIFO(void); 打印函数print() 核心函数FIFO() 5.主要函数代码 #include int choose; //选择置换方法 int PageOrder[100]; //页面走向 int Order=0; //页面计数 int MaxPage; //页面总数 int MaxPhy; //物理块总数 int count; //命中次数struct PageTable //页表结构体 { int PageNomber; int PhyNomber; int Sta; //状态位 int Visit; //访问位 int Change; //改变位 };struct PageTable p[10];//最多同时进入10个页表void main() { void Init(); void Fifo(); void Lru(); Init(); cout<><><<"1、fifo><"1、fifo> cout<> cout<> cout<><> }void Init() { cout<<"请输入页表长度"; cin="">>MaxPage; for(int i=1;i<=maxpage;i++)>=maxpage;i++)> p[i].PageNomber=i; p[i].PhyNomber=0; p[i].Change=0; p[i].Sta=0; p[i].Visit=0; } cout<><<"请输入物理块数"; cin="">>MaxPhy; cout<> PageOrder[0]=1; while(PageOrder[j]!=0) { j++; Order++; cin>>PageOrder[j]; if(j>99) { cout<<"超过最大数量,请重新输入,以0结束!"; continue;="" }=""><"超过最大数量,请重新输入,以0结束!";> }void Fifo() { int Max(struct PageTable M[]); struct PageTable i[10];//模拟物理块 for(int j=0;j i[j].PageNomber=0; i[j].Visit=0; } int b=0;//标志位,标记物理块已满 for(int k=1;k if(b==1)//物理块满,进行页面置换 { int a=0;//标志位,是否命中 for(int m=0;m { if(i[m].PageNomber==PageOrder[k]) { a=1; count++; cout<><<" ";="" break;="" }=""><"> if(a==1)continue;//命中继续循环 int Ma=Max(i);//未命中,选择时间最长的物理块进行置换 cout<><><<" ";="" i[ma]="p[PageOrder[k]];" for(int="" l=""><"> for(j=0;j if(i[j].PageNomber==0) { i[j]=p[PageOrder[k]]; cout<><<" ";="" for(int="" l=""><"><=j;l++) i[l].visit++;="" if(j="=MaxPhy-1)" b="b+1;" break;="">=j;l++)> }void Lru() {}int Max(struct PageTable M[])//返回最大值 { int temp,Max=0; temp=M[0].Visit; for(int j=1;j if(temp temp=M[j].Visit; Max=j; } } return(Max); } 5 5.测试案例 比如设置物理块个数为3,页面序号7 0 1 2 3 0 4 2 3,代码应列出算法置换的具体细节。 接下来我就讲下FIFO这种情况,FIFO就是先进先出的访问方式,根据题目里面的访问顺序:6 0 1 2 0 3 0 4 2 3,所有首先访问的是7,当第一次访问6 的时候,内存中当然是没有的,所以就会发生中断去读取数据,完成中断之后,内存中就有了一个6,接着访问的是0,当然此时内存中也没有0,所以又会发生一次中断,同理,完成中断之后,内存中就有0了,接下来访问的就是第三个数1,很明显,此时内存中也是没有该元素的,所以也会发生中断,完成中断后内存里面就有一个1了。此时内存中的数据为701。 接下来就要注意思想的转化了,因为题目中说了只有3块存储空间,到目前为止,3块空间都用完了。所以,在访问第4个数字时(也就是访问2 的时候),必须先丢弃一个数据,根据题目要求是FIFO的原理,所以,理所当然就应该丢弃最先访问的7,并去访问新的数据--2,即2替换7的位置,所以也会发生中断,并且中断完成后内存中的数据是201。 接下来又要访问第五个数字,即访问第二个0的时候,此时,内存的数据为201,其中刚好有一个0,所有就不会发生中断,而是继续访问下一个数,即第六个数--4。此时内存中没有4这个数字,并且空间也全部占满了的,所有又必须丢弃一个数字,当然由于是FIFO,所有肯定会丢弃2,并再发生一次中断去读取4,当中断完成后,内存中的数据为430。类似推断最后内存的数据为423 。 6. 算法流程图 由结果可以看出,使用FIFO算法,总是淘汰最先进入内存的页面,即即选择在内存中驻留时间最久的页面予以淘汰。 实验四 页面置换算法 一、 实验目的 理解并掌握模拟分页式虚拟存储管理的缺页中断, 以及选择页面调度算法处 理缺页中断。 二、 实验内容及要求 选择一种或几种页面置换算法进行编程以实现该算法。 三、 实验流程图 四、 实验程序 1、 FIFO 算法 #include #define n 20 #define m 4 void main() { int ym[n],i,j,q,mem[m]={0},table[m][n]; char flag,f[n]; printf( for (i=0;i scanf( printf( for (i=0;i { q =0; while ((ym[i]!=mem[q])&&(q!=m)) q++; if (q==m) flag=' *' ; //缺页,则置标志 flag 为‘ *’ else flag=' ' ; if (flag==' *' ) { for (j=m -1;j >0;j --) //淘汰最先调入的页面调入当前访问的 mem[j]=mem[j-1]; mem[0]=ym[i]; } for (j=0;j table[j][i]=mem[j]; f[i]=flag; } printf( for (i=0;i { for (j=0;j printf( printf( } for (i=0;i printf( } 2、 LRU 算法 #include #define n 20 #define m 5 void main() { int ym[n],i,j,q,mem[m]={0},table[m][n]; char flag,f[n]; printf( for (i=0;i scanf( printf( for (i=0;i { q =0; while ((ym[i]!=mem[q])&&(q!=m)) q++; if (q==m) flag='*'; //缺页,则置标志 flag 为‘ *’ else flag=' '; for (j=q;j >0;j --) mem[j]=mem[j-1]; mem[0]=ym[i]; for (j=0;j table[j][i]=mem[j]; f[i]=flag; } printf( for (i=0;i { for (j=0;j printf( printf( } for (i=0;i printf( } 五、 实验结果 1、 FIFO(四内存块 ) 2、 LRU(五内存块 ) 六、 实验心得 通过这次实验, 进一步了解了什么是缺页中断, 以及处理缺页中断的 调度算法。通过自己编程,加深了对理论学习的理解。范文二:页面置换算法的模拟
范文三:页面置换算法的比较
范文四:页面置换算法FIFO算法
范文五:页面置换算法(FIFO算法,LRU算法)