#include<stdio.h>

#include<iostream.h>

#include <stdlib.h>

#include<time.h>

//存放页地址流的数组

int pageNums[150]; 

//生成页地址流

void createPageAddr()

{

 srand((unsigned)time(0)); //以当前时间做随机种子

 int i,addr,pageN,count;

 count=0;

 i=0;

 while(i<150)  //每次循环，构造地址流的150个地址中的一个地址

 {

      if(count==0) {addr=(rand()%120+1)%120;pageN =addr/10;}

      //count=0表示，在[0, 119]的指令地址之间随机选取一起点M,顺序/执行一条指令(+1),即获得M+1的指令地址; pageNum为地址所在页号

 if(count==1) {addr=rand()%(addr+1);pageN=addr/10;}

      //count=1表示，在前地址[0, M+1]中随机选取一条指令并执行,该指令的地址为M;

      if(count==2) {pageN=((addr+1)%120)/10;}

 //顺序执行一一条指令，其地址为M+1; 

      if(count==3){pageN=(rand()%(120-(addr+2))+addr+2)%120/10;}

 //在后地址[M+2, 119]中随机选取一条指令并执行; /

      + +count;

      pageNums[i]=pageN;

      if(count==4){count=0;} //进入下一个4次循环，再分4步生成4个地址

      i++; 

 }                        

       //输出页地址流

      cout<<"页地址流(共150个虚存逻辑页地址):\n";

 for(i=0;i<150;i++) {cout<<pageNums[i]<<" ";}

 cout<<endl;

}

   struct aa{       //代表一个物理页的节点

 int page;  //物理页存放的虚存页号

 aa* next;  //指向下一物理页

};

   void main()

   {

      int i,m=4://4个物理页

      aa *head, *tail,*temp,*table;              //用于构建4个物理页的指针

      //构建4个节点的链表，表示4个物理页

      table=new(aa);                      //建 立第一一个物理页节点

 head=table;                 //链表头指针指向该节点

 table->page=-1;                //初值-1表示没有放置虚存页

 temp=table;                  //临时指针指向第一一个物理页

 for(i=2;i<=m;i++)                  //继续构建m-1个物理页

{ 

 table=new{aa);               //新建-一个物理页节点

      table->page=-1;

      temp->next=table;                   //前一 一个节点的next指向本节点，形成链表

 temp=table;                        //临时指针指向新建物理页节点

      if(i==m){table->next=NULL;}       //最后物理页节点next指针指向空

 }         

      tail=table;  //尾指针指向链表尾

      createPageAddr(); //生成页地址流

      //以下是LRU最近最少使用算法+

      int temp1;  //LRU算法中，temp1 临时保存物理页中命中的逻辑页号

 int answer; //LRU 算法中，页命中时(颇在内存) answer 置1

 int ffalse=0;  //LRU算法中，累加未命中次数+1

      for(i=0;i<150;i++)

 {

       answer=0; //页命中时(页在内存) answer置1

  temp=head;  //临时指针指向链表头

  table=head;

       while(table!=NULL) //循环查找内存中的虚页号， 看是否页命中

  {

         if(table->page==pageNum[i]) {answer=1;temp=table;}

//页命中，answer 置1, temp指向命中的物理页节点

         table=table->next;

  }

       if(answer==1) //如果页命中

  {

         temp1=temp->page;  //temnp1临时保存物理页中命中的逻辑页号

while (temp!=NULL&&temp->next!=NULL) 

//所有比命中页位置低的页号上移一个位置

{ temp->page=temp->next->page;

           temp=temp->next;

}

        tail->page=temp1; //命中的烦放入最 下面的物理页

  }

      if(answer!=1) //如果页没有命中

 {

       ffalse=ffalse+1; //末命中次数+1

//淘汰第-一个物理页中的逻辑页号，其它逻辑页号上移一个位置

  temp=head;

       while (temp!=NULL&&temp->next!=NULL) 

  {

          temp->page=temp->next->page;

 temp=temp->next;

  }

    tail->page=pageNums[i]; //新的逻辑页（虚页）放入最下面的物理页

      }

      //---------------------------------------------------------------------------------------

//输出物理块中虚页地址本次变化情况：

if (i==0) cout<< "物理块中虚页地址变化情况：\n";

if (i<20)                                     //仅显示前20个变化，可自己调节输出数目

{

     for(aa*ti=head;ti!=NULL;ti=ti->next) cout<<ti->page<<"  ";

        cout<<endl;

}

 }

  //-------------------------------------------------------------------------------------

  double sum=1.0-ffalse/120.0;                         //计算命中率

  cout<<"未命中次数:"<<ffalse<<" "<<endl;

  cout<<"LRR算法命中率:"<<sum<<" "<<endl;

}