模拟FIFO和LRU算法试验报告

实验名称：模拟FIFO和LRU算法

学校：长安大学

学院：信息学院

班级：24060901

姓名：***

日期：2012-5-3

一、实验题目：

先进先出（FIFO）页面置换算法和最近最久未使用（LRU）置换算法程序设计

二、实验目的：

通过对FIFO，LRU算法的模拟，进一步理解进程的基本概念，加深对进程运行状态和进程调度过程、调度算法的理解。

三、实验设备及环境：

1. 硬件设备：PC机一台

2. 软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境，如C \\C++\\Java 等编程语言环境。

四、实验内容及要求：

（1）用C/C++语言编程实现对FIFO，LRU算法的模拟。

（2）每个用来标识进程的进程控制块PCB可用结构来描述，包括以下字段：

五、实验方法内容

一．算法流程图

二．

主要模块

FIFO功能函数设计：

Fifo_replace(void);  //构造函数

 ~Fifo_replace(void); //析构函数

 int findSpace(void); //查找是否有空闲内存

 int findExist(int curpage);  //查找内存中是否有该页面

 int findReplace(void);  //查找应予置换的页面

 void display(void);  //显示

 void FIFO(void);   //FIFO算法

 void BlockClear(void);  //BLOCK恢复

 pageInfor *block;  //物理块

 pageInfor *page;  //页面号串

 int memory_state[Bsize][Psize];

 int s;   //缺页统计

三．主要代码设计

FIFO部分代码

#include

#define Bsize 3

#define Psize 12

struct pageInfor

{

 int content;//页面号

 int timer;//被访问标记

};

class Fifo_replace

{

public:

  Fifo_replace(void);  //构造函数

 ~Fifo_replace(void); //析构函数

  int findSpace(void); //查找是否有空闲内存

  int findExist(int curpage);  //查找内存中是否有该页面

  int findReplace(void);  //查找应予置换的页面

  void display(void);  //显示

  void FIFO(void);   //FIFO算法

void BlockClear(void);  //BLOCK恢复

  pageInfor *block;  //物理块

  pageInfor *page;  //页面号串

  int memory_state[Bsize][Psize];

  int s;   //缺页统计

private:

};

Fifo_replace::Fifo_replace(void)

{

  int QString[12]={4,3,2,1,4,3,5,4,3,2,1,5};

 s=0;

 block = new pageInfor[Bsize];

for(int i=0; i {

  block[i].content = -1;

  block[i].timer = 0;

 }

 page = new pageInfor[Psize];

  for(i=0; i {

   page[i].content = QString[i];

   page[i].timer = 0;

 }

}

Fifo_replace::~Fifo_replace()

{

   s=0;

}

int Fifo_replace::findSpace(void)

{

for(int i=0; i if(block[i].content == -1)

  return i;//找到空闲内存，

 return -1;

}

int Fifo_replace::findExist(int curpage)

{

for(int i=0; i if(block[i].content == page[curpage].content)

  return i;//找到内存中有该页面，返回BLOCK中位置

 return -1;

}

int Fifo_replace::findReplace(void)

{

 int pos = 0;

for(int i=0; i if(block[i].timer >= block[pos].timer)

   pos = i;//找到应予置换页面，返回BLOCK中位置

 return pos;

}

void Fifo_replace::display(void)

{

for(int i=0; i if(block[i].content != -1)

cout< cout<}

void Fifo_replace::FIFO(void)

{

 int exist,space,position ;

for(int i=0; i {

  exist = findExist(i);

  if(exist != -1)

  {

for(int b=0; b   {

    memory_state[b][i]=memory_state[b][i-1];

   }

   s++;

//cout<<"不缺页"<  }

  else

  {  

   space = findSpace();

   if(space != -1)

   {

for(int b=0; b    {

     memory_state[b][i]=memory_state[b][i-1];

    }

    block[space] = page[i];

    memory_state[space][i]=block[space].content;

    if(space==1)

    {

     memory_state[1][0]=0;

     memory_state[2][0]=0;

    }

    else

    {

     memory_state[2][1]=0;

    }

    //display();

   }

   else

   {

for(int b=0; b    {

        memory_state[b][i]=memory_state[b][i-1];

    }

    position = findReplace();

    block[position] = page[i];

    memory_state[position][i]=block[position].content;

    //display();

   }

  }

for(int j=0; j   block[j].timer++;//BLOCK中所有页面TIMER++

 }

}

void Fifo_replace::BlockClear(void)

{

for(int i=0; i {

  block[i].content = -1;

  block[i].timer = 0;

 }

}

LRU部分代码实现：

#include

#include

#define M 4 

#define N 17 

#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\\n")    /*表格控制*/ 

typedef struct page 

{ 

    int num;    /*记录页面号*/ 

    int time;    /*记录调入内存时间*/ 

}Page;            /* 页面逻辑结构，结构为方便算法实现设计*/ 

Page b[M];        /*内存单元数*/ 

int c[M][N];    /*暂保存内存当前的状态：缓冲区*/ 

int queue[100];    /*记录调入队列*/ 

int K;        /*调入队列计数变量*/ 

/*初始化内存单元、缓冲区*/ 

void Init(Page *b,int c[M][N]) 

{ 

    int i,j; 

for(i=0;i    { 

        b[i].num=-1; 

        b[i].time=N-i-1; 

    } 

for(i=0;i     for(j=0;j        c[i][j]=-1; 

} 

/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/ 

int GetMax(Page *b) 

{ 

    int i; 

    int max=-1; 

    int tag=0; 

for(i=0;i    { 

     if(b[i].time>max)

        { 

            max=b[i].time; 

            tag=i; 

        } 

    } 

    return tag; 

} 

/*判断页面是否已在内存中*/ 

int    Equation(int fold,Page *b) 

{ 

    int i; 

for(i=0;i    { 

        if (fold==b[i].num) 

        return i; 

    } 

    return -1; 

} 

/*LRU核心部分*/ 

void Lru(int fold,Page *b) 

{ 

    int i; 

    int val; 

    val=Equation(fold,b); 

if (val>=0)

    { 

        b[val].time=0; 

     for(i=0;i        if (i!=val) 

        b[i].time++; 

    } 

    else 

    { 

        queue[++K]=fold;/*记录调入页面*/ 

        val=GetMax(b); 

        b[val].num=fold; 

        b[val].time=0; 

     for(i=0;i        if (i!=val) 

        b[i].time++; 

    } 

} 

/*主程序*/ 

六、实验结果

1.执行结果

FIFO部分

LRU部分：

2.结果分析

由结果可以看出,使用FIFO算法，总是淘汰最先进入内存的页面，即即选择在内存中驻留时间最久的页面予以淘汰。使用LRU算法则是选择最近最久未使用的页面予以淘汰。 

七、实验总结

这次实验让我深刻理解了FIFO和LRU算法。由于FIFO所依据的条件是各个页面存入的时间，而页面调入的先后并不能反映页面的使用情况，所以FIFO算法的性能较差。LRU算法相对较好。

通过这个实验我体会到了编程的思路流程，结构流程图的作用。一个程序如果一开始计划的好，结构设计完善，才可能顺利进行。