探索 OS 的内存管理原理

前言

内存作为计算机系统的组成部分，跟开发人员的日常开发活动有着密切的联系，我们平时遇到的 Segment Fault、OutOfMemory、Memory Leak、GC 等都与它有关。本文所说的内存，指的是计算机系统中的主存（Main Memory），它位于存储金字塔中 CPU 缓存和磁盘之间，是程序运行不可或缺的一部分。

在计算机系统中，主存通常都是由操作系统（OS）来管理，而内存管理的细则对开发者来说是无感的。对于一个普通的开发者，他只需懂得如何调用编程语言的接口来进行内存申请和释放，即可写出一个可用的应用程序。如果你使用的是带有垃圾回收机制的语言，如 Java 和 Go，甚至都不用主动释放内存。但如果你想写出高效应用程序，熟悉 OS 的内存管理原理就变得很有必要了。

下面，我们将从最简单的内存管理原理说起，带大家一起窥探 OS 的内存管理机制，由此熟悉底层的内存管理机制，写出高效的应用程序。

独占式内存管理

早期的单任务系统中，同一时刻只能有一个应用程序独享所有的内存（除开 OS 占用的内存），因此，内存管理可以很简单，只需在内存上划分两个区域：

在多任务系统中，计算机系统已经可以做到多个任务并发运行。如果还是按照独占式的管理方式，那么每次任务切换时，都会涉及多次内存和磁盘之间的数据拷贝，效率极其低下：

最直观的解决方法就是让所有程序的数据都常驻在内存中（假设内存足够大），这样就能避免数据拷贝了：

但这样又会带来另一个问题，程序之间的内存地址空间是没有隔离的，也就是程序 A 可以修改程序 B 的内存数据。这样的一个重大的安全问题是用户所无法接受的，要解决该问题，就要借助虚拟化的力量了。

虚拟地址空间

为了实现程序间内存的隔离，OS 对物理内存做了一层虚拟化。OS 为每个程序都虚拟化出一段内存空间，这段虚拟内存空间会映射到一段物理内存上。但对程序自身而言，它只能看到自己的虚拟地址空间，也就有独占整个内存的错觉了。

上图中，虚拟内存空间分成了三个区域，其中 Code 区域存储的是程序代码的机器指令；Heap 区域存储程序运行过程中动态申请的内存；Stack 区域则是存储函数入参、局部变量、返回值等。Heap 和 Stack 会在程序运行过程中不断增长，分别放置在虚拟内存空间的上方和下方，并往相反方向增长。

从虚拟地址空间到物理地址空间的映射，需要一个转换的过程，完成这个转换运算的部件就是 MMU（memory management unit），也即内存管理单元，它位于 CPU 芯片之内。

要完成从虚拟地址到物理地址到转换，MMU 需要 base 和 bound 两个寄存器。其中 base 寄存器用来存储程序在物理内存上的基地址，比如在图 5 中，程序 A 的基地址就是 192KB；bound 寄存器（有时候也叫 limit 寄存器）则保存虚拟地址空间的 Size，主要用来避免越界访问，比如图 5 中程序 A 的 size 值为 64K。那么，基于这种方式的地址转换公式是这样的：

物理地址 = 虚拟地址 + 基地址

以图 5 中程序 A 的地址转换为例，当程序 A 尝试访问超过其 bound 范围的地址时，物理地址会转换失败：

现在，我们再次仔细看下程序 A 的物理内存分布，如下图 7 所示，中间有很大的一段空闲内存是“已申请，未使用”的空闲状态。这也意味着即使这部分是空闲的，也无法再次分配给其他程序使用，这是一种巨大的空间浪费！为了解决这个内存利用率低下的问题，我们熟悉的段式内存管理出现了。

段式内存管理

在上一节中，我们发现如果以程序为单位去做内存管理，会存在内存利用率不足的问题。为了解决该问题，段式内存管理被引入。段（Segment）是逻辑上的概念，本质上是一块连续的、有一定大小限制的内存区域，前文中，我们一共提到过 3 个段：Code、Heap 和 Stack。

段式内存管理以段为单位进行管理，它允许 OS 将每个段灵活地放置在物理内存的空闲位置上，因此也避免了“已申请，未使用”的内存区域出现：

