Linux页面置换算法的C语言实现

Linux页面置换算法的C语言实现

编写算法，实现页面置换算法FIFO、LRU、OPT；针对内存地址引用串，进行页面置换算法进行页面置换。

其中，算法所需的各种参数由输入产生（手工输入或者随机数产生）；输出内存驻留的页面集合，缺页次数以及缺页率。

#include <stdio.h>
//#include <conio.h>
#include <stdlib.h>
#include <time.h>//随机数

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

int M;
int N; 

typedef struct page
{
 int num; /*记录页面号*/
 int time;  /*记录调入内存时间*/    //（lru那用到）
 int index; //记录调入内存的先后次序  //从1开始（FIFO那用到）
}Page;          /* 页面逻辑结构，结构为方便算法实现设计*/
Page b[10];      /*内存单元数*/ //从0开始

int c[10][150];  /*暂保存内存当前的状态：缓冲区*/
int queue[100];    /*记录调入队列*/
int K;       /*调入队列计数变量*/ 

/*初始化内存单元、缓冲区*/
void Init(Page *b,int c[10][150])
{
 int i,j;
 for(i=0;i<M;i++)
 {
 b[i].num=-1;
 b[i].time=M-i-1;
 b[i].index=i+1;
 }
 for(i=0;i<M;i++)
 for(j=0;j<N;j++)
  c[i][j]=-1;
} 

/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/
int GetMaxTime(Page *b)
{
 int i;
 int max=-1;
 int tag=0;
 for(i=0;i<M;i++)
 {
 if(b[i].time>max)
 {
  max=b[i].time;
  tag=i;
 }
 }
 return tag;
} 

/**int GetMinTime(Page *b)
{
 int i;
 int min=1000;
 int tag=0;
 for(i=0;i<M;i++)
 {
 if(b[i].time<min)
 {
  min=b[i].time;
  tag=i;
 }
 }
 return tag;
} **/

/*判断页面是否已在内存中*/
int  Equation(int fold,Page *b)
{
 int i;
 for(i=0;i<M;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);  //判断页面是否已在内存中，val代表在内存中的位置
 if (val>=0)    //在内存中
 {
 b[val].time=0;  //存在就把那个东西的时间变成0
 for(i=0;i<M;i++)
  if (i!=val)
  b[i].time++; // 其他的时间就要累加
 }
 else
 {
 queue[++K]=fold;/*记录调入页面*/
 val=GetMaxTime(b);  //取得在内存中停留最久的页面,默认状态下为最早调入的页面，val代表在内存中的位置
 b[val].num=fold;
 b[val].time=0;
 for(i=0;i<M;i++)
  if (i!=val)
  b[i].time++;
 }
} 

//FIFO核心部分   先进先出置换算法
void FIFO(int fold,Page *b)
{
 int i;
 int val;
 bool flag=false;
 val=Equation(fold,b);  //判断页面是否已在内存中，val代表在内存中的位置

 if (val<0)    //不在内存中
 {
 queue[++K]=fold;/*记录调入页面*/
 for(i=0;i<M;i++)
 {
  if (b[i].num<0)//如果有空
  {
  b[i].num=fold;
  b[i].index=i+1;
  flag=true;
  break;
  }
 }
 if (flag==false)//如若没有空余则找到最先进去的被淘汰
 {
  for(i=0;i<M;i++)
  {
  if(b[i].index==1)
  {
   val=i;
  }
  }
  b[val].num=fold;
  b[val].index=M;
  for(i=0;i<M;i++)
  {
  if(i!=val)
     b[i].index--; //因为有一个被淘汰了，所有其他的Index就需要更新
  }
 }
 }
}

//Optimal核心部分   最佳置换算法
void Optimal(int a[150],int pos,Page *b)
{
 int i,j;
 int val;
 int fold=a[pos];
 bool flag=false;

 val=Equation(fold,b);  //判断页面是否已在内存中，val代表在内存中的位置

 if (val<0)    //不在内存中
 {
 queue[++K]=fold;/*记录调入页面*/
 for(i=0;i<M;i++)
 {
  if (b[i].num<0)
  {
  b[i].num=fold;
  flag=true;
  break;
  }
 }
 if (flag==false)
 {
  for(i=0;i<M;i++)
  {
  for(j=pos+1;j<N;j++)
  {
   if (b[i].num!=a[j])
   { b[i].time= 1000; }//如果后面不需要再用它了把时间改成最大1000
   else
   {
   b[i].time=j;//否则赋值为j
   break;
   }
  }
  }
  val=GetMaxTime(b);  //取得在内存中停留最久的页面,默认状态下为最早调入的页面，val代表在内存中的位置
  b[val].num=fold;
 }
 }
}

