为什么需要页面置换算法

操作系统只把应用程序中“常用”的数据和代码放在物理内存中，而不常用的数据和代码放在了硬盘这样的存储介质上。如果应用程序访问的是“常用”的数据和代码，那么操作系统已经放置在内存中了，不会出现什么问题。但当应用程序访问它认为应该在内存中的的数据或代码时，如果这些数据或代码不在内存中，会产生缺页异常。

如果发生了缺页中断，就需要从磁盘上将需要的页面调入内存。如果内存没有多余的空间，就需要在现有的页面中选择一个页面进行替换。使用不同的页面置换算法，页面更换的顺序也会各不相同。如果挑选的页面是之后很快又要被访问的页面，那么系统将很开再次产生缺页中断，因为磁盘访问速度远远内存访问速度，缺页中断的代价是非常大的。因此，挑选哪个页面进行置换不是随随便便的事情，而是有要求的。

页面置换算法

• 最优 (Optimal) 页面置换算法
  　　由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长的未来时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于操作系统其实无法预知一个应用程序在执行过程中访问到的若干页中，哪一个页是未来最长时间内不再被访问的，因而该算法是无法实际实现，但可以此算法作为上限来评价其它的页面置换算法。

• 先进先出(First In First Out, FIFO)页面置换算法
  　　该算法总是淘汰最先进入内存的页，即选择在内存中驻留时间最久的页予以淘汰。只需把一个应用程序在执行过程中已调入内存的页按先后次序链接成一个队列，队列头指向内存中驻留时间最久的页，队列尾指向最近被调入内存的页。这样需要淘汰页时，从队列头很容易查找到需要淘汰的页。FIFO算法只是在应用程序按线性顺序访问地址空间时效果才好，否则效率不高。因为那些常被访问的页，往往在内存中也停留得最久，结果它们因变“老”而不得不被置换出去。FIFO算法的另一个缺点是，它有一种异常现象（Belady现象），即在增加放置页的页帧的情况下，反而使缺页异常次数增多。

• 二次机会（Second Chance）页面置换算法
  　　为了克服FIFO算法的缺点，人们对它进行了　　改进。此算法在页表项（PTE）中设置了一位访问位来表示此页表项对应的页当前是否被访问过。当该页被访问时，CPU中的MMU硬件将把访问位置“1”。当需要找到一个页淘汰时，对于最“老”的那个页面，操作系统去检查它的访问位。如果访问位是0，说明这个页面老且无用，应该立刻淘汰出局；如果访问位是1，这说明该页面曾经被访问过，因此就再给它一次机会。具体来说，先把访问位位清零，然后把这个页面放到队列的尾端，并修改它的装入时间，就好像它刚刚进入系统一样，然后继续往下搜索。二次机会算法的实质就是寻找一个比较古老的、而且从上一次缺页异常以来尚未被访问的页面。如果所有的页面都被访问过了，它就退化为纯粹的FIFO算法。

• 时钟算法
  　　为了改善第二次机会算法的缺点，先驱们提出了时钟算法。时钟算法的核心思想是：将页面排成一个时钟的形状，该时钟有一个针臂，每次需要更换页面时，我们从针臂所指的页面开始检查。如果当前页面的访问位为0，即从上次检查到这次，该页面没有被访问过，将该页面替换。反之，就将其访问位清零，并顺时针移动指针到下一个页面。重复这些步骤，直到找到一个访问位为0的页面。
  　　例如下图所示的一个时钟，指针指向的页面是F，因此第一个被考虑替换的页面是F。如果页面F的访问位为0，F将被替换。如果F的访问位为1，则F的访问位清零，指针移动到页面G。从表面上看，它和第二次机会算法类似，都是访问位为0就更换，反之则再给一次机会。但是，它和第二次机会算法还是有几点不同：
  　　
  　　（1）他们的数据结构不一样，第二次机会使用的是链表，时钟算法使用的是索引（整数指针）。这样，其使用的内存空间不一样。
  　　（2）第二次机会需要使用额外的内存，而时钟算法可以直接使用页表。使用页表的好处是无需额外的空间，更大的好处是页面的访问位会定期自动清零，这样将使得时钟算法的时间分辨粒度较第二次机会算法高，从而取得更好的页面替换效果。
  　　时钟算法的精髓是第二次机会，其缺点也就和第二次机会算法一样：过于公平，没有考虑到不同页面调用频率的不同，有可能换出不应该或不能换出的页面，还可能造成无限循环。

