LRU页面置换算法模拟-最近最久未使用置换算法 第2页

#include<stdio.h>
#include<conio.h>
#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<N;i++)
       {
              b[i].num=-1;+
              b[i].time=N-i-1;
       }
       for(i=0;i<M;i++)
              for(j=0;j<N;j++)
                     c[i][j]=-1;
}


/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/
int GetMax(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    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);
       if (val>=0)
       {
              b[val].time=0;
              for(i=0;i<M;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<M;i++)
                     if (i!=val)
                            b[i].time++;
       }
}
/*主程序*/
void main()
{
       int a[N]={1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4};
       int i,j;
start: 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");
       Myprintf;
       for(j=0;j<N;j++)
              printf("|%2d ",a[j]);
       printf("|\n");
       Myprintf;
       for(i=0;i<M;i++)
       {     for(j=0;j<N;j++)
              {
              if(c[i][j]==-1)
                     printf("|%2c ",32);
              else
                     printf("|%2d ",c[i][j]);
              }
              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);
       printf("\nAre you continuing!\ty?");
       if(getche()=='y')
              goto start;

}

 


四、测试与评价

 

1、程序运行结果输出

内存状态为:

 

|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|

 

| 1 | 0 | 1 | 0 | 2 | 4 | 1 | 0 | 0 | 8 | 7 | 5 | 4 | 3 | 2 | 3 | 4 |

 

|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|

 

| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 |

 

|   | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 4 |

 

|   |   |   |   | 2 | 2 | 2 | 2 | 2 | 8 | 8 | 8 | 8 | 3 | 3 | 3 | 3 |

 

|   |   |   |   |   | 4 | 4 | 4 | 4 | 4 | 7 | 7 | 7 | 7 | 2 | 2 | 2 |

 

|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|

 

 

 

调入队列为:  1  0  2  4  8  7  5  4  3  2

 

缺页次数为:    10

 

缺页率:        0.588235

 

Are you continuing!     y?

 

2、  程序执行是稳定的,高效的。在LRU算法中,要找出最近最久未使用的页面的话,就必须设置有关的访问记录项,且每一次访问这些记录项,页面都必须更新这些记录项。这个记录项在此程序中为

 

typedef struct page

 

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

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

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

如此显然要花费较大的系统开销(包括时间和空间上的),这也是实际系统中不直接采用LRU算法作为页面置换算法的直接原因,但由于其在页面置换的优越性,实际系统常使用LRU的近似算法。

3、由于程序旨在页面置换算法的模拟,程序并没有设计自动执行的功能,这也是本设计的缺陷。

上一页  [1] [2] 

Copyright © 2007-2012 www.chuibin.com 六维论文网 版权所有