地址转换

从上图 8 可知，段式内存管理中程序的物理内存空间可能不再连续了，因此为了实现从虚拟地址到物理地址到转换，MMU 需要为每个段都提供一对 base-bound 寄存器，比如：

给一个虚拟地址，MMU 是如何知道该地址属于哪个段，从而根据对应的 base-bound 寄存器转换为对应的物理地址呢？

假设虚拟地址有 16 位，因为只有 3 个段，因此，我们可以使用虚拟地址的高 2 位来作为段标识，比如00表示 Code 段，01表示 Heap 段，11表示 Stack 段。这样 MMU 就能根据虚拟地址来找到对应段的 base-bound 寄存器了：

但这样还不是能够顺利的将虚拟地址转换为物理地址，我们忽略了重要的一点：Heap 段和 Stack 段的增长方向是相反的，这也意味着两者的地址转换方式是不一样的。因此，我们还必须在虚拟地址中多使用一位来标识段的增长方向，比如0表示向上（低地址方向）增长，1表示向下（高地址方向）增长：

下面，看一组段式内存管理地址转换的例子：

那么，总结段式内存管理的地址转换算法如下：

// 获取当前虚拟地址属于哪个段Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT// 得到段内偏移量Offset  = VirtualAddress & OFFSET_MASK// 获得内存增长的方向GrowsDirection = VirtualAddress & GROWS_DIRECTION_MASK// 有效性校验if (Offset >= Bounds[Segment])    RaiseException(PROTECTION_FAULT)else    if (GrowsDirection == 0) {      PhysAddr = Base[Segment] + Offset    } else {      PhysAddr = Base[Segment] - Offset    }

内存共享和保护

段式内存管理还可以很方便地支持内存共享，从而达到节省内存的目的。比如，如果存在多个程序都是同一个可执行文件运行起来的，那么这些程序是可以共享 Code 段的。为了实现这个功能，我们可以在虚拟地址上设置保护位，当保护位为只读时，表示该段可以共享。另外，如果程序修改了只读的段，则转换地址失败，因此也可以达到内存保护的目的。

内存碎片

段式内存管理的最明显的缺点就是容易产生内存碎片，这是因为在系统上运行的程序的各个段的大小往往都不是固定的，而且段的分布也不是连续的。当系统的内存碎片很多时，内存的利用率也会急剧下降，对外表现就是虽然系统看起来还有很多内存，却无法再运行起一个程序。

解决内存碎片的方法之一是定时进行碎片整理：

但是碎片整理的代价极大，一方面需要进行多次内存拷贝；另一方面，在拷贝过程中，正在运行的程序必须停止，这对于一些以人机交互任务为主的应用程序，将会极大影响用户体验。

另一个解决方法就是接下来要介绍的页式内存管理。

页式内存管理

页式内存管理的思路，是将虚拟内存和物理内存都划分为多个固定大小的区域，这些区域我们称之为页（Page）。页是内存的最小分配单位，一个应用程序的虚拟页可以存放在任意一个空闲的物理页中。

物理内存中的页，我们通常称之为页帧（Page Frame）

因为页的大小是固定的，而且作为最小的分配单位，这样就可以解决段式内存管理中内存碎片的问题了。

但页内仍然有可能存在内存碎片。

地址转换

页式内存管理使用页表（Page Table）来进行虚拟地址到物理地址到转换，地址转换的关键步骤如下：

1）根据虚拟页找到对应的物理页帧

每个虚拟页都有一个编号，叫做 VPN（Virtual Page Number）；相应的，每个物理页帧也有一个编号，叫做 PFN（Physical Frame Number）。页表存储的就是 VPN 到 PFN 的映射关系。

2）找到地址在物理页帧内的偏移（Offset）

地址在物理页帧内的偏移与在虚拟页内的偏移保持一致。

我们可以将虚拟地址划分成两部分，分别存储 VPN 和 Offset，这样就能通过 VPN 找到 PFN，从而得到 PFN+Offset 的实际物理地址了。

比如，假设虚拟内存空间大小为 64Byte（6 位地址），页的大小为 16Byte，那么整个虚拟内存空间一共有 4 个页。因此我们可以使用高 2 位来存储 VPN，低 4 位存储 Offset：

