#include<iostream>
#include<windows.h>
using namespace std;
typedef struct node
{
int name;
struct node *next;
}Linklist;
typedef struct
{
Linklist *front,*rear;
}LQueue;
LQueue *p;
LQueue *q;
void InitQueue(LQueue *qu)//置空队OK
{
qu->front=new Linklist;
qu->front->next=NULL;
qu->rear=qu->front;
}
int Empty(LQueue *qu)//判队空 ok
{
if(qu->front==qu->rear)
return 1;
else
return 0;
}
void EnQueue(LQueue *qu,int n)//入队
{
qu->rear->next=new Linklist;
qu->rear=qu->rear->next;
qu->rear->name=n;
qu->rear->next=NULL;
}
int DeQueue(LQueue *qu)//出队
{
Linklist *s;
if(Empty(qu))
return NULL;
else
{
s=qu->front;
qu->front=qu->front->next;
delete s;
return(qu->front->name);
}
}
int DeQueue_LRU(LQueue *qu,int x,int memoryblock_size)
{
Linklist *s;
int n,i;
if(Empty(qu))
return NULL;
else
{
if(x==1)
{
n=DeQueue(qu);
return(n);
}
else
{
s=qu->front;
for(i=0;i<x-2;i++)
{
s=s->next;
}
s=s->next->next;
return(s->next->name);
}
}
}
//定义位视图
int system_memory[8][8];
//定义页表
struct pagetable_entry
{
int memory_number;//块号
int memory_state;//状态位
}page_table[20], page_tableLRU[20];
//初始化位视图
void initsystem_memory()
{
int i,j,k;
for(k=0;k<8;k++)
{
system_memory[0][k]=1;
}
for(i=1;i<8;i++)
for(j=0;j<8;j++)
{
system_memory[i][j]=rand()%2;
}
/* for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
cout<<system_memory[i][j]<<" ";
}
cout<<endl;
}
*/
}
//初始化页表
void initpage_table()
{
int i;
for(i=0;i<20;i++)
{
page_table[i].memory_number=-1;
page_table[i].memory_state=0;
}
}
int saveopt[100];
struct new_OPT
{
int OPT_number;//块号
int OPT_state;//状态位
}save_OPT[20];
void initopt_table()
{
int i;
for(i=0;i<20;i++)
{
save_OPT[i].OPT_number=-1;
save_OPT[i].OPT_state=0;
}
}
//定义存储OPT时的内存块数组
int OPT_memoryblock[10];
//初始化OPT_memoryblock、OPT_memoryblocksub
void init_OPT_blocksub()
{
int i;
for(i=0;i<10;i++)
{
OPT_memoryblock[i] = -1;
}
}
void changeaddress(int b_num,int memo_size,int log_add)
{
int a,b,c;//页号,页内地址
a=log_add/memo_size;
b=log_add%memo_size;
c=b_num*memo_size+b;
cout<<"页号和偏移量:"<<a<<"---"<<b<<endl;
cout<<"物理地址为:"<<hex<<c<<endl;
}
void displaypagetabel(int page_size)
{
int i;
cout<<"页号\t"<<"块号\t"<<"标识位"<<endl;
for(i=0;i<page_size;i++)
cout<<i<<"\t"<<dec<<page_table[i].memory_number<<"\t"<<page_table[i].memory_state<<endl;
}
void displaymemory(int memoblock_size)
{
int i;
cout<<"主存块"<<endl;
for(i=memoblock_size-1;i>=0;i--)
{
cout<<dec<<OPT_memoryblock[i]<<endl;
}
}
void displaylesspage(int n1,int n2,int n3)
{
cout<<"总访问次数:"<<dec<<n1+n2+n3<<endl;
cout<<"缺页次数:"<<dec<<n1+n2<<endl;
double sum;
sum=((n1+n2)*100)/(n1+n2+n3);
cout<<"缺页率:"<<sum<<"%"<<endl;
}
void main()
{
int pagetabel_size,memoryblock_size,memory_size,logical_address,block_num;
char method;
int i,j,k=0,k1,k2,k3,k4,k5,cnt=0,cnt1=0,cnt2=0,num=0,opt=0,optcnt=0,optcnt1=0;
int n1,n2,m;
/////////////////////////////////////////////////
cout<<"请输入页表长度:"<<endl;
cin>>pagetabel_size;
/////////////////////////////////////////////////
cout<<"请输入块数:"<<endl;
cin>>memoryblock_size;
/////////////////////////////////////////////////
cout<<"请输入块的长度（b）:"<<endl;
cin>>memory_size;
/////////////////////////////////////////////////
cout<<"请输入置换算法FIFO或LRU(f or l)"<<endl;
cin>>method;
/////////////////////////////////////////////////
initsystem_memory();
initpage_table();
init_OPT_blocksub();
initopt_table();
p=new LQueue;
q=new LQueue;
InitQueue(p);
InitQueue(q);
displaypagetabel(pagetabel_size);
displaymemory(memoryblock_size);
while(1)
{
if(method=='f')
{
cout<<"请输入逻辑地址:"<<endl;
cin>>hex>>logical_address;
if(logical_address==-1)
{
if(num==0)
exit(1);
else
{
/* for(int j=0;j<num;j++)
{
cout<<saveopt[j]<<endl;
}*/
int o,o5,o4,o2,o1,o6,s,o7;
for(s=0;s<memoryblock_size;s++)
{
save_OPT[s].OPT_number=saveopt[s];
// cout<<save_OPT[s].OPT_number<<endl;
}//将数据放到块中
for(o7=0;o7<memoryblock_size;o7++)
{
cout<<save_OPT[o7].OPT_number<<endl;
}
system("pause");
// cout<<"s="<<s<<endl;
for(o=memoryblock_size;o<num;o++)
{
for(o1=0;o1<memoryblock_size;o1++)//测块中数据和块外一样不一样
{
if(save_OPT[o1].OPT_number==saveopt[o])//测下一个数据等不等
{
for(o7=0;o7<memoryblock_size;o7++)
{
cout<<save_OPT[o7].OPT_number<<endl;
}
system("pause");
goto a1;
}
}
for(o2=o+1;o2<num;o2++)//不等，测下一个，找最远的
{
for(int o3=0;o3<memoryblock_size;o3++)
{
if(save_OPT[o3].OPT_number==saveopt[o2]&&save_OPT[o3].OPT_state==0&&optcnt<memoryblock_size-1)
{
save_OPT[o3].OPT_state=1;
optcnt++;
}
}
}
optcnt=0;
for(o4=0;o4<memoryblock_size;o4++)
{
if(save_OPT[o4].OPT_state==0)
{
save_OPT[o4].OPT_number=saveopt[o];
optcnt1++;//计缺页
goto a0;
}
}
a0: ;
for(o5=0;o5<memoryblock_size;o5++)
{
save_OPT[o5].OPT_state=0;
}
for(o7=0;o7<memoryblock_size;o7++)
{
cout<<save_OPT[o7].OPT_number<<endl;
}
system("pause");
a1: ;
}
cout<<"-----最佳置换算法-----"<<endl;
cout<<"总访问次数:"<<num<<endl;
cout<<"缺页次数:"<<optcnt1+memoryblock_size<<endl;
double optsum;
optsum=(optcnt1+memoryblock_size)*100/num;
cout<<"缺页率:"<<optsum<<"%"<<endl;
exit(1);
}
}
else
{
n1=logical_address/memory_size;
saveopt[num]=n1;
num++;
if(n1>pagetabel_size)
{
cout<<"超出页表范围!请重新输入....."<<endl;
}
else
{
if(page_table[n1].memory_number!=-1)
{
cnt2++;
changeaddress(page_table[n1].memory_number,memory_size,logical_address);
displaylesspage(cnt,cnt1,cnt2);
displaypagetabel(pagetabel_size);
displaymemory(memoryblock_size);
}
if(page_table[n1].memory_number==-1&&cnt<memoryblock_size)
{
for(i=1;i<8;i++)
{
for(j=0;j<8;j++)
if(system_memory[i][j]==0)
{
cnt++;
system_memory[i][j]=1;
block_num=i*8+j+1;
changeaddress(block_num,memory_size,logical_address);
displaylesspage(cnt,cnt1,cnt2);
page_table[n1].memory_number=block_num;
page_table[n1].memory_state=1;
if(OPT_memoryblock[k]=-1&&k<memoryblock_size)
{
OPT_memoryblock[k]=n1;
k++;
}
EnQueue(p,n1);
displaypagetabel(pagetabel_size);
displaymemory(memoryblock_size);
break;
}
break;
}
}
if(page_table[n1].memory_number==-1&&cnt==memoryblock_size)
{
cnt1++;
n2=DeQueue(p);//出来的页号
EnQueue(p,n1);
changeaddress(page_table[n2].memory_number,memory_size,logical_address);
displaylesspage(cnt,cnt1,cnt2);
page_table[n1].memory_number=page_table[n2].memory_number;
