#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<iostream>
using namespace std;
#define Maxsize 64
#define X 64
////***** 定义页表结构体*****////
struct Page
{
int Yh; //页表的页号
int kh; //页表的块号
int State; //页表的状态
};
typedef struct node
{
int data[Maxsize];
int top;
}SeqStack; //定义顺序栈
unsigned char RAM[8];
int Map[64];
int YeHao[X]; //定义访问页号的序列
int Length,Size,kuaisu; //定义页表的长度，页块大小，内存块的个数int C;
int Num; //定义内存队列节点的个数
int Visit[Maxsize]; //定义访问过的页面序列号
struct Page page1[100]; //定义页表结构体数组
struct Page page2[100];
struct Page page3[100];
int d; //定义逻辑地址
int Yh; //定义页号
int Yd; //定义相对地址
int v; //定义访问次数
int n1=0; //命中次数
int n2=0; //定义LRU算法的命中次数SeqStack *neichun1=(SeqStack *)malloc(sizeof(SeqStack));
SeqStack *neichun2=(SeqStack *)malloc(sizeof(SeqStack));
SeqStack *neichun3=(SeqStack *)malloc(sizeof(SeqStack));
///////*******创建位示图******//
void weishitu(){
int k=0;
srand(time(0));
for(int i=0;i<8;i++){
RAM[i]=(unsigned char)rand()%256;
}
cout<<endl;
for(int j=0;j<64;j++)
{
int x=j%8;int y=j/8;
unsigned char temp=(unsigned char)pow(2,x);
if(( unsigned char)(RAM[y]&temp)==temp)
Map[j]=1;
else
{
Map[j]=0;
}
}
for(int m=0;m<64;m++)
{
cout<<" "<<Map[m];
if(m%8==7)
cout<<endl;
}
}
////***********对栈的操作**********////
void setnull(SeqStack *s)
{
s->top=-1;
}
int StackIsEmpty(SeqStack *s)
{
if (s->top == -1)
return 1;
else
return 0;
}
void StackPush(SeqStack *s, int x)
{
s->top++;
s->data[s->top] = x;
}
int StackPop(SeqStack *s){
s->top--;
return(s->data[s->top+1]);
}
////*****将栈中的最后一个元素删除******////
void outStack(SeqStack *s){
int SS[Maxsize];
int j=0;
while(!StackIsEmpty(s)&&j<kuaisu)
{
SS[j]=StackPop(s);
j++;
}
for(int i=kuaisu-2;i>=0;i--)
{
StackPush(s,SS[i]);
}
}
////**********删除栈中的任意元素***********/////
void DeleteStack(SeqStack *s,int xx){
int SS[Maxsize];
int j=0;
while(!StackIsEmpty(s)&&s->data[s->top]!=xx&&j<kuaisu){
SS[j]=StackPop(s);
j++;
}
StackPop(s);
for(int i=j-1;i>=0;i--)
{
StackPush(s,SS[i]);
}
}
////**********将栈中的任意元素放到栈顶***********/////
void TopStack(SeqStack *s,int xx){
int SS[Maxsize];
int j=0;
while(!StackIsEmpty(s)&&s->data[s->top]!=xx&&j<kuaisu){
SS[j]=StackPop(s);
j++;
}
StackPop(s);
for(int i=j-1;i>=0;i--)
{
StackPush(s,SS[i]);
}
StackPush(s,xx);
}
void input(){
cout<<" 欢迎使用请求分页存储区管理实验"<<endl;
cout<<" 指导老师：金虎"<<endl; cout<<" "<<endl;
cout<<"输入页表长度:";
cin>>Length;
for(int i=0;i<Length;i++){
page1[i].Yh=i;
page1[i].kh=-1;
page1[i].State=0;
}
for(int j=0;j<Length;j++){
page2[j].Yh=j;
page2[j].kh=-1;
page2[j].State=0;
}
for(int k=0;k<Length;k++){
page3[k].Yh=k;
page3[k].kh=-1;
page3[k].State=0;
}
setnull(neichun1);
setnull(neichun2);
setnull(neichun3);
cout<<"输入内存块数:";
cin>>kuaisu;
cout<<"输入块长(k):";
cin>>Size;
C=Size*1024;
}
void address(){
printf("输入地址: ");
scanf("%x",&d);
Yh=d/C;
Yd=d%C;
if(Yh>Length-1)
{
cout<<"错误!! 地址越界!!"<<endl; cout<<"请重新输入逻辑地址:"; scanf("%x",&d);
Yh=d/C;
Yd=d%C;
}
printf("页号：%d\n",Yh);
printf("十进制大小:%d\n",d);
v++;
Visit[v-1]=Yh;
}
void output(Page page[10],SeqStack *Memory,int c,float e)
///page为页表，Memory为内存栈，c为物理地址，e为命中次数，f为缺页率{
float f;
cout<<"页号"<<" "<<"块号"<<" "<<"状态位"<<endl;
for(int i=0;i<Length;i++)
{
cout<<" "<<page[i].Yh<<" "<<page[i].kh<<" "<<page[i].State<<endl;
}
cout<<endl;
printf("内存分配块：\n");
cout<<"序号"<<" "<<"页号"<<endl;
for(int k=0;k<Memory->top+1;k++)
cout<<" "<<k<<" "<<Memory->data[k]<<endl;
for(int j=Memory->top+1;j<kuaisu;j++)
cout<<" "<<j<<" "<<"-1"<<endl;
cout<<endl;
printf(" 物理地址：%x \n",c);
printf(" 访问次数：%d \n",v);
int h=v-e;
printf(" 缺页次数：%d \n ",h);
f=(1-e/v)*100;
printf("缺页率:%5.2f%",f);
cout<<"%"<<endl;
}
void outopt(Page page[10],SeqStack *Memory,int x,float e)
///page为页表，Memory为内存栈，c为物理地址，e为命中次数，
{
float f; //定义f为缺页率
cout<<"页号"<<" "<<"块号"<<" "<<"状态位"<<endl;
for(int i=0;i<Length;i++)
{
cout<<" "<<page[i].Yh<<" "<<page[i].kh<<" "<<page[i].State<<endl;
}
printf("内存分配块：\n");
cout<<"序号"<<" "<<"页号"<<endl;
for(int k=0;k<Memory->top+1;k++)
cout<<" "<<k<<" "<<Memory->data[k]<<endl;
for(int j=Memory->top+1;j<kuaisu;j++)
cout<<" "<<j<<" "<<"-1"<<endl;
printf(" 访问次数：%d \n",x);
int h=x-e;
printf(" 缺页次数：%d \n ",h);
f=(1-e/x)*100;
printf("缺页率:%5.2f%",f);
cout<<"%"<<endl;
}
int jisu1(){
int c1;
for(int i=kuaisu;i<v;i++)
{
int flag0=0;
if(Visit[i]==neichun3->data[0])
{
flag0=1;
c1=i;
}
if(flag0==1) break;
if(Visit[i]!=neichun3->data[0])
c1=Maxsize+3;
}
return c1;
}
int jisu2(){
int c2;
for(int i=kuaisu;i<v;i++){
int flag0=0;
if(Visit[i]==neichun3->data[1])
{
flag0=1;
c2=i;
}
if(flag0==1) break;
if(Visit[i]!=neichun3->data[1]) c2=Maxsize+2;
}
return c2;
}
int jisu3(){
int c3;
for(int i=kuaisu;i<v;i++){
int flag0=0;
if(Visit[i]==neichun3->data[2])
{
flag0=1;
c3=i;
}
if(flag0==1) break;
if(Visit[i]!=neichun3->data[2]) c3=Maxsize+1;
}
return c3;
}
int Max(){
int c1=jisu1();
int c2=jisu2();
int c3=jisu3();
int Max0,Max;
if(c1>c2) Max0=c1;
else Max0=c2;
if(Max0>c3) Max=Max0;
else Max=c3;
return Max;
}
////*****先进先出（FIFO）算法******/////
void FIFO(){
if(page1[Yh].State==1) n1++;
else {
page1[Yh].State=1;
if(neichun1->top+1<kuaisu)
{
int flag=0;
for(int i=0;i<64;i++)
{
if(Map[i]==0)
{
flag=1;
Map[i]=1;
page1[Yh].kh=i;
StackPush(neichun1,Yh);
}
if(flag==1) break;
}
}
else{
int s=neichun1->data[0];
page1[Yh].kh=page1[s].kh;
page1[Yh].State=1;
page1[s].State=0;
page1[s].kh=-1;
outStack(neichun1);
StackPush(neichun1,Yh);
}
}
int wl=page1[Yh].kh*C+Yd;
output(page1,neichun1,wl,n1);
}
////*******LRU(最近最久未使用)*********//// void LRU(){
if(page2[Yh].State==1)
{
n2++;
TopStack(neichun2,Yh);
}
else{
page2[Yh].State=1;
if(neichun2->top+1<kuaisu)
{
int flag1=0;
for(int i=0;i<64;i++)
{
if(Map[i]==0)
{
flag1=1;
Map[i]=1;
page2[Yh].kh=i;
StackPush(neichun2,Yh);
}
if(flag1==1) break;
}
}
else{
int s=neichun2->data[0];
page2[Yh].kh=page2[s].kh;
page2[Yh].State=1;
page2[s].State=0;
page2[s].kh=-1;
outStack(neichun2);
StackPush(neichun2,Yh);
}
}
int wl=page2[Yh].kh*C+Yd;
output(page2,neichun2,wl,n2);
}
/////*********最佳(OPT)置换算法**********/////
void OPT(){
int m=0; //定义OPT算法的命中次数
for(int i=0;i<v;i++)
{
Yh=Visit[i];
if(page3[Yh].State==1) m++;
else{
page3[Yh].State=1;
if(neichun3->top+1<kuaisu)
{
int flag2=0;
for(int j=0;j<64;j++)
{
if(Map[j]==0)
{
flag2=1;
Map[j]=1;
page3[Yh].kh=j;
StackPush(neichun3,Yh);
}
if(flag2==1) break;
}
}
else
{
int leaf; //定义将要删除页号
int max=Max();
if(max==jisu1()) leaf=neichun3->data[0];
else if(max==jisu2()) leaf=neichun3->data[1];
else if(max==jisu3()) leaf=neichun3->data[2];
page3[Yh].kh=page3[leaf].kh;
page3[Yh].State=1;
page3[leaf].State=0;
page3[leaf].kh=-1;
DeleteStack(neichun3,leaf);
StackPush(neichun3,Yh);
}
}
outopt(page3,neichun3,i+1,m);
}
}
void main(){
input();
cout<<"位示图:";
weishitu();
cout<<" "<<endl; cout<<" 选择置换算法"<<endl;
cout<<endl;
cout<<" FIFO : F "<<endl;
cout<<endl;
cout<<" LRU: L "<<endl;
cout<<endl;
cout<<" OPT :O "<<endl;
cout<<endl;
cout<<" 位示图重置:R "<<endl;
cout<<" "<<endl; char A;
while(1){
cout<<" 输入算法:"<<endl;
cout<<">";
cin>>A;
switch(A){
case 'F':
case 'f': address();FIFO(); break;
case 'L':
case 'l': address();LRU();break;
case 'o':
case 'O':
{
cout<<"访问页号:"<<endl;
for(int i=0;i<v;i++){
cout<<Visit[i]<<" ";
}
cout<<endl;
OPT(); break;
}
case 'R':
case 'r': cout<<"位示图:"<<endl;
weishitu();
for(int i=0;i<v;i++){
Visit[i]=NULL;
}
v=0;
setnull(neichun1);
setnull(neichun2);
setnull(neichun3);
}
}
}。
