页面置换-操作系统实验报告

1、实验二 页面置换算法实现一、实验目的1）了解内存分页管理策略2）掌握调页策略3）掌握一般常用的调度算法4）学会各种存储分配算法的实现方法。5）了解页面大小和内存实际容量对命中率的影响。二、实验内容采用页式分配存储方案， 通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响， 设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换：1. 先进先出的算法（FIFO）2. 最近最久未使用算法（LRU）3. 最佳置换算法（OPT）实验分析在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时， 为了保证该进程能够正常运行，

2、 系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏， 直接影响到系统的性能。 一个好的页面置换算法， 应该有较低的页面更换频率。2.1 先进先出（ FIFO ）页面置换算法当需要访问一个新的页面时， 首先查看物理块中是否就有这个页面， 若要查看的页面物理块中就有， 则直接显示， 不需要替换页面； 如果要查看的页面物理块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；若没有空闲物理块，则替换页面。并将物理块中所有页面timer+ 。2.2 最近久未使用 （LRU） 置换算法的思路最近久未使用置换算法的替换规则，是根据页面

3、调入内存后的使用情况来进 行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问 以来所经历的时间,当需淘汰一个页面的时候选择现有页面中其时间值最大的进 行淘汰。2.3 最佳（OPT置换算法的思路其所选择的被淘汰的页面，是以后不使用的，或者是在未来时间内不再被访 问的页面，采用最佳算法，通常可保证获得最低的缺页率。三、实验流程3.1 系统功能图图3-1系统功能图方面置操主界面-H 最佳置报3.2 算法流程图1）先进先出（FIFO ）页面置换算法流程图图3-2先进先出页面置换算法流程图2)最近久未使用(LRU)置换算法图3-3最近久未使用置换算法流程图3）最佳（OPT ）置换算法

4、喻出不缺无找块号最小内存次中下次慢用强现衽最久的页输出当前页输出当前贡输切页信息图3-4最佳置换算法流程图四、源程序#include#include #include #include #define L 20/页面长度最大为20int M; /内存块struct Pro/淀义一个结构体int num,time;Input(int m,Pro pL)/ 打印页面走向状态coutm;if(m20|m10) coutendl;cout”页面长度必须在1020之间endlendl;cout请重新输入L：;else break;while(1);int i,j;j=time(NULL);/ 取时钟时间

5、srand(j);/以时钟时间j为种子，初始化随机数发生器coutendl;cout输出随机数：endl;coutendl;for(i=0;im;i+)pi.num=rand( )%10;/产生 0 到 9之间的随机数放到数组 p 中pi.time=0;coutpi.num ;coutendlendl;return m;void print(Pro *page1)打印当前的页面Pro *page=new ProM;page=page1;for(int i=0;iM;i+)coutpagei.num ;coutendl;int Search(int e,Pro *page1 )/寻找内存块中与/

6、e 相同的块号Pro *page=new ProM;page=page1;for(int i=0;iM;i+)if(e=pagei.num)return i;/ 返回 i 值 return -1;int Max(Pro *page1)/寻找最近最长未使用的页面Pro *page=new ProM;page=page1;int e=page0.time,i=0;while(iM) / 找出离现在时间最长的页面if(epagei.time) e=pagei.time;i+;for( i=0;iM;i+)if(e=pagei.time)return i;/ 找到离现在时间最长的页面返回 其块号ret

7、urn -1;int Count(Pro *page1,int i,int t,Pro pL)/ 记录当前内存块中页面离下次使用间隔 长度Pro *page=new ProM;page=page1;int count=0;for(int j=i;jL;j+)if(paget.num=pj.num )break;/ 当前页面再次被访问时循环结束else count+;/S贝 count+1return count;/回 count 的值int main()int c;int m=0,t=0;float n=0;Pro pL;m=Input(m,p);/调用 input 函数，返回 m 值 cou

