实验报告三

——内存页面置换算法的设计

姓名：** 学号：*** 班级：信息安全二班

一、实习内容

• 实现最近最久未使用（LRU）置换算法

二、实习目的

• LINUX中，为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其一部分调入内存便可运行，还支持请求调页的存储管理方式。

• 本实习要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。

三、实习题目

1. 最近最久未使用（LRU）置换算法原理就是：当需要淘汰某页面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。

• 例如: 分配给该进程的页块数为3，一个20位长的页面访问序列为:12560,36536,56042,70435，

则缺页次数和缺页率按下图给出:

2. 假定分配给该进程的页块数为3，页面访问序列长度为20。本实验可以采用数组结构实现，首先随机产生页面序列，当发生请求调页时，若内存已满，则需要利用LRU算法，将当前一段时间内最久未使用过的页替换出去。

• 模拟程序的算法如下图：

四、实现代码为：

#include＜stdio.h＞

#define M 3

#define N 20

#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n") /*表格控制*/

typedef struct page

{

int num; /*记录页面号*/

int time; /*记录调入内存时间*/

}Page; /* 页面逻辑结构，结构为方便算法实现设计*/

Page b[M]; /*内存单元数*/

int c[M][N]; /*暂保存内存当前的状态：缓冲区*/

int queue[100]; /*记录调入队列*/

int K; /*调入队列计数变量*/

/*初始化内存单元、缓冲区*/

void Init(Page *b,int c[M][N])

{

int i,j;

for(i=0;i＜N;i++)

{

b[i].num=-1;

b[i].time=N-i-1;

}

for(i=0;i＜M;i++)

for(j=0;j＜N;j++)

c[i][j]=-1;

}

/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/

int GetMax(Page *b)

{

int i;

int max=-1;

int tag=0;

for(i=0;i＜M;i++)

{

if(b[i].time＞max)

{

max=b[i].time;

tag=i;

}

}

return tag;

}

/*判断页面是否已在内存中*/

int Equation(int fold,Page *b)

{

int i;

for(i=0;i＜M;i++)

{

if (fold==b[i].num)

return i;

}

return -1;

}

void Lru(int fold,Page *b) /*LRU核心部分*/

{

int i;

int val;

val=Equation(fold,b);

if (val＞=0)

{

b[val].time=0;

for(i=0;i＜M;i++)

if (i!=val)

b[i].time++;

}

else//页面不存在

{

queue[++K]=fold;/*记录调入页面*/

val=GetMax(b);

b[val].num=fold;

b[val].time=0;

for(i=0;i＜M;i++)

if (i!=val)

b[i].time++;

}

}

main()/*主程序*/

{

int a[N]={1,0,5,1,7,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4};

int i,j;

start:

K=-1;

Init(b, c);

for(i=0;i＜N;i++)

{

Lru(a[i],b);

c[0][i]=a[i];

/*记录当前的内存单元中的页面*/

for(j=0;j＜M;j++)

c[j][i]=b[j].num;

}

/*结果输出*/

printf("nei cun zhuang tai ：\n");

Myprintf;

for(j=0;j＜N;j++)

printf("|%2d ",a[j]);

printf("|\n");

Myprintf;

for(i=0;i＜M;i++)

{

for(j=0;j＜N;j++)

{

if(c[i][j]==-1)

printf("|%2c ",32);

else

printf("|%2d ",c[i][j]);

}

printf("|\n");

}

Myprintf;

printf("\ndiao ru dui lie :");

for(i=0;i＜K+1;i++)

printf("%3d",queue[i]);

printf("\nque ye ci shu ：%6d\nque ye lv：%16.2f%%\n",K+1,(float)(K+1)/N*100);

}

五、在虚拟机上的具体操作及结果

六、思考题

• 比较LRU和其他置换算法各自的优缺点，能够实现其他置换算法模拟设计，分析内存页面数的变化对各种置换算法命中率的影响。

答: 内存页面数越多哦,命中率越高.

LRU算法可以减少页错误率,较易理解.

最优算法页错误最低,且没有Belady异常,但是较难实现

FIFO算法容易理解和实现,但是页错误率较高

七、实验总结

明白LRU算法的原理,当内存页面中不存在当前页面时,且没有空闲页面,将替换近期最少使用的页面,这种算法可以有效减少替换掉常用页面的次数,从而减少页错误率.