[架构之路-188]-《软考-系统分析师》-3-操作系统 - 图解页面替换算法LRU、LFU

前言：

LRU、LFU是两种容易混淆的替换算法。本文就是探讨这个问题。

替换算法的本质是：在岗位总数不变的情况，来了一个新人，如何淘汰掉一个老人的算法。

看似是计算机的问题，实际上是一个非常现实的职场问题。

替换算法的基本思想：时间局部性和空间局部性原理，用过去、现在推测未来！！！

FIFO：保护的是新员工，淘汰的工龄最大的员工，对新员工最有利，对老员工不利。

LFU：保护的是历史功劳最大，淘汰的是功劳最小，对老员工有利，对新员工不利。

LRU：保护的是最近贡献最大，淘汰的是最近贡献最小的，对最近最忙的员工有利，对历史贡献大和搞预研的人不利。

无论是cache的替换算法，还是Web页面的替换算法，本质是都是新人淘汰旧人的算法。

一、内存置换算法的缘由

计算机的运行的程序和数据保存在内存中，内存的空间是有限的，所运行的程序可能需要新的数据，而数据不在内存，在磁盘(硬盘)中。 CPU 访问的页面在物理内存时，便会产生一个缺页中断，请求操作系统将所缺页调入到物理内存。

对于要新加载到内存的页面，需要一定的算法来确定把哪些页面剔除出去给新的要加进来的页面让位，之所以需要算法，就是因为内存资源是有限的。所以，页面置换算法的功能是，当出现缺页异常，需调入新页面而内存已满时，选择被置换的物理页面，也就是说选择⼀个物理页面换出到磁盘，然后把需要访问的页面换入到物理页。

那其算法目标则是，尽可能减少页面的换入换出的次数，常见的页面置换算法有如下几种【1】：

•     最佳页面置换算法（OPT）
  

•     先进先出置换算法（FIFO）
  

•     最近最久未使用的置换算法（LRU）
  

•     时钟页面置换算法（Lock）
  

•     最不常用置换算法（LFU）
  

备注：

替换算法的本质：替换掉未来最不可能使用的页面。

然而，未来还发生，因此，算法的本质是：****用过去的经验推测未来！！！

二、算法详解

2.1 最佳页面置换算法（OPT） =》 理论上的最优，实际无法保证

最佳页面置换算法基本思路是，置换在「未来」最⻓时间不访问的页面。所以，该算法实现需要计算内存中每个逻辑页面的「下⼀次」访问时间，然后比较，选择未来最长时间不访问的页面。我们举个例⼦，假设⼀开始有 3 个空闲的物理页，然后有请求的页面序列，那它的置换过程如下图【图源自小林coding】：

在这个请求的页面序列中，缺页共发生了 7 次（空闲页换入 3 次 + 最优页面置换 4 次），页面置换共发生了 4 次。

第1次：7号页面，使用空闲页面替换。

第2次：0号页面，使用空闲页面替换。

第3次：1号页面，使用空闲页面替换。

第4次：2号页面，替换掉7号页面

第5次：0号页面，不需要替换，命中。

这很理想，但是实际系统中无法实现，因为程序访问页面时是动态的，我们是无法预知每个页面在「下⼀次」访问前的等待时间。所以，最佳页面置换算法作用是为了衡量你的算法的效率，你的算法效率越接近该算法的效率，那么说明你的算法是高效的。

2.2 先进先出置换算法（FIFO）-- 按加载时间/最早访问时间排序

FIFO算法的本质：淘汰掉年龄最大的，不管是过去和当下的贡献值，也不管未来是否能做贡献。

FIFO算法的核心思想是：年龄越大，未来的潜力越小！（虽然这不一定对）

年龄记录：按照加载的先后顺序排序，它保护的是最年轻的人 。

很显然，FIFO算法很不合理！！！

既然我们⽆法预知页面在下⼀次访问前所需的等待时间，那我们可以选择在内存驻留时间最长，或或者说，加载到内存中最早的（有可能反复使用）的页面进行中置换，这个就是「先进先出置换」算法的思想。还是以前⾯的请求的⻚⾯序列作为例子，假设使用先进先出出置换算法，则过程如下图：

在这个请求的页面序列中，缺页共发生了 10 次，页面置换共发⽣了 7 次，跟最佳页面置换算法比较起来，性能明显差了很多。

这是因为，先进入的页面，不代表该页面未来就再使用，很有可能，某个页面，虽然最先加载到内存中，但会被频繁使用，如果把这种未来频繁使用的页面替换出去，就导致性能的下降。

