lru页面置换算法_操作系统 | 页面置换算法

• 功能与目标

硬盘的读写要比内存慢一到两个数量级，所以要尽可能减少页面的换进换出次数

有一些需要常驻内存，比如操作系统

• 实验设置与评价方法

如何分析比较

• 最优页面置换算法(OPT，optimal)

理想状态下我们想要替换很长一段时间都不会使用的一个页，把需要的页放到内存中去，也就是根据将来什么时候会访问来设计叫做最优页面置换算法，但是操作系统运行时候，很难知道将来会使用哪个内存，这是一个理想情况，实际系统无法实现

• 先进先出算法(FIFO)

实现起来很简单，有个list就行了，类似于栈

时间5时刻，物理页中没有e，只有a b c d，因为初始顺序为a->b->c->d,所以要产生中断，进行页面替换，替换掉存在时间最长的a，时间7时刻，物理页中此时的a已经没有了，所以要进行替换，这时存在时间最长的为b，所以b替换为a

可以看到FIFO算法实现简单，但是产生缺页次数比较多

• 最近最久未使用算法(LRU，Least Recently Used)

两种实现方法

结果不错，但是代价比较大

使用堆栈的方法，实现过程如上图所示

• 时钟页面置换算法(Clock)

FIFO算法需要记录精确的时间，开销比较大，用不太精确，近似的访问时间的状态

一个页表项存的是页帧号，页表项它的索引是页号index，所以页帧号和页表项有个对应关系，知道页号也就能知道对应的页帧号，也就是物理页帧号是多少，查到对应的地址

除了页帧号，还有bit访问位

现在有5个物理页帧，要访问的虚拟页有Page0-7，8个

   建好一个环形的List

   目前Page 7 4 0 3 1这5个页是放在物理内存中

  resident bit存在位，判断是否存在，如果是1代表在物理内存中是存在的，存在代表映射关系是正常的

  used bit访问位，如果是1，代表被访问过一次

  frame number 0 3 4 1 5 是页帧号

   首先resident bit位必须是1，在Clock算法中依据是used bit，作为置换的依据

   指针指向上一个访问位置，运行过程中，产生缺页中断，需要替换

   当前指针在Page0的页表项，used bit这里为1，代表被访问过，首先要把bit清零，然后顺时针看下一项，一直找的used bit为0的那一个页表项，这个物理页的页帧应该被替换，在这里是序列为1的页表项Page0，替换成当前缺页需要替换的页帧号，把虚拟页Page6的内容替换到物理位置为5的位置上

 二次机会法

Page table entries for resident papges：

初始的abcd都是10代表了都是读操作

时刻2是a的写操作、时刻4的b是写操作，所以都要变成11，写操作位要进行置1

时刻5，产生缺页中断，现在指针指向a位置，这里会把a变成01，b变成01，c变成00，d变成00，转一圈回来a是01，变成00，往下走，b变成00，继续往下，c因为是00，所以被替换，同时指针指向下一个位置。

优先把只读的页换出去，相当于有两次机会，对于可写页减少了换出的概率，比Clock算法更好

• 最不常用算法(LFU，Least Frequently Used)

不是算法本身不常用，而时算法采用的策略不畅使用

• Belady现象

• LRU、FIFO和Clock的比较

LRU算法符合栈的特点，给的物理页帧越多，产生缺页越少

LRU考虑历史信息，FIFO不考虑

如果程序具有局部特点，适合LRU，可以产生比较少的缺页

程序没有局部特征，三个算法结果可能一样

Clock类似于FIFO算法，这里运用了一些硬件物理bit，来模拟访问时间(先后顺序)，可以逼近LRU算法，开销比较小

算法只是一个环节，对于程序特点，最好具有局部性

• 全局页面置换算法

上面的算法主要是针对一个进程来讲，实际操作系统多个程序，所以要研究全局页面置换算法

分配三个物理页帧，则会产生9次缺页

分配四个物理页帧，则会产生1次缺页

物理页帧大小会对整个页面置换效果产生比较大的影响

程序在运行过程中实际是动态的，开始需要物理页帧比较多，中减少，到结束时又会需要很多，对于物理页帧的需求是可变的

前面的算法假定分配的物理页帧是固定的，操作系统中可以跑多个程序，此时如果依然是给每个程序分配固定的物理页帧是不合理的。限制了灵活性，根据程序的运行阶段，动态的调整物理页帧的大小

• 工作集模型

一个进程当前正在使用的逻辑页面集合

起始时间t1 向左十个长度，访问的物理页帧只有 1 2 5 6 7

起始时间t2 向左是个长度，访问的物理页帧只有 3 4

两个不同时间，访问特点不一致，t2的工作集具有很好的局部性，重复性强

• 工作集页置换算法

形成工作集窗口，在窗口中的页代表当前这段时间内被访问的页，有需要替换的页则要替换不在工作集的页，第二个，随着程序的执行，窗口随着时间其实在平移挪动，某一个页不在串口中时也要进行丢弃，不一定非得等到缺页情况才进行丢弃，只要页不属于工作集窗口，那丢弃。

时刻1 产生一次缺页中断，工作集 ac d e，工作集窗口是4

时刻2 不产生缺页中断，此时的工作集窗口是 a c d，e不属于工作集窗口的页，e需要被换出，只读的直接free，写入的写回到硬盘中去

时刻3 工作集没有变化

时刻4 产生缺页中断，b放进来，同时a换出，这里不是页不够了(有别于局部置换算法)，为什么换a，是因为a的访问时间为0，已经超出了工作集窗口

时刻6 产生缺页，工作集变成4个

当前在物理内存中放了哪些页取决于它是否在这个工作集窗口之内，如果工作集窗口设置为4，所有超出窗口的页都需要被换出，这样确保物理内存中可以有足够的空间存在，在系统层面，可以确保系统的缺页次数降低

• 缺页率置换算法

上面的窗口是固定的，可不可以窗口本身变化

• 抖动问题

工作集体现了程序在执行过程中它本身对内存访问的固有属性

常驻集体现的是操作系统要把我们当前运行的程序要访问哪些页面放到内存中来

如果说常驻集小于工作集，那么产生缺页会很多

程序运行多，机器越来越慢，内存快用完，会产生大量的缺页，进行大量的换入换出，频繁的IO操作，缺页中断，CPU的效率就会很低

操作系统希望达到运行程序尽量多，CPU效率在峰值，所以要找得到平均点