内存管理 - Yuanyang-Lee's Blog

为什么需要内存管理？

计算机的内存被所有进程共享，但是编译器和程序员无法得知当前还有多少进程在内存中的什么地方。
内存管理的主要需求：
- 代码重定向（Code relocation）
  
  代码重定位是指将程序中的某些代码或数据从一个位置移动到另一个位置的过程。
- 保护 & 共享（Protection & Sharing）
- 使得每个进程都有自己的地址空间，便于程序员编程

虚拟内存 & 物理内存

虚拟内存（Virtual memory），也称逻辑内存（Logical memory），是给每个程序进程分配的内存，其大小由计算机寻址位数决定，对于 32 位机器而言，虚拟内存的大小为 \(2 ^ {32}\) B \(=\) \(4\) GB；对于 64 为机器而言，虚拟地址的大小为 \(2 ^ {64}\) B \(\approx\) \(4 \times 10 ^ 9\) GB，这已经满足绝大多数内存存储需求。

虚拟内存中的地址称为虚拟地址，是每个进程可以访问的地址。如下图，使用 64 位 ARM 机器编写的一个 C 语言程序，所打印的变量地址就是虚拟地址：
物理内存（Phsical memory），也称真实内存（Real memory），物理内存中的地址称为物理地址，是程序真正占用的地址，每个有效虚拟地址都会映射到与之特定的物理地址。

内存映射

由于虚拟内存是不存在的，所以我们在寻址时要根据虚拟内存找到对应的物理内存，这样的技术称为内存映射。

内存分区

内存分区（Partition Memory）是一种古老的内存映射方式，其有两个主要分类，一个是不变分区（Fixed Partitioning），另一个是动态分区（Dynamic Partitioning）。

不变分区：
- 在机器启动时间（Boot time）就将内存分为几个连续的分区，每个分区只能装载一个进程，分区大小在系统启动时确定，并在整个运行期间保持不变。
  
  如下图所示，x 表示进程已使用内存：
  
  Block 1 Block 2 Block 3 Block 4 Block 5
  
  xxxxx xx000 x0000 xxx00 x0000
  
  可见，这样简单粗暴的分区方式一是限制了每个进程内存的增长，同时产生了大量的内部碎片（Internel fragmentation），即我们可能会给一些进程预留一些不会使用到的内存。
- 硬件要求：一个基地址寄存器（Base register），基地址寄存器存储了每个进程对应物理内存的起始地址，寄存器的数据在上下文切换（Context switch）时由 OS 加载。
- 映射公式： \[ \text{Physical Address} = \text{Logical Address} + \text{Base Register} \]
动态分区
- 动态分区相对而言更加灵活，动态分区技术只在程序被加载，即操作系统创建新进程时创建分区。
- 这种按需分配的分区技术可以避免内部碎片，但是未被分配的内存会零散分布在内存中，造成外部碎片（External fragmentation），例如下图：
- 硬件要求：一个基地址寄存器，这一点和不变分区技术一致；同时还需要一个限制寄存器（Limit register），限制寄存器限制了进程内存的最大偏移量。
- 映射公式： \[ \text{Physical Address} = \text{Logical Address} + \text{Base Register} \] 保护机制： \[ \text{if}\ (\text{Physical Address} > \text{Base register} + \text{Limit register}) \implies \text{TRAP!} \] 当程序尝试访问超出其限制寄存器定义的内存段范围时，操作系统会捕获并处理异常，这就是我们常说的段错误（Segmentation fault）。

Block 1	Block 2	Block 3	Block 4	Block 5
`xxxxx`	`xx000`	`x0000`	`xxx00`	`x0000`

页 & 帧

页（Page）和帧（Frame）是现代计算机内存管理中两个重要概念，它们都是一种固定大小且相等的内存块（一般是 4 KB）。页用于指代虚拟内存，而帧用于指代物理内存。有效的页都可以映射到物理内存中的某个帧，即计算机会给每个正在运行的进程的每个页分配一个帧（不考虑多级页表）。

