/*
实现最不经常使用页面置换算法（NFU）。

算法思想：选择访问次数最少的页面淘汰之。

实现这种算法的一种方法是在页表中为每一页增加一个计数器，一页一个。
页面第1次调入内存时，计算器置初值1。以后每次访问该页面时，计数器加1。
发生缺页中断时，选择计数器值最小的一页淘汰。
如果计数器值相同，则选择页面号小的那一页置换。

注意：假定内存中一共可以有10个页面。

程序运行时：

1． 输入：页面流文件，其中存储的是一系列页面号（用空格隔开），用来模拟待换入的页面。

2． 输出：

（1）对于每一个页面流文件，每换入一个页面（即：每读入一个页面号），判断是否有页面需要被换出。若有，把被换出的页面号输出到屏幕；若没有，则要在输出“*”即可。

（2）总缺页次数。

3． 处理要求：

程序运行时，首先提示“请输入页面流文件名：”；

输入文件名后，程序将读入文件中有关数据；

程序按照NFU算法模拟页面置换；

根据页面流文件和NFU算法，每换入一个页面，将被换出的页面号输出到屏幕，若没有换出页面输出“*”。
*/

#include <stdio.h>
#include <conio.h>

#define PAGENUM 3     //定义内存页面数
#define MAXSIZE 100   //定义页面流文件中页面的个数
#define NULLPAGE -1   //定义无效的页面

char pagebuf[MAXSIZE]; //用于保存输入的页面
int pagecnt;       //保存实际输入的页面数

char page[PAGENUM];   //内存页面
char page2[PAGENUM];   //内存页面的统计信息 (LFU算法里)

int loc;           //指向当前需要换出的位置 (FIFO算法里)
int exchangenum;     //总缺页次数


//读入页面流文件
int readfile(void)
{
  FILE *pfile;
  char filename[256];
  int i,j;
  char k;

  printf("请输入页面流文件名:
");
  scanf("%s",filename);
  pfile = fopen(filename,"rt");
  if(pfile == NULL)
  {
    printf("打开文件失败
");
    return 0;
  }

  j = 0;
  while(1)
  {
    i = fscanf(pfile,"%d",&k);
    if((i == EOF) || (i == 0))break; //读入失败时退出循环
    pagebuf[j] = k;
    j ++;
  }
  pagecnt = j; //输入的页面个数
  fclose(pfile);
  return 1;
}

//显示输入的页面流
void DisplayPageBuf(void)
{
  int i;

  printf("您输入的页面流:
");
  for(i = 0; i < pagecnt; i ++)
    printf("%d ",pagebuf);
  printf("
");
}

//初始化内存中的页面
void InitPage(void)
{
  int i;

  for(i = 0; i < PAGENUM; i ++)
  {
    page = -1;
    page2 = 0;
  }
}

//检查当前输入的页是否已经在内存中
//如果页面在内存中,返回该页面在内存中的位置
int PageIsInMemory(int pn)
{
  int i;

  for(i = 0; i < PAGENUM; i ++)
    if(page == pn)
        return i+1; //注意,这里加了1
  return 0;
}



/*算法思想
用一个指针始终指向下一个换入的位置
*/
void FIFO(void)
{
  int i;

  printf("先进先出页面置换算法(FIFO)算法输出:
");

  loc = 0;
  exchangenum = 0;
  for(i = 0; i < pagecnt; i ++)
  {
    if(PageIsInMemory(pagebuf))
        printf("%s ","*");       //页面已经在内存中,不需要换出
    else
    {
        if(page[loc] == NULLPAGE)   //页面没在内存中,不需要换出
          printf("%s ","*");
        else
          printf("%d ",page[loc]); //页面没在内存中,需要换出
         
        page[loc] = pagebuf;     //调整下一个要换入的位置
        loc ++;
        if(loc >= PAGENUM)loc = 0;
         
        exchangenum ++;         //缺页计数递增
    }
  }
  printf("
");
  printf("总缺页率: %d
",exchangenum);
}


/*算法思想
把最近访问的页面总是放在第一个页面,
这样最后一个页面就是需要换出的
*/
void LRU(void)
{
  int i,j,x;
  char y;

  printf("最近最少使用页面置换算法(LRU)输出:
");
 
  exchangenum = 0;
  for(i = 0; i < pagecnt; i ++)
  {
    x = PageIsInMemory(pagebuf);
    if(x)
    {
        printf("%s ","*");       //页面已经在内存中,不需要换出
       
        y = page[x-1];         //保存当前访问的页面
        for(j = x-1; j >= 1; j --) //调整页面顺序
        {
          page[j] = page[j-1];
        }
        page[0] = y;
    }
    else
    {
        if(i < PAGENUM)
        {
          printf("%s ","*");         //页面没在内存中,不需要换出
          page[PAGENUM-1 - i] = pagebuf;  
        }
        else
        {
          printf("%d ",page[PAGENUM-1]);   //页面没在内存中,需要换出
          for(j = PAGENUM-1; j >= 1; j --) //调整页面顺序
            page[j] = page[j-1];
          page[0] = pagebuf;   //保存调入的页面
        }

        exchangenum ++;
    }
  }
  printf("
");
  printf("总缺页率: %d
",exchangenum);
}

/*算法思想
对每个内存页面做访问次数统计,访问次数最少的被换出内存
如果有几个页面同时满足调出的条件,选择页面号最小的那个调出
对于每个新调入的页面,访问次数为1
*/
void LFU(void)
{
  int i,j;
  int k;
  int l;
  int m;

  printf("最近最不常用使用页面置换算法(LFU)输出:
");
  loc = 0;
  exchangenum = 0;
  for(i = 0; i < pagecnt; i ++)
  {
    j = PageIsInMemory(pagebuf);
    if(j)
    {
        printf("%s ","*"); //页面已经在内存中,不需要换出
        page2[j-1] ++;   //访问次数递增
    }
    else
    {
        if(i < PAGENUM) //页面没在内存中,不需要换出
        {
          printf("%s ","*");
          page = pagebuf;
          page2 = 1;
        }
        else
        {
          //寻找需要换出的页面
          //满足访问次数最少并且页面号最小
         
          k = page2[0]; //保存访问次数
          l = page[0]; //保存对应页号
          m = 0;     //保存换出的页面位置
         
          for(j = 1; j < PAGENUM; j ++)
          {
            if(k > page2[j])
            {
                k = page2[j];
                l = page[j];
                m = j;
            }
            else if((k == page2[j]) && (l > page[j]))
            {
                k = page2[j];
                l = page[j];
                m = j;
            }    
          }
          printf("%d ",l); //打印换出的页面号
          page[m] = pagebuf;
          page2[m] = 1;
        }
        exchangenum ++;
    }
  }
  printf("
");
  printf("总缺页率: %d
",exchangenum);
}

void main()
{
  readfile();
  DisplayPageBuf();
  printf("
");
  FIFO();
  InitPage();
  printf("
");
  LRU();
  InitPage();
  printf("
");
  LFU();
  getch();
}

更多资料尽在四联自考论坛（http://bbs.4lzx.com），转贴请保留此信息。