• NRU（最近未被使用）算法
  　　顾名思义，NRU就是选择一个在最近一段时间内没有被访问过的页面进行替换，这是基于程序访问的时空局域性。因为根据时空局域性原理，一个最近没有被访问的页面，在随后的时间里也不太可能被访问，而NRU的实现方式就是利用页面的访问和修改位。
  　　每个页面都有一个访问位和一个修改位，凡是对页面进行读写操作时，访问位被设置为1。当进程对页面进行读写操作时，修改位设置为1。根据这两个位的状态来对页面进行分类的话，可以分成以下四种页面类型：1、2、3、4.
  　　
  　　有了这个分类，NRU算法就按照这四类页面的顺序依次寻找可以替换的页面。如果所有页面皆被访问和修改过，那也只能从中替换掉一个页面，因此NRU算法总是会终结的。
  　　当然，这种分类比较笼统，在同一类页面里，我们没有办法分辨出哪一类被访问的时间更近一些。即在某些情况下，我们替换的可能并不是最近没有被使用的页面。

• LRU（最近最少使用）算法
  　　与NRU算法相比，LRU算法不仅考虑最近是否用过，还要考虑最近使用的频率。这里是基于过去的数据预测未来：如果一个页面被访问的频率低，那么以后很可能也用不到。
  　　LRU算法的实现必须以某种方式记录每个页面被访问的次数，这是个相当大的工作量。最简单的方式就是在页表的记录项里增加一个计数域，一个页面被访问一次，这个计数器的值就增加1。于是，当需要更换页面时，只需要找到计数域值最小的页面替换即可，该页面即是最近最少使用的页面。另一种简单实现方式就是用一个链表将所有页面链接起来，最近被使用的页面在链表头，最近未被使用的放在链表尾。在每次页面访问时对这个链表进行更新，使其保持最近被使用的页面在链表头。
  　　LRU算法虽然很好，但是实现成本高（需要分辨出不同页面中哪个页面时最近最少使用的），并且时间代价大（每次页面访问发生时都需要更新记录）。因此，一般的商业操作系统都没有采纳LRU页面更新算法。

• 工作集算法
  　　由于不可能精确地确定那个页面是最近最少使用的，那就干脆不花费这个力气，只维持少量的信息使得我们选出的替换页面不太可能是马上又会使用的页面即可。这种少量的信息就是工作集信息。
  　　工作集概念来源于程序访问的时空局限性，即在一段时间内，程序访问的页面将局限在一组页面集合上。例如，最近k次访问均发生在某m个页面上，那么m就是参数为k时的工作集。我们用w(k,t)来表示在时间t时k次访问所涉及的页面数量。
  　　显然，随着k的增长，w(k,t)的值也随之增长；但是当k增长到某个数值之后，w(k,t)的值将增长极其缓慢甚至接近停滞，并维持一段时间的稳定，如下图所示：
  　　
  　　由上图可以看出，如果一个程序在内存里面的页面数与其工作集大小相等或者超过工作集，则该程序可在一段时间内不会发生缺页中断。如果其在内存的页面数小于工作集，则发生缺页中断的频率将增加，甚至发生内存抖动。
  　　因此，工作计算法的目标就是维持当前的工作集的页面在物理内存里面。每次页面更换时，寻找一个不属于当前工作集的页面替换即可。这样，我们再寻找页面时只需要将页面分离为两大类即可：当前工作集内页面和当前工作集外页面。如此，只要找到一个飞当前工作集的页面，将其替换即可。
  　　工作集算法的优点：实现简单，只需要在页表的每个记录增加一个虚拟时间域即可。而且，这个时间域不是每次发生访问时都需要更新，而是在需要更换页面时，页面更换算法对其进行修改，因此时间成本也不大。
  　　工作集算法的缺点：每次扫描页面进行替换时，有可能需要扫描整个页表。然而，并不是所有页面都内存里，因此扫描过程中的一大部分时间将是无用功。另外，由于其数据结构是线性的，会造成每次都按同样的顺序进行扫描，显得不太公平。

• 工作集时钟算法
  　　鉴于工作集算法的缺点，先驱们将工作集算法与时钟算法结合起来，设计出了工作集时钟算法，即使用工作集算法的原理，但是将页面的扫描顺序按照时钟的形式组织起来。这样每次需要替换页面时，从指针指向的页面开始扫描，从而达到更加公平的状态。而且，按时钟组织的页面只是在内存里面的页面，在内存外的页面不放在时钟圈里，从而提高实现效率。
  　　鉴于其时间与空间上的优势，工作集时钟算法被大多商业操作系统所采纳。

参考

[1] https://chyyuu.gitbooks.io/ucorebook/content/zh/chapter-3/swap_algors.html
[2] http://www.cnblogs.com/edisonchou/p/5094066.html

页面置换算法