实验报告三
——内存页面置换算法的设计
姓名：丛菲 学号：20100830205 班级：信息安全二班
一、实习内容
? 实现最近最久未使用（LRU）置换算法
二、实习目的
? LINUX中，为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和
回收均以页为单位进行，一个进程只需将其一部分调入内存便可运行，还支持请求调页的存储管理方式。
? 本实习要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技
术的特点，掌握请求页式存储管理的页面置换算法。
三、实习题目
1. 最近最久未使用（LRU）置换算法原理就是：当需要淘汰某页面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。
? 例如: 分配给该进程的页块数为3，一个20位长的页面访问序列
为:12560,36536,56042,70435，
则缺页次数和缺页率按下图给出:
2. 假定分配给该进程的页块数为3，页面访问序列长度为20。本实验可以采用数组结构实现，首先随机产生页面序列，当发生请求调页时，若内存已满，则需要利用LRU算法，将当前一段时间内最久未使用过的页替换出去。
? 模拟程序的算法如下图：
四、实现代码为：
#include
Myprintf
printf(\
/*表格控制*/ 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 GetMax(Page *b) { }
/*判断页面是否已在内存中*/ int Equation(int fold,Page *b) { }
void Lru(int fold,Page *b) /*LRU核心部分*/ {
int i; int val;
val=Equation(fold,b); int i; { } return -1;
if (fold==b[i].num)
return i;
for(i=0;i int i; int max=-1; int tag=0; for(i=0;i if(b[i].time>max) { } max=b[i].time; tag=i; int i,j; for(i=0;i for(i=0;i for(j=0;j c[i][j]=-1; b[i].num=-1; b[i].time=N-i-1; } if (val>=0) { } else//页面不存在 { } queue[++K]=fold;/*记录调入页面*/ val=GetMax(b); b[val].num=fold; b[val].time=0; for(i=0;i if (i!=val) b[i].time++; b[val].time=0; for(i=0;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; K=-1; Init(b, c); for(i=0;i /*结果输出*/ printf(\：\\n\ Myprintf; for(j=0;j printf(\ printf(\ Myprintf; for(i=0;i for(j=0;j Lru(a[i],b); c[0][i]=a[i]; /*记录当前的内存单元中的页面*/ for(j=0;j c[j][i]=b[j].num; start: } } } if(c[i][j]==-1) printf(\ printf(\ else printf(\ Myprintf; printf(\ for(i=0;i printf(\ printf(\：m\\nque ye lv：.2f%%\\n\ 五、在虚拟机上的具体操作及结果 六、思考题 ? 比较LRU和其他置换算法各自的优缺点，能够实现其他置换算法模拟设计，分析内 存页面数的变化对各种置换算法命中率的影响。 答: 内存页面数越多哦,命中率越高. LRU算法可以减少页错误率,较易理解. 最优算法页错误最低,且没有Belady异常,但是较难实现 FIFO算法容易理解和实现,但是页错误率较高 七、实验总结 明白LRU算法的原理,当内存页面中不存在当前页面时,且没有空闲页面,将替换近期最少使用的页面,这种算法可以有效减少替换掉常用页面的次数,从而减少页错误率.