经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C 语言 » 查看文章
先进先出(FIFO)页面置换算法C语言实现、最近最久未使用(LRU)页面置换算法C语言实现
来源:cnblogs  作者:S_MIL  时间:2021/12/15 9:05:44  对本文有异议

1.实现效果

 

 2.实现源代码

  1 #include<iostream>
  2 #include<process.h>
  3 #include<stdlib.h>
  4 #include<ctime>
  5 #include<conio.h>
  6 #include<stdio.h>
  7 #include<string.h>
  8 using namespace std;
  9 
 10 #define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")/*表格控制*/
 11 #define bsize 4 //物理块大小
 12 #define psize 16 //进程大小 
 13  void chushihua();//初始化函数
 14  void ymzh();
 15  void yemianzhihuan ();
 16  void changeaddr(struct Page p[], int logaddr);
 17  void dizhizhuanhuan(); 
 18  void menu();
 19  int wang();
 20  
 21  int yemianliu[32]={0};//全局变量数组,地址流
 22  int p;
 23  struct Page  {
 24      int pno;//页号
 25      int flag;//标志位
 26      int cno;//主存号
 27      int modf;//修改位
 28      int addr;//外存地址
 29 }Page;  //全局变量p是一共有多少地址流 
 30 
 31  typedef struct pagel
 32  {
 33      int num; /*记录页面号*/ 
 34      int time;  /*记录调入内存时间*/
 35  }Pagel;  /*页面逻辑结构,方便算法实现*/
 36  
 37  Pagel b[bsize]; /*内存单元数*/
 38  int c[bsize][psize];/*保存内存当前的状态:缓冲区*/
 39  int queue[100];/*记录调入队列*/
 40  int k;/*调入队列计数变量*/
 41  int phb[bsize]={0};//物理块标号
 42  int pro[psize]={0};//进程序列号
 43  int flag[bsize]={0};//进程等待次数(存放最久未被使用的进程标志)*/
 44  int i=0,j=0;//i表示进程序列号,j表示物理块号*/
 45  int m =-1,n =-1;//物理块空闲和进程是否相同判断标志*/
 46  int mmax=-1, maxflag=0;//标记替换物理块进程下标*/ 
 47  int count =0; //统计页面缺页次数
 48  
 49  void chushihua() //初始化函数
 50 {
 51      int t;
 52      srand(time(0));//随机产生指令序列
 53          p=12+rand()%32;
 54      cout<<"地址流序列:";
 55      cout<<endl;
 56      for(i=0; i<p; i++)
 57      {
 58          t=1+rand()%9;
 59          yemianliu[i]=t;//将随机产生的指令数存入页面流
 60     }
 61     for (i=p-1;i>=0;i--)
 62     {
 63         cout<<yemianliu[i]<<" ";
 64     }
 65     cout<<endl;
 66 }
 67 void ymzh() 
 68 {
 69     chushihua();
 70      yemianzhihuan();
 71 }
 72 
 73  void yemianzhihuan()
 74  {
 75       int a;
 76      printf("----------------------------------\n");
 77      printf("☆☆欢迎使用分页模拟实验系统☆☆\n");
 78      printf("----------------------------------");
 79      printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
 80      printf("☆☆1.进入硬件地址变换算法  ☆☆\n");
 81      printf("☆☆------------------------☆☆\n");
 82      printf("☆☆2.进入页面置换算法      ☆☆\n");
 83      printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); 
 84      printf("请输入您的选择:");
 85  switch(a)
 86  {
 87      case 1:
 88          ymzh(); 
 89          break;
 90      case 2:
 91          wang();
 92          break;
 93      default:
 94      cout<<"输入有误,请重新输入!"<<endl;
 95      break;
 96  }
 97 }
 98 
 99  void changeaddr(struct Page p[], int logaddr){//地址变换
100      int j=logaddr/64;//对应的块号
101      int k=logaddr%64; //对应的偏移量
102      int flag=0;
103      int addr;
104      for(int i=0;i<8;i++)
105      {
106         if(p[i].pno==j)//找到对应的页号
107         {
108             if(p[i].flag==1)//页面标志为1
109             {
110              addr=p[i].cno*64+k;
111              cout<<"物理地址为:"<<addr<<endl;
112              cout<<"详细信息:"<<"\t页面号:"<<p[i].pno<<"\t 主存号:"<<p[i].cno<<"\t偏移量:"<<k<<endl;
113              flag=1;
114              break;
115             }
116         }
117     }
118     
119         if(flag==0)
120             cout<<"该页不在主存,产生缺页中断"<<endl;
121     }
122     
123  void dizhizhuanhuan()
124  {
125      int a;
126      int ins;//指令逻辑地址
127      struct Page p[8];
128     p[0].pno=0;p[0].flag=1;p[0].cno=5;p[0].modf=1;p[0].addr=011;
129     p[1].pno=1;p[1].flag=1;p[1].cno=8;p[1].modf=1;p[1].addr=012;
130     p[2].pno=2;p[2].flag=1;p[2].cno=9;p[2].modf=0;p[2].addr=013;
131     p[3].pno=3;p[3].flag=1;p[3].cno=10;p[3].modf=0;p[3].addr=015;
132     p[4].pno=4;p[4].flag=0;p[4].addr=017;
133     p[5].pno=5;p[5].flag=0;p[5].addr=025;
134     p[6].pno=6;p[6].flag=0;p[6].addr=212;
135     p[7].pno=7;p[7].flag=0;p[7].addr=213;
136      printf("\t\t\t--------------------------------\n");
137      printf("\t\t\t☆☆欢迎使用分页模拟实验系统☆☆\n");
138      printf("\t\t\t---------------------------------\n");
139      printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
140      printf("\t\t\t☆☆1.输入指令              ☆☆\n");
141      printf("\t\t\t☆☆------------------------☆☆\n");
142      printf("\t\t\t☆☆2.进入页面置换算法      ☆☆\n");
143      printf("\t\t\t☆☆------------------------☆☆\n");
144      printf("\t\t\t☆☆0.EXIT                  ☆☆\n");
145      printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
146  while(a!=0)
147  {
148     cout<<endl<<"请输入您的选择:";
149      cin>>a;
150      
151     cout<<"页号"<<"标记位"<<"外存地址"<<"主存号"<<endl;
152      for(int i=0;i<8;i++)
153      {
154          cout<<p[i].pno<<"\t"<<p[i].flag<<"\t"<<p[i].addr<<"\t";
155          if(p[i].flag)
156          cout<<p[i].cno;
157          cout<<endl;
158     }
159     
160  switch(a)
161  {
162      case 0:printf("\t\t\t再见!\t\t\t\n"); break;
163      case 1: 
164          cout<<"请输入指令的逻辑地址:";
165          cin>>ins;
166          changeaddr(p, ins);break;
167      case 2: system("CLS"); a=wang();break;
168      default:cout<<"输入有误,请重新输入!"<<endl;break;
169     }
170 }
171 }
172 
173  void menu() 
174  {
175  int a;
176      printf("\t\t\t--------------------------------\n");
177      printf("\t\t\t☆☆欢迎使用分页模拟实验系统☆☆\n");
178      printf("\t\t\t---------------------------------\n");
179      printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
180      printf("\t\t\t☆☆1.输入指令              ☆☆\n");
181      printf("\t\t\t☆☆------------------------☆☆\n");
182      printf("\t\t\t☆☆2.进入页面置换算法      ☆☆\n");
183      printf("\t\t\t☆☆------------------------☆☆\n");
184      printf("\t\t\t☆☆0.EXIT                  ☆☆\n");
185      printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
186      printf("请选择所要执行的操作:");
187      scanf("%d",&a);
188      switch(a)
189      {
190      case 0: printf("\t\t\t-再见!-\t\t\t\n");break;
191      case 1: dizhizhuanhuan (); break;
192      case 2: wang (); break;
193      default:cout<<"输入有误,请重新输入!"<<endl;break;
194     }
195 }
196 int main()
197  {
198      menu();
199 }
200 
201 //****************随机产生序列号函数
202  int* build()
203  {
204      printf("随机产生一个进程序列号为:\n"); 
205      int i=0;
206      for(i=0; i<psize; i++)
207      {
208          pro[i]=10*rand()/(RAND_MAX+1)+1;
209          printf("%d ", pro[i]);
210 }
211      printf("\n");
212      return(pro);
213 }
214 
215 //***************************************查找空闲物理块
216  int searchpb()
217  {
218      for (j=0;j<bsize; j++)
219      {
220          if(phb[j] == 0)
221          {
222                m=j;
223              return m;
224              break;
225         }
226     }
227      return -1;
228 }
229 //************************************查找相同进程 
230  int searchpro() 
231  {
232      for(j=0;j< bsize;j++)
233      {
234          if(phb[j] =pro[i])
235          {
236              n=j;
237              return j;
238         }
239     }
240  return -1;
241 }
242 
243 //*************************初始化内存
244 void empty()
245  {
246      for(i=0;i<bsize;i++)
247          phb[i]=0;
248      count=0;   //计数器置零
249 }   //******先进先出页面置换算法
250  void FIFO()
251 {
252      for( i=0; i<psize; i++)
253      {
254 //     m=searchpb();
255 //     n=searchpro();   
256         //找到第一个空闲的物理快
257         for(j=0;j<bsize;j++) {
258             if(phb[j] == 0){
259                 m=j;
260                 break;
261             }
262         }
263         //找与进程相同的标号
264         for(j=0;j<bsize;j++) {
265             if(phb[j] == pro[i]){
266                 n=j;
267             }
268         }
269 
270  //找flag值最大的
271      for(j=0;j<bsize;j++)
272     {
273          if(flag[j]>maxflag)
274          {
275              maxflag = flag[j];
276              mmax = j;
277         }
278     }
279     
280     if(n == -1)//不存在相同进程
281     {
282         if(m != -1)//存在空闲物理块 
283         {
284             phb[m]=pro[i];//进程号填入该空闲物理块
285 //             count++;
286              flag[m]=0;
287              for (j=0;j<=m; j++)
288              {
289                  flag[j]++;
290             }
291             m=-1;
292         }
293          else//不存在空闲物理块
294          {
295              phb[mmax] =pro[i];
296              flag[mmax] =0;
297              for (j=0;j<bsize;j++)
298             {
299                  flag[j]++;
300             }
301              mmax = -1;
302              maxflag = 0;
303              count++;
304         }
305     }
306     else//存在相同的进程
307     {
308          phb[n] = pro[i];
309          for(j=0;j<bsize;j++)
310         {
311              flag[j]++;
312         }
313         n=-1;
314     }
315      for(j=0;j < bsize;j++)
316      {
317         printf("%d ", phb[j]);
318     }
319          printf("\n");
320     }
321      printf("缺页次数为:%d\n",count);
322      printf("缺页率 :%16. 6f",(float)count/psize); 
323      printf("\n");
324 }
325 /*初始化内存单元、缓冲区*/
326  void Init(Pagel *b,int c[bsize][psize])
327  {
328      int i,j;
329      for (i=0;i<psize;i++)
330      {
331          b[i].num=-1;
332          b[i].time=psize-i-1;
333 }
334  for(i=0;i<bsize;i++)
335      for(j=0;j<psize;j++)
336         c[i][j]=-1;
337 }
338 /*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/
339  int GetMax(Pagel *b)
340  {
341      int i;
342      int max=-1;
343      int tag=0;
344      for(i=0;i<bsize;i++)
345      {
346          if(b[i].time>max)
347          {
348              max=b[i].time;
349              tag= i;
350         }
351     }
352      return tag;
353 }
354 
355 /*判断页面是否已在内存中*/
356  int Equation(int fold, Pagel *b)
357  {
358      int i;
359     for(i=0;i<bsize;i++)
360     {
361          if(fold==b[i]. num)
362              return i;
363     }
364      return -1;
365 }
366 /*LRU核心部分*/
367  void Lruu(int fold, Pagel *b)
368  {
369      int i;
370      int val;
371      val=Equation(fold, b);
372      if (val>=0)
373      {
374          b[val].time=0;
375          for(i=0;i<bsize;i++)
376              if (i!=val)
377                  b[i].time++;
378     }
379      else
380      {
381          queue[++k]=fold;/*记录调入页面*/
382          val=GetMax(b);
383          b[val].num=fold;
384          b[val].time=0;
385          for (i=0;i<bsize;i++){
386          
387 //         URLcount++;
388              if (i!=val)
389                  b[i].time++;
390         }
391     }
392 }
393 
394  void LRU()
395  {
396      int i,j;
397      k=0;
398      Init(b, c);
399      for(i=0; i<psize; i++)
400      {
401          Lruu(pro[i],b);
402          c[0][i]=pro[i];
403         /*记录当前的内存单元中的页面*/
404          for(j=0;j<bsize;j++)
405             c[j][i]=b[j].num;
406     }  
407 
408     /*结果输出*/
409      printf("内存状态为:\n");
410      Myprintf;
411     for(j=0;j<psize;j++)
412          printf("|%2d", pro[j]);
413      printf("|\n");
414      Myprintf;
415  
416      for(i=0;i<bsize;i++)
417      {
418          for(j=0; j<psize; j++)
419          {
420              if(c[i][j]==-1)
421                  printf("|%2c",32);
422               else
423                  printf("|%2d",c[i][j]);
424         }
425          printf("|\n");
426     }
427 
428      Myprintf;
429 //     printf("\n调入队列为:");
430 //    for(i=0;i<k;i++)
431 //        printf("%3d", queue[i]);
432         
433     printf("\n缺页次数为:%6d\n   缺页率 :%16. 6f", k+1,(float)(k+1)/psize); 
434 }
435 
436 //********主函数
437  int wang()
438  {
439      int sel;
440      do{
441      printf("\t\t\t--------------------------------\n");
442      printf("\t\t\t☆☆欢迎使用分页模拟实验系统☆☆\n");
443      printf("\t\t\t---------------------------------\n");
444      printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
445      printf("\t\t\t☆☆       虚拟内存         ☆☆\n");
446      printf("\t\t\t☆☆------------------------☆☆\n");
447      printf("\t\t\t☆☆1.产生随机序列          ☆☆\n");
448      printf("\t\t\t☆☆------------------------☆☆\n");
449      printf("\t\t\t☆☆2.最近最久未使用        ☆☆\n");
450      printf("\t\t\t☆☆------------------------☆☆\n");
451      printf("\t\t\t☆☆3.先进先出              ☆☆\n");
452      printf("\t\t\t☆☆------------------------☆☆\n");
453      printf("\t\t\t☆☆0.退出                  ☆☆\n"); 
454      printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
455      printf("请选择所要执行的操作:");
456      scanf("%d",&sel);
457      switch(sel)
458     {
459          case 0: printf("\t\t\t再见!t\t\t\n"); break;
460          case 1: build(); break;
461          case 2: printf("最近最久未使用\n"); LRU();empty(); printf("\n");break;
462          case 3: printf("先进先出算法\n"); FIFO();empty();printf("\n");break;
463          default:printf("请输入正确的选项号!");printf("\n\n");break;
464     }
465 }while(sel !=0 );
466      return sel;
467 }

 

 

原文链接:http://www.cnblogs.com/SMIL/p/15675161.html

 友情链接: NPS