Linux内核页交换算法：内存管理的智慧密码

在当今数字化时代，随着软件应用的不断发展和功能的日益强大，它们对内存的需求也在持续攀升。无论是运行大型数据库管理系统、进行复杂的数据分析和人工智能模型训练，还是畅玩精美的 3A 游戏，内存的重要性愈发凸显。就拿一款热门的 3A 游戏来说，在高画质和高分辨率的设置下，其运行时所占用的内存轻松就能达到十几 GB。而对于那些进行大数据分析的专业软件，在处理海量数据时，对内存的渴望更是强烈，几十 GB 的内存占用也并不罕见。

在 Linux 操作系统中，内存管理是一项至关重要的任务，而其中的页交换算法则是内存管理的核心关键。它就像是一位精明的管家，在物理内存资源有限的情况下，巧妙地协调内存的使用，确保系统能够高效稳定地运行。当系统内存紧张时，页交换算法能够精准地决定哪些内存页面需要被暂时转移到磁盘的交换空间中，以便为更急需内存的程序腾出空间。而当这些被转移的页面再次被需要时，它又能迅速将其从交换空间中取回，重新加载到物理内存里。

页交换算法的优劣，直接关系到整个系统的性能表现。一个高效的页交换算法，能够让系统在内存紧张的情况下依然保持流畅的运行，大大减少程序的卡顿现象，提升用户的使用体验。相反，如果页交换算法不够理想，系统可能会频繁地进行页面交换操作，导致磁盘 I/O 负载过高，进而使系统运行变得迟缓，甚至出现死机的情况。在服务器环境中，这可能会导致服务中断，给企业带来严重的损失；在个人电脑上，也会让用户感到烦躁和不满。那么，Linux 内核中的页交换算法究竟是如何工作的呢？它又有着怎样的奥秘和独特之处？接下来，就让我们一同深入探索 Linux 内核页交换算法的奇妙世界，揭开它神秘的面纱。

一、页交换算法概述

在Linux操作系统中，当内存充足时，内核会尽量多地使用内存作为文件缓存（page cache）， 从而提高系统的性能。文件缓存页面会添加到文件类型的LRU链表中；当内存紧张时，文件缓存页面会被丢弃，或者把修改的文件缓存页面回写到存储设备中，与块设备同步之后便可释放出物理内存。现在的应用程序转向内存密集型，无论系统中有多少物理内存都是不够用的，因此Linux操作系统会使用存储设备作为交换分区，内核将很少使用的内存换出到交换分区，以便释放出物理内存，这个机制称为页交换（swapping），这些处理机制统称为页面回收（page reclaim）。

在最近几十年操作系统的发展过程中，出现了很多页面交换算法，其中每个算法都有各自的优点和缺点。Linux内核中采用的页交换算法主要是经典LRU链表算法和第二次机会（second chance）法。

(1)页面置换过程——页面置换的工作流程如图所示，主要包括以下4个步骤：

(2)页面走向

置换算法的好坏直接影响系统的性能。若采用的置换算法不合适，可能出现这样的现象：刚被换出的页，很快又被访问，为把它调入而换出另一页，之后又访问刚被换出的页，……如此频繁地更换页面，以致系统的大部分时间花费在页面的调度和传输上。此时，系统好像很忙，但实际效率却很低。这种现象称为“抖动”。

好的页面置换算法能够适当降低页面更换频率（减少缺页率），尽量避免系统“抖动”。

为评价一个算法的优劣，可将该算法应用于一个特定的存储访问序列（也叫页面走向）上，并且计算缺页数量。

二、Linux 内存管理基础

2.1内存管理的重要性

内存管理，作为操作系统的关键核心功能，对于系统的稳定高效运行而言，有着举足轻重的意义，其主要任务涵盖内存分配、回收、保护等多个重要方面。

