实验目的：
实现分页式存储地址转换过程，在此基础上实现请求分页的地址转换。实现请求分页式地址转换中出现的缺页现象中，用到的FIFO、LRU、OPT置换算法。
实现方法：
用一张位示图，来模拟内存的分配情况，利用随机数产生一组0和1的数对应内存的使用情况。
利用结构体数组将页表和内存块封装。
实现过程：
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#include<time.h>
struct Page
{
int kuai;
int stage;
}FPage[1000],LPage[1000];
struct Memory
{
int num;
int page;
}FMemory[1000],LMemory[1000],OMemory[1000];
int PageLength; /*页表长度*/
int Memsize; /*内存块数*/
int FAbsent,LAbsent,OAbsent,visit; /*FIFO中的缺页次数 LRU中的缺页次数 访问内存次数 */
int Logical; /*逻辑地址*/
int Pagenumber,Pageaddr;/*页号 页内地址*/
int Physical; /*物理地址*/
int PageSize; /*块的大小*/
int Freemem; /*空闲内存*/
int G[8][8];
int opt[10000]; int oth=0;
int temp[1000];
void GShow()
{
int i,j;
printf("位式图：\n");
for(i=0;i<8;i++)
{
printf("\t");
for(j=0;j<8;j++)
printf("%d ",G[i][j]);
printf("\n");
}
}
void init() /*初始化*/
{
srand((unsigned)time(NULL));
int i,j;
for(i=0;i<8;i++)
G[0][i]=1;
for(i=1;i<8;i++)
{
for(j=0;j<8;j++)
G[i][j]=rand()%2;
}
for(i=0;i<PageLength;i++)
{
FPage[i].kuai=-1; FPage[i].stage=0;
LPage[i].kuai=-1; LPage[i].stage=0;
}
for(i=0;i<Memsize;i++)
{
FMemory[i].page=-1;
}
for(i=0;i<Memsize;i++)
{
LMemory[i].page=-1;
}
for(i=0;i<Memsize;i++)
{
OMemory[i].num=i;
OMemory[i].page=-1;
}
FAbsent=LAbsent=visit=0;
}
void Show()
{
int i;
printf("FPage：\t\t\t\t\tLPage:\n");
printf("\t页号\t块号\t状态位\t\t\t页号\t块号\t状态位\n");
for(i=0;i<PageLength;i++)
{
printf("\t%d\t",i);
if(FPage[i].kuai==-1)
printf(" \t");
else
printf("%d\t",FPage[i].kuai);
printf("%d",FPage[i].stage);
printf("\t\t\t%d\t",i);
if(LPage[i].kuai==-1)
printf(" \t");
else
printf("%d\t",LPage[i].kuai);
printf("%d\n",LPage[i].stage);
}
printf("\nFMemory：\t\t\t\tLMemory：\n");
printf("\t块号\t页号\t\t\t\t块号\t\t页号\n");
for(i=Memsize-1;i>=0;i--)
{
printf("\t%d\t",i);
if(FMemory[i].page==-1)
printf(" \t\t");
else
printf("%d\t\t",FMemory[i].page);
printf("\t\t%d\t",i);
if(LMemory[i].page==-1)
printf("\n");
else
printf("\t%d\n",LMemory[i].page);
}
printf("Logical: %d\n",Logical);
printf("Count: %d %d\n",Pagenumber,Pageaddr);
printf("Physical: %d\n",Physical);
printf("PageSize: %d\n",PageSize);
printf("Visit: %d\n",visit);
printf("FAbsent: %d LAbsent: %d\n",FAbsent,LAbsent);
printf("FRate: %.2f%% LRate: %.2f%%\n",(double)FAbsent*100/(double)visit,(double)LAbsent*100/(double)visit);
}
void FIFO() /*FIFO算法*/
{
int i;
int m,n;
if(FPage[Pagenumber].stage==1) /*命中*/
;
else /*缺页*/
{
FAbsent++;
FPage[Pagenumber].stage=1;
for(i=0;i<Memsize;i++)
{
if(FMemory[i].page==-1)
{
for(m=1;m<8;m++)
{
for(n=0;n<8;n++)
if(G[m][n]==0)
{
break;
}
if(n<8)
break;
}
Freemem=(m-1)*8+n;
FMemory[i].page=Pagenumber;
FPage[Pagenumber].kuai=Freemem;
break;
}
}
if(i==Memsize)
{
FPage[Pagenumber].kuai=FPage[FMemory[0].page].kuai;
FPage[FMemory[0].page].kuai=-1;
FPage[FMemory[0].page].stage=0;
for(i=0;i<Memsize-1;i++)
FMemory[i].page=FMemory[i+1].page;
FMemory[i].page=Pagenumber;
}
}
}
void LRU() /*LRU算法*/
{
int i,j,m,n,l;
//bool flag=true;
for(l=0;l<Memsize;l++)
if(LMemory[l].page==-1)
break;
if(LPage[Pagenumber].stage==1)/*命中*/
{
for(i=0;i<l;i++)
{
if(LMemory[i].page==Pagenumber)
{
for(j=i;j<l-1;j++)
{
LMemory[j].page=LMemory[j+1].page;
}
LMemory[j].page=Pagenumber;
break;
}
}
}
else /*没命中*/
{
LAbsent++;
LPage[Pagenumber].stage=1;
if(l<Memsize) //问题出在这里,l++之前需要判断一下 如果l<memsize说明有空闲块，则l++ ,否则块已经满了,l不能++ ...
l++;
for(i=0;i<l;i++)
{
if(LMemory[i].page==-1)
{
for(m=1;m<8;m++)
{
for(n=0;n<8;n++)
if(G[m][n]==0)
{
G[m][n]=1;
break;
}
if(n<8)
break;
}
Freemem=(m-1)*8+n;
LMemory[i].page=Pagenumber;
LPage[Pagenumber].kuai=Freemem;
for(j=i;j<l-1;j++)
{
LMemory[j].page=LMemory[j+1].page;
}
LMemory[j].page=Pagenumber;
break;
}
}
if(i==l)
{
LPage[LMemory[0].page].stage=0;
LPage[Pagenumber].kuai=LPage[LMemory[0].page].kuai;
LPage[LMemory[0].page].kuai=-1;
for(j=0;j<l-1;j++)
LMemory[j].page=LMemory[j+1].page;
LMemory[j].page=Pagenumber;
}
}
}
void OPTshow()
{
int i;
printf("\t");
for(i=Memsize-1;i>=0;i--)
{
if(OMemory[i].page==-1)
printf(" ");
else
printf(" %d",OMemory[i].page);
}
printf("\n");
}
void OPT()
{
printf("\nOPTMemory：\n");
printf("\t 2 1 0\n\n");
int i,j,k,l,m,n;
int count=0;
for(i=0;i<oth;i++)
{
for(j=0;j<Memsize;j++)
{
if(OMemory[j].page==opt[i])
break;
}
if(j<Memsize)
;
else
{
for(j=0;j<Memsize;j++)
{
if(OMemory[j].page==-1) /*如果此时内存没满还有空缺 就直接将页号写进去*/
{
OMemory[j].page=opt[i];
break;
}
}
if(j==Memsize) /*需要发生置换*/
{
OAbsent++;
for(n=0;n<Memsize;n++)
temp[n]=0;
for(k=i+1;k<oth;k++)
{
for(l=0;l<Memsize;l++)
{
if(OMemory[l].page==opt[k])
{
temp[l]++;
break;
}
}
count=0;
for(m=0;m<Memsize;m++)
{
if(temp[m]==0)
count++;
}
if(count>1&&k<oth-1)
;
else
{
for(m=0;m<Memsize;m++)
if(temp[m]==0)
{
OMemory[m].page=opt[i];
break;
}
}
}
}
}
OPTshow();
}
printf("OAbsent: %d\n",OAbsent);
printf("ORate: %.2f%%\n",(double)OAbsent*100/(double)visit);
}
void cometrue()
{
printf("输入页表长度（页）：");
scanf("%d",&PageLength);
printf("输入内存块数（块）：");
scanf("%d",&Memsize);
printf("输入页面大小（kb）：");
scanf("%d",&PageSize);
init();
while(printf("输入逻辑地址(10进制): ")&&scanf("%d",&Logical))
{
if(Logical!=-1)
{
Pagenumber=Logical/(PageSize*1024);
Pageaddr=Logical%(PageSize*1024);
if(Pagenumber>=PageLength)
{
printf("越界中断......!\n");
continue;
}
opt[oth++]=Pagenumber;
GShow();
FIFO();
LRU();
Physical=Freemem*PageSize*1024+Pageaddr;
visit++;
Show();
}
else if(Logical==-1)
{
int i;
printf("页号访问序列：\n");
for(i=0;i<oth;i++)
printf("%d ",opt[i]);
printf("\n");
OPT();
break;
}
}
}
int main()
{
cometrue();
return 0;
}