下面看一个转换例子，VPN（01）通过页表找到对应的 PFN（111），虚拟地址和物理地址的页内偏移都是0100，那么虚拟地址010100对应的物理地址就是1110100了。

页表和页表项

OS 为每个程序都分配了一个页表，存储在内存当中，页表里由多个页表项（PTE，Page Table Entry）组成。我们可以把页表看成是一个数组，数组的元素为 PTE：

以 x86 系统下的 PTE 组成为例，PTE 一共占 32 位，除了 PFN 之外，还有一些比较重要的信息，比如 P（Present）标识当前页是否位于内存上（或是磁盘上）；R/W（Read/Write）标识当前页是否允许读写（或是只读）；U/S（User/Supervisor）标识当前页是否允许用户态访问；A（Access）标识当前页是否被访问过，在判断当前页是否为热点数据、页换出时特别有用；D（Dirty）标识当前页是否被修改过。

页式内存管理的缺点

地址转换效率低

根据前文介绍，我们可以总结页式内存管理机制下地址转换的算法如下：

// 从虚拟地址上得到VPNVPN = (VirtualAddress & VPN_MASK) >> SHIFT// 找到VPN对应的PTE的内存地址PTEAddr = PTBR + (VPN * sizeof(PTE))// 访问主存，获取PTEPTE = AccessMemory(PTEAddr)// 有效性校验if (PTE.Valid == False)    RaiseException(INVALID_ACCESS)else    // 获取页内偏移量    offset = VirtualAddress & OFFSET_MASK    // 计算得出物理地址    PhysAddr = (PTE.PFN << PFN_SHIFT) | offset

我们发现，每次地址转换都会访问一次主存来获取页表，比段式内存管理（无主存访问）低效很多。

占用空间大

假设地址空间为 32-bit，页的大小固定为 4KB，那么整个地址空间一共有$2^{32}/4KB=2^{20}$个页表，也即页表一共有$2^{20}$个 PTE。现假设每个 PTE 大小为 4-byte，那么每个页表占用 4MB 的内存。如果整个系统中有 100 个程序在运行，那么光是页表就占用了 400MB 的内存，这同样是用户无法接受的。

接下来，我们将介绍如何去优化页式内存管理的这两个显著缺点。

让页式管理的地址转换更快

TLB：Translation-Lookaside Buffer

根据前文所述，页式内存管理地址转换因为多了一次主存访问，导致效率很低。如果能够避免或者减少对主存的访问，那么就能让地址转换更快了。

很多人应该都可以想到通过增加缓存的方式提升效率，比如为避免频繁查询磁盘，我们一般在内存中增加一层缓存来提升数据访问效率。那么为了提升访问主存中数据的效率，自然应该在离 CPU 更近的地方增加一层缓存。这个离 CPU 更近的地方，就是前文提到的位于 CPU 芯片之内的 MMU。而这个高速缓存，就是 TLB（Translation-Lookaside Buffer），它缓存了 VPN 到 PFN 到映射关系，类似于这样：

增加 TLB 之后，地址转换的算法如下：

VPN = (VirtualAddress & VPN_MASK) >> SHIFT(Success, TlbEntry) = TLB_Lookup(VPN)if (Success == True)   // TLB Hit    if (CanAccess(TlbEntry.ProtectBits) == True)        Offset   = VirtualAddress & OFFSET_MASK        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset    else        RaiseException(PROTECTION_FAULT)else                  // TLB Miss    PTEAddr = PTBR + (VPN * sizeof(PTE))    PTE = AccessMemory(PTEAddr)    if (PTE.Valid == False)        RaiseException(SEGMENTATION_FAULT)    else if (CanAccess(PTE.ProtectBits) == False)        RaiseException(PROTECTION_FAULT)    else        TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)        RetryInstruction()

从上述算法可以发现，在 TLB 缓存命中（TLB Hit）时，能够避免直接访问主存，从而提升了地址转换的效率；但是在 TLB 缓存不命中（TLB Miss）时，仍然需要访问一次主存，而且还要往 TLB 中插入从主存中查询到的 PFN，效率变得更低了。因此，我们必须尽量避免 TLB Miss 的出现。

