FCFS_LRU_OPT.rar_replacement pages_虚拟存储器_页面置换

// page.cpp: implementation of the page class. // ////////////////////////////////////////////////////////////////////// #include "page.h" ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// page::page() { MaxDizhi=0;//初始化最大地址 MinDizhi=32768;//初始化最小地址 iSize=1024;//初始化页面的大小 MaxM=1;//初始化分配给作业的内存块数 } int page::creatDizhi() { d[0]=10000;//第一条指令的地址 int a,i; for(i=1;i<256;i++) { a=rand()%1024+1; if( a>0 && a<513 ) d[i] = d[i-1]+1; else if( a>512 && a<769 ) d[i] = rand()%(d[i-1])+1; else if( a>768 && a<1025) d[i] = d[i-1]+1+rand()%(32767-d[i-1]); } return 0; } int page::getMaxMin()//获得该作业的最大和最小地址 { for(int i=0;i<256;i++) { if(MaxDizhi<d[i]) MaxDizhi=d[i]; if(MinDizhi>d[i]) MinDizhi=d[i]; } return 1; } int page::getMaxM()//确定该作业所需要的最大内存块数 { int H=MaxDizhi/iSize; if(MaxDizhi%iSize!=0)H++; int L=MinDizhi/iSize; if(MinDizhi%iSize!=0)L++; MaxM=H-L+1; return MaxM; } int page::getChange()//确定该作业访问的页号的顺序，对于相邻相同的页号，合并为一个 { int count=1; change[0]=d[0]/iSize; if(d[0]%iSize!=0) change[0]++; int j=1;int i; for(i=1;i<256;i++) { int temp=d[i]/iSize; if(d[i]%iSize!=0) temp++; if(temp!=change[j-1]) { change[j]=temp;count++;j++; } } return count; } int page::FIFO(int a[],int m,int p[],int count)//采用先进先出算法 //其中a[]:表示内存中的页数；m:为分配给作业的内存块数； //p[]:表示该作业访问的页号顺序；count:为该作业访问的页号的总个数 { int k=0; int countF=0; int i,j; for(j=m;j<count;j++) { for(i=0;i<m;i++) if(a[i]==p[j])break; if(i==m) { a[k]=p[j]; k=(k+1)%m; countF++; } } return countF; } int page::LRU(int b[],int m,int p[],int count)//采用LRU算法 //其中a[]:表示内存中的页数；m:为分配给作业的内存块数； //p[]:表示该作业访问的页号顺序；count:为该作业访问的页号的总个数 { int countL=0; int i,j,ii; for(j=m;j<count;j++) { for(i=0;i<m;i++) if(b[i]==p[j])break; if(i==m) { for(ii=0;ii<m-1;ii++) b[ii]=b[ii+1]; b[ii]=p[j]; countL++; } else { int temp=b[i]; for(ii=i;ii<m-1;ii++) b[ii]=b[ii+1]; b[ii]=temp; } } return countL; } int page::OPT(int c[],int m,int p[],int count)//采用OPT算法 //其中a[]:表示内存中的页数；m:为分配给作业的内存块数； //p[]:表示该作业访问的页号顺序；count:为该作业访问的页号的总个数 { int countO=0; int i,j,ii,jj; for(j=m;j<count;j++) { for(i=0;i<m;i++) if(c[i]==p[j])break; if(i==m) { int mincount=count; int outpage;//被换出的页号 int tempcount=0; for(ii=0;ii<m;ii++) { for(jj=j;jj<count;jj++) if(c[ii]==p[jj]) tempcount++; if(mincount>tempcount) { mincount=tempcount; outpage=c[ii]; tempcount=0; } tempcount=0; } for(ii=0;ii<m;ii++) if(c[ii]==outpage)break; c[ii]=p[j]; countO++; } } return countO; } int page::doPage() { creatDizhi(); cout<<"将要被运行的作业共有256条指令，其地址范围是[0，32767]，"<<endl; cout<<"可供选择的页面大小是：1，2，4，8，16(单位是：K)，"<<endl; cout<<"输入时仅需输入数据即可(可以输入任意的数据)，不必输入单位！"<<endl<<endl; cout<<"请输入你所选择的页面大小："; cin>>iSize; iSize*=1024; int count=getChange(); cout<<"该作业依次要访问的页号的总数是："<<count<<endl<<endl; int *pFIFO=new int [count]; int *pLRU=new int [count]; int *pOPT=new int [count]; int i; for(i=0;i<count;i++) pFIFO[i]=pLRU[i]=pOPT[i]=change[i]; getMaxMin(); int M=getMaxM(); int m; cout<<"该作业所需的最大内存块数是："<<M<<endl<<"下面给出的是[1,"<<M<<"]的各个数作为分配给该作业的内存块数的情况！"<<endl; cout<<endl<<"结论如下:"<<endl; for(m=1;m<=M;m++) { int *a=new int[m]; int *b=new int[m]; int *c=new int[m]; a[0]=b[0]=c[0]=change[0]; int j,ii; for(i=1;i<m;i++) { for(j=i;j<count;j++) { for(ii=0;ii<i;ii++) if(a[ii]==change[j])break; if(ii==i) { a[i]=b[i]=c[i]=change[j];break; } } if(j==count)break; } int CountF=FIFO(a,m,pFIFO,count); int CountL=LRU(b,m,pLRU,count); int CountO=OPT(c,m,pOPT,count); delete a;delete b;delete c; cout<<"页面大小为:"<<iSize/1024<<"K,分配给程序的内存块数是:"<<m<<",则"<<endl; cout<<"OPT算法的缺页率为:"<<" "<<CountO/(float)count<<endl; cout<<"FIFO算法的缺页率为:"<<" "<<CountF/(float)count<<endl; cout<<"LRU算法的缺页率为:"<<" "<<CountL/(float)count<<endl; } return 0; } page::~page() { }