我们根据页查找到帧，然后根据帧号找到真实的物理内存：

页到帧的映射是如何进行的呢？接下来就引入了我们的页表。

页表 & 一级页表寻址

以 32 位操作系统为例，每个逻辑地址我们可以分成两部分：

高 20 位比特：用于表示页编号（Page number），大小从 \(0\) 到 \(2 ^ {20} - 1\)。
低 12 位比特：用于表示页偏移地址（Offset in page），大小从 \(0\) B 到 \(2 ^ {12} - 1\) B，说明每个页的大小为 \(4\) KB。

操作系统为每个进程维护了一个页表（Page table），每个页表项（PTE）如下：

高 20 位比特表示页帧编号，对应的是物理地址的帧编号，即作为物理地址的高 20 位比特。
后续几个域：
- P（Present）：一般用作有效位，即该页表项对应的帧是否在内存中。
- W（Writeable）：表示页面是否可写。
- U（User）：用于表示用户权限。
- PWT（Page Write Transparent）：用于指定页面级别的写透明策略（External cache write-through）。
- PCD（Page Cache Disabled）：是否禁用高速缓存。
- A（Accessd）：表示页面最近是否被访问过。
- D（Dirty）：页面最近是否被修改过（只用于 PTE）。
- L（Large）：指示操作系统和硬件是否使用大页面（Large Page）而不是标准的小页面（Small Page）来管理内存。

如何根据逻辑地址加页表寻址？

Paging workflow

根据逻辑地址的页编号，加上存储页表地址的寄存器存储的值就可以找到目标页编号对应的页表项；

以 x86 架构为例子，CR3（Control Register 3）用于管理分页机制。CR3寄存器主要用于存储页目录表的基地址（Page Directory Base Address），它是分页机制中的重要组成部分，用于虚拟地址到物理地址的转换。
页表项中的页帧号对应物理内存中的帧编号，加上逻辑地址的偏移值，即可映射到真实的物理地址。

这种映射方式由许多优点：

消除了外部碎片，可能还会有内部碎片，但是对于 4KB 的页面而言内部碎片不会造成多大的空间浪费；
易于实现；
易于保护和共享；
很容易分配物理内存，每次从空闲帧列表中选择一些帧进行分配即可。

空闲帧列表（List of free frames）是一个在操作系统内存管理中常见的数据结构，用于跟踪系统中哪些物理内存帧（或页面帧）当前是空闲的，可以用于分配给新的进程或任务。

于此同时也造成了一些问题：

页表太大（Page table size is too large）：

一个页表项一共 \(4\) B，页面编号一共有 \(2 ^ {20}\) 个，每个进程都要维护一个 \(4 \times 2 ^ {20}\) B \(=\) \(4\) MB 的页表，如果当前系统有 1000 个进程，则需要维护约 \(4\) GB 的页表，事实上每个进程有许多页面都是完全不使用的，造成了很大的空间浪费。
内存访问慢（Memory access is slow）：

不同于之前的内存分区技术，页面映射需要通过页表进行内存访问，这样使得访问速度大打折扣。

后文我们提及的多级页表和 TLB 技术将解决这两个问题。

页面交换 & 页面错误

页面交换

我们不难注意到，当前 64 位机器的逻辑内存远远大于实际的物理内存大小，那么当物理内存不够后，逻辑内存又是如何分配的呢？

事实上，物理内存中许多帧长期不会被使用，这样的帧操作系统会将其置换到磁盘中（这里可以类比进程的挂起），这样的技术称为页面交换（Page Swapping）。

Page Swapping

回到刚刚的问题，当物理内存不够后，又要给新的逻辑地址分配帧时，又该如何做呢？

答案是：将当前物理内存中的闲置帧转移到磁盘中，给新的帧预留位置，然后对页表进行对应的更新，如下图所示（图源：B 站）。

帧锁定（Frame Locking）

注意，不是所有帧都可以被置换到磁盘，有些特殊的帧会被锁定而无法被置换到磁盘，比如：