最理想的情况就是替换到，为了可能不会使用或未来使用次数最少的页面。

2.3 最近最久未使用的置换算法（LRU）-- 按最后一次访问时间排序

LRU算法的本质是：淘汰掉最近（Recently）最空闲，没事干的那个人，不管他未来是否有事干。

LRU算法的核心思想是：最近最闲，意味着未来可能也是最闲，最没有价值。

空闲值计算方法：每命中一次，空闲值-1， 没有命中，空闲值+1，它保护过去最近最忙的人，对历史贡献大的人是不友好的，因为，随着时间的推移，历史贡献大的人，贡献值会抵消（空闲一次，空闲值-1），最近（Recently），叠加了时间的因素，对于过去功劳大，最近没有贡献的老员工是不利的。

    最近最久未使用（LRU）的置换算法的基本思路是，**发生缺页时**，选择**最长时间没有被访问**的页面进行置 换，也就是说，该算法假设：**已经很久没有使用的页面很有可能在未来较长的⼀段时间内仍然不会被使用**。

    这种算法近似最优置换算法，最优置换算法是通过「未来」的使用情况来推测要淘汰的页面，而 LRU 则是 通过**「历史」的使用情况**来推测要淘汰的页面。 还是以前⾯的请求的页面序列作为例子，假设使用最近最久未使用的置换算法，则过程如下图：

在这个请求的页面序列中，缺页共发⽣了 9 次，页面置换共发⽣了 6 次，跟先进先出置换算法⽐较起 来，性能提高了⼀些。

虽然 LRU 在理论上是可以实现的，但代价很高。为了完全实现 LRU，需要在内存中维护⼀个所有页面的 链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。 困难的是，在每次访问内存时都必须要更新「整个链表」。在链表中找到⼀个页面，删除它，然后把它移 动到表头是⼀个⾮常费时的操作。

所以，LRU 虽然看上去不错，但是由于开销比较大，实际应用中比较少使用。

2.4 时钟页面置换算法（Lock）

时钟页面置换算法就可以两者兼得，它跟 LRU 近似，又是对 FIFO 的⼀种改进。

该算法的思路是，把所有的页面都保存在⼀个类似钟面的「环形链表」中，⼀个表针指向最老的页面。 当发生缺页中断时，算法首先检查表针指向的页面： 如果它的访问位位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移⼀个位置； 如果访问位是 1 就清除访问位，并把表针前移⼀个位置，重复这个过程直到找到了⼀个访问位为 0 的 页面为止；

2.5 最不频繁使用算法（LFU）=》 访问/命中次数排序

LFU算法的本质：替换掉贡献最小的那个人

LFU核心思想是：过去贡献最小，未来可能贡献最小。

衡量贡献大小的方法：每命中（使用）一次，贡献值+1，它保护的是贡献最大的人，贡献大不受时间推移的影响和消耗，但对不忙的人，没有考量。

    最不常用（LFU）算法，这名字听起来很调皮，但是它的意思不是指这个**算法不常用**，而是当发生缺页中 断时，选择**「访问次数」最少的那个页面，并将其淘汰**。

它的实现方式是，对每个页面设置⼀个「访问计数器」，每当⼀个页面被访问时，该页面的访问计数器就累加 1。在发生缺页中断时，淘汰计数器值最小的那个页面。

看起来很简单，每个页面加⼀个计数器就可以实现了，但是在操作系统中实现的时候，我们需要考虑效率和硬件成本的。 要增加⼀个计数器来实现，这个硬件成本是比较高的.

另外如果要对这个计数器查找哪个页面访问次数最 小，查找链表本身，如果链表长度很大，是非常耗时的，效率不高。

但还有个问题，LFU 算法只考虑了频率问题，没考虑时间的问题，比如有些页面在过去时间里访问的频率很高，但是现在已经没有访问了，而当前频繁访问的页面由于没有这些页面访问的次数高，在发生缺页中 断时，就会可能会误伤当前刚开始频繁访问，但访问次数还不高的页面。 那这个问题的解决的办法还是有的，可以定期减少访问的次数，比如当发生时间中断时，把过去时间访问的页面的访问次数除以 2，也就说，随着时间的流失，以前的高访问次数的页面会慢慢减少，相当于加大 了被置换的概率。

缺点：

过去访问多的页面，不代表未来访问次数越多，比如循环结束后的页面，未来很有可能就不再访问了。