页面置换算法

在地址映射时，如果刚好CPU执行一个指令，需要用到该指令中的虚拟地址中对应的物理地址，但是该虚拟地址没有对应的物理地址的映射，则会让cpu产生一个缺页中断。操作系统必须在内存中选择一个页面将其换出内存，以便为即将调入的页面腾出空间，如果要换出的页面在内存驻留期间已经被修改过，就必须把它写回磁盘以更新该页面在磁盘上的副本，如果该页面没有被修改过，那么就不用回写。在这里，有以下几个算法来选择需要淘汰的页面。

假设系统为进程分配了三个物理块，访问页面顺序如下，
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

1、最佳置换算法（最优页面置换算法，Optimal,OPT）

在内存中，总是移除那些不可能用到的页面，如果没有这样的页面，则总是移除最长时间不需要访问的页面。如下图，

image.png

发生缺页中断次数为9，页面置换次数为6

2、先进先出置换算法（FIFO）

由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最久进入的页面放在表头。当缺页中断发生时，淘汰表头的页面并把最新调入的页面加到表尾。如下图

image.png

发生缺页中断次数为15，页面置换次数为12

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

这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。如下图：

image.png

发生缺页中断次数为12，页面置换次数为9