赞
踩
#include<stdio.h>
#define N 3 //物理块的个数
int Nl = 20;//页面访问序列的长度
void LRU(int block[],int blockN,int list[],int listN)//LRU替换算法
{
int i, j;//定义替换次数
int rep1 = 0;//缺页次数
int rep2 = 0;//置换页面次数
int DisplacedPages[20] = {0};
int time[N];//各个物理块最近一次访问至现在的时间
for(i = 0;i < blockN;i++)//初始化
time[i] = 0;
for(i = 0;i < listN; i++)
{
for(j = 0; j < blockN; j++) //更新时间记录
if(block[j] != -1)
time[j]++;
for(j = 0; j < blockN; j++)
if(block[j] == list[i]) //命中
{
time[j] = 0;
break;
}
else if(block[j] == -1) //未命中但块中为空
break;
if(j < blockN && block[j] == -1)//未命中且物理块未满,直接存入
{
block[j] = list[i];
time[j] = 0;
rep1++;
}
else if(j == blockN)//需要替换
{
int max = 0;
for(int k = 0;k < blockN;k++)//寻找最久未访问的地址所在的物理块的位置
{
if(time[max] < time[k])
max = k;
}
DisplacedPages[rep2] = block[max];
rep2++;
rep1++;
block[max] = list[i];
time[max] = 0;
}
printf("当前访问的页面为:%d\n",list[i]);
printf("访问后物理块内的页面为:");
for(int m = 0;m < blockN;m++)//显示当前物理块的状态
{
if(block[m] == -1)
break;
printf("|%d| ",block[m]);
}
if (j == blockN)
printf("置换了%d\n", DisplacedPages[rep2-1]);
printf("\n");
}
printf("缺页的次数为:%d 缺页率:%d/%d=%.2f\n", rep1, rep1, listN, (float)(rep1)/(float)listN);
printf("置换的页面为:");
for (i=0; i<rep2; i++)
printf("%d,", DisplacedPages[i]);
}
int main()
{
int block[N], list[20] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};//默认序列
int df = 1;
for(int i = 0;i < N;i++)//初始化
{
block[i] = -1;
}
printf("是否使用默认序列?(1:否 其他数字:是)");
scanf("%d", &df);
if (df == 1)
{
printf("请输入页面个数:");
scanf("%d", &Nl);
printf("请输入页面访问序列:\n");
for(i = 0;i < Nl;i++)
scanf("%d", &list[i]);
}
LRU(block, N, list, Nl);//调用LRU页面置换算法
printf("\n");
return 0;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。