编程模拟LRU算法的控制过程
1.1 设计目的
- 用C语言实现最近最久未使用（LRU）置换算法
- 了解内存分页管理策略
- 掌握调页策略
- 掌握一般常用的调度算法
- 选取调度算法中的典型算法，模拟实现
1.2 开发环境
window10系统的Dev-C++环境
1.3 原理
最近最久为使用(LRU)算法
LRU算法是根据页面调入内存后的使用情况进行决策的。就是利用“最近的过去”作为“最近的将来”的近似，因此是将最近最久未使用的页面予以淘汰。该算法赋予每一个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,当淘汰一个页面时，选择现有页面中t值最大的，及最近最久为使用的页面予以淘汰。
1.4 数据与程序
数据：4,3,2,1,4,3,5,4,3,2,1,5
程序代码：
#include<stdio.h>
/*内存物理块结构体*/
int block_num; /*分配的物理块数*/
int page_num; /*要访问的页面序列个数*/
int page[100]; /*要访问的页面序列*/
int memory[10]; /*物理块中的页号*/
int table[100][10]; /*显示矩阵*/
int reg[10]; /*寄存器--记录页面的访问时间*/
char Que[100]; /*数组，记录是否缺页*/
/*主函数*/
int main()
{
int count=0; /*记录缺页次数*/
int i,j,k;
printf("━━━━━━━━━━━━━━━━━━━━━\n");
printf(" 实验六：LRU页面置换算法 \n");
printf(" \n");
printf(" 学号：20191008308 \n");
printf(" 姓名：QXP \n");
printf("━━━━━━━━━━━━━━━━━━━━━\n");
while(1)
{
printf("请输入分配的物理块的个数(M<=10):\n");
scanf("%d",&block_num);
if(block_num>10)
printf("输入不合法，请重新输入");
printf("\n");
break;
}
while(1)
{
printf("请输入要访问的页面序列个数(P<=100):\n");
scanf("%d",&page_num);
if(page_num>100)
printf("输入不合法，请重新输入");
printf("\n");
break;
}
printf("请依次输入要访问的页面序列，以空格隔开:\n");
for(i=0;i<page_num;i++)
{
scanf("%d",&page[i]);
Que[i] = 'N';
}
for(i=0;i<block_num;i++)
memory[i]=-1; //初始内存块中默认为空，用-1表示
//访问页面
for(i=0;i<page_num;i++)
{
if(i==0) //访问的第一个页面
{
memory[i]=page[i];
reg[i]=i;
for(j=0;j<block_num;j++)
table[i][j]=memory[j];`在这里插入代码片`
Que[i]='Y';
count++;
}
else
{ /*判断新页面号是否在物理块中*/
for(j=0,k=0;j<block_num;j++)
{
if(memory[j]!=page[i])
k++;
else
{ /*新页面在内存块中*/
reg[j]=i; //刷新该页面的访问时间
for(int n=0;n<block_num;n++)
table[i][n]=memory[n];
}
}
}
if(k==block_num) /*新页面不在物理块中，缺页*/
{
int q=0;
Que[i]='Y';
count++;
for(int j=0;j<block_num;j++)
{
if(memory[j]==-1) /*内存块未满*/
{
memory[j]=page[i];
reg[j]=i;
for(int n=0;n<block_num;n++)
table[i][n]=memory[n];
break;
}
else
q++;
}
if(q==block_num)/*内存块已满，需采用LRU置换算法选择换出页*/
{
int min=0; //记录换出页
for(int m=1;m<block_num;m++)
if(reg[m]<reg[min])
min=m;
memory[min]=page[i];
reg[min]=i; /*记录该页的访问时间（新到的页面进入之前min的位置，需将min位置的访问时间更改）*/
for(int n=0;n<block_num;n++)
table[i][n]=memory[n];
}
}
}
/*输出运行过程及结果*/
printf("采用LRU页面置换算法结果如下: \n");
printf("\n");
printf("\n");
printf("页号:");
for(i=0;i<page_num;i++)
printf("%3d",page[i]);
printf("\n");
printf("-----------------------------------------------------\n");
for(i=0;i<block_num;i++)
{
printf("块%2d:",i);
for(j=0;j<page_num;j++)
printf("%3d",table[j][i]);
printf("\n");
}
printf("-----------------------------------------------------\n");
printf("缺页:");
for(i=0;i<page_num;i++)
printf("%3c",Que[i]);
printf("\n");
printf("-----------------------------------------------------\n");
printf("\t缺页次数:%d\n",count);
printf("\t缺页率:%d/%d\n",count,page_num);
printf("-----------------------------------------------------\n");
}
1.5 程序运行结果
1.6实验总结与心得体会
用C语言实现最近最久未使用（LRU）置换算法，了解了内存分页管理策略，调页策略。