更好地利用 TLB

下面，我们通过一个数组遍历的例子来介绍如何更好地利用 TLB。

假设我们要进行如下的一次数组遍历：

int sum = 0;for (i = 0; i < 10; i++) {    sum += a[i]; }

数组的内存的分布如下：

a[0]~a[2]位于 Page 5 上，a[3]~a[6]位于 Page 6 上，a[7]~a[8]位于 Page 7 上。当我们首先访问 a[0]时，由于 Page 5 并未在 TLB 缓存里，所以会先出现一次 TLB Miss，接下来的 a[1]和 a[2]都是 TLB Hit；同理，访问 a[3]和 a[7]时都是 TLB Miss，a[4]~a[6]和 a[8]~a[9]都是 TLB Hit。所以，整个数组遍历下来，TLB 的缓存命中情况为：Miss，Hit，Hit，Miss，Hit，Hit，Hit，Miss，Hit，Hit，TLB 缓存命中率为 70%。我们发现，访问同一页上的数据 TLB 的缓存更易命中，这就是空间局部性的原理。

接下来，我们再次重新遍历一次数组，由于经过上一次之后 Page 5 ～ Page 7 的转换信息已经在 TLB 缓存里里，所以第二次遍历的 TLB 命中情况为：Hit，Hit，Hit，Hit，Hit，Hit，Hit，Hit，Hit，Hit，TLB 缓存命中率为 100%！这就是时间局部性的原理，短时间内访问同一内存数据也能够提升 TLB 缓存命中率。

TLB 的上下文切换

因为 TLB 缓存的是当前正在运行程序的上下文信息，当出现程序切换时，TLB 里面的上下文信息也必须更新，否则地址转换就会异常。解决方法主要有 2 种：

• 方法 1：每次程序切换都清空 TLB 缓存（Flush TLB），让程序在运行过程中重新建立缓存。

• 方法 2：允许 TLB 缓存多个程序的上下文信息，并通过 ASID（address space identifier，地址空间标识符，可以理解为程序的 PID）做区分。

方法 1 实现简单，但是每次程序切换都需要重新预热一遍缓存，效率较低，主流的做法是采用方法 2。

需要注意的是 TLB 是嵌入到 CPU 芯片之内的，对于多核系统而言，如果程序在 CPU 之间来回切换，也是需要重新建立 TLB 缓存！因此，把一个程序绑定在一个固定的核上有助于提升性能。

让页表更小

大页内存

降低页表大小最简单的方法就是让页更大。前文的例子中，地址空间为 32-bit，页的大小为 4KB，PTE 的大小为 4-byte，那么每个页表需要 4MB 的内存空间。现在，我们把页的大小增加到 16KB，其他保持不变，那么每个页表只需要$2^{32}/16KB=2^{18}$个 PTE，也即 1MB 内存，内存占用降低了 4 倍。

大页内存对 TLB 的使用也有优化效果，因 TLB 能够缓存的上下文数量是固定的，当页的数量更少时，上下文换出的频率会降低，TLB 的缓存命中率也就增加了，从而让地址转换的效率更高。

段页式内存管理

根据前文所述，程序的地址空间中，堆与栈之间的空间很多时候都是处于未使用状态。对应到页表里，就是有很大一部分的 PTE 是 invalid 状态。但因为页表要涵盖整个地址空间的范围，这部分 invalid 的 PTE 只能留在页表中，从而造成了很大的空间浪费。

前文中，我们通过段式内存管理解决了堆与栈之间内存空间的浪费问题。对应到页表中，我们也可以为页式内存管理引入段式管理的方式，也即段页式内存管理，解决页表空间浪费的问题。

具体的方法是，为程序的地址空间划分出多个段，比如 Code、Heap、Stack 等。然后，在每个段内单独进行页式管理，也即为每个段引入一个页表：

从上图可知，将页表分段之后，页表不再需要记录那些处于空闲状态的页的 PTE，从而节省了内存空间的消耗。

多级页表

降低页表大小另一个常见的方法就是多级页表（Multi-level Page Table），多级页表的思路也是减少处于空闲状态的页的 PTE 数量，但方法与段页式内存管理不同。如果说段页式内存管理可以看成是将页表分段，那么多级页表则可以看成是将页表分页。