系统内核
I/O 缓存
...

页面错误

如果某时刻，进程需要访问某个页面，如果发现该页面对应的帧不在内存中，这个时候就会触发页面错误（Page fault）。至于这个页面是否在内存中，由前文提到的 PTE 中的比特位「P」决定。

页面错误主要有两种：

Major Page Fault（主要页面错误）

进程尝试访问虚拟内存中的页面，但该页面尚未在物理内存中。一般是我们在上文提到的已加载的页面因为换出到磁盘而不再在物理内存中。
Minor Page Fault（次要页面错误）

次要页面错误是发生在虚拟内存系统中的一种事件。当一个进程尝试访问当前不在其转换后备缓冲器（TLB，这个一会会讲）中但实际上已经加载到物理内存中的页时，就会发生轻微页面错误。换句话说，这意味着所需的数据是在内存中的，只是没有在快速查找的硬件缓存中记录。

这里我们说说主要页面错误的处理流程：

处理器读取到进程访问逻辑地址的请求，将地址传送至内存管理单元（MMU，Memory Management Unit），通过页面编号找到对应的页表项，通过其判断位「P」为 0，说明其对应物理帧不在内存中，触发了一个页面错误；
接着将信息传达给操作系统的页面错误处理器，从磁盘找到对应的物理帧；
找到对应帧后，将数据加载到内存中；
更新对应的页表项；

完成上述步骤后，页面错误处理器通知调度器，重新进行调度。

常规保护错误（GPF）

常规保护错误（General Protection Fault）是一种计算机硬件或操作系统的错误，它表示发生了一种无法处理的保护性异常。通常情况下，GPF 会导致程序崩溃，操作系统终止程序的执行，并通常会生成错误报告以记录问题。

如果是用户级进程触发 GPF，则操作系统会将该进程 kill，如果是内核级的进程，则可能导致系统崩溃而重启。

GPF

多级页表

前文我们提到，如果使用一级页表结构，则每个进程都要维护一个包含大约 100 万个 PTE 的页表，十分占用空间。为了解决这个问题，现代操作系统中一般使用多级页表结构。

二级页表

二级页表引入了页表目录（Page Directory）的概念，即很多个页表会被存储在一个页表目录中，处理器寻址时先通过页表目录找到逻辑地址对应的目录，然后找到目录中对应的页表，最后找到页表中的目标页表项，实现多级索引。

以 32 位操作系统为例，在二级页表目录中，一个逻辑地址可以被划分如下：

10 bits	10 bits	12 bits
Directory Index	Page Table Index	Offset in page

寻址过程：

根据逻辑地址高 10 位比特（31 ～ 22）的目录索引，与基地址寄存器的值（页表目录的起始地址）相加，得到目标 PDE 的值；
目标 PDE 的高 20 位比特表示页表的编号，逻辑地址中间 10 位比特（21 ～ 12）表示页表项的索引，从而可以找到目标 PTE；
目标 PTE 的高 20 位比特表示目标物理帧的编号，加上逻辑地址最后 12 个比特表示的偏置，即可得到最后的地址。

为什么二级页表可以节省空间呢？

让我们来算一算，对于每个进程而言，需要维护一个页表目录，页表目录一共有有 \(2 ^ {10}\) 个 PDE，每个 PDE 大小为 \(4\) B，因此总大小为 \(4 \times 2 ^ {10}\) B = \(4\) KB。接下来，我们根据程序内存需求给页表目录分配页表即可。因此对于每一个进程，需要维护的最小内存就只有 \(4\) KB，相对于一级页表足足小了近一千倍。

事实上，如果进程内存分配比较密集，就意味着有大量的 PDE 是不需要分配页表项的。

三级页表 & 四级页表

三级页表和四级页表通常用于 64 位操作系统，特别是在 x86_64 或 AMD64 架构中。这是因为 64 位操作系统能够访问非常大的虚拟地址空间，通常超过了 32 位操作系统的限制。为了有效地管理如此大的虚拟内存空间，需要更多级的页表来进行地址映射和管理。

