图解 | Linux内存回收之LRU算法

发表于 3年以前 | 总阅读数：295 次

内存 是操作系统非常重要的资源，操作系统要运行一个程序，必须先把程序代码段的指令和数据段的变量从硬盘加载到内存中，然后才能被运行。如下图所示：

但内存资源是有限的，随着系统中运行的进程越来越多，系统中可用的内存就会越来越少。那么，当可用内存不足时，Linux 内核是怎么处理的呢？

本文将会介绍，当可用内存不足时，Linux 内核的处理方式。

一、内存不足的处理方式

我们思考一下，当系统的可用内存不足时，进程继续申请内存会发生什么事情？

当系统的可用内存不足时，内核为了保证进程有足够的内存可用，将会对内存进行回收工作。内存回收工作主要包括以下几个步骤：

内核为了加速某些操作（如文件 I/O），会对操作的结果进行缓存（如文件页缓存），而缓存使用的内存是可以被回收的。所以，当可用内存不足时，首先会回收内核中的缓存。
如果回收内核缓存后，系统的可用内存仍然处于不足。那么，内核将会触发 swap 机制。swap 机制会将某些进程所占用的内存交换（写入）到硬盘中，然后释放这些内存，从而让系统有更多可用的内存。本文将会重点介绍 swap 机制。
如果触发 swap 机制后，系统的可用内存仍不能满足系统需求，那么将会触发 OOM（Out Of Memory） 机制。OOM 机制将会挑选一些进程，然后将这些进程杀死来，从而获取更多可用内存。

由于回收内存的方式有三种，所以本文重点以 swap 机制作为分析对象，来介绍当内存不足时，内核是怎么进行内存回收工作的。

二、swap机制原理

在分析 swap 机制的实现前，我们先来介绍一下 swap 机制的原理。

本文使用 Linux-2.6.23 版本内核。

swap 这个单词是 交换 的意思，顾名思义就是把某些进程所占用的内存交换（写入）到硬盘，然后把内存释放给操作系统，这样操作系统就有更多可用的内存。如下图所示：

由于 swap 机制的本质是将进程所占用的内存写入到硬盘中，然后释放这些内存。那么，就涉及到应该将哪些进程的内存交换到硬盘中。

每个进程都不希望自己占用的内存被交换到硬盘中，因为内存被交换到硬盘后，如果进程要使用到这些内存时，必须先将这些内存从硬盘中加载到内存中，才能继续使用，这样进程的性能将会大打折扣。正因为这个原因，内核必须提供一种最优的方案来挑选一些内存交换到硬盘，并且对进程性能的影响降到最小。

由于进程的内存空间分为多个段，如 代码段、数据段、mmap段、堆段 和 栈段 等。那么，哪些段的内存会被交换到硬盘中呢？

答案就是：所有段的内存都有可能交换到硬盘。不过对于 代码段 和 mmap段 这些与文件有映射关系的内存区，只需要将数据写回到文件即可（由于代码段的内容不会改变，所以不用进行回写）。

而对于 数据段、堆段 和 栈段 这些段中的内存页，由于没有与文件进行映射（称为 匿名内存页），所以内核必须提供一个文件（或硬盘分区）来存储这些内存页的数据，这个文件（或硬盘分区）被称为 交换分区。

从上面的分析可以得出两个重要的信息：

匿名内存页：没有与任何文件进行映射的内存页。
交换分区：用于存储匿名内存页数据的文件或硬盘分区。

下面主要介绍当系统内存不足时，内核是怎样将进程的 匿名内存页 写入到 交换分区 中，并且回收这些 匿名内存页 的。

1. LRU 内存淘汰算法

当系统内存不足，并且触发 swap机制 时，内核应该选择哪些 匿名内存页 写入到 交换分区 中呢？如果随机选择一些 匿名内存页 写入到 交换分区，就有可能出现如下问题：

把某个进程的 匿名内存页 写入到 交换分区 后，进程又马上访问这个内存页，从而又要把这个内存页从 交换分区 中读入到内存中。这样只会增加系统的负荷，并且不能解决系统内存不足的问题。

为了解决这个问题，Linux 内核引入了 LRU内存淘汰算法，用过 Memcached 或者 Redis 的同学应该都了解过 LRU算法。当系统内存不足时，Memcached 和 Redis 都是使用 LRU算法 来淘汰内存的。

LRU（Least Recently Used） 中文翻译是 最近最少使用 的意思，其原理就是：当内存不足时，淘汰系统中最少使用的内存，这样对系统性能的损耗是最小的。

为了实现 LRU算法，内核维护了两个双向链表：active_list 和 inactive_list。下面介绍下这两个链表的作用：

active_list：活跃内存页链表。也就是说进程会经常访问这个链表中的内存页，所以进行内存淘汰时，不应该淘汰这个链表中的内存页。
inactive_list：不活跃内存页链表。也就是说进程很少会访问这个链表中的内存页，所以进行内存淘汰时，主要淘汰这个链表中的内存页。

在 Linux 内核中，每个 内存区(zone) 都会维护着一个 active_list 和一个 inactive_list。内存区 是内存管理中的一个对象，为了描述更加清晰，我们暂时当成内核中只有一个内存区，也就是说暂时认为内核中只维护着一个 active_list 和一个 inactive_list。如下图所示：

另外，每个内存页都有个 PG_referenced 的标志位，表示此内存页是否被访问过，这个标志位在内存回收过程中起着至关重要的作用。

当某个进程申请一个匿名内存页时，内核会把这个内存页添加到 活跃内存页链表(active_list) 中，并且将 PG_referenced 标志位设置为 0。如下图所示：

而当某个匿名内存页被进程访问时，根据内存页所在的 LRU 链表作不同的操作：

如果内存页原来处于 活跃链表 中，那么就会把此内存页的 PG_referenced 设置为 1。
如果内存页原来处于 非活跃链表 中，并且 PG_referenced 为 0。那么将内存页的 PG_referenced 标志位设置为 1。
如果内存页原来处于 非活跃链表 中，并且 PG_referenced 为 1。那么将会把内存页从 非活跃链表 移动到 活跃链表，并且将 PG_referenced 设置为 0。

下图展示了上述各种情况的流转过程：

而当系统内存不足时，需要进行内存淘汰过程。内存页淘汰过程与上述过程刚好相反，下面介绍一下内存页淘汰的过程。

内存淘汰时，只能从 非活跃链表 中进行淘汰，淘汰过程如下：

从 非活跃链表 的尾部开始进行内存淘汰，如果内存页的 PG_referenced 标志位为 1 时，将跳过此内存页，并且将此内存页的 PG_referenced 标志位设置为 0。
如果内存页的 PG_referenced 标志位为 0 时，那么将此内存页写入到 交换分区 中，并且将所有与此内存页的映射解除绑定，然后释放此内存页。

上述过程是由 shrink_inactive_list 函数完成，如下图所示：