页面置换实验报告.doc

操作系统课 程 设 计 报 告起评分理论成绩实践成绩总成绩 院系： 信息管理学院 专业： 计算机科学与技术 班级： 计科Q1241班 学号： 12150123 姓名： 罗家骏 专题：页面置换算法一：实验目的1、熟悉内存分页管理策略。2、了解页面置换的算法，掌握一般常用的调度算法。3、掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 4、锻炼知识的运用能力和动手实践能力。二：实验原理 1.在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。2.最佳置换算法（OPT）（理想置换算法）：从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。3.先进先出置换算法（FIFO）：是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。4.最近最久未使用（LRU）算法：这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。任务：设计一个虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程,并计算访问命中率：要求设计主界面以灵活选择某算法，且以下算法都要实现1）先进先出算法（FIFO）2）最近最久未使用算法（LRU）3）最佳置换算法（OPT）思想：1. 最佳置换算法：最佳置换算法是一种理论上的算法，其所选择的被淘汰页面，将是以后永不使用的，或者是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 17772222444000000077700000333222221111100001111000333332222212. 先进先出页面置换算法:这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即使选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按先后次序连接成一个队列，并设置一个指针，成为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，所以先进先出算法并不能保证这些页面不被淘汰。7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 17772222444000000077700000333222222111100001111000333332222213. 最近最久未使用置换算法：最久最久未使用的页面置换算法，是根据页面调入的先后的使用情况进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即使最近最久未使用的页面予以淘汰。最近最久未使用算法7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1777222244400011111110000000003333330000000111333222222222777任务目的：1通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。2通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。3掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。方案：输入页面序列，缺页时按OPT .FIFO、LRU、的策略进行页面置换，输出置换情况和缺页次数。假设页面数不超过total_pages。SumMax表示简化了的页表，只包含页号序列。distribute_block表示分配给该进程的块数。count用来表示置换次数。初始化：输入分配的块数distribute_block，输入页面序列，存放于数组Sum中。按照循环，依次查找页面是否存在于页表中，不存在则置换页面，初始为0，变化同上。格式化依次输出访问下一个页面后的页表，然后输出缺页中断总次数框图：程序要点详解： #includeusing namespace std; /预定义存储空间#define Max 100 /宏定义#define Min 20 全局变量定义 ，方便子函数的访问static int distribute_block; /distribute_block表示系统分配给主存static int total_pages; /total_pages表示程序的页面数OPT算法要点：void opt(int *s,int *b)int i,j,k,max； Int temp,count=0;int sumMin;for(j=1;j=total_pages;j+) for(i=1;idistribute_block) /没有找到的条件判断count+; /统计页面置换的次数for(i=1;i=distribute_block;i+) /找出内存中的页面在到达后面的程序页面中的次数for(k=j+1;ktotal_pages) sumi=0; /当访问后，令sumi=0 for(temp=0,i=1;itemp) max=i; temp=sumi; bmax=sj; /变换主存的页面数 for(i=1;i=distribute_block;i+)coutbit; /输出主存的页面coutendl;cout-opt算法-endl;cout页面置换的次数为countendl; /输出页面置换的次数cout缺页中断率为double(count)/total_pagesendl; /输出缺页中断率cout-endl;coutendl;Fifo算法要点void fifo(int *s,int *b) /*s表示页面程序所在的块数的数组，*b表示内存里面的块数数组 int i,j,k,max;int temp,count=0;int sumMin=0;for(j=1;j=total_pages;j+) /检测b数组中是否含有aj元素for(i=1;idistribute_block) /没有的条件判断count+; /统计页面置换的次数 for(temp=0,i=1;i=distribute_block;i+) /按照fifo算法，改变的b数组中的数值 for(k=1;k=j & k=distribute_block;k+) sumk+; if(jtemp) max=k; temp=sumk; bmax=sj;summax=0;for(i=1;i=distribute_block;i+)coutbit;coutendl; cout-fifo算法-endl;cout页面置换的次数为countendl;cout缺页中断率为double(count)/total_pagesendl;cout-endl;coutendl;lru算法要点void lru(int *s,int *b) int i,j,k,max;int temp,count=0;int sumMin;for(j=1;j=total_pages;j+) for(i=1;idistribute_block) /没有的条件判断count+; /统计页面置换的次数for(i=1;i=distribute_block;i+)if(j=1;k-) if(bi=sk) sumi=j-k; break; for(temp=0,k=1;ktemp) max=k; temp=sumk;bmax=sj; for(i=1;i=distribute_block;i+)coutbit;coutendl;cout-lru算法-endl;cout页面置换的次数为countendl;cout缺页中断率为double(count)/total_pagesendl;cout-endl;coutendl;主函数：int main()int SumMax,blockMin; /SumMax表示储存程序所在的页面，blockMin表示块存储的页面int x; int i;int count=0; coutdistribute_block; couttotal_pages;cout请输入程序的total_pages个内容所在的页面:;for(i=1;iSumi;cout/初始化块的存储页面，负数表示暂时未存储endl; cout请输入块存储的distribute_block个页面:;for(i=1;iblocki;docout1opt算法 2.fifo算法 3.lru算法 4.结束进程x;switch(x)case 1: opt(Sum,block);break;case 2: fifo(Sum,block);break;case 3: lru(Sum,block);break;default:break;while(x!=4); return 0;程序：#includeusing namespace std;#define Max 100#define Min 20static int distribute_block; /distribute_block表示系统分配给主存static int total_pages; /total_pages表示程序的页面数/opt算法void opt(int *s,int *b)int i,j,k,max,temp,count=0;int sumMin;for(j=1;j=total_pages;j+) for(i=1;idistribute_block) /没有找到的条件判断count+; /统计页面置换的次数for(i=1;i=distribute_block;i+) /找出内存中的页面在到达后面的程序页面中的次数for(k=j+1;ktotal_pages) sumi=0; for(temp=0,i=1;itemp) max=i; temp=sumi; bmax=sj; for(i=1;i=distribute_block;i+)coutbit;coutendl;cout-opt算法-endl;cout页面置换的次数为countendl;cout缺页中断率为double(count)/total_pagesendl;cout-endl;coutendl;/fifo算法void fifo(int *s,int *b) /*s表示页面程序所在的块数的数组，*b表示内存里面的块数数组 int i,j,k,max;int temp,count=0;int sumMin=0;for(j=1;j=total_pages;j+) /检测b数组中是否含有aj元素for(i=1;idistribute_block) /没有的条件判断count+; /统计页面置换的次数 for(temp=0,i=1;i=distribute_block;i+) /按照fifo算法，改变的b数组中的数值 for(k=1;k=j & k=distribute_block;k+) sumk+; if(jtemp) max=k; temp=sumk; bmax=sj;summax=0;for(i=1;i=distribute_block;i+)coutbit;coutendl; cout-fifo算法-endl;cout页面置换的次数为countendl;cout缺页中断率为double(count)/total_pagesendl;cout-endl;coutendl;/lru算法void lru(int *s,int *b) int i,j,k,max;int temp,count=0;int sumMin;for(j=1;j=total_pages;j+) for(i=1;idistribute_block) /没有的条件判断count+; /统计页面置换的次数for(i=1;i=distribute_block;i+)if(j=1;k-) if(bi=sk) sumi=j-k; break; for(temp=0,k=1;ktemp) max=k; temp=sumk;bmax=sj; for(i=1;i=distribute_block;i+)coutbit;coutendl;cout-lru算法-endl;cout页面置换的次数为countendl;cout缺页中断率为double(count