在内存分配方面，当一个新的程序启动时，操作系统需要为其精准地分配足够的内存空间，以确保程序能够顺利加载并运行。这就好比在一座大型写字楼里，为每一家新入驻的公司合理分配办公场地，让它们能够正常开展业务。如果内存分配不合理，比如分配的内存过小，程序可能无法完整加载，导致运行出错；而分配过大，则会造成内存资源的浪费，就像给一家小型创业公司分配了一个超大的办公区域，却有大量空间闲置。

内存回收同样不可或缺。当程序运行结束或者不再需要某些内存空间时，操作系统必须及时将这些内存回收，以便重新分配给其他有需求的程序。这类似于写字楼里的公司退租后，物业要及时清理场地，重新出租给新的租户。若内存回收不及时，就会出现内存泄漏的问题，随着时间的推移，系统可用内存会越来越少，最终导致系统性能严重下降，甚至崩溃。

内存保护则是保障系统安全稳定运行的重要防线。它能防止不同程序之间的内存相互干扰和非法访问，确保每个程序只能在自己被分配的内存空间内进行操作。这就如同写字楼里的每家公司都有自己独立的办公区域，彼此之间不能随意闯入和破坏，保证了各个公司的正常运作和数据安全。如果没有内存保护机制，一个恶意程序可能会随意修改其他程序的内存数据，导致其他程序运行出错，甚至整个系统瘫痪。

2.2Linux 内存管理的特点

与其他操作系统相比，Linux 内存管理在灵活性、高效性和对硬件的适应性等方面展现出了显著的特点 。

Linux 内存管理的灵活性体现在多个方面。它支持多种内存分配策略，能够根据不同的应用场景和需求，选择最合适的分配方式。在一些对内存使用效率要求极高的科学计算应用中，Linux 可以采用特定的内存分配策略，减少内存碎片的产生，提高内存的利用率。同时，Linux 还允许用户根据自己的需求对内存管理进行定制和优化，用户可以通过修改内核参数等方式，调整内存管理的行为，以满足特定的业务需求。

高效性也是 Linux 内存管理的一大亮点。它采用了先进的内存管理算法，能够快速地进行内存分配和回收操作，减少系统的开销。在处理大量并发进程时，Linux 的内存管理系统能够迅速为每个进程分配所需的内存，并且在进程结束后及时回收内存，使得系统能够高效地处理多任务。Linux 还通过内存缓存等技术，提高了数据的访问速度，进一步提升了系统的整体性能。例如，它会将经常访问的数据缓存到内存中，当再次访问这些数据时，就可以直接从内存中读取，而无需从速度较慢的磁盘中读取，大大提高了数据的读取效率。

Linux 内存管理对硬件的适应性也非常出色，它能够很好地支持各种不同类型的硬件平台，无论是常见的 x86 架构，还是 ARM、PowerPC 等架构，Linux 都能充分发挥硬件的性能优势，实现高效的内存管理。在嵌入式设备中，由于硬件资源有限，Linux 可以根据设备的具体硬件配置，灵活地调整内存管理策略，确保系统在有限的内存条件下稳定运行。对于具有不同内存大小和特性的硬件，Linux 能够自动识别并进行优化，以达到最佳的内存使用效果。

2.3页交换算法原理

页交换算法的设计和实现，紧密依赖于局部性原理。局部性原理包含时间局部性和空间局部性两个重要方面 。

时间局部性指的是，在程序运行过程中，如果一个数据项在某个时刻被访问，那么在不久的将来，它很可能会再次被访问。例如，在一个循环结构的程序中，循环变量会在每次循环时被频繁访问，这就体现了时间局部性。假设一个程序中有一个循环，用于计算数组中所有元素的总和，循环变量 i 在每次循环中都会被访问，而且在整个循环执行期间，i 会被多次重复访问，这就是时间局部性的典型表现。

空间局部性则是说，如果一个数据项的地址被访问，那么与它在空间位置上临近的数据项的地址，很可能也会在不久之后被访问。这是因为程序在访问内存时，通常会按照一定的顺序进行。比如，在访问一个数组时，程序会依次访问数组中的各个元素，这些元素在内存中是连续存储的，访问了一个元素后，下一个被访问的元素大概率是与之相邻的元素，这体现了空间局部性。例如，有一个包含 100 个整数的数组，当程序访问数组的第 5 个元素时，接下来很可能会访问第 6 个、第 7 个等相邻的元素。

