页面置换算法

页面置换算法

在进程运行过程中，若需要访问的物理块不在内存中，就需要通过一定的方式来将页面载入内存，而此时内存很可能已无空闲空间，因此就需要一定的算法来选择内存中要被置换的页面，这种算法就被称为页面置换算法。页面置换算法的好坏，将直接影响系统的性能。

页面的换入、换出需要磁盘I/O，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率。

下面介绍几种常用的页面置换算法。

• 最佳置换算法（OPT）
• 先入先出置换算法（FIFO）
• 最近最久未使用置换算法（LRU）
• 时钟置换算法（CLOCK）
• 改进型的时钟置换算法

1.最佳置换算法（OPT）

该算法是一种理想化的算法，具有非常好的性能，但是由于目前无法预知未来，因此难以实现。

该算法选择淘汰的页面是：未来永远不会再使用的页面 or 未来最长时间不再被访问的页面。该算法保证了可以获得最低缺页率，但无法预知未来页面的使用情况，因此目前无法实现，但通常用来评价其他算法。

例：假定系统为某进程分配了三个物理块,并考虑有以下的页面号引用串:
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

进程运行时,先将 7,0,1 三个页面装入内存。以后,当进程要访问页面 2 时,将会产生缺页中断。此时 OS 根据最佳置换算法,将选择页面 7 予以淘汰。这是因为页面 0 将作为第 5 个被访问的页面,页面 1 是第 14 个被访问的页面,而页面 7 则要在第 18 次页面访问时才需调入。下次访问页面 0 时,因它已在内存而不必产生缺页中断。当进程访问页面 3时,又将引起页面 1 被淘汰;因为,它在现有的 1,2,0 三个页面中,将是以后最晚才被访问的。下图给出了采用最佳置换算法时的置换图。由图可看出,采用最佳置换算法发生了 6 次页面置换。

2.先进先出页面置换算法（FIFO）

该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。

例:假设系统为某进程分配了三个内存块，并考虑到有以下页面号引用串：3，2，1，0，3，2，4，3，2，1，0，4

当进程第一次访问页面0 时,将把第 3 页换出,因为它是最先被调入内存的;在第一次访问页面 3 时,又将把第 2 页换出, 因为它在现有的 2, 1, 0 三个页面中是最老的页。 由下图可以看出,利用 FIFO 算法时进行了 6 次页面置换，9次缺页中断。

3.最近最久未使用算法(LRU)

最近最久未使用置换算法(LRU):每次淘汰的页面是最近最久未使用的页面实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。该算法的实现需要专门的

例:假设系统为某进程分配了四个内存块，并考虑到有以下页面号引用串:1，8，1，7，8，2，7，2，1，8，3，8，2，1，3，1，7，1，3，7

在手动做题时，若需要淘汰页面，可以逆向检查此时在内存中的几个页面号。在逆向扫

4.时钟置换算法（CLOCK）

时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法（NRU)
简单的CLOCK算法实现方法：为每个页面设置一个访问位(访问位为1，表示最近访问过;访问位为0，表示最近没访问过)，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)。

5.改进型的时钟置换算法

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。

因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过;修改位=1，表示页面被修改过。
为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1，1）表示一个页面近期被访问过，且被修改过。

算法规则： 将所有可能被置换的页面排成一个循环队列
第一轮:从当前位置开始扫描到第一个(0,0）的帧用于替换。本轮扫描不修改任何标志位
第二轮:若第一轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于替换。本轮将所有扫描过的帧访问位设为0
第三轮:若第二轮扫描失败，则重新扫描，查找第一个(0,0）的帧用于替换。本轮扫描不修改任何标志位
第四轮:若第三轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于替换。
由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描。