yemian.txt

页面置换算法:实现先进先出页面置换算法,最近最少使用页面置换算法,最少使用页面置换算法

//操作系统页面调用模拟
#include<stdlib.h>
#include<iostream.h>
#include<time.h>

struct page;
typedef struct Page *PPage;
struct Page{
 int num;
 int used;
 };

////////////////////////////
//函数功能:产生指令序列
//函数参数:指令序列数组
void instructing(int a[])
{
  srand( (unsigned)time( NULL ) );
  //语句可初始化一个随机数 ; 
  int s=rand()/32767*319;
  for(int i=0;i<320;i+=4)
   {a[i]=s;
    a[i+1]=a[i]+1;
    a[i+2]=a[i+1]*rand()/32767;
    a[i+3]=a[i+2]+1;
    s=a[i+3]+(319-a[i+3])*rand()/32767;
  }
}
///////////////////////////////////
//函数功能:内存初始化
//函数参数:内存页
void initial(PPage page[])
{
 for(int i=0;i<8;i++)
   {page[i]->num=-1;
    page[i]->used=0;   
   }
}
//////////////////////////////////////
//函数功能:实现先进先出页面置换算法
//函数参数:page[]内存页,内存页数sum,指令x,记录加载次数times
void FIFO(PPage page[],int sum,int x,int &times)
{
	int i;
  for(i=0;(page[i]!=NULL)&&(i<sum);i++)//内存中是否有指令的所在页
    if(page[i]->num==x/10)return ;
    times++;                            //没有,加载指令的所在页

  for(i=0;(page[i]!=NULL)&&(i<sum-1);i++)//老页向前覆盖
  {page[i]->num=page[i+1]->num;
     page[i]->used=page[i+1]->used;
  }                                       
  page[i]->num=x/10;                      //新页放最后    
  page[i]->used=0;

}
//////////////////////////////////////////////
//函数功能:最近最少使用页面置换算法
//函数参数:page[]内存页,内存页数sum,指令x,记录加载次数times
void LRU(PPage page[],int sum,int x,int &times)
{
  	int i,k;
  for(i=0;(page[i]!=NULL)&&(i<sum);i++)
   	{
		page[i]->used=page[i]->used+1;   //非被访问页记数加1
		if(page[i]->num==x/10)           //刚刚被访问的页记数清零
		{page[i]->used=0;return ;  }               
	}
    times++;                              //没有,加载指令的所在页
    if(i<sum-1){page[i]->num=x/10;page[i]->used=0;}//仍有剩余页
	else
	{
	 for(k=0,i=0;i<sum;i++)
       if(page[k]->used<page[i]->used)k=i; //寻找最长时间未被访问的页
	   page[k]->num=x/10;
	   page[k]->used=0;                    //刚刚被访问的页计数清零
	   	}
}
////////////////////////////////////////////
//函数功能:最少使用页面置换算法
//函数参数:page[]内存页,内存页数sum,指令x,记录加载次数times
void LFU(PPage page[],int sum,int x,int &times)
{
	int i,k;
  for(i=0;(page[i]!=NULL)&&(i<sum);i++)   //寻找内存是否有指令的所在页
		if(page[i]->num==x/10)            //被访问页计数加1    
		{page[i]->used+=1;return ;  }               
	    times++;                           //没有,加载指令的所在页
    if(i<sum-1){page[i]->num=x/10;page[i]->used=0;}//仍有剩余页
	else
	{
	 for(k=0,i=0;i<sum;i++)                  //寻找被访问次数最少的页
       if(page[k]->used>page[i]->used)k=i;   
	   page[k]->num=x/10;                     //将最少的替换出去
	   page[k]->used=0;                       //计数器清零
	   	}
}
//////////////////////
void main()
{
  int a[320],i=0,j=0,times=0;
  PPage page[8];

  instructing(a);
  
  for(i=0;i<320;i++)
   {cout<<a[i]<<"\t";
  if(i%10==9)cout<<endl;  }
  
  for(i=0;i<8;i++)
	  page[i]=(PPage)new Page;

  initial(page);
  cout<<"\n先进先出页面置换算法命中率(内存4-8页):\n";
  for(i=4;i<=8;i++)
  {
    times=0;
	 for(j=0;j<320;j++)
		 FIFO(page,i,a[j],times);
    double x=1.0-times/320.0;
    cout<<i<<"页:"<<x*100<<"%"<<"\t";      //输出命中率
  }

   initial(page);
  cout<<"\n最近最少使用页面置换算法命中率(内存4-8页):\n";
  for(i=4;i<=8;i++)
  {
    times=0;
	 for(j=0;j<320;j++)
		 LRU(page,i,a[j],times);
    double x=1.0-times/320.0;
    cout<<i<<"页:"<<x*100<<"%"<<"\t";      //输出命中率     
  }

  initial(page);
    cout<<"\n最少使用页面置换算法命中率(内存4-8页):\n";
  for(i=4;i<=8;i++)
  {
    times=0;
	 for(j=0;j<320;j++)
	   		 LFU(page,i,a[j],times);	
	double x=1.0-times/320.0;           //输出命中率
    cout<<i<<"页:"<<x*100<<"%"<<"\t";
  }
  

}