前言

之前简单介绍过虚拟内存是如何与物理内存进行地址映射的: 虚拟内存分页机制的地址映射, 但是仅仅地址映射是不够的, 在地址映射说过会有缺页的情况, 此时就需要操作操作系统将缺少的页加载到内存中. 但是, 如果内存满了怎么办呢? 毕竟虚拟内存一般都要大于物理内存的, 不可能将所有虚拟内存中的内容都加载到物理内存中.

当需要加载虚拟内存中的内容时, 发现物理内存已经没有空闲空间了. 肿么办嘞? 淘汰一个旧页面, 就可以腾出空间来加载新的页面了. 既然涉及到淘汰, 那么淘汰哪一个页面就是一个问题了. 这篇文章就简单介绍一下几个页面置换的算法, 或者说是页面淘汰的算法.

页面置换算法

什么样的页面置换算法是好的呢? 简单说, 就是尽可能的减少缺页中断的次数. 在发生缺页中断的时候, 是要损失一部分性能的.

最优页面置换

如果有4个页面已经加载了, 现在要在它们之间选择一个进行淘汰, 选择哪一个呢? 要想让中断发生的次数最少, 那么马上就要用到的页面是不能被淘汰的, 这么算下来, 就应该淘汰那个在访问序列中最后的页面. 举个例子:

为什么要在最开始先将内存填满, 而不是用到的时候再进行加载呢? 个人认为, 有如下好处

根据顺序执行的原则, 连续的页很可能马上就要用到. 故可以减少未来缺页的次数
即使加载的页用不到, 缺页中断的时候被淘汰了也没有带来性能的损失.
程序启动的时候, 虽然不能占用全部物理内存, 但还是会分配部分起始内存的. 内存空着也是空着, 不如先将程序加载进去

因为例子的局限性, 例子仅用作对置换规则的理解, 不用作各个算法优劣的比较

但是, 别高兴的太早, 这种情况太过于理想化了, 操作系统是无法预知未来的, 因此这个算法并不能在实际中应用. 讲话了, 不能用你提他干啥啊, 虽然不能实际实现, 但可以作为一个评价其他算法的优劣的标准呀, 越接近最优页面置换的就越好.

接下来, 几个实际应用的置换算法将相继登场(因为无法预测未来, 他们都是基于历史访问来判断的):

先进先出

既FIFO, 看名字就能看出来, 那个页面先进来, 哪个页面就先淘汰. 还使用相同的序列进行举例:

但是, 注意看我标记tip1的地方, 页面b在上一次访问刚刚被淘汰, 马上就又要用到了, 这这这…

实现

先进先出的方式, 实现起来很简单, 只需要维护一个页面换入的队列即可. 淘汰时从队首取出淘汰, 放入是添加到队尾即可.

Belady 现象

提到了先进先出, 那么就要说一下这个算法反常识的Belady现象. 不用去找belady这个单词的意思了, 他是首次发现这种现象的前辈名字.

在常识中, 随着物理页容量增大, 那么缺页中断的频率也会下降, 因为可以将更多的页面放入内存中了嘛. 但是, FIFO可能会出现这样一种情况: 随着物理页容量增大, 缺页中断的频率也随之增大.

举个例子: 有这样一个访问序列: [a, b, c, d, a, b, e, a, b, c, d, e]. 此时物理页中数据为空, 依次将页面读入内存. 过程就不说了, 直接说结果:

当物理页数量为3时, 产生9次缺页中断
当物理页数量为4时, 产生10次缺页中断

而这种Belady现象, 只有FIFO有, 其他算法都没有, 我特意造了写访问序列, 想找到其他算法也存在这种现象的情况, 很可惜, 没有找到. 不过已经就这种现象写了论文描述, 有时间尝试着看看.

最近最久未使用(LRU)

这就是大名鼎鼎的LRU了. 需要淘汰的时候, 刚刚被访问过的页面不能被淘汰, 那就淘汰那个已经很久没有被访问过的页面. 再次举例:

有没有发现, 其实LRU是在仿最优算法, 思路就是, 虽然我无法预测未来, 但是过去我是知道的, 又根据程序的局部性原理, 如果一个页刚刚被访问过, 那么他很大概率马上会再次访问. 而已经很久没有被访问的页面, 未来可能也不会访问.

虽然过去不能完全预测未来, 但好在程序的局部性原理又救了我们, 可以说是最优算法的一个近似解了. 但是别高兴的太早, 思路再好也要拿出可行的方案才行.

实现

要找到哪一个页面已经很久没有访问过了, 可以维护一个访问序列的链表, 首部是刚刚被访问的页面, 尾部就是很久都没有被访问的页面. 这样淘汰页面的时候直接取尾部的页面进行淘汰.

要维护这样的一个链表, 就需要在每次访问内存, 从链表中找到这个页面, 将其移动到首部