事实上它们的原理和二级页表差不多，无非就是多了几层映射罢了。

3-Level Paging

4-Level Paging

引入多级页表后，我们解决了进程页表空间过大的问题，但我们还没有解决寻址速度慢的问题，而且随着访问级数的增加，访问慢的问题甚至被加剧了。为了解决这个问题，人们又提出了 TLB 技术。

TLB

TLB 介绍

TLB（Translation Lookaside Buffer），是计算机体系结构中的一个关键硬件组件，用于加速虚拟内存到物理内存的地址转换过程。TLB是全关联高速缓存（Fully Associative Cache）的一种，专门用于存储最近执行的虚拟地址到物理地址的映射关系，以提高内存访问速度。

Fully associative cache（全关联高速缓存）是一种高速缓存（Cache）的组织结构，其中缓存中的每个数据块可以存储在任何位置，而不受特定的缓存行或集的限制。与其他类型的高速缓存结构相比，全关联高速缓存提供了更大的灵活性，但通常需要更复杂的硬件来实现。

TLB 存储了虚拟地址到物理地址的映射表项。每个表项包括虚拟地址、物理地址和其他控制信息。当处理器执行内存访问指令时，它会首先检查 TLB，看是否存在所需的映射，如果存在，就会使用 TLB 中的映射进行地址转换（TLB hit），否则，它将访问主内存或页表来获取映射（TLB miss），使用页表映射获取物理内存后回过头来更新 TLB，下一次访问同一个进程的同一页只需要访问 TLB 就行。

当操作系统进行进程上下文切换时，TLB 通常会被刷新。这是因为不同的进程具有不同的虚拟地址空间，因此之前在 TLB 中的虚拟地址到物理地址的映射不再有效。切换到新的进程时，TLB 需要被清空，以确保新进程的地址映射生效。

现代操作系统寻址过程：

引用局部性

尽管 TLB 可以提高 CPU 访问逻辑地址的速度，但 TLB 能存储的空间非常小，远小于实际内存大小，它是如何实现一个全局加速效果的呢？

引用局部性（Locality of reference）是计算机科学和计算机体系结构中的一个重要概念，用于描述在程序访问内存或数据时的一种观察现象。引用局部性指的是程序在一段时间内倾向于多次访问相邻的内存地址或数据元素，而不是随机分散地访问内存。

引用局部性通常分为两种主要类型：

时间局部性（Temporal Locality）：时间局部性表示程序在短时间内多次访问相同的内存地址或数据元素。这意味着一旦程序访问了某个内存位置，它可能会在不久的将来再次访问相同的位置。这种情况下，缓存（如 TLB 等）可以有效地提高性能，因为它们可以保存最近访问的数据，以供稍后的访问使用。
空间局部性（Spatial Locality）：空间局部性表示程序在访问一个内存地址或数据元素时，可能会紧接着访问相邻的内存地址或数据元素。这意味着程序倾向于连续地访问内存位置，而不是跳跃式地访问。空间局部性有助于高效地使用缓存，因为缓存可以将相邻的数据块一起加载，从而提高数据的有效性。

这是一个统计意义上的概念，其很好解释了 TLB 的加速原理。

几个问题

页面大小对寻址速度的影响？

页面越大，其包含的内存就越大，则可以减少 TLB miss 的数量，可以加快页面映射的速度。
缓存慢之后如何更新 TLB 的条目？

采用 FIFO 算法进行调度，保证 TLB 存储的页面中永远有最新访问的。

做一个小测试

为了测试 TLB 对运行效率的影响，我们准备以下两段程序：

// demo_1.cpp
#include <iostream>
#include <chrono>

int arr[10000][10000];

int main() {
    auto start = std::chrono::high_resolution_clock::now();

    for (int i = 0; i < 10000; i++) {
        for (int j = 0; j < 10000; j++) {
            arr[i][j] = i + j;
        }
    }

    auto end = std::chrono::high_resolution_clock::now();
    
    std::chrono::duration<double> elapsed = end - start;
    std::cout << "耗时: " << elapsed.count() << " 秒" << std::endl;

    return 0;
}

