首页 > 代码库 > C语言实现FIFO算法与LRU算法

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

2024-07-04 05:12:55   235人阅读

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

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

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

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

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

   

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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;
}

 

 


联系
我们