#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;
}
