(LRU)置换算法-操作系统.pdf

(LRU)置换算法-操作系统

实验报告三

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

姓名：田玉祥

班级：计算机科学与技术专业一班

一、实验内容

·实现最近最久未使用（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，

若都没有这些情况，则用函数intMAX(inta,intb,intc)找到权值最大
的，进行替换，并将其他页的权值加1.

实验代码：

//LRU算法，最近最少使用的页替换算法

#include<iostream>

#include<string>

usingnamespacestd;

intMAX(inta,intb,intc)//赋值之后的权值中找到权值最大的，返回
它的下标也就是最近最少使用的

{

intmax=a;

if(max<b)

{

max=b;

if(max<c)

max=c;

}

else

if(max<c)

max=c;

if(a==max)//找到权值最大的数的下标

return0;

elseif(b==max)

return1;

elseif(c==max)

return2;

}

intmain()

{

//stringk;//k表示当前最近最少使用的页;

inti,j,n,l,m,p,q;//j表示当前访问的页是否已经在访问,0表示没
有发生缺页，1表示发生缺页

//q来表示页表是否有空格，即当前是否全
部在使用，1表示全部在使用，0表示还有空格

string*b=newstring[3];//存放页表

int*c=newint[3];//存放页表的权值

for(i=0;i<3;i++)

{

c[i]=1;

}

请输入要访问的页码页数：

cin>>n;

string*a=newstring[n];//存放所有要访问的页

请输入个每一次要访问的页码页号：

for(i=0;i<n;i++)

cin>>a[i];

页表访问过程如下，“1”表示发生缺页，“0”表示不发生缺页：

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<<j<<endl;

}

//如果访问的页发生缺页有两种情况

if(j==1)//第一种，页表有空闲帧

for(l=0;l<3;l++)

{

{

b[l]=a[i];

c[l-1]++;

c[l-2]++;

for(p=0;p<3;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++)