基于局部性原理，页交换算法在选择置换页面时，会重点关注页面的访问频率和访问时间。对于那些长时间没有被访问，或者访问频率极低的页面，算法会认为它们在未来一段时间内被访问的可能性也较小，从而将这些页面作为优先置换的对象。这样，就可以确保物理内存中始终保留着那些最有可能被频繁访问的页面，提高内存的使用效率，减少页面置换的次数，进而提升系统的整体性能。如果一个程序在运行过程中，某个页面已经很长时间没有被访问了，根据局部性原理，这个页面在未来短时间内被访问的概率相对较低，页交换算法就会考虑将这个页面置换到磁盘交换分区，为更需要内存的页面腾出空间 。

三、最佳置换算法（OPT）

最佳置换算法，其所选择的被淘汰的页面将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。采用最佳置换算法通常可保证最低的缺页率。但是人们目前还无法与之，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但是可以利用该算法取评价其他的算法。

(1)算法思想

举例如下：

我们将页面队列存在一个Vector动态数组中。我们可以从图中得知：当发生页面置换时，就要寻找在未来最长时间内不再被访问的页面，将其置换出去，比如当内存中存在的页面为 7、0、1,且要访问页面2时，此时我们要寻找页面队列中将要访问到的页面2以后的页面队列（0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1）中，页面7、0、1哪个最久未被访问到，即寻找页面7、0、1在以后的队列中第一次出现的这三个页面的下标值最大的那一个。因为页面7在后面的页面队列中再次被访问到是数组中下标为17的地方,页面0再次被访问到是数组下标为4的地方，页面1再次被访问的是数组中下标为13,所以页面7是未来最久才被访问的页面，所以将页面7置换出去，将页面2调入内存中。

具体算法：每个页面都有两个属性，一个是页面号id，一个是时间参数count（此属性在LRU中才会用到）

运行结果截图：

四、先进先出法(FINO)

页面替换算法是操作系统中用于解决内存不足的问题的一种算法。在实现时，可将内存在等大块，称作页面，将进程所需的内存也分成等大的块，即页，当进程访问一个新页时，若内存已满，则需要选择一个已驻留的页，将其后备存储设备中的内容读入内存中，以使新页能够进入内存。页面替换算法中的「组 2」指的是先进先出算法（FIFO）。

这是最简单的页面替换算法。在该算法中，操作系统跟踪队列中内存中的所有页面，最旧的页面在队列的前面。当一个页面需要被替换时，队列前面的页面被选中进行删除。

示例-1。考虑页面引用字符串1、3、0、3、5、6 和 3 页槽。

最初所有的槽都是空的，所以当 1、3、0 到来时，它们被分配到空槽——> 3页错误。 当 3 出现时，它已经在内存中，所以 —> 0 Page Faults。然后是 5，它在内存中不可用，因此它替换了最旧的页槽，即 1。—>1页错误。 最后是 6，它在内存中也不可用，因此它替换了最旧的页槽，即 3 —>1页错误。

(1)算法实现

FIFO 算法简单易懂，实现方便。它基于队列数据结构来实现，将最先进入队列的页面置换出去，以便腾出空间给新页面使用。这里给出 FIFO 页面替换算法的示例代码

这个示例使用了一个队列来模拟内存中的页面帧，当队列未满时直接插入页面，当队列已满时进行页面替换。每次发生页面错误（即访问不在内存中的页面）时，计数器增加。最后输出总的页面错误次数。

(2)算法分析

FIFO 页面替换算法的优点是简单易懂，实现方便。它不需要对进程访问的页面做特定的访问规划，因此适用于任何进程。另外，由于 FIFO 算法严格按照页面进入内存的顺序进行替换，所以可以保证每个页面的等待时间相同，避免了某些页面总是被替换的问题。

