《操作系统 - 清华大学》6 -1：局部页面置换算法：最优页面置换算法

0. 概述

页面置换算法涉及到两个主要的小部分，一个是局部页面置换算法，一个是全局页面置换算法，分别就这两部分介绍一系列的算法，讲解它们的特点，它们之间具体的操作过程，以及各自的比较等等。

1. 页面置换算法的功能与设计目标

首先看页面置换算法的功能和目标：

1. 功能： 当缺页中断发生之后，需要调入新的页面，调新页面时，如果这时候内存里面的物理页已经满了，那需要把当前一些不常用的页，把它换出去，空出新的页面，把需要的页面给放进去，这是为什么需要置换的很重要功能。

2. 目标： 换出页面意味着对硬盘进行读或者写操作，希望尽量减少页面的换入换出操作。因为硬盘的读写比内存读写要慢 1~2 数量级以上，通过这种方式可以确保整个系统的执行比较快速，而不是说受制于大量的硬盘读写，使得整个虚存的效率会极大地降低。

   很重要的目标是减少换入换出的次数，内存页换入或换出到磁盘的次数。

也不是说内存中所有的物理页都需要换入换出，有些物理页是需要常驻内存的，比如说操作系统中很重要的一些数据，它的代码段和数据，这些是随时要访问的，这些页需要把它常驻内存，可以用页面锁定技术，能够把相关的页放在内存里面，使得这些页在做页面置换算法的时候不在被处理，可以确保操作系统随时都能够正常的工作。

2. 页面置换算法的评价方法

其实有一系列页面置换算法，怎么有效地分析比较它们呢？需要设置一定的实验环境，当然可以在实际机器里面跑操作系统，能够写出各种各样页面置换算法测它，当然这种情况测试比较复杂，有更简单办法，可以设置大致的模拟环境，比如几个正在运行程序，它有一系列内存访问，把内存地址给记录下来，它读写的内存地址，形成一个序列。
上图可以看到，把地址访问序列记录下来，以页号和偏移做标记，比如(3，0) 访问第3个页面，0 偏移，这一系列的序列就形成了访问的序列，就是内存访问序列。

当然在考虑页面置换算法时候，需要注意什么呢？ 可以把它的偏移给忽略掉，只关注访问页。

因为只有当一个页不存在时候，才会产生缺页中断，才会需要考虑，是否需要把页置换出去，如果在同一个页里面多次访问，只有第一次才会产生中断，一旦把这页调到内存来之后，就不太会产生缺页中断，只有后面如果这一页在进一步访问中，它又被置换出去了，才可能产生缺页中断。

所以可以把 offset 给忽略掉，只保留这个页号访问的序列，形成随着页访问的序列的 List。有 List 之后，就可以设计基于整个 List 的各种各样的页面置换算法，在一定的页帧或者物理页大小的情况下，用某种算法会产生多少次缺页次数，产生缺页越少，效率越高。最底是一次缺页都不产生，当然这种情况是不太现实的，只是希望说减少缺页中断次数。

3. 最优页面置换算法的工作原理

首先想到就是如果当一个中断产生之后，到底应该替换哪一个页？如果可以预知未来的话，希望是替换将来很长一段时间都不会被访问到的页，可以认为这种页暂时不需要，把这个页替换出去，等将来真的需要再把它置换进来，把当前正需要的放内存中了，根据将来什么时候会访问的信息来设计页面置换算法，称之为 最优页面置换算法。

算法怎么实现？首先需要知道未来的情况，但是操作系统在运行应用程序的时候，它其实很难知道将来这个程序会访问哪些页面。所以说这算法依据的条件是理想情况，实际系统中其实无从知道每一个正在跑的程序需要访问的页面是哪一个。所以说这个算法其实很难实现，因为获得这个条件很难获得，那怎么办呢？

其实这个算法确实是不太实际的算法，但是可以把这个算法做评价标准。因为这个算法根据未来的情况来做推断，按照道理来说产生缺页会很少，所以可以把它做最佳的评价标准，看看程序采取其他的置换算法之后，它的缺页次数跟这种算法性比较。

只要把一个程序跑了之后，就可以得到程序访问的序列。根据序列就知道未来，当然这已经成过去了，在这种情况下可以采用最优置换算法得出在预知未来情况下最好的结果是什么。最少页面缺页的次数，比较就知道，希望设计出页面置换算法能够接近它的性能，如果能逼近它，就认为这种算法是比较好的算法。

4. 最优页面置换算法示例

举例说明这个页面置换算法怎么来跑，刚才已经设置实验环境

表的最上行时间轴，表明在 0 1 2 3 4 时刻到底访问了哪些页；第二行访问的页列表， a b c d 表示，比如1时刻访问c， 2 时刻访问 a 页；下面页帧表明当前操作系统给程序分配了四个物理页帧，但需要注意，虽然给分配4个页帧，整个要访问的页有5个，很显然这种情况下就可能出现物理页不够情况，就会产生页置换，在这种情况下最优置换算法怎么实现？

0 时刻物理页帧已经存了 a、b、c、d 四个虚拟页，访问前四个 c a d b 的时候，其实对应的物理页帧都存在了， 所以说在接下来这四次访问不会产生缺页中断。

但是第五次访问 e 时候，因为虚拟的 e 没有在物理页帧中，这时候需要把某一个需要替换出去的页给它换出去，换哪一页？如果基于最优置换算法，应该换离它下次访问最远的那页，离a 最远的时间是7，离 b 最远是6， c 是 9，d 是10，可以看出来最远的是 d，所以需要把 d 给换出去，留出空间填上 e。