void LruMain(int a[150])
{
 int i,j;
 K=-1;
 Init(b, c);
 for(i=0;i<N;i++) //
 {
 Lru(a[i],b);
 c[0][i]=a[i];
 /*记录当前的内存单元中的页面*/
 for(j=0;j<M;j++)
  c[j][i]=b[j].num;
 } 

 /*结果输出*/
 printf("\n内存状态为：\n");
 Myprintf;
 for(j=0;j<N;j++)
 printf("|%2d ",a[j]);
 printf("|\n");

 Myprintf; //#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")  //*表格控制*/
 for(i=0;i<N;i++)
 {
 for(j=0;j<M;j++)
 {
  if(c[j][i]==-1)
  printf("%3c ",32);
  else
  printf("%3d ",c[j][i]);
 }
 printf("\n");
 } 

 Myprintf;
 printf("\n调入队列为:");
 for(i=0;i<K+1;i++)
 printf("%3d",queue[i]);
 printf("\n缺页次数为：%6d\n缺页率：%16.6f",K+1,(float)(K+1)/N);
}

void FIFOMain(int a[150])
{
 int i,j;
 K=-1;
 Init(b, c);
 for(i=0;i<N;i++) //
 {
 FIFO(a[i],b);
 c[0][i]=a[i];
 /*记录当前的内存单元中的页面*/
 for(j=0;j<M;j++)
  c[j][i]=b[j].num;
 }
 /*结果输出*/
 printf("\n内存状态为：\n");
 Myprintf;
 for(j=0;j<N;j++)
 printf("|%2d ",a[j]);
 printf("|\n");

 Myprintf; //#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")  //*表格控制*/
 for(i=0;i<N;i++)
 {
 for(j=0;j<M;j++)
 {
  if(c[j][i]==-1)
  printf("%3c ",32);//空格
  else
  printf("%3d ",c[j][i]);
 }
 printf("\n");
 } 

 Myprintf;
 printf("\n调入队列为:");
 for(i=0;i<K+1;i++)
 printf("%3d",queue[i]);
 printf("\n缺页次数为：%6d\n缺页率：%16.6f",K+1,(float)(K+1)/N);
}

void OptimalMain(int a[150])
{
 int i,j;
 K=-1;
 Init(b, c);
 for(i=0;i<N;i++) //
 {
 Optimal(a,i,b);
 c[0][i]=a[i];
 /*记录当前的内存单元中的页面*/
 for(j=0;j<M;j++)
  c[j][i]=b[j].num;
 }
 /*结果输出*/
 printf("\n内存状态为：\n");
 Myprintf;
 for(j=0;j<N;j++)
 printf("|%2d ",a[j]);
 printf("|\n");

 Myprintf; //#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")  //*表格控制*/
 for(i=0;i<N;i++)
 {
 for(j=0;j<M;j++)
 {
  if(c[j][i]==-1)
  printf("%3c ",32);
  else
  printf("%3d ",c[j][i]);
 }
 printf("\n");
 } 

 Myprintf;
 printf("\n调入队列为:");
 for(i=0;i<K+1;i++)
 printf("%3d",queue[i]);
 printf("\n缺页次数为：%6d\n缺页率：%16.6f",K+1,(float)(K+1)/N);
}

void main()
{
 int a[150];
 int i;
 char s;

 printf("请输入物理块数：");
 scanf("%d",&M);

 printf("请输入所要访问的页面数：");
 scanf("%d",&N);
 srand(time(NULL));
 for(i=0;i<N;i++)
 {
 a[i]=rand()%10;   /*随机生成要访问的页面流*/
 }
 printf("所要访问的页面号序列为：");
 for(i=0;i<N;i++)
 printf("%d ",a[i]);

 printf("\n");
 printf("页面置换步骤如下：\n");
 while(1)
  {
 printf("\n\n///");
 printf("\nPlease select 1:FIFO算法\n        2:LRU算法\n        3:Optimal算法\n        4:退出\n");
 scanf("%s",&s);
 switch(s)
 {
    case '1':FIFOMain(a);break;
    case '2':LruMain(a); break;
  case '3':OptimalMain(a); break;
    case '4':exit(0); break;
 }
 }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。