一个程序的页面走向，FIFO和LRU页面置换算法

Question

在一个请求分页面管理中，一个程序的页面走向为1、2、3、4、1、2、5、1、2、3、4、5。
计算利用：
（1）FIFO页面置换算法
（2）LRU页面置换算法
当分配给程序4个存储块（开始时没有装入页面）时的缺页中断次数。

Answer 1

#include"stdio.h"
#include"stdlib.h"
#include"time.h"

void FIFO(void);
void LRU(void);

char a;
int m=4,n=12,i,y[12]={1,2,3,4,1,2,5,1,2,3,4,5}; /*m为物理块数，n为要访问的页面数*/
typedef struct page{
int num;
int time;
}Page;
Page x[10];

int GetMax(page *x) /*求出那个物理块中的页面呆的时间最长，返回物理块号*/
{
int i;
int max=-1;
int tag=0;
for(i=0;i<m;i++)
{
if(x[i].time>max)
{ max=x[i].time;
tag=i;
}
}
return tag;
}

void Xunhuan()
{
printf("Please select 1:FIFO算法\n 2:LRU算法\n");
scanf("%s",&a);
printf("物理块数：4\n");
//scanf("%d",&m);
for(i=0;i<m;i++) /*将空的物理块中数据置为-1*/
{
x[i].num=-1;
}
printf("所要访问的页面数：12\n");
//scanf("%d",&n);
//srand(time(NULL));

printf("所要访问的页面号序列为：");
for(i=0;i<n;i++)
printf("%d ",y[i]);
printf("\n");
printf("页面置换步骤如下：\n");
switch(a)
{
case '1':FIFO();break;
case '2':LRU(); break;
}
}

void main()
{
char a;
Xunhuan();
while(1)
{
printf("Continue or Exit:C/Anykey:\n");
scanf("%s",&a);
if(a=='c'||a=='C')
Xunhuan();
else break;
}
exit(0);
}

void FIFO(void)
{
int i,j,u;
for(i=0;i<m;i++)
x[i].time=0;
x[0].num=y[0];
x[0].time=1;
printf(" %d \n",x[0].num);
for(i=1;i<n;i++)
{ u=0;
for(j=0;j<m;j++)
if(x[j].num==y[i])
{
u=1;
break;
}
if(u!=1&&x[m-1].num!=-1)
{
j=GetMax(x);
x[j].num=y[i];
x[j].time=0;
}
if(u!=1&&x[m-1].num==-1)
{
for(j=0;j<m;j++)
{
if(x[j].num==-1)
{x[j].num=y[i];
break;}
}
}
for(j=0;j<m;j++)
if(x[j].num!=-1)
x[j].time++;

for(j=0;j<m;j++)
if(x[j].num==-1)
printf("%2c ",32);
else
printf("%2d ",x[j].num);
printf("\n");
}
}

void LRU()
{
int i,j,u;
for(i=0;i<m;i++)
x[i].time=0;
x[0].num=y[0];
x[0].time=1;
printf(" %d \n",x[0].num);
for(i=1;i<n;i++)
{ u=0;
for(j=0;j<m;j++)
if(x[j].num==y[i]) /*物理块中存在相同页面*/
{
x[j].time=0; /*将相同的物理块的time置为0*/
u=1;
break;
}
if(u!=1&&x[m-1].num!=-1) /*物理块中无相同页面且物理块已填满*/
{
j=GetMax(x);
x[j].num=y[i];
x[j].time=0; /*将刚替换的页面所在的物理块time置为0*/
}
if(u!=1&&x[m-1].num==-1) /*物理块中无相同页面且物理块未填满*/
{
for(j=0;j<m;j++)
{
if(x[j].num==-1)
{x[j].num=y[i];
break;}
}
}
for(j=0;j<m;j++)
if(x[j].num!=-1)
x[j].time++; /*每执行完一次time加1*/

for(j=0;j<m;j++)
if(x[j].num==-1)
printf("%2c ",32);
else
printf("%2d ",x[j].num);
printf("\n"); /*格式化输出*/
}
}

Answer 2

FIFO(先进先出页面置换算法)：
1 2 3 4 1 2 5 1 2 3 4 5
————————————
1 1 1 1 1 1 2 3 4 5 1 2
2 2 2 2 2 3 4 5 1 2 3
3 3 3 3 4 5 1 2 3 4
4 4 4 5 1 2 3 4 5
X X X X X X X X X X
共10次缺页中断

LRU（最近最少使用页面置换算法）：
1 2 3 4 1 2 5 1 2 3 4 5
————————————
1 1 1 1 2 3 4 4 4 5 1 2
2 2 2 3 4 1 2 5 1 2 3
3 3 4 1 2 5 1 2 3 4
4 1 2 5 1 2 3 4 5
X X X X X X X X

共八次缺页中断

Answer 3

FIFO:
1
12
123
1234
1234 命中
1234 命中
5234
5134
5134 命中
5134 命中
5134 命中

缺页7次

LRU
1
12
123
1234
1234 命中
1234 命中
1254
1254 命中
1254 命中
1253
1453
1453 命中

缺页为7次

Answer 4

上面那个是我回答的，刚才忘了登陆...