操作系统 FIFO页面置换算法

鼯鼠

先进先出算法（FIFO算法）

    FIFO算法维护一个先进先出队列，队列长度为分配给这个进程的页面数M。开始时队列是空的，装入进程的第一页即可启动运行，当访问到某个不在内存的页面时，把它从辅存调入，加入FIFO队列的尾部。
    下图是一个实例，假定页面序列P为7 0 1 2 0 3 0 4，M=3，图中给出了页面队列的变化情况。这个极端例子在总共8次页面访问中，只有一次访问成功，缺页率f达87.5%。

表示页面失效        表示页面未失效

FIFO的页面队列

    FIFO算法的优点是简单。一个很严重的缺点是在有的情况下，给进程的页面数M增加时，同样的页面序列P，缺页率反而增加，这称为FIFO异常。有兴趣的话，不妨自己构造这种例子。当某个页面刚被淘汰又要调入时容易产生这种现象。可以构造出无限多个例子。

代码如下：

#include<stdio.h>

int p1[10]={6,1,2,3,2,1,3,2,5,2};
int temp[3]={0};

//判断调用的值是否存在页面中
bool IsExit(int sCh)
{
 for(int i=0;i<3;i++)
  if(temp==sCh)
   return false;
 return true;
}
void FIFO(int p[10],int nZe)
{
 //内存标示mem1标示当前第一块内存页，mem2标示当前第二块内存页，mem3标示当前第三块内存页
 //flagle表示内存状态：Ready内存准备状态，false内存失败缺页，需要置换,true内存中已存在，不用置换
 printf("mem1\tmem2\tmem3\tflagle\n");
 printf("%d\t%d\t%d\tReady\n",temp[0],temp[1],temp[2]);
 for(int i = 0;i<10;i++)
  //如果没有在页面队列中
  if(IsExit(p))
  {
   temp[0]=temp[1];
   temp[1]=temp[2];
   temp[2]= p;
   //打印出内存状态
   printf("%d\t%d\t%d\tfalse\n",temp[0],temp[1],temp[2]);
  }
  else
   printf("%d\t%d\t%d\ttrue\n",temp[0],temp[1],temp[2]);
}
void main(){
 
 FIFO(p1,10);
 getchar();
}