页面置换算法fifo算法

《页面置换算法fifo算法》由会员分享，可在线阅读，更多相关《页面置换算法fifo算法（8页珍藏版）》请在金锄头文库上搜索。

1、 网络教育学院网络教育学院 操作系统操作系统课课 程程 设设 计计题题 目：目： 页面置换算法页面置换算法 FIFOFIFO 算法算法 学习中心：学习中心： 层层 次：次： 专专 业：业： 年年 级：级： 年 春/秋 季 学学 号：号： 学学 生：生： 井杰 辅导教师：辅导教师： 龙珠 完成日期：完成日期： 2016 年 1 月 28 日页面置换算法页面置换算法 FIFOFIFO 算法算法在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选

2、择淘汰哪一页的规则叫做页面置换算法。在请求分页存储器管理系统中，我们需要一个页面置换算法，而先进先出算法就是最早出现的一种算法，利用该算法可以实现页面的置换，实现内存的充分利用，使进程可以执行。先进先出置换算法（先进先出置换算法（FIFOFIFO） 最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个 FIFO 队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。 这种算法只是在

3、按线性顺序访问地址空间 时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。FIFO 的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。1先进先出（先进先出（FIFO）该算法实现简单，只需把一个进程已调入内存的页面，按先后顺序链接成一

4、个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。1、输入当前要调用的页面号2、判断该页面是否已在队列内，若在队列内，不执行任何操作若不在队列内。则执行以下操作判断队列是否已满,若队列未满，直接把该页面号存入队列 若队列已满，删除并返回队头元素，然后把该页面号存入队3、输出置换次数，依次输出置换出的页面。2先进先出算法思路先进先出算法思路在请求分页存储器管理系统设计中，先进先出（FIFO）算法是一种给出页面访问的顺序与分配给作业的主存块数，使用队列作为数据结构编写算法，实现统计缺页次数与页面置换操作，该算法总是先淘汰最先进入内存的页面，即选择在内存中停留时间最久的页面予以淘汰。3.

5、先进先出算法步骤先进先出算法步骤1.设置一些页面参数，int pagenum=0 内存页面数int total=0 要访问的页面总数int lacknumber 缺页的总数2.设置一个队列int seque20=0; 队列长度设置为 20 ，且初值设为 03.执行算法输入 1,2,3,4,1,2,5,1,2,3,4,5以输入-1 结束4.算法数据结构算法数据结构Array020 Void main()系统主函数 Cin pagenum 键盘输入 页号 存储页面号序列 page 存储装入物理块中的页面 memery 访问函数 void Visit(int) void FIFO(void); 打印

6、函数 print() 核心函数 FIFO()5.主要函数代码主要函数代码#include int choose; /选择置换方法 int PageOrder100; /页面走向 int Order=0; /页面计数 int MaxPage; /页面总数 int MaxPhy; /物理块总数 int count; /命中次数 struct PageTable /页表结构体 int PageNomber;int PhyNomber;int Sta; /状态位int Visit; /访问位int Change; /改变位 ;struct PageTable p10;/最多同时进入 10 个页表 vo

7、id main() void Init();void Fifo();void Lru();Init();coutchoose;if(choose=1)coutMaxPage;for(int i=1;iMaxPhy;coutPageOrderj;if(j99)cout“超过最大数量，请重新输入,以 0 结束！“;continue; void Fifo() int Max(struct PageTable M);struct PageTable i10;/模拟物理块for(int j=0;jMaxPhy;j+)ij.PageNomber=0;ij.Visit=0;int b=0;/标志位，标记物理

8、块已满for(int k=1;kOrder;k+)if(b=1)/物理块满，进行页面置换int a=0;/标志位，是否命中for(int m=0;mMaxPhy;m+)/判断命中if(im.PageNomber=PageOrderk)a=1;count+;cout“命中“ “;break;if(a=1)continue;/命中继续循环int Ma=Max(i);/未命中，选择时间最长的物理块进行置换cout“替换“Ma“ “;iMa=pPageOrderk;for(int l=0;lMaxPhy;l+)il.Visit+;continue;for(j=0;jMaxPhy;j+)/页面写入空物理

9、块if(ij.PageNomber=0)ij=pPageOrderk;cout“进入“ “;for(int l=0;l=j;l+)il.Visit+;if(j=MaxPhy-1)b=b+1;break; void Lru() int Max(struct PageTable M)/返回最大值 int temp,Max=0;temp=M0.Visit;for(int j=1;jMaxPhy;j+)if(tempMj.Visit)temp=Mj.Visit;Max=j;return(Max); 55测试案例测试案例比如设置物理块个数为 3，页面序号 7 0 1 2 3 0 4 2 3，代码应列出算

10、法置换的具体细节。时刻123456789访问顺序70123042377722244400033322M=31110003F12345678接下来我就讲下 FIFO 这种情况，FIFO 就是先进先出的访问方式，根据题目里面的访问顺序：6 0 1 2 0 3 0 4 2 3，所有首先访问的是 7，当第一次访问 6 的时候，内存中当然是没有的，所以就会发生中断去读取数据，完成中断之后，内存中就有了一个 6，接着访问的是 0，当然此时内存中也没有 0，所以又会发生一次中断，同理，完成中断之后，内存中就有 0 了，接下来访问的就是第三个数 1，很明显，此时内存中也是没有该元素的，所以也会发生中断，完成中

11、断后内存里面就有一个 1 了。此时内存中的数据为 701。接下来就要注意思想的转化了，因为题目中说了只有 3 块存储空间，到目前为止，3 块空间都用完了。所以，在访问第 4 个数字时（也就是访问 2 的时候），必须先丢弃一个数据，根据题目要求是 FIFO 的原理，所以，理所当然就应该丢弃最先访问的 7，并去访问新的数据-2，即 2 替换 7 的位置，所以也会发生中断，并且中断完成后内存中的数据是 201。 接下来又要访问第五个数字，即访问第二个 0 的时候，此时，内存的数据为 201，其中刚好有一个 0，所有就不会发生中断，而是继续访问下一个数，即第六个数-4。此时内存中没有 4 这个数字，并且空间也全部占满了的，所有又必须丢弃一个数字，当然由于是FIFO，所有肯定会丢弃 2，并再发生一次中断去读取 4，当中断完成后，内存中的数据为 430。类似推断最后内存的数据为 423 。6.6. 算法流程图算法流程图开始检查内存是否有空闲 块选择最先进入的页 面置换读入访问页面信息存入页面输出置换出的页面序号结束未读完已读完有无由结果可以看出,使用 FIFO 算法，总是淘汰最先进入内存的页面，即即选择在内存中驻留时间最久的页面予以淘汰。