虚拟内存系统【页面置换算法】

在虚拟内存管理程序中，当内存不足时，由于内存压力会迫使操作系统换出一些页，为常用的页腾空间，确定要将哪个页换出就是操作系统要执行的页面置换算法.

📖1. 最优页面置换算法(OPT)

最优页面置换算法的思想为：如果你不得不踢出一些页，为什么不踢出在最远的将来才会访问的页呢？ 也就是说，缓存中所有其他页都比这个页重要，因为在访问最远将来会访问的页时，比肯定会先访问其他页.

我们来看一个简单的例子，来理解最优页面置换算法. 假设一个程序按照下面的顺序访问虚拟页：0，1，2，0，1，3，0，3，1，2，1，假设缓存可以存3个页：

下面为页面的访问过程：

我们计算缓存命中率：有6次命中和5次未命中，那么缓存命中率为54.4%，但我们忽略页的第一次未命中，那么命中率为81.8%，但是，未来的访问是无法知道的，所以你无法为操作系统实现最优策略. 因此，在开发一个真正的、可实现的策略时，我们就必须寻找其他方式决定把哪个页面提出.

📖2. 先入先出置换算法(FIFO)

许多早期的系统避免了尝试达到最优的复杂性，采用了非常简单的替换策略. 例如：一些系统使用FIFO（先入先出）页面置换算法，页在进入系统时，简单地放入一个队列，当发生替换时，先入的页被踢出，FIFO有一个很大的优势：实现简单.

我们依然使用三个页0,1,2来观察访问过程：

对比FIFO和最优策略，FIFO明显不如最优策略，FIFO命中率只有57.1%，先进先出（FIFO）无法确定页的重要性：即使页0已被多次访问，FIFO仍然会将其踢出，因为它是第一个进入内存的.

📖3. 随机(Random)

在内存满的时候它随机选择一个页进行替换，随机具有类似与FIFO的属性，实现起来很简单，但是它在挑选替换哪个页时不够智能.

我们依然使用三个页0,1,2来观察访问过程：

随机的表现完全取决于多幸运，随机比FIFO好一点，比最优的差一点.

📖4. 最近最少使用的置换算法(LRU)

任何像FIFO这样简单的策略都可能会有一个共同的问题：它可能会踢出一个重要的页，而这个页马上要被引用，先进先出（FIFO）将先进入的页踢出. 如果这恰好是一个包含重要代码或数据结构的页，它还是会被踢出，尽管它很快会被重新载入，因此，FIFO、Random和类似的策略不太可能达到最优，需要更好的策略.

LRU思想：页替换策略可以使用的一个历史信息是频率，如果一个页被访问了很多次，也许它不应该被替换，因为它显然更有价值. 页更常用的属性是访问的近期性，越近被访问过的页，也许再次被访问的可能性也就越大.

这个算法的思想是基于局部性原则：程序倾向于频繁的访问某些代码和数据结构（例如循环访问某些数据），因此，我们应该尝试用历史数据来确定哪些页面更重要，并在需要时将这些页保存在内存中.

为了更好的理解LRU，使用三个页0,1,2来观察访问过程：

我们可以计算LRU算法下的页命中率：6/8 = 75%，它已经快接近最优置换算法了.

📖5. 近似LRU 时钟页面置换算法

为什么需要近似LRU？

为了实现LRU，我们需要做很多工作，在每次页访问（即每次内存访问，不管是取指令还是存储）时，我们都必须更新一些数据，从而将该页移到列表的前面（最近使用），与FIFO相比，FIFO的页列表仅在页被踢出或者新页添加到列表时才被访问，为了记录哪些页是最少和最近被使用，系统必须对每次内存引用做一些记录工作，有可能会影响性能.

所以我们可以不需要找到绝对最旧的页来替换，找到差不多旧的页就可以.

系统中的所有页都放在一个循环列表（环形链表）中，时钟指针开始指向某个特定的页，当必须进行页替换时，操作系统检查当前指向的页P的使用位是1还是0，如果是1，则意味着页面P最近被使用过，因此不适合被替换. 然后，P的使用位设置为0，时钟指针指下一页，该算法一直持续到找到一个使用位为0的页，使用位为0意味着这个页最近没有被使用过，最坏的情况下，如果所有的页都已经被使用了，那么就将所有页的使用位都设置为0.

📖6. 最不常用算法

记录每个页面的访问次数，当发生缺页中断时，将访问次数最少的页面置换出去，此方法需要对每个页面访问次数进行统计，额外开销.

📖7. 考虑脏页

时钟页面置换算法会对内存中的页是否被修改做出考虑：

如果页已被修改并因此变成脏页，则踢出它时就必须将它写回磁盘，这个操作代价较大，如果它没有被修改，踢出就没有成本，物理帧可以简单的重用于其他目的而不需要额外的I/O操作，因此，一些系统更倾向于踢出干净页，而不是脏页.