页面置换算法FIFO算法.doc

网络教育学院
《操作系统》课程设计

题目：页面置换算法FIFO算法
学习中心：
层次：
专业：
年级：年春/秋季
学号：
学生：井杰
辅导教师：龙珠
完成日期：2016年1月28日

页面置换算法FIFO算法
在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生HYPERLINK"http://baike.baidu.com/view/3071978.htm"\t"_blank"缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则HYPERLINK"http://baike.baidu.com/view/880.htm"\t"_blank"操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。在请求分页存储器管理系统中，我们需要一个页面置换算法，而先进先出算法就是最早出现的一种算法，利用该算法可以实现页面的置换，实现内存的充分利用，使进程可以执行。

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

1．先进先出（FIFO）
该算法实现简单，只需把一个进程已调入内存的页面，按先后顺序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
1、输入当前要调用的页面号
2、判断该页面是否已在队列内，若在队列内，不执行任何操作
若不在队列内。则执行以下操作判断队列是否已满,若队列未满，直接把该页面号存入队列若队列已满，删除并返回队头元素，然后把该页面号存入队
3、输出置换次数，依次输出置换出的页面。
2．先进先出算法思路
在请求分页存储器管理系统设计中，先进先出（FIFO）算法是一种给出页面访问的顺序与分配给作业的主存块数，使用队列作为数据结构编写算法，实现统计缺页次数与页面置换操作，该算法总是先淘汰最先进入内存的页面，即选择在内存中停留时间最久的页面予以淘汰。
3.先进先出算法步骤
1.设置一些页面参数，
intpagenum=0内存页面数
inttotal=0要访问的页面总数
intlacknumber缺页的总数
2.设置一个队列
intseque[20]={0};队列长度设置为20，且初值设为0
3.执行算法
输入1,2,3,4,1,2,5,1,2,3,4,5
以输入-1结束
4.算法数据结构
Array[0][20]
Voidmain()系统主函数
Cin>>pagenum键盘输入页号
存储页面号序列page[]
存储装入物理块中的页面memery[]
访问函数voidVisit(int)
voidFIFO(void);
打印函数print()
核心函数FIFO()
5.主要函数代码
#include<iostream.h>intchoose;//选择置换方法intPageOrder[100];//页面走向intOrder=0;//页面计数intMaxPage;//页面总数intMaxPhy;//物理块总数intcount;//命中次数structPageTable//页表结构体{intPageNomber;intPhyNomber;intSta;//状态位intVisit;//访问位intChange;//改变位};structPageTablep[10];//最多同时进入10个页表voidmain(){voidInit();voidFifo();voidLru();Init();cout<<"请选择置换方法"<<endl<<"1、FIFO2、LRU"<<endl;cin>>choose;if(choose==1){cout<<"物理块变化过程:"<<endl;Fifo();cout<<endl;cout<<"命中次数："<<count<<endl;}elseLru(