内存管理算法讲解

lilac

2024-06-12 2025-06-12 约 5221 字预计阅读 23 分钟

在 Linux 内核中，内存管理是至关重要的部分，可谓是学好Linux的必经之路。

1 CPU访问内存的过程

用图的方式来说明问题，简单直接：

蓝色部分是cpu，灰色部分是内存，白色部分就是cpu访问内存的过程，也是地址转换的过程：

TLB（Translation Lookaside Buffer）检查：
- CPU首先检查TLB，以确定是否有已缓存的虚拟地址到物理地址的映射关系。
- 如果TLB命中（TLB Hit），则直接使用TLB中的映射结果。
- 如果TLB未命中（TLB Miss），则需要进一步查找页表。
页表查找：
- 如果TLB未命中，CPU会查找页表，以确定虚拟地址对应的物理地址。
- 页表通常存储在主存中，但也可以被缓存（例如，二级TLB）。
- 如果页表中没有找到对应的映射关系（页表项不存在或无效），则触发缺页异常（Page Fault）。
缺页异常处理：
- 缺页异常由操作系统处理。
- 操作系统会：
  - 查找或分配一个空闲的物理页。
  - 将所需的数据从外存（如磁盘）加载到该物理页中。
  - 更新页表，建立虚拟地址到物理地址的映射关系。
  - 刷新TLB，将新的映射关系加入到TLB中。
- 处理完缺页异常后，CPU重新执行导致缺页的指令。
访问Cache：
- 在页表更新并刷新TLB之后，CPU再次尝试访问内存。
- 由于TLB中已经有了正确的映射关系，CPU可以正确地查找物理地址。
- CPU会检查Cache，以确定数据是否已经在Cache中。
- 如果Cache命中（Cache Hit），则直接从Cache中读取数据。
- 如果Cache未命中（Cache Miss），则从主存中读取数据，并可能将数据加载到Cache中。
主存访问：
- 如果在访问主存时，该页又被换出（例如，由于内存压力导致的操作系统页置换），确实可能再次触发缺页异常，但这种情况确实很少见。

1.1 页表查找示例

在当前主流架构中，ARM64、x86 默认使用4级页表，ARM32 在未启用 LPAE 时使用二级页表，启用 LPAE 后则使用三级页表。

我们以 x86-64 架构默认的 4级分页表为例，假设给定的虚拟地址 0x123456789ABCDEF0，如何确定物理页的最后位置？

在x86-64架构中，通常使用4级分页表，分别是：

页全局目录 (PGD, Page Global Directory)
页上层目录 (PUD, Page Upper Directory)
页中间目录 (PMD, Page Middle Directory)
页表 (PT, Page Table)

每一级表项的大小通常为8字节，每页大小是4KB（4096字节），因此每页可以存储512个表项（4096字节 / 8字节 = 512个表项）。这意味着每个表项占用9位地址空间（2^9 = 512）。虚拟地址的48位被分割成4个9位的索引（用于指向四级表）和一个12位的偏移（指向页内的具体位置）。

具体来说：

48-47位：固定为0（因为只用48位地址）
46-39位：PGD索引（9位）
38-30位：PUD索引（9位）
29-21位：PMD索引（9位）
20-12位：页表索引（9位）
11-0位：页内偏移（12位）

对于给定的虚拟地址 0x000056789ABCDEF0，我们按照上述规则进行分段：

46-39位：0x100（二进制：1000000000000，十进制：4096，但实际取0-511，这里需要取9位，即2^9 = 512个可能的值，这里应该是0x100 & 0x1FF = 0x100 = 256）
38-30位：0x150（二进制：000101010000，十进制：336）
29-21位：0x1B0（二进制：000110110000，十进制：432）
20-12位：0x2C0（二进制：001011000000，十进制：704）
11-0位：0x3F0（二进制：0000001111110000，十进制：1008）

这样我们就得到了各个索引的具体值。这些值用于在多级页表中逐层查找，直到找到最终的物理地址。具体流程如下：

根据PGD索引（256）在PGD表中找到对应的PUD表指针。
使用PUD索引（336）在找到的PUD表中找到对应的PMD表指针。
使用PMD索引（432）在找到的PMD表中找到对应的页表指针。
最后，使用页表索引（704）在页表中找到包含物理地址的表项。
最后的12位偏移（1008）用于确定物理页内的具体位置。

2 Buddy 分配算法

旨在通过将内存划分为不同大小的块来减少内存碎片并提高内存分配的效率。它通过维护多个空闲内存块列表，每个列表对应一种特定大小的块，来实现快速的内存分配和回收。

在了解分配算法前，梳理一些基本知识。如：

页框：将内存空间划分为固定且大小相等的区域，也叫物理块、内存块、页帧

2.1 页框和Buddy算法的关系

页框（Page Frame）是操作系统中内存管理的最小单位，通常大小为4 KB。Buddy算法是一种内存分配算法，用于管理空闲页框。它将空闲页框组织成不同大小的块，每个块的大小是2的幂。这些不同大小的块被组织成多个链表，每个链表中的块大小相同。

