#include<stdio.h>
#include<iostream.h>
#include<malloc.h>
#include<windows.h>
#include<string.h>
struct wsz{
int ws[30][3]; //每行第1元素为 “物理块号”,第2元素为“内存块号”,第3元素为“状态位”
int n;
}yb;
struct duizhan{
int dui[30][8]; //最多可容纳30组测试数据,可对应内存8块物理块。
int x,y,y1; //x为测试数据组数 y为内存物理块数
int wulikuai[8];
int queye,fangwen;
double queyelv;
}FIFO,LRU,OPT;
struct jilu{
int shunxu[30]; //可记录30组测试数据
int n;
}jl;
int cxk,size,wl;
char z1[20]="0123456789ABCDEF";
char z2[20]="0123456789abcdef";
int yehao;
unsigned int yeneidizhi;
char s[10]; //临时16进制地址存储数组
int get(char s){
int i;
for(i=0;i<16;i++){
if(z1[i]==s||z2[i]==s)
return i;
}
return -1;
}
int make(char *s){
int i;
int n=strlen(s);
int c;
unsigned int wuli;
wuli=0;
if(strcmp(s,"#")){
for(i=0;i<n;i++){
c=get(s[i]);
if(c!=-1){
wuli=wuli*16+c;
}
else{
cout<<"ERROR:~输入的数据不符合要求; 可能是地址越界或位数多于4位:"<<endl<<"ERROR:~请检查后从新输入(如果结束访问内存以#结束输入):";
return 1;
}
}
yehao=(int)wuli/(size*1024);
yeneidizhi=wuli%(size*1024);
if(yehao>=yb.n){
cout<<"ERROR:~输入的数据不符合要求; 可能是地址越界或位数多于4位:"<<endl<<"ERROR:~请检查后从新输入(如果结束访问内存以#结束输入):";
return 1;
}
FIFO.fangwen++;
if(yb.ws[yehao][2]){
jl.shunxu[jl.n]=yehao;
jl.n++;
for(i=0;i<FIFO.y;i++){
FIFO.dui[FIFO.x+1][i]=FIFO.dui[FIFO.x][i];
}
FIFO.x++;
return 1;
}
else{
FIFO.queye++;
if(FIFO.y1<FIFO.y){
for(i=0;i<FIFO.y1;i++){
FIFO.dui[FIFO.x+1][i]=FIFO.dui[FIFO.x][i];
}
FIFO.dui[FIFO.x+1][FIFO.y1]=yehao;
jl.shunxu[jl.n]=yehao;
jl.n++;
yb.ws[yehao][0]=FIFO.wulikuai[FIFO.y1];
yb.ws[yehao][2]=1;
FIFO.y1++;
FIFO.x++;
}
else{
for(i=0;i<FIFO.y;i++){
FIFO.dui[FIFO.x+1][i]=FIFO.dui[FIFO.x][i+1];
}
FIFO.dui[FIFO.x+1][FIFO.y-1]=yehao;
yb.ws[yehao][2]=1;
yb.ws[yehao][0]=yb.ws[FIFO.dui[FIFO.x][0]][0];
yb.ws[FIFO.dui[FIFO.x][0]][2]=0;
FIFO.x++;
jl.shunxu[jl.n]=yehao;
jl.n++;
}
return 1;
}
}
else
return -1;
}
void bianhuan(){
char t[5];
int y,i;
i=0;
y=yb.ws[yehao][0];
unsigned int dizhi;
dizhi=y*size*1024+yeneidizhi;
while(dizhi){
t[i]=z1[dizhi%16];
i++;
dizhi=dizhi/16;
}
while(i>=0){
cout<<t[i-1];
i--;
}
}
void print(){
system("cls");
cout<<endl<<"**********************************FIFO***********************************";
cout<<endl<<endl<<endl<<" 内存中物理块数为:"<<FIFO.y<<" 页面大小为: "<<size<<"(KB)"<<endl;
cout<<endl<<"********************** 页 表 为 : *******************"<<endl;
int i,j;
printf("程序块号为: ");
for(i=0;i<yb.n;i++){
printf("%4d",i);
}
printf("\n");
printf("内存中物理块号为:");
for(i=0;i<yb.n;i++){
if(yb.ws[i][2])
printf("%4d",yb.ws[i][0]);
else
printf(" ");
}
printf("\n");
printf("状态位为: ");
for(i=0;i<yb.n;i++){
printf("%4d",yb.ws[i][2]);
}
printf("\n****************************堆栈内保存情况:******************************\n");
for(j=FIFO.y-1;j>=0;j--){
printf("\n");
printf("%4d",j);
for(i=0;i<=FIFO.x;i++){
if(FIFO.dui[i][j]!=-1)
printf("%4d",FIFO.dui[i][j]);
else
printf(" ");
}
}
printf("\n");
printf("*************************************************************************\n");
printf("缺页次数为:%d",FIFO.queye);
printf("访问次数为:%d",FIFO.fangwen);
if(FIFO.fangwen)
FIFO.queyelv=((double)FIFO.queye)/FIFO.fangwen;
printf("缺页率为: %3.2f",FIFO.queyelv*100);
printf("\n\n");
}
int lookLRU(int i){ //本函数用于检查LRU堆栈中是否存在i,如果存在返回位置否则返回-1;
int j;
if(LRU.x!=-1){
for(j=0;j<LRU.y;j++){
if(LRU.dui[LRU.x][j]==i)
return j;
}
}
return -1;
}
void printduibi(){
int j,i;
system("cls");
printf("\n********************FIFO****堆栈内保存情况:******************************\n");
for(j=FIFO.y-1;j>=0;j--){
printf("\n");
printf("%4d",j);
for(i=0;i<=FIFO.x;i++){
if(FIFO.dui[i][j]!=-1)
printf("%4d",FIFO.dui[i][j]);
else
printf(" ");
}
}
printf("\n");
printf("*************************************************************************\n");
printf("缺页次数为:%d",FIFO.queye);
printf("访问次数为:%d",FIFO.fangwen);
if(FIFO.fangwen)
FIFO.queyelv=((double)FIFO.queye)/FIFO.fangwen;
printf("缺页率为: %3.2f",FIFO.queyelv*100);
printf("\n\n");
printf("\n***************LRU**********堆栈内保存情况:******************************\n");
for(j=LRU.y-1;j>=0;j--){
printf("\n");
printf("%4d",j);
for(i=0;i<=LRU.x;i++){
if(LRU.dui[i][j]!=-1)
printf("%4d",LRU.dui[i][j]);
else
printf(" ");
}
}
printf("\n");
printf("*************************************************************************\n");
printf("缺页次数为:%d",LRU.queye);
printf("访问次数为:%d",LRU.fangwen);
if(LRU.fangwen)
LRU.queyelv=((double)LRU.queye)/LRU.fangwen;
printf("缺页率为: %3.2f",LRU.queyelv*100);
printf("\n\n");
printf("\n***************OPT**********堆栈内保存情况:******************************\n");
for(j=OPT.y-1;j>=0;j--){
printf("\n");
printf("%4d",j);
for(i=0;i<=OPT.x;i++){
if(OPT.dui[i][j]!=-1)
printf("%4d",OPT.dui[i][j]);
else
printf(" ");
}
}
printf("\n");
printf("*************************************************************************\n");
printf("缺页次数为:%d",OPT.queye);
printf("访问次数为:%d",OPT.fangwen);
if(OPT.fangwen)
OPT.queyelv=((double)OPT.queye)/OPT.fangwen;
printf("缺页率为: %3.2f",OPT.queyelv*100);
printf("\n\n");
}
void popLRU(int n){
int flag=-1,i;
flag=lookLRU(n);
LRU.fangwen++;
if(flag!=-1){
for(i=0;i<LRU.y1;i++){
if(LRU.dui[LRU.x][i]!=-1)
LRU.dui[LRU.x+1][i]=LRU.dui[LRU.x][i];
}
LRU.x++;
while(flag<LRU.y1){
LRU.dui[LRU.x][flag]=LRU.dui[LRU.x][flag+1];
flag++;
}
LRU.dui[LRU.x][LRU.y1-1]=n;
}
else{
LRU.queye++;
if(LRU.y1<LRU.y){
for(i=0;i<LRU.y;i++){
if(LRU.x!=-1)
LRU.dui[LRU.x+1][i]=LRU.dui[LRU.x][i];
}
LRU.dui[LRU.x+1][LRU.y1]=n;
LRU.x++;
LRU.y1++;
}
else{
for(i=0;i<LRU.y-1;i++){
LRU.dui[LRU.x+1][i]=LRU.dui[LRU.x][i+1];
}
LRU.dui[LRU.x+1][LRU.y-1]=n;
LRU.x++;
}
}
}
void moniLRU(){
int i,j;
LRU.x=-1;
LRU.y=FIFO.y;
for(i=0;i<LRU.y;i++){
LRU.wulikuai[i]=FIFO.wulikuai[i];
}
for(i=0;i<30;i++){
for(j=0;j<LRU.y;j++){
LRU.dui[i][j]=-1;
}
}
LRU.y1=0;
for(i=0;i<jl.n;i++){
popLRU(jl.shunxu[i]);
}
}
bool search(int n){
int i;
if(OPT.x==-1)
return false;
for(i=0;i<OPT.y;i++){
if(OPT.dui[OPT.x][i]==n)
return true;
}
return false;
}
int lookOPT(){ //在栈中选择合适的页号替换当前页号,返回其游标
int *t;
int max=-1;
int i,j;
t=(int *)malloc(sizeof(int)*(OPT.y));
for(i=0;i<OPT.y;i++){
for(j=OPT.x+1;j<jl.n;j++){
if(OPT.dui[OPT.x][i]==jl.shunxu[j]){
t[i]=j;
break;
}
}
if(j==jl.n) t[i]=30;
}
for(i=0;i<OPT.y;i++){
max=(t[i]>t[max])?i:max;
}
return max;
}
void popOPT(int n){
int i;
OPT.fangwen++;
if(search(n)){ //看当前是否缺页,是为0,否为1
for(i=0;i<OPT.y1;i++){
OPT.dui[OPT.x+1][i]=OPT.dui[OPT.x][i];
}
OPT.x++;
}
else{
OPT.queye++;
if(OPT.y1<OPT.y){ //缺页时且栈未满
for(i=0;i<OPT.y1;i++){
if(OPT.x!=-1)
OPT.dui[OPT.x+1][i]=OPT.dui[OPT.x][i];
}
OPT.dui[OPT.x+1][OPT.y1]=n;
OPT.x++;
OPT.y1++;
}
else{ //缺页且栈满
if(lookOPT()!=-1){ //如果存在最佳替换
for(i=0;i<OPT.y1;i++){
OPT.dui[OPT.x+1][i]=OPT.dui[OPT.x][