C语言实现FIFO算法与LRU算法

浏览数：29 / 时间：2015年06月08日

在操作系统中，当程序在运行过程中，若其所要访问的页面不再内存中而需要把他们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存调出一页程序或数据送磁盘的兑换区中。但哪一个页面调出，须根据一定的算法确定。通常，把选择换出页面的算法称为页面置换算法（Page-Replacement Algorithms）.置换算法的好坏将直接影响到系统的性能。

1) 先进先出(FIFO)页面置换算法

该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程调入内存，按先后顺序排成一个队列，并设置一个指针，称为替换指针，使他总能指向最老的页面。但该算法与进程与实际运行的规律不相适应，效率最差。

2) 最近最久为使用(LRU)算法

LRU算法是根据页面调入内存后的使用情况进行决策的。就是利用“最近的过去”作为“最近的将来”的近似，因此是将最近最久未使用的页面予以淘汰。该算法赋予每一个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,当淘汰一个页面时，选择现有页面中t值最大的，及最近最久为使用的页面予以淘汰。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

#include <stdio.h>
 
#define PAGES 12  /*页面引用页数*/
#define M 3      /*当前分配给改作业的物理块数*/
//#define M 4
/*页面引用串*/
int page[PAGES] =  {4,3,2,1,4,3,5,4,3,2,1,5};
int rel[M][PAGES];   /*存储结果数组*/
/*内存物理块结构体*/
typedef 
struct{
  int 
pnum;     /*该块中所存的页面号*/
  int 
tm;       /*从最近一次调入所经历的时间*/
}PBlock;
/*初始化物理块数组*/
void 
init(PBlock *pb)
{
  int 
i,j;
  //pb = (PBlock*)malloc(sizeof(PBlock)*M);
  for(i=0;i<M;i++){
    pb[i].pnum = -1;
    pb[i].tm 
= -1;
    for(j=0;j<PAGES;j++){
      rel[i][j] = -1;
    }
  }
}
/*打印结果数组*/
void 
printRelArr(int 
rel[M][PAGES])
{
  int 
i,j;
  for(i=0;i<M;i++){
    for(j=0;j<PAGES;j++){
      if(rel[i][j]==-1)
        printf("_ ");
      else
        printf("%d ",rel[i][j]);
    }
    printf("\n");
  }
}
/*打印一维数组*/
void 
printArr1(int 
*arr,int 
n)
{
    int 
i;
    for(i=0;i<n;i++){
      printf("%d ",arr[i]);
    }
    printf("\n");
}
/*查看页面号为num的页面是否在内存块中,存在返回1*/
int 
in_mem(int 
num,PBlock *pb,int 
m)
{
  int 
i;
  int 
b = 0;
  for(i=0;i<m;i++){
      if(pb[i].pnum == num){
        b = 1;
        break;
      }
  }
  return 
b;
}
/*FIFO 算法的实现,无需考虑时间*/
int 
fifo(PBlock *pb,int 
m)
{
  int 
lps=0;   /*缺页次数*/
  double 
lpp;   /*缺页率*/
  int 
p = 0;    /*替换指针*/
  int 
index =0;  /*页面号索引*/
  while(index<PAGES){
      if(!in_mem(page[index],pb,M)){    //如果该页面不在物理块中
        pb[p].pnum = page[index];        /*将该页面放入物理块中*/
        p = (p+1)%M;                     /*替换指针移动*/
        lps++;                           /*却也次数加 1*/
        for(int 
i=0;i<M;i++){
          rel[i][index] = pb[i].pnum;
        }
      }
      index++;
  }
  printf("FIFO算法所得缺页次数为 %d\n",lps);
  lpp = (double)lps/PAGES;
  printf("FIFO算法缺页率为 %0.4lf \n",lpp);
  printf("页面号序列为:\n");
  printArr1(page,PAGES);
  printf("结果数列为:\n");
  printRelArr(rel);
  return 
0;
}
/*获得最近最久的块*/
int 
getP(PBlock *pb,int 
p)
{
  int 
i;
  bool 
out = true;  //
  for(i=0;i<M;i++){
    if(pb[i].tm 
== -1){
      p = i;
      out = false;
      break;
    }
  }
  if(out){
    for(i=0;i<M;i++){
      if(pb[i].tm>pb[p].tm)
        p = i;
    }
  }
  return 
p;
}
int 
getEQnum(int 
num,PBlock *pb)
{
  int 
i;
  int 
in = -1;
  for(i=0;i<M;i++){
    if(pb[i].pnum == num){
      in = i;
      break;
    }
  }
  return 
in;
}
/*LRU算法*/
void 
lru(PBlock *pb,int 
m)
{
  int 
lps=0;   /*缺页次数*/
  double 
lpp;   /*缺页率*/
  int 
p = 0;    /*替换指针*/
  int 
index =0;  /*页面号索引*/
  while(index<PAGES){
      if(!in_mem(page[index],pb,m)){   /*如果页面不在物理块中*/
        p = getP(pb,p);
        pb[p].pnum = page[index];
        pb[p].tm 
= 0;
        lps++;
        for(int 
i=0;i<M;i++){
          rel[i][index] = pb[i].pnum;
        }
      }else{                         /*如果页面在物理块中*/
        int 
in = getEQnum(page[index],pb);  /*获取该页面在物理块中的索引*/
          pb[in].tm 
= 0;
      }
      int 
i;
      for(i=0;i<M;i++){
          if(i!=p&&pb[i].tm!=-1){
            pb[i].tm++;
          }
      }
      index++;
  }
  printf("LRU算法所得缺页次数为 %d \n",lps);
  lpp = 1.0*lps/PAGES;
  printf("LRU算法缺页率为: %0.4lf\n",lpp);
  printf("页面号序列为:\n");
  printArr1(page,PAGES);
  printf("LRU结果数组为:\n");
  printRelArr(rel);
}
int 
main()
{
    //printArr(rel);
  PBlock pb[M];
  init(pb);
  fifo(pb,M);
  init(pb);
  lru(pb,M);
  return 
0;
}