2.2 内存分配和释放过程

Buddy 算法主要用于物理内存的分配和管理，它关注的是如何在物理内存层面有效地分配和回收内存块，以减少内存碎片并提高内存利用率。

2.2.1 1. 分配内存

当一个进程请求内存时，操作系统会根据请求的大小（以页框为单位）找到合适大小的空闲块。如果找不到正好匹配的块，就找到大于请求大小的最小的块，并将其分割成两个相等的部分，并通过递归分割，直到找到合适大小的块。

2.2.1.1 示例：分配3个页框

假设初始时有一个大小为8个页框的空闲块。

初始状态：

空闲链表8：包含一个大小为8个页框的块。

分配3个页框的过程：

找到大于等于3的最小块：大小为4个页框的块（因为4是最接近3且大于3的2的幂）。
分割块：
- 将大小为8的块分割成两个大小为4的块。
- 再将其中一个大小为4的块分割成两个大小为2的块。
- 再将其中一个大小为2的块分割成两个大小为1的块。
分配内存：
- 分配3个页框（例如，使用两个大小为1的块和一个大小为2的块中的一个）。
- 剩余的空闲块包括一个大小为4的块、一个大小为2的块和一个大小为1的块。

分配后的状态：

空闲链表4：包含一个大小为4的块。
空闲链表2：包含一个大小为2的块。
空闲链表1：包含一个大小为1的块。

2.2.2 2. 释放内存

当进程释放内存时，操作系统将释放的块放回对应的空闲链表中。然后检查其伙伴块是否也为空闲，如果是，则合并这两个块成一个更大的块。

2.2.2.1 示例：释放之前分配的3个页框

假设释放的3个页框包括两个大小为1的块和一个大小为2的块中的一个。

释放过程：

将释放的页框放回对应的空闲链表：
- 如果释放的是大小为1的块，放回空闲链表1。
- 如果释放的是大小为2的块，放回空闲链表2。
检查伙伴块并合并：
- 对于每个释放的块，检查其伙伴块是否为空闲。
- 如果伙伴块也为空闲，则合并这两个块成一个更大的块，并放回更大一级的链表中。

释放后的状态：

如果释放的块能够合并，空闲链表中的块大小会增大。

2.2.3 3. 知识点补充

Buddy 算法在物理内存层面提供内存块的分配和回收功能，而虚拟内存管理则在此基础上进行抽象，为应用程序提供了一个独立的、连续的虚拟地址空间。

应用启动时，虚拟地址空间映射到的物理内存通常是连续的。操作系统通常会分配连续的物理内存来满足初始的内存需求，这样可以提高性能并简化内存管理。

应用执行过程中，频繁的 malloc 行为可能导致物理内存的不连续。Buddy 算法会尽力分配连续的内存块，但如果内存碎片化严重，可能无法找到足够大的连续空闲块，从而导致分配失败（操作系统或内存管理器可能采取其他措施，如内存回收，将某些页面换出到磁盘来释放更多的连续内存）。

2.3 内存水位

系统通常具备自动管理内存的机制，而不会全部依赖程序主动释放内存的行为。

内存水位是操作系统用来衡量可用内存的一个指标，它代表了内存的使用情况。通常可以分为高水位、低水位和紧急水位等不同级别。在不同的内存水位时，会触发不同的内存管理行为。

2.3.1 内存水位机制

高水位（high watermark）：当空闲内存高于此水位，内存充足，通常不会触发主动回收。此时，系统可能将一些不常用的页面换出到磁盘，以释放物理内存空间。这有助于防止内存资源的浪费。

低水位（low watermark）：空闲内存低于此水位时，系统会唤醒内存回收线程（如 Linux 中的 kswapd），开始异步回收内存页面。

最小水位（min watermark）：空闲内存低于此水位时，系统会进行同步内存回收，直接阻塞当前进程直到回收到足够的内存页面。

Buddy 伙伴分配算法与内存水位机制的协同工作流程，通过内存水位机制来动态调整内存回收的时机和方式，从而优化内存管理的效率和系统性能。

2.4 碎片化整理算法

在 Buddy 算法中，内存块是按照大小组织成链表的，每个链表中的内存块大小相同。当内存变得碎片化时，可能有许多小的空闲块分散在不同的链表中。

碎片整理的过程中，通过检查空闲块的伙伴是否也空闲来实现。如果两个伙伴块都空闲，它们可以合并成一个更大的块，并从较小的链表中移除，添加到更大的链表中。

2.4.1 示例

假设一段物理内存布局如下：

	碎片整理前			碎片整理后
地址	大小（页框数）	状态	内容	大小（页框数）	状态	内容
0x0000	1	已分配	数据A	1	已分配	数据A
0x0004	1	空闲	-	1	已分配	数据B
0x0008	1	已分配	数据B	1	已分配	数据C
0x000C	1	空闲	-	1	空闲	-
0x0010	1	已分配	数据C	2	空闲	-
0x0014	1	空闲	-	-	-	-

