lru算法缺页率公式

‘壹’ c语言编写页面置换算法

//熬夜弄出来的，记得加分哦
#include<stdio.h>
void Print(int bc[],int blockCount)
{
for(int i=0;i<blockCount;i++)
{
printf("%d ",bc[i]);
}
printf("\n");
}

bool Travel(int bc[],int blockCount,int x)
{
bool is_found=false;
int i;
for(i=0;i<blockCount;i++)
{
if(bc[i]==x)
{
is_found=true;
break;
}
}
return is_found;
}

void FIFO(int pc[],int bc[],int pageCount,int blockCount)
{
printf("0：FIFO置换算法\n");
int i;
if(pageCount<=blockCount)
{
printf("缺页次数为0\n");
printf("缺页率为0\n");
}
else
{
int noPage=0;
int p=0;
for(i=0;i<pageCount;i++)
{

//printf("引用页：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
}
else
{
if(p==blockCount)
{
p=0;
}
bc[p]=pc[i];
p++;

}
noPage++;
//printf("物理块情况：\n");
//Print(bc,blockCount);
}
//printf("\n");
}
printf("FIFO缺页次数为:%d\n",noPage);
printf("FIFO缺页率为:%.2f%%\n",(float)noPage/pageCount*100);
}
}

int FoundMaxNum(int a[],int n)
{
int k,j;
k=a[0];
j=0;
for (int i=0;i<n;i++)
{
if(a[i]>=k)
{
k=a[i];
j=i;
}
}
return j;
}

void LRU(int pc[],int bc[],int pageCount,int blockCount)
{
printf("1：LRU置换算法\n");
if(pageCount<=blockCount)
{
printf("缺页次数为0\n");
printf("缺页率为0\n");
}
else
{
int noPage=0;
int i,j,m;
int bc1[100];
for(i=0;i<blockCount;i++)
{
bc1[i]=0;
}
for(i=0;i<pageCount;i++)
{
// printf("引用页：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
for(int p=0;p<=i;p++)
{
bc1[p]++;
}
}
else
{
for(j=0;j<blockCount;j++)
{
bc1[j]++;
}
int k=FoundMaxNum(bc1,blockCount);
bc[k]=pc[i];
bc1[k]=1;

}
noPage++;
//printf("物理快情况：\n");
//Print(bc,blockCount);
}
else if(Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
for(j=0;j<=i;j++)
{
bc1[j]++;
}
for(m=0;m<=i;m++)
{
if(bc[m]==pc[i])
{
break;
}
}
bc1[m]=1;
bc[m]=pc[i];

}
else
{
for(j=0;j<blockCount;j++)
{
bc1[j]++;
}
for(m=0;m<blockCount;m++)
{
if(bc[m]==pc[i])
{
break;
}
}
bc1[m]=1;
bc[m]=pc[i];
}
}
//printf("\n");
}
printf("LRU缺页次数为:%d\n",noPage);
printf("LRU缺页率为:%.2f%%\n",(float)noPage/pageCount*100);
}
}

void Optiomal(int pc[],int bc[],int pageCount,int blockCount)
{
printf("2：最佳置换算法\n");
if(pageCount<=blockCount)
{
printf("缺页次数为0\n");
printf("缺页率为0\n");
}
else
{
int noPage=0;
int i,j,k;
for(i=0;i<pageCount;i++)
{
// printf("引用页：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
}
else
{
int max=0;
int blockIndex;;
for(j=0;j<blockCount;j++)
{
for(k=i;k<pageCount;k++)
{
if(bc[j]==pc[k])
{
break;
}
}
if(k>=max)
{
max=k;
blockIndex=j;
}
}
bc[blockIndex]=pc[i];

}
noPage++;
//printf("物理快情况：\n");
//Print(bc,blockCount);
}
//printf("\n");
}
printf("OPT缺页次数为:%d\n",noPage);
printf("OPT缺页率为:%.2f%%\n",(float)noPage/pageCount*100);
}
}

int main()
{
int pageCount,blockCount,i,pc[100];
printf("输入页面数\n");
scanf("%d",&pageCount);
printf("输入页面走向\n");
for(i=0;i<pageCount;i++)
{
scanf("%d",&pc[i]);
}
blockCount=3;//物理块数
int bc1[100];
printf("\n");
FIFO(pc,bc1,pageCount,blockCount);
int bc2[100];
printf("\n");
LRU(pc,bc2,pageCount,blockCount);
int bc3[100];
printf("\n");
Optiomal(pc,bc3,pageCount,blockCount);
return 0;
}

‘贰’ LRU替换算法怎么理解，过程好难，这个题麻烦大神帮我看看

• LRU是LeastRecently Used 近期最少使用算法，也就是说，近期最少使用的那个页面，将被置换出去（可以理解为这个页面将被废弃）

• 对于本题。内存容量为4个页面，这是要清楚的。具体看下面的表格：

• 缺页率 = 6 / 20 =3/ 10 = 30%

• 我具体解释下上面的表格吧。

  从上到下是4个页面。

• 最开始，1需要被调用，将1放入内存中，由于1一开始没有，所以一次缺页

• 然后，8要被调用，，将1放入内存中，由于8一开始没有，所以又产生一次缺页

• 以此往后，直到4块内存都满了，最新使用过的放在最下面（页4），则置换出最上面（页1）。

• 通俗地说，就是总共空间只有4块。只能放4个页面。那么当页面满的时候，就把你很久很久没有使用过的那个页面（也就是近期最少使用的页面）置换出去，然后补充新的页面进来。

• 这个算是页面置换里面比较经典的一个算法了，希望能帮到你！