写点什么

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

用户头像
胧月
关注
发布于: 28 分钟前

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


但内存资源是有限的,随着系统中运行的进程越来越多,系统中可用的内存就会越来越少。那么,当可用内存不足时,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 函数完成,如下图所示:


另外,处于 活跃链表 的内存页也有衰退的过程,衰退过程如下:

  • 如果内存页的 PG_referenced 标志位为 1,那么衰退过程将会把此内存页的 PG_referenced 标志位设置为 0。

  • 如果内存页的 PG_referenced 标志位为 0,那么衰退过程将会把此内存页移动到 非活跃链表 中。

上述过程是由 shrink_active_list 函数完成,如下图所示:


2. LRU 算法状态流转

我们最后以一张状态流转图来描述 LRU 算法的过程:


三、总结

本文主要介绍了 Linux 内核内存回收过程中使用的 LRU 算法的原理,在下一篇文章中,我们将会介绍 Linux 内核是如何实现内存回收的,有兴趣的敬请期待。


来源:https://mp.weixin.qq.com/s/lf5xDoQzlgnKVwNZjOHlmg

用户头像

胧月

关注

还未添加个人签名 2021.08.17 加入

还未添加个人简介

评论

发布
暂无评论
图解 | Linux内存回收之LRU算法