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

1、实验报告内存页面置换算法的设计姓名：田玉祥班级：计算机科学与技术专业一班实验内容实现最近最久未使用（ LRU ）置换算法二、实验目的? LINUX 中，为了提高内存利用率， 提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其部分调入内存便可运行，还支持请求调页的存储管理方式。? 本实习要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面 置换算法。三、实验题目1. 最近最久未使用（ LRU ）置换算法原理就是：当需要淘汰某页面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。?例如：分配

2、给该进程的页块数为3, 个20位长的页面访问序列为：12560,36536,56042,70435则缺页次数和缺页率按下图给出：序 列12560365365S0427043&111666eae6&6666777332220005555554440005EEE333333300222444是是是是是是疋疋疋疋疋疋疋疋疋图3-1缺页欢敌：It缺页率：15/20=0. ?5假定分配给该进程的页块数为 3,页面访问序列长度为20。本实 验可以采用数组结构实现，首先随机产生页面序列，当发生请求调页 时，若内存已满，则需要利用 LRU算法，将当前一段时间内最久未 使用过的页替换出去。程序实

3、现想法：用一个数组an来存放所有需要访问的页，用一个数组b3来存 放页表，用数组c3来存放页表每一页的权值，就是最近最少使用的 度，度越高则使用率越小，用n次循环，每次ai进行判断时先判断 有没有空格，再判断ai是否已经在页表中，此时注意要将权值归1, 若都没有这些情况，则用函数 int MAX(int a,int b,int c) 找到权值最大的， 进行替换，并将其他页的权值加 1.实验代码：/LRU 算法，最近最少使用的页替换算法#include<iostream> #include <string> using namespace std ;/赋值之后的权值中找到

4、权值最大的，返回它的int MAX(int a,int b,int c) 下标也就是最近最少使用的int max = a ;if(max<b)max = b ;if(max<c)max = c ;elseif(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

5、表示发生缺页/q 来表示页表是否有空格， 即当前是否全部在使用， 1 表示全部在使用，0 表示还有空格/存放页表string *b = new string 3 ;int *c = new int 3 ;/存放页表的权值for(i=0;i<3;i+)bi = " "ci = 1 ;coutvv"请输入要访问的页码页数："vve ndl ;cin >> n ;string *a = new string n ;/存放所有要访问的页 coutvv"请输入"vvnvv"个每一次要访问的页码页号："vve

6、ndl ;for(i=0;i<n;i+)cin>>ai ;coutvv"页表访问过程如下，“ 1”表示发生缺页，“0”表示不发生缺页："vvendl ;for(i=0;i<n;i+)/表示页表没有空位，全被使用for(l=0;lv3;l+)if(ai=bl)cl=1 ;/将权值设为 1 cl-1+;cl-2+;cl+1+;cl+2+;break ;if(j=0)接输出。并将其权值设为 1/如果需要访问的页正在被访问，即已经在页表，直for(l=0;l<3;l+)cout<<bl<<"IIcout<<

7、j<<endl ;/如果访问的页发生缺页有两种情况if(j=1)/第一种，页表有空闲帧for(l=0;l<3;l+)if(bl=" ")bl=ai ;cl-1+ ;cl-2+ ;for(p=0;p<3;p+)cout<<bp<<"IIcout<<j<<endl ;break ;if(j=1&&q=1)/须要访问的页不在页表中m = MAX(c0,c1,c2) ;bm=ai ;cm=1 ;cm-1+;cm-2+;cm+1+;cm+2+;for(p=0;p<3;p+)cout

8、<<bp<<"IIcout<<j<<endl ;system("pause") ;return 0 ;代码实现：:弋"EE丞样C握序旦筠隹业让RUU旳tig'LRU辟已要询可的页码页数：la个每一软S访问的页码页号"fl" *示不S圭竝页.HHkLLars1 -T-ltH44清按任意龍继绩.，四、思考题:?比较LRU和其他置换算法各自的优缺点，能够实现其他置换算法模拟设 计，分析内存页面数的变化对各种置换算法命中率的影响。答：内存页面数越多，命中率越高，因为所有页都使用后，发生缺页下次命中时有更多的页可以与当前需要的页进行比较，所以命中率较高。LRU算法可以减少页错误率，较易理解.最优算法页错误最低，且没有Belady异常,但是较难实现FIFO算法容易理解和实现，但是页错误率较高五、实验总结通过本次实验明白了 LRU算法的过程，通过编程得知 LRU算法发生缺页时的两种情况，第一种是页表有空闲的帧但是没有当前所需 要的页，另外一