5种页面置换算法C++实现

计算并输出下述各种算法在不同内存容量下的命中率。 A. FIFO先进先出的算法 B. LRR最近最少使用算法 C. OPT最佳淘汰算法（先淘汰最不常用的页地址）

#include
#include
#include 
#include
struct aa{//结构体 模拟内存区
  int page;
  int count;//被命中次数
  aa* next;
  };


void main（）
{while（1）{//为了验证结果添加的循环 实验去掉
 time_t t;
 srand（unsigned（time（&t）））;////用来设置随机序列的第一个数，否则每次出来的序列都是一样的
 int injiimanswerffalsecountfangfatemp1minnnmm;
 double sum;
 aa *head*tail*temp*table*first*ti;
/* nn=4;mm=1;
 for（nn=4;nn<32;nn++）
 {
  for（mm=1;mm<5;mm++）
  {*/
 cout<<“输入物理块数：“;
 cin>>m;  //产生存储结构体的数量
 //m=nn;
 /**
 ***	FIFO 先进先出
 ***	LRR 最近最少使用算法
 ***	OPT	最优淘汰算法
 ***	LFR	最少访问页面算法
 ***	NUR	最近没有使用页面先淘汰
 **/
 cout< cout<<“fangfa:  1-FIFO;2-LRR;3-OPT;4-LFR;5-NUR“< cout<<“Mothed:“;
 cin>>fangfa;
 //fangfa=mm;
 ffalse=0;
 answer=0;
 table=new（aa）;//链表的表头
 temp=table;
 table->page=-1;
 table->count=0;
 head=table;
 for（ii=2;ii<=m;ii++）
 {
    table=new（aa）;//动态生成模拟内存区内的访问区间
    table->page=-1;//初始化
    table->count=0;
    temp->next=table;//原链表（下句temp=table使得temp总指向链表的最后一个结构体）的最后一个结构体的指向此结构体  
    temp=table;//刚创建的新的结构体，也就是链表最后的结构体  
    if （ii==m）{table->next=NULL;} //置空  
 }
 tail=table;//tail指向最后一个结构体   末尾
 temp=head;
 first=head;//head temp 全都指向链表头
 count=0; //计算指令所在页的根据
 i=0;
 while（i<320）
 {
	min=400;
    if （count==0） {n=（rand（）%320+1）%320; j=n/10;}
	if （count==1） {n=rand（）%（n+1）;j=n/10;}
	if（count==2） {j=（（n+1）%320）/10;}
	if（count==3） {j=（（rand（）%（320-n-2））+n+2）/10;}

   table=head;
   temp=head;
   answer=0;// 标志位 命中的时候置1 
   min=400;

    if （fangfa==5）
   {
		while（table!=NULL）
		{
			if （table->page==j）
			{
				answer=1;
				table->count=2;
			}
			table=table->next;
		}

		if （answer!=1）
		{
			table=head;
			while （table!=NULL）
			{
				if （table->count				{
					temp=table;
					min=table->count;
				}
				table=table->next;
			}

			if （temp->page!=-1） ++ffalse;
			
			temp->page=j;
			temp->count=1;
		}

		table=head;
		if （（i%32）==0）
		{
			while（table!=NULL）
			{
				if （table->page!=-1） table->count=1;
				// if （table->page==j）{answer=1;++（table->count）;}
				table=table->next;
			}
		}
   }//if fangfa=5结束

   //思想：循环中最少被访问者被替换
   if （（fangfa==4）||（fangfa==3））
   {
		while（table!=NULL）
		{
			if （table->page==j）//命中
			{
				answer=1;//更改标志位
				++（table->count）;//增加命中次数
			}
			table=table->next;
		}//直接返回外循环

		if（answer!=1）//此轮循环（外循环）中 所有结构体均未命中 替换
		{  
			table=head;//指向表头
			while （table!=NULL）
			{//遍历链表
				if （table->count				{
					temp=table;
					min=table->count;//循环所有的结构体之后 temp指向了整个链表中最少被访问（命中）的结构体
				}
				table=table->next;
			}

			if （temp->page!=-1）//不是第一次访问
			{
				++ffalse;//增加未命中次数
				temp->page=j;//temp指向为最少 替换掉最少的那个
				
				table=head;//重新指向
				while（table）
				{
					table->count=1;//全部链表访问次数赋1 为下一循环做准备 否则被替换掉的永远是这个位置（刚替换进来 count肯定最小）
					table=table->next;
				}
			}
			else{
				temp->page=j;//第一次访问 等于命中
		

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       5361  2011-06-28 20:08  test.cpp

----------- ---------  ---------- -----  ----

                 5361                    1