⑴ 页面置换算法
在瞎启虚程序的执行过程中，当所访问的信息不在内存时，会由操作系统负责将所需信息从外存调入内存，然后再继续执行程序，如果在调入内存时，发现内存空间不够，会由操作系统负责将内存中暂时用不到的信息换出到外存,由于频繁的进行IO操作会影响计算机性能，所以我们需要使用合适的算法来进行页面的置换。这里介绍几种常见的页面置换算法：
每次选择淘汰的页面将是以后永不使用，或者在最长时间不再被访问的页面，这样可以保证最低的缺页率。但是实际上进程执行的过程才能知道接下来会访问到的是哪个页面，操作系统无法预知，因此最佳置换算法是一种 理想化 算法，无法实现。
每次旁纯选择淘汰的页面是最早进入内存的页面，这种算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问，因此该算法性能磨燃很差。
每次淘汰的页面是最近最久未被使用的页面，需要有额外的内存空间来记录该页面自上次被访问以来所经过的时间，但是性能很好。
该算法是一种性能和开销较均衡的算法，又称最近未使用算法（NRU）。每个页面需要额外添加两个标志位：访问位（0代表最近没有被访问，1代表最近被访问）、修改位（0代表最近没有被修改，1代表最近被修改过）。如果淘汰的页面最近是被修改过，那么淘汰该页面前会进行写入外存的IO操作，使性能变差，所以在其他条件都相同的情况下，应优先淘汰没有修改过的页面。
算法规则：将所有可能被置换的页面排成一个循环队列 （访问位， 修改位）
第一轮：从当前位置开始扫描到第一个（0，0）的页用于替换。
第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0，1）的页面用于替换，同时将扫描过的页面的访问位设为0。例如（1，0）变成（0，0）
第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0，0）的页面用于替换。
第四轮：若第三轮扫描识别，则重新扫描，查找第一个（0，1）的页面用于替换。本次扫描必定会有一个页面被选中。
⑵ 页面置换算法
上文说到，请求分页管理方式中，当需要调入页面到内存中，但此时内存已满，就需要从内存中按照一定的置换算法决定将哪个页面取出将内存给调入的页面。本文将介绍几种页面置换算方法。
本文内容
算法思想：每次选择 淘汰的页面 将是 以后永不使用 ，或者 在最长时间内不再被访问的页面 ，这样可以保证最低的缺页率。
举例说明，假设系统为进程分配了三个内存块，并考虑到有以下页面号引用串（会依次访问这些页面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
....按照此算法依次执行，最后的结果如下
结果图
注：缺页时未必发生页面置换，若还有可用的空闲内存空间就不用进行页面置换。
最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此， 最佳置换算法是无法实现的 。
算法思想：每次选择 淘汰的页面是最早进入内存的页面。
该算法很简单，每次淘汰最在内存中待时间最久的各个，下面分别给出系统为进程分为配三个内存块和四个内存块的执行情况图。访问序列为3,2,1,0,3,2,4,3,2,1,0,4
分配三个内存块的情况：
分配四个内存块的情况：
当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为 贝莱迪（Belay）异常 。
只有FIFO算法会产生Belay异常。 另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此， 算法性能差。
算法思想： 每次淘汰的页面是最近最久未使用的页面。
实现方法：赋予每个页面对应的页表项中，用 访问字段记录该页面纯亏自上次被访问以来所经历的时间t。 当需要淘汰一个页面时，选择现有页面中t最大的页面，即最近最久未使用。
举例说明，加入某系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
这里先直接给出答案
结果图
最佳置换算法那性能最好，但无法实现。先进先出置换算法实现简单，但是算法性能差。最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。 时钟置换算法 是一种 性能和开销均春裤配平衡 的算法。又称 CLOCK算法 ，或 最近未用算法 （ NRU ，Not Recently Used）
简单CLOCK算法 算法思想：为每个页面设置一个 访问位 ，再将内存中的页面都通过 链接指针链接成一个循环队列 。当某个页被访问时，其访问位置1.当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，暂不换出，将访问位改为0，继续检查下一个页面，若第一轮扫描中所有的页面都是1，则将这些页面的访问位一次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个扒指淘汰页面最多会经过 两轮扫描 ）。
这个算法指针在扫描的过程就像时钟一样转圈，才被称为时钟置换算法。
简单的时钟置换算法仅考虑到了一个页面最近是否被访问过。事实上，如果淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。 只有淘汰的页面被修改过时，才需要写回外存。
因此，除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。
改进型时钟置换算法的 算法思想 ： 在其他在条件相同时，应该优先淘汰没有被修改过的页面， 从而来避免I/O操作。
为了方便讨论，用（访问位，修改位）的形式表示各页面的状态。如（1,1）表示一个页面近期被访问过，且被修改过。
算法规则 ：将所有可能被置换的页面排成一个循环队列
由于第二轮已将所有的页的访问位都设为0，因此第三轮、第四轮扫描一定会选中一个页，因此 改进型CLOCK置换算法最多会进行四轮扫描。
假设系统为进程分配了5个内存块，某时刻，各个页的状态如下图
如果此时有新的页要进入内存，开始第一轮扫描就找到了要替换的页，即最下面的状态为（0,0）的页。
某一时刻页面状态如下
如果此时有新的页要进入内存，开始第一轮扫描就发现没有状态为（0，0）的页，第一轮扫描后不修改任何标志位。所以各个页状态和上图一样。
然后开始第二轮扫描，尝试找到状态为（0,1）的页，并将扫描过后的页的访问位设为0，第二轮扫描找到了要替换的页。
某一时刻页面状态如下
第一轮扫描没有找到状态为（0,0）的页，且第一轮扫描不修改任何标志位，所以第一轮扫描后状态和上图一致。
然后开始第二轮扫描，尝试找状态为（0,1）的页，也没有找到，第二轮扫描需要将访问位设为1，第二轮扫描后，状态为下图
某一时刻页面状态如下
具体的扫描过程和上面相同，这里只给出最后的结果，如下图
所以，改进型的CLOCK置换算法最多需要四轮扫描确定要置换的页。从上面的分析可以看出，改进型的CLOCK置换算法
(1) 第一优先级淘汰的是 最近没有访问且没有修改 的页面。
(2) 第二优先级淘汰的是 最近没有访问但修改 的页面。
(3) 第三优先级淘汰的是 最近访问但没有修改 的页面。
(4) 第四优先级淘汰的是 最近访问且修改 的页面。
⑶ FIFO可能会发生Belady异常，堆栈算法不会发生Belady异常，如LRU。证明为何不会异常。
LRU置换算法不会出现Belady异常：
在先进先出算法(FIFO)——选择装入最早的页面置换的过程中，可以通过链表来表示各页的装入时间先后。FIFO的性能较差，因为较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出，并且有Belady现象。所谓Belady现象是指：采用FIFO算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。
⑷ 最佳置换算法最后一个怎么办
最佳置换算法(OPT)(理想置换算法):从主存中移出永远不再需要的页面;如无这样的页面存在,则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。 最佳置换算法可以用来评价其他算法。