Question

页面置换算法

Answer 1

在程序的执行过程中，当所访问的信息不在内存时，会由操作系统负责将所需信息从外存调入内存，然后再继续执行程序，如果在调入内存时，发现内存空间不够，会由操作系统负责将内存中暂时用不到的信息换出到外存,由于频繁的进行IO操作会影响计算机性能，所以我们需要使用合适的算法来进行页面的置换。这里介绍几种常见的页面置换算法：

每次选择淘汰的页面将是以后永不使用，或者在最长时间不再被访问的页面，这样可以保证最低的缺页率。但是实际上进程执行的过程才能知道接下来会访问到的是哪个页面，操作系统无法预知，因此最佳置换算法是一种 理想化 算法，无法实现。

每次选择淘汰的页面是最早进入内存的页面，这种算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问，因此该算法性能很差。

每次淘汰的页面是最近最久未被使用的页面，需要有额外的内存空间来记录该页面自上次被访问以来所经过的时间，但是性能很好。

该算法是一种性能和开销较均衡的算法，又称最近未使用算法（NRU）。每个页面需要额外添加两个标志位：访问位（0代表最近没有被访问，1代表最近被访问）、修改位（0代表最近没有被修改，1代表最近被修改过）。如果淘汰的页面最近是被修改过，那么淘汰该页面前会进行写入外存的IO操作，使性能变差，所以在其他条件都相同的情况下，应优先淘汰没有修改过的页面。

算法规则：将所有可能被置换的页面排成一个循环队列 （访问位， 修改位）

第一轮：从当前位置开始扫描到第一个（0，0）的页用于替换。

第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0，1）的页面用于替换，同时将扫描过的页面的访问位设为0。例如（1，0）变成（0，0）

第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0，0）的页面用于替换。

第四轮：若第三轮扫描识别，则重新扫描，查找第一个（0，1）的页面用于替换。本次扫描必定会有一个页面被选中。