然而，FIFO 页面替换算法也存在明显的缺陷。由于该算法只关注页面进入内存的时间，而未考虑各页面的重要性和使用频率，因此会导致某些频繁使用的页面被不必要地替换出去，从而降低系统的性能。此外，FIFO 算法还容易受到局部性原理的影响，即刚刚被访问的页面很可能很快再次被访问，但由于 FIFO 算法只考虑页面进入内存的时间，因此可能导致这些重要页面被替换出去。

五、经典LRU链表算法

LRU是Least Recently Used的缩写，意为最近最少使用。根据局部性原理，LRU假定最近不使用的页面在较短的时间内也不会频繁使用。在内存不足时，这些页面将成为被换出的候选者。内核使用双向链表来定义LRU链表，并且根据页面的类型将LRU链表分为LRU_ANON和LRU_FILE。每种类型根据页面的活跃性分为活跃LRU链表和不活跃LRU链表，所以内核中一共有如下5个LRU链表：

LRU链表之所以要分成这样，是因为当内存紧缺时总是优先换出文件映射的文件缓存页面 （LRU_FILE链表中的页面），而不是匿名页面。因为大多数情况下，文件缓存页面不需要被回写到磁盘，除非页面内容修改了（称为脏页），而匿名页面总是要在写入交换分区之后，才能被换出。LRU链表按照内存节点配置，也就是说，每个内存节点中都有一整套LRU链表，因此内存节点的描述符数据结构（pglist_data）中有一个成员lruvec指向这些链表。枚举类型变量lru_list 列举出上述各种LRU链表的类型，lruvec数据结构中定义了上述各种LRU类型的链表：

万事从图说起，经典LRU链表算法如下图所示：

为了使读者有更真切的理解，下文将根据流程图围绕源代码进行讲解这个过程：

将页面加入 LRU 链表：

lru_to_page(&lru_list)和list_del(&page->lru)函数的组合用于从LRU链表中获取页面。其中，lru_to_page()的实现如下：

lru_to_page()使用了(head)->prev，表示从链表的末尾获取页面。因此，LRU链表实现了 FIFO算法。最先进入LRU链表的页面在LRU中的时间会越长，老化时间也越长。

在系统执行过程中，页面总是在活跃LRU链表和不活跃LRU链表之间转移，不是每次访问内存页面都会发生这种转移，而是发生的时间间隔比较长。随着时间的推移，这会导致—种热平衡，最不常用的页面将慢慢移动到不活跃LRU链表的末尾，这些页面正是页面回收中最合适的候选者。

六、时钟置换算法

时钟置换算法可以认为是一种最近未使用算法，即逐出的页面都是最近没有使用的那个。我们给每一个页面设置一个标记位u，u=1表示最近有使用u=0则表示该页面最近没有被使用，应该被逐出。

按照1-2-3-4的顺序访问页面，则缓冲池会以这样的一种顺序被填满：

注意中间的指针，就像是时钟的指针一样在移动，这样的访问结束后，缓冲池里现在已经被填满了，此时如果要按照1-5的顺序访问，那么在访问1的时候是可以直接命中缓存返回的，但是访问5的时候，因为缓冲池已经满了，所以要进行一次逐出操作，其操作示意图如下：

最初要经过一轮遍历，每次遍历到一个节点发现u=1的，将该标记位置为0，然后遍历下一个页面，一轮遍历完后，发现没有可以被逐出的页面，则进行下一轮遍历，这次遍历之后发现原先1号页面的标记位u=0，则将该页面逐出，置换为页面5，并将指针指向下一个页面。假设我们接下来会访问2号页面，那么可以直接命中指针指向的页面，并将这个页面的标记为u置为1。<br />但是考虑一个问题，数据库里逐出的页面是要写回磁盘的，这是一个很昂贵的操作，因此我们应该优先考虑逐出那些没有被修改的页面，这样可以降低IO。因此在时钟置换算法的基础上可以做一个改进，就是增加一个标记为m，修改过标记为1，没有修改过则标记为0。那么u和m组成了一个元组，有四种可能，其被逐出的优先顺序也不一样：