实验报告三
——内存页面置换算法的设计
姓名：田玉祥
班级：计算机科学与技术专业一班
一、实验内容
·实现最近最久未使用（LRU）置换算法
二、实验目的
•LINUX中，为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其
一部分调入内存便可运行，还支持请求调页的存储管理方式。
•本实习要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面
置换算法。
三、实验题目
1. 最近最久未使用（LRU）置换算法原理就是：当需要淘汰某页
面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。
•例如: 分配给该进程的页块数为3，一个20位长的页面访问序列为:12560,36536,56042,70435，
则缺页次数和缺页率按下图给出:
假定分配给该进程的页块数为3，页面访问序列长度为20。
本实验可以采用数组结构实现，首先随机产生页面序列，当发生请求调页时，若内存已满，则需要利用LRU算法，将当前一段时间内最久未使用过的页替换出去。
程序实现想法：
用一个数组a[n]来存放所有需要访问的页，用一个数组b[3]来存放页表，用数组c[3]来存放页表每一页的权值，就是最近最少使用的度，度越高则使用率越小，用n次循环，每次a[i]进行判断时先判断有没有空格，再判断a[i]是否已经在页表中，此时注意要将权值归1，若都没有这些情况，则用函数int MAX(int a,int b,int c) 找到权值最大的，进行替换，并将其他页的权值加1.
实验代码：
//LRU算法，最近最少使用的页替换算法
#include<iostream>
#include <string>
using namespace std ;
int MAX(int a,int b,int c) //赋值之后的权值中找到权值最大的，返回它的下标也就是最近最少使用的
{
int max = a ;
if(max<b)
{
max = b ;
if(max<c)
max = c ;
}
else
if(max<c)
max = c ;
if(a==max) //找到权值最大的数的下标
return 0 ;
else if(b==max)
return 1 ;
else if(c==max)
return 2 ;
}
int main()
{
// string k ; //k表示当前最近最少使用的页;
int i,j,n,l,m,p,q ; //j表示当前访问的页是否已经在访问,0表示没有发生缺页，1表示发生缺页
//q来表示页表是否有空格，即当前是否全部在使用，1表示全部在使用，0表示还有空格
string *b = new string [3] ; //存放页表
int *c = new int [3] ; //存放页表的权值
for(i=0;i<3;i++)
{
b[i] = " " ;
c[i] = 1 ;
}
cout<<"请输入要访问的页码页数："<<endl ;
cin >> n ;
string *a = new string [n] ; //存放所有要访问的页
cout<<"请输入"<<n<<" 个每一次要访问的页码页号："<<endl ;
for(i=0;i<n;i++)
cin>>a[i] ;
cout<<"页表访问过程如下，“1”表示发生缺页，“0”表示不发生缺页："<<endl ; for(i=0;i<n;i++)
{
j = 1 ;
q = 1 ; //表示页表没有空位，全被使用
for(l=0;l<3;l++)
if(a[i]==b[l])
{
j = 0 ;
c[l]=1 ; //将权值设为1
c[l-1]++;
c[l-2]++;
c[l+1]++;
c[l+2]++;
break ;
}
if(j==0) //如果需要访问的页正在被访问，即已经在页表，直接输出。
并将其权值设为1
{
for(l=0;l<3;l++)
cout<<b[l]<<" " ;
cout<<j<<endl ;
}
//如果访问的页发生缺页有两种情况
if(j==1) //第一种，页表有空闲帧
for(l=0;l<3;l++)
{
if(b[l]==" ")
{
b[l]=a[i] ;
c[l-1]++ ;
c[l-2]++ ;
for(p=0;p<3;p++)
cout<<b[p]<<" " ;
cout<<j<<endl ;
q = 0 ;
break ;
}
}
if(j==1&&q==1) //须要访问的页不在页表中
{
m = MAX(c[0],c[1],c[2]) ;
b[m]=a[i] ;
c[m]=1 ;
c[m-1]++;
c[m-2]++;
c[m+1]++;
c[m+2]++;
for(p=0;p<3;p++)
cout<<b[p]<<" " ;
cout<<j<<endl ;
}
}
system("pause") ;
return 0 ;
}
代码实现：
四、思考题：
•比较LRU和其他置换算法各自的优缺点，能够实现其他置换算法模拟设计，分析内存页面数的变化对各种置换算法命中率的影响。
答：内存页面数越多，命中率越高，因为所有页都使用后，发生缺页下次命中时有更多的页可以与当前需要的页进行比较，所以命中率较高。
LRU算法可以减少页错误率,较易理解.
最优算法页错误最低,且没有Belady异常,但是较难实现 FIFO算法容易理解和实现,但是页错误率较高
五、实验总结
通过本次实验明白了LRU算法的过程，通过编程得知LRU算法
发生缺页时的两种情况，第一种是页表有空闲的帧但是没有当前所需要的页，另外一种是没有空闲帧也没有当前所需要的页，要分两种情况，通知这还要再是不是发生缺页的大前提下，由于很难找到最近最少使用的那一页来替换，所以花了不少时间，我通过给每页表中的每一页赋权值的方法解决了找到那个最近最少使用的一页，这个方法很好，希望能在下次的实验中多家努力。