hnru.cpp

最近未使用页淘汰（NRU）算法或者时钟算法是实际使用的诸多页淘汰算法中的一种。本课程设计是使用C程序设计语言

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

typedef struct
{
	int pagenum;     //页号    
	int mbit;        //修改位 
}Page;               //页面请求队列    

typedef struct
{
	int pageno;     //页号
	int rbit;          //访问位
	int mbit;          //修改位
	int status;     //该页的状态位，表示是否被占用
}Wspace;

void print(Page *page,Wspace *wspace,int j,int wnum)
{   int k;
    printf("申请的页号:\n");
    printf("pagenum mbit\n");
    printf("%4d  %4d\n",(page+j)->pagenum,(page+j)->mbit);
    printf("内存中的页号：\n");
    printf("pagenum rbit mbit\n");
         for(k=0;k<wnum;k++)
		  {
            printf("%d        %d    %d",wspace[k].pageno,wspace[k].rbit,wspace[k].mbit);
            printf("\n");
		  }
}

void callin(Page *page,Wspace *wspace,int n,int j)
{   wspace[n].pageno=(page+j)->pagenum;         //调入页面号
    wspace[n].rbit=1;                           //访问位置1
	wspace[n].mbit=(page+j)->mbit;              //修改修改位
    wspace[n].status=1;                         //状态位置1，表示本页已被占用
}

void read(int argc,char * argv[],Page **page,int *pnum,int *wnum,Wspace **wspace)
{  FILE *file;
   char temp[80];
   int i;
   if(argc!=2) exit(0);
   if((file=fopen(argv[1],"r"))==NULL)
  {
    printf("read file failed\n");
    exit(0);
  }
   fscanf(file,"%5s %d",temp,wnum);
   fscanf(file,"%5s %d",temp,pnum);
   fscanf(file,"%s",temp);
   *wspace=(Wspace*)malloc(sizeof(Wspace)**wnum);
   *page=(Page*)malloc(sizeof(Page)**pnum);
   for(i=0;i<*wnum;i++)
   { (*wspace)[i].pageno=0;(*wspace)[i].rbit=0;(*wspace)[i].mbit=0;(*wspace)[i].status=0;}
   printf("wnum:%d\n",*wnum);    
   printf("pnum:%d\n",*pnum);    
   printf("pagenum mbit\n");
   for(i=0;i<*pnum;i++)
  {
    fscanf(file,"%d %d",&((*page)+i)->pagenum,&((*page)+i)->mbit);
	printf("%d %d\n",((*page)+i)->pagenum,((*page)+i)->mbit);
  }
   fclose(file);
}


void nru(Page *page,Wspace *wspace,int pnum,int wnum,int b[4])
{int i,j,m,n,k;
 
 for(j=0;j<pnum;j++)     //j表示申请页面的序号，处理完一次，j自动加1，直至申请页面全部处理完毕
 { 
    for(m=0;m<wnum;m++)
       if(wspace[m].pageno==(page+j)->pagenum) break;  //查找申请页是否在工作集
    if(m<wnum) 
	{
       callin(page,wspace,m,j);
	   print(page,wspace,j,wnum);        //若在工作集，则将该页调入至此，访问位置1，并输出相关信息
	}
	else
	{  for(k=0;k<wnum;k++)
	     if(wspace[k].status==0) break;      //查找工作集是否存在空闲页
	   if(k<wnum)
	   {  
         callin(page,wspace,k,j);
         print(page,wspace,j,wnum);        //若存在空闲页，则将该页调入至此，访问位置1，并输出相关信息
	   }
	   else
	   { 
         for(i=0;i<4;i++)  b[i]=0;//b数组各元素赋初始值为0
         for(m=0;m<wnum;m++)
         {  if(wspace[m].rbit==0&&wspace[m].mbit==0)  b[0]=1;//工作集存在访问位、修改位分别为00的页面时，b[0]置1
            if(wspace[m].rbit==0&&wspace[m].mbit==1)  b[1]=1;//工作集存在访问位、修改位分别为01的页面时，b[1]置1
            if(wspace[m].rbit==1&&wspace[m].mbit==0)  b[2]=1;//工作集存在访问位、修改位分别为10的页面时，b[2]置1   
            if(wspace[m].rbit==1&&wspace[m].mbit==1)  b[3]=1;//工作集存在访问位、修改位分别为11的页面时，b[3]置1
         } 
     
           
        if(b[0]==1)
		{
			for(n=0;n<wnum;n++)
			 if(wspace[n].rbit==0&&wspace[n].mbit==0) break;
			callin(page,wspace,n,j);        //如果b[0]=1,查找第一个访问位和修改位为00的页面，调入申请页至此
            for(n=0;n<wnum;n++)  wspace[n].rbit=0;     //遍历工作集，将各页访问位置0
            print(page,wspace,j,wnum);    //输出相关信息
		}
		else if(b[1]==1)
		{
            for(n=0;n<wnum;n++)
			 if(wspace[n].rbit==0&&wspace[n].mbit==1) break;
			callin(page,wspace,n,j);        //如果b[1]=1,查找第一个访问位和修改位为01的页面，调入申请页至此
            for(n=0;n<wnum;n++)  wspace[n].rbit=0;   //遍历工作集，将各页访问位置0
			print(page,wspace,j,wnum);    //输出相关信息
		}
		else if(b[2]==1)
		{
		    for(n=0;n<wnum;n++)
			 if(wspace[n].rbit==1&&wspace[n].mbit==0) break;
		    callin(page,wspace,n,j);       //如果b[2]=1,查找第一个访问位和修改位为10的页面，调入申请页至此
            for(n=0;n<wnum;n++)  wspace[n].rbit=0;   //遍历工作集，将各页访问位置0
		    print(page,wspace,j,wnum);    //输出相关信息
		}
		else
		{
			callin(page,wspace,0,j);       //调入申请页至工作集的第0页
            for(n=0;n<wnum;n++)  wspace[n].rbit=0;   //遍历工作集，将各页访问位置0
			print(page,wspace,j,wnum);    //输出相关信息
		}
	  }
  }	
  printf("\n");
 }
}


void main(int argc,char * argv[])
{  Page *page;
   Wspace *wspace;
   int pnum;
   int wnum;
   int b[4];
   read(argc,argv,&page,&pnum,&wnum,&wspace);
   nru(page,wspace,pnum,wnum,b);
   free(page);
   free(wspace);
}