具体的做法是将页表按照一定大小分成多个部分（页目录，Page Directory，PD），如果某个页目录下所有的页都是处于空闲状态，则无须为该页目录下的页申请 PTE。

以二级页表为例，下图对比了普通页表和多级页表的构成差异：

下面，我们再对比一下普通页表和多级页表的空间消耗。还是假设地址空间为 32-bit，页的大小为 4KB，PTE 的大小为 4-byte，一共有$2^{20}$个页，那么普通页表需要 4MB 的内存空间。现在，我们将$2^{20}$个页切分为$2^{10}$份，也即有$2^{10}$个页目录，每个页目录下管理$2^{10}$个页，也即有$2^{10}$个 PDE（Page Directory Entry）。假设 PDE 也占 4-byte 内存，且根据 20/80 定律假设有 80%的页处于空闲状态，那么二级页表只需要 0.804MB！($2^{10}\ast 4$${+2^{20}4(1-80%)}$)

由此可见，多级页表能够有效降低页表的内存消耗。多级页表在实际运用中还是较为常见的，比如 Linux 系统采用的就是 4 级页表的结构。

Swap Sapce: 磁盘交换区

到目前为止，我们都是假设物理内存足够大，可以容纳所有程序的虚拟内存空间。然而，这往往是不切实际的，以 32-bit 地址空间为例，一个程序的虚拟内存为 4G，假设有 100 个程序，那么一共需要 400G 的物理内存（忽略共享部分）！另外，程序运行过程中，并不是一直都需要所有的页，很多时候只需要其中的一小部分。

因此，如果我们可以先把那些暂时用不到的页先存在磁盘上，等需要用到时再加载到内存上，那么就可以节省很多物理内存。磁盘中用来存放这些页的区域，被称作 Swap Sapce，也即交换区。

在这种机制之下，当程序访问某一个地址，而这个地址所在的页又不在内存上时，就会触发缺页（Page Fault）中断。就像 TLB 缓存不命中时会带来额外的开销一样，缺页也会导致内存的访问效率降低。因为在处理缺页中断时，OS 必须从磁盘交换区上把数据加载到内存上；而且当空闲内存不足时，OS 还必须将内存上的某些页换出到交换区中。这一进一出的磁盘 IO 访问也直接导致缺页发生时，内存访问的效率下降许多。

因此，在空闲内存不足时，页的换出策略显得极为重要。如果把一个即将要被访问的页换出到交换区上，就会带来本可避免的无谓消耗。页的换出策略很多，常见的有 FIFO（先进先出）、Random（随机）、LRU（最近最少使用）、LFU（最近最不经常使用）等。在常见的工作负载下，FIFO 和 Random 算法的效果较差，实际用的不多；LRU 和 LFU 算法都是建立在历史内存访问统计的基础上，因此表现较前两者好些，实际应用也多一些。目前很多主流的操作系统的页换出算法都是在 LRU 或 LFU 的基础上进行优化改进的结果。

最后

本文主要介绍了 OS 内存管理的一些基本原理，从独占式内存管理，到页式内存管理，这过程中经历了许多次优化。这其中的每一种优化手段，都朝着如下 3 个目标前进：

1、透明化（transparency）。内存管理的细节对程序不可见，换句话说，程序可以自认为独占整个内存空间。

2、效率（efficiency ）。地址转换和内存访问的效率要高，不能让程序运行太慢；空间利用效率也要高，不能占用太多空闲内存。

3、保护（protection）。保证 OS 自身不受应用程序的影响；应用程序之间也不能相互影响。

当然，目前主流的操作系统（如 Linux、MacOS 等）的内存管理机制要比本文介绍的原理复杂许多，但本质原理依然离不开本文所描述的几种基础的内存管理原理。

参考

1、Operating Systems: Three Easy Pieces, Remzi H Arpaci-Dusseau / Andrea C Arpaci-Dusseau

2、为什么 HugePages 可以提升数据库性能 , 面向信仰编程

3、探索CPU的调度原理, 元闰子的邀请

更多文章请关注微信公众号：元闰子的邀请