为了维护这样一个链表, 给每次内存访问都增加了额外的负担, 操作系统占用的时间越久, 留给应用程序的时间响应的就越少. 可以说得不偿失, 开销太大了.

所以, 虽然LRU看上去很美好, 但是没有一个高效的算法来实现它

时钟页面置换(二次机会)

在之前介绍页面的地址映射时说过, 页表中的每一页都存在着一些标志位, 而其中的一个标志位, 标识当前页是否被访问过, 当页面被访问时, 会由硬件负责将此标记为置为1, 注意是由硬件来完成的, 所以效率是很高的.

我们能不能利用这个标志位来实现页面置换呢? 参考LRU算法, 淘汰那个已经很久没有访问过的页面. 如果说, 先将所有访问位置为0, 等到下一次需要淘汰页面的时候, 找到一个访问位仍是0的页面, 说明在这期间这个页面从来没有被访问过不就可以了么

但是, 现实中的内存动辄几个 G, 如果每次都将所有的页面标识位修改一遍, 效率也是很慢的. 为了提高效率, 可以对这个算法再次进行近似. 将所有的页面连接为一个环, 使用一个指针在环上遍历, 每次需要淘汰页面的时候, 指针就开始遍历, 找到第一个访问位为0的页面淘汰, 同时在遍历的期间, 顺便把经过的页面访问位置为0. 这样每次只扫描部分页面, 最差情况扫描所有(将当前置为0, 扫描一圈回来必定拿到0), 故此算法的步骤如下:

若指针当前指向的页面, 访问位为0, 直接淘汰并指向下一页. 否则进入下一步
若当前页访问位为1, 将其改为0并指向下一页, 回到上一步.

对于被访问过的页面, 会在第二次扫描的时候进行淘汰, 算是给了两次机会吧.

还用刚才的序列进行举例:

时钟算法可以说是对LRU的一个可实现的近似解了. 据说在实际应用中, 效率是比较接近LRU的.

增强版时钟算法

在选择页面淘汰的时候, 如果两个页面都不会被访问了, 淘汰一个和淘汰另一个有区别么? 有的, 别忘了, 页面置换的时候, 不光换入, 还有换出的操作, 也就还是会将淘汰页的数据写回磁盘, 当然如果页面没有被修改就不需要写回的操作了, 数据都一样嘛. 怎么知道页面有没有被修改呢? 巧了, 也有一个标记页面修改的标记位.

刚刚的时钟算法用到了标志位中的访问位, 那么如何将修改位也加入到判断标准中, 优先淘汰没有被修改的页面, 就能够提高页面置换的效率了. 两个标志位的话, 就有如下四种情况, 分情况讨论:

(访问位1, 修改位0): 最近访问过, 将访问位置为0
(访问位1, 修改位1): 最近访问过, 将访问位置为0
(访问位0, 修改位0): 最近没有访问且没有修改, 可以直接置换
(访问位0, 修改位1): 最近没有访问但修改过, 将修改位置为0, 等待下一轮访问

但是, 但是, 你有没有想过, 如果将标志位中的修改位置为0了, 那么操作系统进行页面置换的时候, 依据什么来判断当前页是否需要执行回写磁盘的操作呢? 所以, 修改位是不能动的. 如果不动修改位, 又如何来实现呢? 那就要增加额外变量来记录了:

第一圈扫描的时候, 淘汰(访问位0, 修改位0)的页面
- 同时在扫描的过程中将访问位改为0
如果第一圈没找到, 那么第二圈淘汰(访问位0, 修改位1)的页面

也就是说, 和时钟算法对数据的处理规则相同, 唯一不同的是额外增加临时变量记录当前是第几圈, 第一圈淘汰(访问位0, 修改位0)的页面, 第二圈才会淘汰(访问位0, 修改位1)的页面. 也就是将修改过的页面进行降权操作.(当然, 也可以有其他实现方式, 不过大体意思不变) 再次举例:

如此操作, 使得被修改的页面更不容易被换出去, 进而提升页面置换效率. 实现起来和时钟算法相似. 是时钟算法的增强版.

最不常用(LFU)

既LFU, 在淘汰的时候, 淘汰使用次数最少的页面. 也是一种依据过去预测未来的思路, 过去使用较多的页, 很可能在未来也会多次访问. LRU的考察纬度是时间, 而LFU的考察纬度是次数. 再次上图:

有这样一种情况, 程序在初始的时候频繁访问页面 A, 等到程序平稳运行了, 就不会再访问页面 A 了. 但是, 因为计数的结果, 页面 A 的访问次数及高, 导致一直没有被淘汰, 长期驻留在内存中. 如何避免这样的问题呢? 其实也很简单, 出现问题是因为增加了时间纬度, 只需要每个一段时间将页面的计数左移一位(除以2), 这种页面的访问次数就会随着时间推移降下来了.