// demo_2.cpp
#include <iostream>
#include <chrono>

int arr[10000][10000];

int main() {
    auto start = std::chrono::high_resolution_clock::now();

    for (int i = 0; i < 10000; i++) {
        for (int j = 0; j < 10000; j++) {
            arr[j][i] = i + j;
        }
    }

    auto end = std::chrono::high_resolution_clock::now();
    
    std::chrono::duration<double> elapsed = end - start;
    std::cout << "耗时: " << elapsed.count() << " 秒" << std::endl;

    return 0;
}

上面的代码中，二者唯一的区别就是循环的顺序不一样，demo_1.cpp 内层循遍历数组第二维，外层循环遍历数组第一维，demo_2.cpp 反之。

接下来我们比较二者的运行效率，在这里我们使用 -O0 参数保证 g++ 编译器不对程序做过多优化。

注意到两段几乎一样的代码，demo_1.cpp 比 demo_2.cpp 快了一倍不止。

这是为什么呢？

总所周知，在 C/C++ 中，所有的二维数组本质上还是一维数组，即它们所有行在空间上都是连续的，如果我像 demo_1.cpp 那样先进行行遍历，然后进行列遍历，就意味着当进程第一次访问 arr[i][j] 出现次要页面错误后会将其所在页放置在 TLB 缓存中，之后对 arr[i][j + 1] 、arr[i][j + 2] ... 这些在同一个页面的地址数据的访问都会触发 TLB hit，就不需要再进行一轮页面映射操作了。而对于 demo_2.cpp 而言，其先遍历列，然后遍历行，arr[j][i] 和 arr[j + 1][i] 不在同一个页面内，因此每一次访问都会触发 TLB miss，从而只能进行页面映射找到对应的物理帧，效率远低于 demo_1.cpp。

Thrashing

Thrashing 通常用来描述在虚拟内存系统中的一种严重性能问题。Thrashing 指的是操作系统不断地将页面从物理内存交换到磁盘，然后再将其换回物理内存，不断地重复这个过程。这种情况导致系统的性能急剧下降，因为大部分时间都用于页面交换，而不是执行实际的计算任务。Thrashing 一般发生在工作集（Working Set）不在内存中从而导致页面错误率（Page Fault Rate）高的情况。

Working Set（工作集）是计算机内存管理领域的一个重要概念，它用于描述一个进程或应用程序在一段时间内所活跃地使用的物理内存中的一组页面或内存块。工作集有助于了解进程的内存访问模式，以便更好地管理内存资源并优化性能。

除此之外，页面大小也可以影响页面错误率：

小页面：在主存中会发现大量的页面随着执行过程中时间的推移将包含进程中靠近最近引用的部分，从而导致低页面错误率。
大页面：导致页面包含远离最近引用的位置，从而导致高页面错误率。

当一个进程在 Paging 上花费的时间比程序本身执行的时间要长，我们就可以称这个进程处于 Thrashing 状态。

Thrashing 状态下系统资源基本用于 Paging，导致处理器的执行使用率低

解决 Thrashing 的方案：

增加物理内存；
进程的页按需分配；
使用更高效的页面替换策略（如 LRU 或 LFU 等）。
LRU（Least Recently Used）是一种常见的页面置换算法，用于管理计算机系统中的高速缓存或虚拟内存中的页面。LRU 算法的目标是确定哪个页面最久没有被访问，并将其替换掉，以便给新的页面或数据腾出空间。
- 如何实现？—— 比如利用 x86 32 位 PTE 中的比特位「A」

操作系统

#操作系统 #内存管理 #MMU #页表

内存管理

https://goer17.github.io/2023/11/02/内存管理/

作者

Captain_Lee

发布于

2023年11月2日

许可协议

Transfomer 框架 | 逐层剖析，从原理到代码上一篇

循环神经网络 RNN 下一篇