碎片整理过程

空闲链表 1（大小为 1 页框）：包含地址 0x0004、0x000C、0x0014

合并相邻空闲块

检查空闲链表，无相邻的空闲块可以合并
移动已分配块

系统判断、并决定移动的数据块，将它们集中到内存起始部分，以腾出更大的空闲空间
- 移动数据B：将数据B从0x0008移动到地址0x0004；更新所有对数据B的引用，例如进程N的内存映射
- 移动数据C：同上
更新空闲链表

移动后，重新检查空闲链表，并进行相邻空闲块合并。则得到：
- 空闲链表 1（大小为 1 页框）：包含地址 0x000C
- 空闲链表 2（大小为 2 页框）：包含地址 0x0010

注意

内存碎片整理通常只在必要时才会移动内存块，优先尝试合并相邻的空闲块，如果合并无法满足需求，才会考虑移动已分配的内存块来腾出更大的连续空闲区域。内存碎片整理涉及内存拷贝，需要将数据从一个位置复制到另一个位置，这涉及到读取源数据和写入目标位置的操作，会消耗 CPU 时间和内存带宽。

3 Slab 分配算法

Slab 分配器是一种用于管理小对象内存分配的算法，旨在减少内存碎片并提高内存分配和回收的效率。它通过缓存预分配的内存块来管理内存，特别适合用于频繁分配和释放小对象的场景。

3.1 基本概念

对象（Object）：对象是 Slab 分配器管理的基本单位，通常是用户分配的小块内存。

Slab：Slab 是一个连续的内存块，通常与一个内存页大小相同。一个 Slab 包含多个对象。

缓存（Cache）：Slab 分配器为每种类型的对象维护一个缓存。每个缓存包含多个 Slab。

当缓存首次创建时，会分配一个或多个 Slab，并将这些 Slab 中的内存划分为对象，对象大小由 kmalloc 指定。

3.2 工作原理

Slab 分配器围绕着高效性、局部性、可扩展性与灵活性设计。

高效性：通过缓存预分配的内存块，减少了频繁调用底层内存分配器的开销，提高了内存分配和释放的效率。
局部性：由于对象在物理内存上更紧凑，增强了缓存局部性和 TLB 局部性，提升了整体性能。
可扩展性：适用于多核系统，每个 CPU 可以有独立的 Slab 缓存，减少锁竞争，提升并发性能。
灵活性：允许为对象指定构造和析构函数，便于对象的初始化和清理。

3.2.1 内存分配

缓存创建：当首次为某种类型的对象分配内存时，Slab 分配器创建一个缓存。
Slab 初始化：缓存创建后，分配一个或多个 Slab 给该缓存。每个 Slab 初始化为包含多个对象。
对象分配：内存分配请求到达时，首先从缓存的空闲链表中取一个对象。如果空闲链表为空，则从 Slab 中取一个对象。

3.2.2 内存回收

对象释放：对象释放时，先检查对应的缓存是否设置了析构函数。若设置了，先执行析构函数释放资源，然后将对象加入缓存的空闲链表。
Slab 回收：当缓存中的某个 Slab 的所有对象都变为空闲时，Slab 会被回收，内存可还给伙伴系统。

3.3 示例

当用户首次调用 kmalloc(size_t size) 或类似函数，且请求的内存大小与之前创建的缓存对象大小不匹配时，内核会创建一个新的缓存。

3.3.1 初始状态

假设根据 szie 创建一个缓存 cache_foo，用于管理大小为 64 字节的对象。通常每个 Slab 大小为 4 KB（1 页框），可以容纳 64 个字节的对象。

对象个数 = 4KB / 64 Byte = 4 * 1024 Byte / 64 Byte = 64 个

缓存 cache_foo，设置对象大小为 64 字节
分配一个 Slab（4 KB）给 cache_foo。这个 Slab 被划分为 64 个字节的对象，共 64 个对象。所有对象初始时都处于空闲状态。

3.3.2 分配对象

第一次分配：进程 A 请求一个 64 字节的对象。Slab 分配器从 cache_foo 的空闲链表中取出一个对象。
第N次分配：进程 B 请求一个 64 字节的对象。从空闲链表或 Slab 中取出一个对象，如果空闲链表为空，则从 Slab 中取出一个对象。

从 Slab 中取对象流程：首先会从伙伴系统申请一个新的 Slab，随后将新申请的 Slab 划分为多个对象并初始化。将上述所有对象都添加到空闲链表中，之后从更新后的链表里取一个对象供分配。

3.3.3 回收对象

释放对象：进程 A 释放之前分配的对象。Slab 分配器调用对象的析构函数（如果设置），然后将对象加入 cache_foo 的空闲链表。
Slab 收缩：当 cache_foo 的某个 Slab 中所有对象都变为空闲时，这个 Slab 会被回收，内存可还给伙伴系统。

目录