8、t”请输入分配的物理块 m(26):; coutendl6|M2) coutendl;coutvv”物理块m必须在26之间vvendlvvendl;coutvv”请重新输入m： ;else break;while(1);Pro *page=new ProM;dofor(int i=0;iM;i+)/初始化页面基本情况 pagei.num=O;pagei.time=m-1-i;)i=0;coutendl;cout1:FIFO 页面置换 2:LRU 页面置换”vvendl;coutvv”3:OPT 页面置换 4:退出vvendl;coutvv”请选择页面置换算法：endl;cinc;if(c=1)

9、/FIFO 页面置换(n=0;cout FIFO算法页面置换情况如下：endl;coutendl;while(i=O) 当前页面在内存中coutpi.num/ 输出当前页 pi.numcoutvv不缺页endl;i+; /i 加 1)else/售前页不在内存中(if(t=M)t=O;else(n+;/缺页次数加1paget.num=pi.num; /把当前页面放入内存中coutpi.numprint(page); /甘丁ER当前页面t+; 下一个内存块 i+; 指向下一个页面)coutendl;coutvv”缺页次数：n缺页率：n/mendlendl;)if(c=2)/LRU 页面置换n=0;

10、cout LRU 算法页面置换情况如下: endl;coutendl;while(i=0)/ 如果已在内存块中paget.time=0;/把与它相同的内存块的时间置 0for(a=0;aM;a+)if(a!=t)pagea.time+;/ 其它的时间加1coutpi.num ;cout不缺页endl;else /如果不在内存块中n+; /缺页次数加1t=Max(page); /返回最近最久未使用的块号赋值给tpaget.num=pi.num; / 进行替换paget.time=0; /替换后时间置为0coutpi.num ;print(page);for(a=0;aM;a+)if(a!=t)

11、pagea.time+; /其它的时间加1i+;coutendl;coutvv”缺页次数：n缺页率：n/mendlendl;)if(c=3)/OPT 页面置换(n=0;cout OPT算法置换情况如下:endl;coutendl;while(i=0)/如果已在内存块中(coutpi.numcoutvv不缺页endl;i+；)else/4口果不在内存块中(int a=0;for(t=0;tM;t+)if(paget. num=0)a+; 记录空的内存块数if(a!=O)有空内存(int q=M;for(t=0;tt)q=t;/把空内存块中块号最小的 找出来pageq.num=pi.num;n+;

12、coutpi.num;print(page);i+；)else(int temp=0,s;for(t=0;tM;t+)寻找内存块中下次使用离现在最久的页面if(tempCount(page,i,t,p)(temp=Count(page,i,t,p);s=t; 把找到的块号赋给spages.num=pi.num;n+;coutpi.num;print(page);i+;coutendl;cout”缺页次数：n缺页率：n/mendlendl;if(c = 4) break;while(c=1|c=2|c=3);return 0;五、实验结果5.1 程序主界面运行程序后，将会提示用户输入页面长度，长

13、度在10到20之间。当用户输 入长度（以12为例）后，系统将会显示随机数。系统提示用户输入分配的物理 块，用户输入数据（以3为例）。程序主界面运行图如图5-1所示。请输入页面长度。陋N 12 输出随机数：请榆入分配的物理块皿263 ：图5-1程序主界面5.2 先进先出（FIFO）页面置换算法运行结果选择算法1之后，进入算法1的操作。系统会显示算法的页面置换情况 先来先服务算法的运行图如图5-2所示。1：FIF。贝面罩换 2：LRU贝面置换3M0PI页茴置换4 m退出请选择页面豌算法.2 10 5 y ge 6i b11的算法贝面置换情况如下：2 1 10不缺页116下22 15缺页次数：10缺页率*。,88争33图5-2先进先出页面置换算法运行结果图5.3 最近久未使用（LRU）置换算法运行结果选择算法2之后，进入算法2的操作。系统会显示算法的页面置换情况 最近久未使用的运行图如图5-3所示。图5-3最近久未使用置换算法运行结果图4）最佳（OPT ）置换算法运行结果选择算法3之后，进入算法3的操作。系统会显示算法的页面置换情况 最近久未使用的运行图如图5-